Макс 509 (chyyr) wrote,
Макс 509
chyyr

Category:

Задачка

В какой-то математической олимпиаде для школьников была недавно любопытная задачка.

Дано натуральное число 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?
Tags: математика
Subscribe

  • Иван IV, за свою жестокость прозванный Васильевичем.

    Iwan IV surnommé BASILOWITZ & connu dans nos Histoires sous le nom du Tyran Jean Basilide. Иван IV, прозванный Васильевичем, и известный в нашей…

  • Воспоминания о будущем

    Народные лингвисты будущего будут объяснять происхождение русско-украинских пар golod/holod, gorka/hirka, godnost'/hidnist' и т.п. тем, что палец на…

  • Навеяло френдлентой

    А на Арракисе меланжевый ад. Я наберу меланжи — буду рад, Но я тебе не дам, не смей меня винить! Ну посмотрите, до чего хороша, Но без меня ты не…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments