МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Руководитель Дмитрий Владимирович Трущин
2014/2015 учебный год

Занятие 20 (11 апреля 2015 года). Принцип Дирихле и делимость.

1.
Кощей Бессмертный пообещал Ивану-Царевичу, что сохранит ему жизнь, если Иван в течение минуты назовет две степени двойки с одинаковыми последними цифрами. Помогите Ивану.
2.
Если Иван-Царевич найдет две степени двойки с двумя совпадающими последними цифрами, то Кощей отдаст ему в жены Василису Прекрасную, если с тремя — то и полцарства в придачу. Если не справится — голова с плеч. Стоит ли браться за дело?
3.
Докажите, что: а) среди любых 11 целых чисел найдутся два, оканчивающихся одной и той же цифрой; б) среди любых 8 целых чисел найдутся два, разность которых делится на 7.
4.
Витта задумала пять натуральных чисел и возвела их в квадраты. Оля утверждает, что среди этих квадратов найдутся такие два числа, что их разность делится на 9. Права ли она?
5.
Докажите, что из любых 10 чисел можно выбрать либо число, делящееся на 10, либо несколько, сумма которых делится на 10.
6.
Докажите, что существует кратное 321 число, в записи которого участвуют а) только нули и единицы; б) только единицы.
7.
Сколько можно взять различных натуральных чисел от 1 до 10 так, чтобы среди них не нашлось двух, одно из которых точно вдвое больше другого?
8.
Какое наибольшее количество натуральных чисел, не превышающих 40, можно выбрать так, чтобы ни одно из них не делилось на другое?
9.
a)
Даны 8 различных натуральных чисел, каждое из которых не больше 15. Докажите, что среди их попарных разностей найдутся три одинаковых.
b)
Даны 20 различных натуральных чисел, меньших 70. Докажите, что среди их попарных разностей найдутся четыре одинаковые.
10.
Докажите, что среди любых 9 последовательных натуральных чисел найдется по крайней мере одно число, взаимно простое с каждым из остальных.
11.
Докажите, что из 37 целых чисел всегда можно найти ровно 7 таких, сумма которых делится на 7.
12.
Докажите, что если число натуральное число n не делится на простое число p, то среди степеней числа n найдётся такая, которая имеет остаток 1 при делении на p.