2021 вступительный экзамен в Матцентр ФМЛ 239

На каждой из двадцати пяти карточек записано по одному натуральному числу (среди чисел могут быть и одинаковые). Вася заметил, что число на любой карточке нацело делится на числа, записанные ровно на половине из оставшихся двадцати четырех карточек. Докажите, что Вася где-то ошибся. Выберите утверждение которое лучше других подходит для начала короткого доказательства.

Решение:

• Возьмем карточку на которой написано наименьшее число. Известно, что есть 12 других карточек с числами, на которые наше наименьшее число делится. Т.е. должны быть 13 карточек на которых написано наименьшее число (первые карточки).
• Заметим, что любое из оставшихся 12 чисел обязательно должно делиться хотя бы на одну из 13 первых карточек (11 из оставшихся + 1 из первых). Т.е. оставшиеся 12 чисел обязательно должны делиться на 13 первых карточек (так как они равны). А такого быть не может, так как это противоречит условию задачи.

На столе стоят 100 гирек. Известно, что общий вес любых 50 гирек больше, чем общий вес любых 49 гирек. Докажите, что общий вес любых 49 гирек больше, чем общий вес любых 48 гирек.

Решение "от противного":

• Пусть найдутся 48 гирек, вес которых больше веса 49 гирек.
• Добавив в каждый набор еще одну гирю (любую), получим что 49 гирек больше веса 50 гирек.
• А такого быть не может, так как это противоречит условию.

В каждой клетке квадрата 11 × 11 стоит одно из натуральных чисел от 1 до 11. При этом в каждой строке, в каждом столбце и в каждой из двух больших диагоналей все числа различны. Саша закрасил 10 клеток, расположенных под диагональю, идущей из левого верхнего угла в правый нижний. Докажите, что на закрашенных клетках не может быть 9 совпадающих чисел. Выберите лучшее утверждение для доказательства

Решение "от противного":

• Пусть 9 чисел на закрашенных клетках имеют значение X, а 10-я клетка значение Y не равное X.
• Заметим, что одно из двух (11-9=2) оставшихся чисел X должно находиться в верхней горизонтали, а другое на самой правой вертикали.
• Заметим, что если клетка в правом верхнем углу содержит значение X, то Y на закрашенной клетке равно X, что противоречит условию. Т.е. правая верхняя клетка не равна X.
• Заметим, что диагональ из левого нижнего угла в правый верхний угол не пересекает закрашенные клетки.
• Таким образом мы доказали, что диагональ из левого нижнего угла в правый верхний угол не может содержать число X. Что противоречит условию.
• Вывод: на 9 закрашенных клетках не может быть 9 совпадающих чисел.

В строку выписано 160 чисел, каждое из них - 1, 2, 3, …, 18. Может ли оказаться, что любые два различных числа от 1 до 18 где-то в этой строке стоят рядом друг с другом?

Решение

• Из 18 чисел можно составить 306 пар чисел (18 · 17).
• Исключим симметричные пары вида (X Y) и (Y X). Остается 153 пары в которых расположение чисел не важно.
• Соберем последовательность из 153 полученных пар, когда последнее число пары есть первое число следующей пары (числа внутри пары можно менять местами).
• Если у нас получится составить такую последовательность пар, то, объединив все соседние одинаковые числа в одно, мы получим последовательность из 154 чисел, которая содержит все 153 пары.
• Проверим, возможно ли это.
• Заметим, что у нас есть 17 пар с числом 1, 17 пар с числом 2 ... 17 пар с числом 18
• Т.е., когда мы начнем собирать нашу последовательность из 153х пар, у нас будут оставаться "лишние" пары, которые должны стыковаться с парой, которая ранее уже использовалась. При этом будет "тратиться" лишнее число. оценим количество "лишних" пар.
• Заметим, что лишняя пара может быть для каждого исходного числа (от 1 до 18) если оно не является крайним. Т.е. внутри последовательности чисел обязательно будет 16 лишних пар. Каждая из которых добавляет лишнее число в последовательность чисел.
• Таким образом, минимальная последовательность чисел должна быть не менее 154+16 = 170.
• Вывод: 160 чисел недостаточно для того, чтобы любые два различных числа от 1 до 18 где-то в этой строке стояли рядом друг с другом.

У Маши есть 100 одинаковых плиток 1 × 1, изображенных на рисунке слева. Она хочет замостить ими квадрат 10 × 10. При укладке плитку можно поворачивать. Когда все плитки были уложены, пунктирные линии образовали несколько путей (возможно, замкнутых). Какое наименьшее количество путей могло образоваться? Например, на рисунке справа в квадрате 4 × 4 образовалось 9 путей.

Решение.

• Заметим, что середина каждого маленького квадрата, лежащая на сторонах большого квадрата, обязательно является началом или концом какого-либо пути.
• Всего таких точек 40. И они обязательно являются началом или концом пути.
• Т.е. количество путей не может быть меньше 20.
• Двадцать путей можно построить если расположить все маленькие плитки одинаково. В этом случае все пути будут параллельны одой из диагоналей большого квадрата.

У Димы есть 201 одинаковых по внешнему виду монет, среди которых 100 фальшивых и 101 настоящих, причем фальшивые монеты весят одинаково и легче настоящих, которые тоже весят одинаково. Еще у Димы есть прибор, который по двум положенным в него монетам определяет, равны монеты по весу, или нет (но не показывает, какая меньше). Дима выбрал одну монету. Как он может установить, является ли выбранная монета настоящей, если прибор после сотого использования выходит из строя?

Решение

• Взвесим попарно 200 оставшихся монет.
• Если количество одинаковых взвешиваний равно четному числу, то выбранная монета настоящая. Если равно нечетному числу, то выбранная монета фальшивая.

В магазине продаются бумажные полоски из 100 клеток, в каждой клетке которых записана одна из цифр 1, 2 или 3. Две полоски называются похожими, если эти два 100-значных числа при наложении совпадают более чем в 50 местах. Сергей купил в магазине восемь полосок. Докажите, что он сможет сам заполнить еще одну полоску из 100 клеток цифрами 1, 2 и 3 так, чтобы она не была похожа ни на одну из его восьми полосок.

Подсказка:

• Решим упрощенную задачу. Пусть есть 8 полосок из 3-х клеток, в каждой клетке которых записана одна из цифр 1, 2 или 3. Две полоски называются похожими если эти два 3-значных числа при наложении совпадают более чем в 2-х местах. Можем ли мы заполнить 9-ю полоску расставив в клетках цифры 1, 2 и 3 так, чтобы она не была похожа ни на одну из исходных восьми полосок.
• Докажем, что сможем.
• Пусть 9-я полоска похожа на какую-то из 8 оригинальных полосок. В этом случае мы можем пересортировать "столбцы" в этой оригинальной полоске и в 9-й полоске так, чтобы сначала шли все единицы из оригинальной полоски, затем все двойки, затем все тройки. Всего возможно 10 таких комбинаций:
  • 1 1 1
  • 1 1 2
  • 1 1 3
  • 1 2 2
  • 1 2 3
  • 1 3 3
  • 2 2 2
  • 2 2 3
  • 2 3 3
  • 3 3 3
• А у нас всего 8 полосок. Т.е. мы всегда сможем выбрать 2 комбинации для 9-й полоски, которые гарантированно сделают эту полоску непохожей на 8 оригинальных полосок.