Международный научно-образовательный электронный журнал «образование и наука в XXI веке». Выпуск №10 (том 1)

Делимость и остатки 
 
1. Десятичная запись числа 
А 
состоит из 30 единиц и нескольких нулей. Может ли 
число 
А 
быть полным квадратом?
Ответ. Не может.
Сумма цифр числа 
А 
равна 30. Поэтому оно делится на 3, но не делится на 9, т. е. 
оно не может быть полным квадратом.
2. Дети, построенные парами, выходят из лесу, где они собирали орехи. В каждой 
паре идут мальчик и девочка, причем у мальчика орехов либо вдвое больше, либо 
вдвое меньше, чем у девочки. Могло ли так случиться, что у всех вместе 1000 
орехов?
Ответ. Не могло.
Заметим, что число орехов у каждой пары детей делится на 3. Это означает, что 
суммарное число орехов должно делиться на 3. Однако 1000 на 3 не делится. 
3. Докажите, что число имеет нечетное число делителей (включая единицу и само 
число) тогда и только тогда, когда оно является точным квадратом.
Решение. Пусть нам дано число S и 
а 
- его делитель.
тогда число - 
a
S
также является делителем числа S, т. е. делители числа 
разбиваются на пары. У числа может быть нечетное число делителей, только если 
числа в какой-нибудь паре совпадают: 
a
S
= 
а, 
откуда S = 
а
2
. 
И наоборот, если S = 
а
2
, 
то 
a
S
= 
а, 
т. е. у числа будет нечетное число делителей.

---

102 

---

103 
 

---

104 
3.
 
Принцип Дирихле 
При решении различных мате математических задач применяется 
специальный метод, получивший название «принцип Дирихле». 
Существует несколько формулировок этого принципа. Самая популярная 
следующая: «Если в n клетках сидит m зайцев, причем n меньше m, то 
хотя бы в одной клетке сидит по крайней мере два зайца». Доказывается 
этот принцип Дирихле легко, методом доказательства от противного. 
Поэтому некоторые из задач, решаемые с помощью принципа Дирихле, 
также можно решить, используя метод доказательства от противного, но 
не все. 
При решении задач выбор зайцев и клеток часто неочевиден. Далеко не 
всегда по формулировке задачи можно определить, что следует применить 
принцип Дирихле. 
Главное достоинство данного метода решения состоит в том, что он дает 
неконструктивное решение. 
Рассмотрим примеры различных задач, решаемых с помощью принципа 
Дирихле. 
1.
В классе 15 учеников. Докажите, что найдутся как минимум 2 
ученика, отмечать дни рождения в одном месяце. ( Решение. Пусть 15 
учеников будут «зайцы». Тогда «клетками» будут месяцы года, их 12. Т.к. 
15 больше 12, то по принципу Дирихле найдется, как минимум, одна 
клетка, в которой будут сидеть по крайней мере 2 «зайца». Т.е. найдется 
месяц, в котором будут отмечать дни рождения не менее 2 учеников 
класса. Это и требовалось доказать. Также задача легко решается с 
использованием метода доказательства от противного. 
2.
В классе 35 учеников. Можно ли утверждать, что среди них найдутся 
хотя бы 2 ученика, фамилии которых начинаются с одной буквы? ( 
Решение. Пусть 35 учеников будут «зайцы», а буквы – это «клетки». В 
русском алфавите 33 буквы. 
Фамилии не могут начинаться на ь и ъ знаки. Т.к. 35 больше 31, то 
найдутся 2 ученика, у которых фамилии начинаются с одной буквы.
3.
Дано 12 целых чисел. Докажите, что из них можно выбрать 2, 
разность которых делится на 11. ( Решение. Примем числа за «зайцев». Т.к. 
их 12, то «клеток» должно быть меньше. Пусть «клетки» - это остатки от 
деления целого числа на 11.Всего «клеток» будет 11: 0,1,2,3,4,5,6,7,8,9,10. 
Тогда по принципу Дирихле, найдется «клетка», в которой будут сидеть не 
менее чем 2 «зайца», т.е. найдутся 2 целых числа с одним остатком. А 
разность двух чисел с одинаковым остатком от деления на 11 будет 
делиться на 11. Действительно, пусть a=11m+q, b=11n+q, тогда a-b= 
11m+q-(11n+q)=11(m-n). ( делится на 11). 
4.
Дано 9 целых чисел. Докажите, что из них можно выбрать 2, разность 
которых делится на 8. (Решается задача подобно задаче № 3. Только 
здесь будет 8 остатков:0,1,2,3,4,5,6,7 – «клетки», а числа – их 9 – «зайцы».
 
5.
В лесу растет миллион елок. Известно, что на каждой из них не более 
600 000 иголок. Докажите, что в лесу найдутся две елки с одинаковым 
количеством иголок.