Задача 78662

Темы:    [ Примеры и контрпримеры. Конструкции ] [ Десятичная система счисления ]

Сложность: 3+ Классы: 10,11

Условие

Можно ли выбрать 100 000 номеров телефонов из 6 цифр каждый так, чтобы при одновременном вычеркивании из всех этих номеров k-той цифры (k = 1, 2,...6) получились все пятизначные номера от 00000 до 99999?

Решение

Докажем, что для этого достаточно выбрать все номера телефонов, для которых сумма цифр делится на десять. Заметим сначала, что при одновременном вычёркивании из всех этих номеров k-й цифры получаются все пятизначные номера, причём каждое ровно по одному разу. Действительно, число  получается при вычёркивании цифры d тогда и только тогда, когда число d + s, где  s = a₁ + ... + a₅, делится на десять, а для любого целого числа s существует ровно одна цифра d, для которой число s + d делится на десять. Следовательно, общее количество выбранных номеров равно количеству пятизначных номеров, т. е. равно 100 000. Таким образом, мы нашли 100 000 номеров, удовлетворяющих требованиям задачи.

Ответ

можно.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	31
Год	1968
вариант
	1
Класс	9
Тур	1
задача
Номер	4