Навчання / Бібліотека / Головоломки

Твердження про трійку сусідів

ГоловоломкиСкладне

$12$ датчиків закріплено по колу огорожі. Кожен датчик є справним (правдомовцем) або зламаним (брехуном). Кожен датчик повідомляє: «Серед мене та моїх $2$ сусідів рівно один зламаний датчик». Скількома різними способами можна призначити типи пронумерованим позиціям так, щоб усі $12$ повідомлень були узгодженими?

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

З’ясуйте, які розташування місць навколо людини роблять її твердження правдивим, і перевірте, що це означає для правдомовців і брехунів.

Розв’язок

Правдомовцеві потрібен рівно один брехун серед нього та його сусідів, а брехунові потрібна кількість брехунів у його трійці, що не дорівнює $1$ ; самотній правдомовець між брехунами має в трійці $2$ брехунів, а $3$ правдомовці поспіль дають середньому $0$ , тож правдомовці трапляються лише суміжними парами.
Один брехун між $2$ правдомовцями бачив би рівно $1$ брехуна (себе), що неприпустимо, тож між послідовними парами правдомовців є щонайменше $2$ брехуни, а випадок без правдомовців (усі брехуни) узгоджений.
Для $k$ пар, кожна з яких має після себе проміжок щонайменше з $2$ брехунів, додаткові брехуни понад $2$ на проміжок разом становлять $12 - 4 k$ і розподіляються $(k - 1 11 - 3 k)$ способами, а розміщення візерунка на $12$ пронумерованих місцях дає $12 \times \frac{( k - 1 11 - 3 k )}{k}$ розташувань.
Це дає $12$ , $30$ і $4$ для $k = 1$ , $2$ , $3$ та $1$ для $k = 0$ , тож загалом $1 + 12 + 30 + 4 = 47$ .

Відповідь: $47$

Наступна задача Назад до бібліотеки