Готовимся к олимпиаде по математике

1.  На доске  выписано число 181818…18 (всего 2014 цифр: 1007 единиц и 1007 восьмёрок). Незнайка вычеркнул из него 14 цифр. Может ли получиться так, что полученное число будет кратно 7?

 Решение. При  решении важно заметить, что если в данном числе любую из цифр 8 заменить на 1, то делимость на 7 не меняется, так как разность между старым и новым числом равна 7000…000  и кратна 7. То есть, если число 111…11 (2000 единиц) делится на 7, то и полученное в результате вычеркивания цифр число также будет делиться на 7. Значит, осталось установить, делится ли число 111…11 (2000 единиц) на 7. Выполняя деление столбиком можно заметить, что число 111111 делится на 7, а числа из меньшего числа единиц не делятся. Но поскольку 2000 не кратно 6, то полученное Незнайкой число не может оказаться кратным 7. 

(Подобные задачи предлагались на муниципальных этапах Всероссийской олимпиады школьников в 10-11 классах, но посильны и более младшим школьникам. Решение этих задач полезно и сдающим ЕГЭ, для решения заданий под номером 21)

3. Интересная задача на использование признаков делимости натуральных чисел. 

Из цифр 4 и 9 (каждая цифра должна быть использована) составить наименьшее возможное натуральное число, кратное 4 и 9.

Решение.

Для того чтобы число делилось на 4 необходимо и достаточно, чтобы число, составленное из двух последних цифр, делилось на 4. Возможные окончания числа: 44, 49, 99, 94. Только первое делится на 4. Для делимости на 9 необходимо и достаточно, чтобы сумма его цифр делилась на 9. От добавления или убирания девяток делимость суммы цифр не меняется, значит, если удалить все девятки, сумма всех оставшихся четвёрок должна делиться на 9. Но 4 и 9 взаимно просты, значит на 9 должно делиться их количество. То есть, в наименьшем числе - девять четвёрок, поскольку число тем меньше, чем меньше в нём цифр. Число тем меньше, чем меньше первые цифры, поэтому получаем, что наименьшее возможное число, кратное 4 и 9, -  это 4444444944.

3. В классе 25 учеников. На уроке физкультуры учитель попросил построиться учеников в шеренгу по убыванию роста учеников слева направо. Но оказалось, что не все ученики построились правильно по росту. Учитель делает замечания двум рядом стоящим ученикам, если они стоят не по росту. После этого они меняются местами. Какое наименьшее число замечаний надо сделать учителю, чтобы все ученики выстроились по росту независимо от их начального положения.

Ответ:300

Решение. Пусть имеется некоторое расположение учеников в шеренге. Рассмотрим всевозможные различные пары учеников (всего таких пар  25×24 : 2 = 300).  Назовем пару учеников, стоящих рядом  друг с другом «хорошей», если эта пара учеников стоит по росту, противном случае будем называть её «плохой». После того как ученики выстроятся по росту не должно остаться «плохих» пар. Заметим, что за одну операцию число «плохих»(«хороших») пар меняется не более чем на 1. В самом деле, только в паре учеников, которые меняются местами,  может появиться или исчезнуть «плохая» («хорошая») пара. Следовательно, при начальном расположении, в котором ученики стоят в обратном порядке (каждая пара учеников образует «плохую» пару), потребуется сделать не менее 300 замечаний.

    Покажем, что 300 замечаний всегда достаточно. Если в некотором расположении ученики  стоят не по росту,  то найдется «плохая» пара учеников, образующая беспорядок. Поменяв местами эту пару учеников, мы уменьшаем число «плохих» пар на 1. Таким образом, каждой операцией мы можем уменьшать число «плохих» пар на 1 и не более, чем через 300 операций прийти правильному порядку учеников.