Задача 79515

Темы:    [ Десятичная система счисления ] [ Принцип Дирихле (прочее) ]

Сложность: 4- Классы: 8,9,10

Условие

Даны 7 различных цифр. Доказать, что для любого натурального числа n найдётся пара данных цифр, сумма которых оканчивается той же цифрой, что и число.

Решение

Пусть a₁,..., a₇ — данные цифры. Заметим, что если a_i есть последняя цифра числа n-a_j, то последние цифры чисел a_i+a_j и n совпадают. Следовательно, достаточно доказать, что при некоторых различных i и j a_i есть последняя цифра числа n-a_j. Так как в наборе {a₁,..., a₇} все цифры различны и в наборе последних цифр чисел вида n-a_i все цифры различны, в каждом из этих наборов по семь цифр, а всего цифр десять, то наборы пересекаются не менее, чем по четырём цифрам. Следовательно, либо выполнено утверждение задачи, либо для четырёх различных цифр b₁, b₂, b₃, b₄ последняя цифра числа n совпадает с последней цифрой числа 2b_i, что невозможно.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	50
Год	1987
вариант
Класс	9
задача
Номер	1