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

Оточені брехунами

ГоловоломкиСереднє

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

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

Підказка

Перекладіть кожен тип на правило про сусідів, а потім розріжте коло на блоки, кожен з яких починається з правдомовця.

Розв’язок

Правдомовець має поруч $2$ брехунів, тож жодні $2$ правдомовці не сидять поруч; твердження брехуна хибне, тож поруч із ним є принаймні один правдомовець, а отже немає $3$ брехунів поспіль.
Тому за кожним правдомовцем іде $1$ або $2$ брехуни, і коло розпадається на блоки по $2$ або $3$ місця. З $x$ блоками по $2$ і $y$ блоками по $3$ потрібно $2 x + 3 y = 10$ , тож $(x, y) = (5, 0)$ або $(2, 2)$ .
Для $k$ блоків у заданому циклічному порядку та $10$ пронумерованих місць кількість розміщень дорівнює $10 \times \frac{( x k )}{k}$ .
Для $(5, 0)$ це $10 \times \frac{1}{5} = 2$ , а для $(2, 2)$ це $10 \times \frac{6}{4} = 15$ , тож загалом $2 + 15 = 17$ .

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

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