Условие:
Рассмотрим полный набор косточек домино, в котором числа на половинках
косточек (будем называть их дольками) могут принимать значения от 0 до п (где n –
натуральное число, рассмотрите вначале пункты этой задачи для небольших
значений n, например, равных 3, 4, 5, 6).
Будем выкладывать косточки домино в соответствии со следующими
правилами. Начинать можно с любой косточки. Каждую следующую косточку
необходимо выкладывать так, чтобы она продолжала уже выложенную цепочку (по
принципу «торец в торец») и при этом число на прикладываемой дольке этой
косточки было равно числу на соответствующей концевой дольке цепочки.
Цепочки из косточек домино, полученные по этим правилам, будем
называть правильными разложениями.
1) Сколько всего косточек домино в указанном наборе (в зависимости от n)?
2) Какое наибольшее число косточек может быть выложено в соответствии с
правилами при каждом значении n (будем называть такие расположения
косточек максимальными правильными разложениями)?
3) Попробуйте определить точно или оценить количество правильных разложений
(хотя бы для некоторых отдельных значений п, п = 3, 4, 5, …).
Решение:
Рассмотрим задачу по порядку. 1) Сколько всего косточек домино в указанном наборе (в зависимости от n)? Косточки домино имеют две половинки, и каждая половинка может принимать значения от 0 до n. Косточка обозначается как (a, b), где a и b — значения на половинках. Поскольку порядок не важен (косточка (a, b) равна косточке (b, a)), мы можем считать только уникальные пары. Количество уникальных косточек можно вычислить следующим образом: - Если a = b, то у нас есть n + 1 вариантов (0,0), (1,1), ..., (n,n). - Если a ≠ b, то мы можем выбрать a и b из n + 1 значений, и количество таких пар буде...