Версия для печати
Убрать все задачи

---

При обычной игре в домино кости выкладываются так, чтобы разность между числами на соседних костях равнялась 0.
Можно ли выложить все 28 костей в замкнутую цепь так, чтобы все эти разности равнялись ±1?

   Решение

Темы:    [ Делимость чисел. Общие свойства ] [ Раскладки и разбиения ] [ Разбиения на пары и группы; биекции ] [ Индукция (прочее) ]

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

Прислать комментарий

Условие

Пусть n и b – натуральные числа. Через  V(n, b)  обозначим число разложений n на сомножители, каждый из которых больше b (например:
36 = 6·6 = 4·9 = 3·3·4 = 3·12,  так что  V(36, 2) = 5).  Докажите, что  V(n, b) < ⁿ/_b.

Решение

  Индукция по n. База  (n = 1)  очевидна:  V(1, b) = 0.
  Шаг индукции. Предположим теперь, что это неравенство верно при всех  m < n. 
  Для каждого делителя  k > b  числа n рассмотрим все разложения числа n, в которых минимальный сомножитель равен k. Количество таких разложений равно  V(ⁿ/_k, k – 1).  Исключение составляет случай  k = n   – такое разложение одно, а  V(ⁿ/_n, n – 1) = 0.  Следовательно,

Замечания

12 баллов

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