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

  • "А я слышал, что все умерли"

    "А встречал версию, что он умер и все события романа - его предсмертные галлюцинации". О боже, как я ненавижу такой поворот беседы. Собрались люди,…

  • Евангелие от Фомы

    118. Симон Петр сказал им: Пусть Мария уйдет от нас, ибо женщины недостойны жизни. Иисус сказал: Смотрите, я направлю ее, дабы сделать ее мужчиной,…

  • Немцы и германцы в Первую мировую

    В чужом журнале один незнакомец (судя по другим его утверждениям - не очень компетентный) заявил, будто в XIX веке слово "немцы" было простонародным,…

  • 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