Макс 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

  • Вымирание динозавров

    " Вымирание динозавров. Вымирания связаны с двумя причинами: внутренней (морфофизиологическое состояние) и внешней (абиотическая и био­тическая…

  • Соотношение полов

    На Элементах увидел неожиданное: Формирование мужских гамет так устроено, что Х- и Y-хромосом образуется поровну. Следует ожидать, что…

  • Пилтдаунский человек

    prokhozhyj выложил ссылку на интереснейшую серию постов про пилтдаунского человека. Коротко напомню, о чем речь: в начале XX века под…

  • 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