Задача 73582

Темы:    [ Сочетания и размещения ] [ Десятичная система счисления ] [ Подсчет двумя способами ]

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

Условие

Из цифр 1 и 2 составили пять n-значных чисел так, что у каждых двух чисел совпали цифры ровно в m разрядах, но ни в одном разряде не совпали все пять чисел. Докажите, что отношение ^m/_n не меньше ⅖ и не больше ⅗.

Решение

  Выпишем числа одно под другим. В каждом разряде ("столбце") пять цифр. Из них можно составить 10 (неупорядоченных) пар. По всем столбцам таких пар будет 10n. Выясним, сколько среди них таких, которые состоят из одинаковых цифр, то есть пар  (1, 1)  и  (2, 2).  В каждом столбце таких пар либо 4, либо 6. Поэтому общее количество таких пар не меньше 4n и не больше 6n. С другой стороны, количество таких пар равно 10m, поскольку всевозможных пар из пяти чисел – 10.
  Итак,  4n ≤ 10m ≤ 6n,  что и требовалось доказать.

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

журнал
Название	"Квант"
год
Год	1970
выпуск
Номер	10
Задача
Номер	М47