Ответы и решения для 5 математических задач от организаторов Almaty Maths Battles

Найдите последнюю цифру числа 1²⁰²⁰ + 2²⁰²⁰ + 3²⁰²⁰ + … + 2022²⁰²⁰

Решение:

Посчитаем сначала последнюю цифру суммы 1²⁰²⁰ + 2²⁰²⁰ + … + 10²⁰²⁰. Если а не делится на 5 и 2, то а⁴ = 1 (mod 10) (например, из теоремы Эйлера). Если оно делится и па 2 и на 5, то последняя цифра равна 0. Если только на 2, то равна 6. Если на 5, то равна 5. При возведении в степень, все эти остатки не меняются, а также 2020 делится на 4. Из всего сказанного легко следует, что сумма равна 6 х 4 + 1 х 4 + 0 + 5 = 3 (mod 10), тогда общая сумма будет 202 х 3 + 1 + 6 = 3 (mod 10), то есть последняя цифра равна 3.

Каждая клетка таблицы n х n закрашена в белый или черный цвет. В углах таблицы стоят 3 белые и 1 черпая клетки. Докажите, что существует квадрат 2 х 2 с нечетным количеством белых клеток.

Решение:

Предположим, что в таблице нет такого квадрата. Рассмотрим любую строку таблицы. Допустим, что под какой-то клеткой этой строки стоит клетка противоположного цвета, тогда во всех клетках будет стоять противоположный цвет. В противоположном же случае, во всех клетках стоит тот же цвет, что и сверху. То есть строки либо меняются полностью, либо остаются такими же. Так как в углах стоят 3 белых клетки и одна черная, то в какой-то «крайней» строке будут две белые угловые клетки, но тогда в противоположной «крайней» строке должно быть либо две черные угловые, либо также две белые, но там будет одна черная и одна белая, откуда противоречие.

Приходя в школу, Алихан здоровается со всеми одноклассниками (кроме, разумеется, самого себя). К началу уроков Алихан не успел поздороваться ровно с одной четвертью от общего числа учеников своего класса, в том числе с Байсеитом. А Байсеит к этому времени поздоровался ровно с одной седьмой из тех одноклассников, с которыми поздоровался Алихан. Какое наименьшее число учеников может быть в классе?

Решение:

Алихан не успел поздороваться с одной четвертью всех учеников класса, а собирался поздороваться со всеми, кроме себя. Таким образом, сам Алихан в эту четверть класса не входит, и значит, Алихан поздоровался с 3/4 от общего количества учеников в классе минус 1 (этот один — сам Алихан). А Байсеит поздоровался с одной седьмой от этого количества учеников. Значит, если количество тех, с кем поздоровался Байсеит, умножить на 7 и прибавить 1, должно получиться три четверти класса, т. е. число, делящееся па 3.

Попробуем подобрать такие числа. Если Байсеит поздоровался с одним человеком, то, умножив 1 на 7 и прибавив 1, получаем, что три четверти класса — это 8 человек. Но 8 на 3 не делится, значит, этот вариант невозможен. Если Байсеит поздоровался с двумя одноклассниками, то аналогично находим, что три четверти класса — это 15 человек. В этом случае в классе учится 20 человек. Если же Байсеит поздоровался с тремя или более одноклассниками, то три четверти класса — это 22 или более человек, и тогда число учеников класса больше 20.

Таким образом, подобранный нами пример даст наименьшее возможное число учеников класса.

Мирон и Ярослав играют в игру. Мирон загадал число из трех цифр от 1 до 8. Ярослав может попробовать угадать его, назвав число, также состоящее из трех цифр от 1 до 8. Если число, названное Ярославом, и число, загаданное Мироном совпадает в хотя бы двух разрядах, то Ярослав побеждает. Всегда ли сможет Ярослав победить, если Мирон даст Ярославу только 32 попытки?

Решение:

Пусть Ярослав сначала назовет следующие 16 чисел:

222, 424, 626, 828

244, 446, 648, 842

266, 468, 662, 864

288, 482, 684, 886

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

В некотором государстве система авиалиний устроена так, что любой город соединен авиалиниями не более, чем с тремя другими городами и из любого города в любой другой город можно перелететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в этом государстве?

Решение:

Из фиксированного города А можно попасть напрямую не более чем в три города, а с одной пересадкой — еще не более чем в 3 х 2 = 6 городов. Таким образом, всего городов может быть не более десяти. Пример сети из 10 городов см. на рисунке: