Задача 78631

Темы:    [ Десятичная система счисления ] [ Процессы и операции ] [ Доказательство от противного ] [ Индукция (прочее) ]

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

Условие

Рассматриваются всевозможные n-значные числа, составленные из цифр 1, 2 и 3. В конце каждого из этих чисел приписывается цифра 1, 2 или 3 так, что к двум числам, у которых во всех разрядах стоят разные цифры, приписываются разные цифры. Доказать, что найдется n-значное число, в записи которого участвует лишь одна единица и к которому приписывается единица.

Решение

Докажем, что есть два числа, различающиеся лишь одной цифрой, к которым приписываются разные цифры. Действительно, предположим, что к любым двум числам, различающимся лишь одной цифрой, приписываются одинаковые цифры. Тогда по индукции доказывается, что к любым двум числам, различающимся k цифрами, приписываются одинаковые цифры. Для k=n получаем противоречие с условием. Значит, есть два числа X=a₁a₂..a_k-1xa_k+1..a_n и Y=a₁a₂..a_k-1ya_k+1..a_n , различающиеся только одной цифрой, к которым приписываются разные цифры p и q . Докажем теперь, что к каждому числу, у которого k -я цифра равна x , приписывается цифра p , а к любому числу, у которого k -я цифра равна y , приписывается q , а к остальным числам приписывается цифра r , отличная от p и q . Действительно, пусть, например, нам дано число Z=b₁b₂..b_k-1x b_k+1..b_n . Пусть цифра z отлична от p и q , а цифра c_i отлична от a_i и b_i , 1 z, c_i 3 . Рассмотрим число T=c₁c₂..c_k-1zc_k+1..c_n . Оно отличается от X и Y во всех разрядах, поэтому к нему приписывается цифра r . Число Z отличеается во всех разрядах от Y и T , поэтому к нему приписывается цифра p . Аналогично рассматриваются случаи, когда k -я цифра данного числа равна y или z . Из доказанного правила приписывания цифр очевидно следует утверждение задачи.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	30
Год	1967
вариант
	1
Класс	10
Тур	2
задача
Номер	5