![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
chyyrВ какой-то математической олимпиаде для школьников была недавно любопытная задачка.
Дано натуральное число k. Посчитайте, сколько существует упорядоченных наборов (a1,...,ak), которые удовлетворяют следующим трем условиям:
1)a1,...,ak - натуральные числа (возможно, повторяющиеся);
2) разность между любыми двумя соседними числами в наборе не превосходит 2 (т.е. для любого индекса i < k верно неравенство |ai - ai+1|< 3)
3) В наборе хотя бы один раз встречается число 4 или число 5 (может быть, оба вместе)
(Слово "упорядоченные" означает, что при изменении порядка чисел набор меняется. То есть (1,3,5,4,3,4) и (1,3,5,4,4,3) - это два различных набора, удовлетворяющих условию задачи при k=6)
С наскока я ее не решил, пришлось остановиться и чуть-чуть подумать.
Комбинаторика там довольно простая, просто надо все аккуратно представить.
1. Сколько существует упорядоченных наборов из k целых чисел, начинающихся с нуля и удовлетворяющих условию 2)?
2. Сколько существует наборов из k натуральных чисел, удовлетворяющих условиям 1) и 2), в которых хотя бы один раз встречается число 1?
3. В наборе, удовлетворяющем условию 2), нет ни числа 5, ни числа 4. Могут ли в нем быть числа 3 и 6?
Дано натуральное число k. Посчитайте, сколько существует упорядоченных наборов (a1,...,ak), которые удовлетворяют следующим трем условиям:
1)a1,...,ak - натуральные числа (возможно, повторяющиеся);
2) разность между любыми двумя соседними числами в наборе не превосходит 2 (т.е. для любого индекса i < k верно неравенство |ai - ai+1|< 3)
3) В наборе хотя бы один раз встречается число 4 или число 5 (может быть, оба вместе)
(Слово "упорядоченные" означает, что при изменении порядка чисел набор меняется. То есть (1,3,5,4,3,4) и (1,3,5,4,4,3) - это два различных набора, удовлетворяющих условию задачи при k=6)
С наскока я ее не решил, пришлось остановиться и чуть-чуть подумать.
Комбинаторика там довольно простая, просто надо все аккуратно представить.
1. Сколько существует упорядоченных наборов из k целых чисел, начинающихся с нуля и удовлетворяющих условию 2)?
2. Сколько существует наборов из k натуральных чисел, удовлетворяющих условиям 1) и 2), в которых хотя бы один раз встречается число 1?
3. В наборе, удовлетворяющем условию 2), нет ни числа 5, ни числа 4. Могут ли в нем быть числа 3 и 6?
