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

Парність серед інших

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

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

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

Підказка

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

Розв’язок

Нехай $L$ — загальна кількість брехунів. Правдомовець бачить серед інших $L$ брехунів, і твердження правдиве, тож $L$ парне.
Брехун бачить серед інших $L - 1$ брехунів, і твердження хибне, тож $L - 1$ непарне, що знову означає парність $L$ .
Отже, розподіл узгоджений рівно тоді, коли загальна кількість брехунів парна, незалежно від типів окремих людей.
Рівно половина з $2^{11}$ розподілів має парну кількість брехунів, а це $2^{10} = 1024$ .

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

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