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

Твердження про кратність

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

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

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

Підказка

Нехай $T$ — кількість правдомовців. Твердження залежать лише від $T$ , тож знайдіть, які $T$ можуть узгодитися з множиною правдивих людей.

Розв’язок

Нехай $T$ — кількість правдомовців. Людина $i$ правдива рівно тоді, коли $i$ ділить $T$ , тож правдомовці — це люди, чиї номери ділять $T$ , і їх має бути рівно $T$ .
Якщо $T = 0$ , кожне число ділить $0$ , що дає $20$ правдомовців, а це суперечність.
Для $T \geq 3$ дільники $T$ , крім самого $T$ , не перевищують $\frac{T}{2}$ , тож правдомовців щонайбільше $1 + \frac{T}{2} < T$ , а це суперечність.
Для $T = 1$ єдиний дільник — $1$ , а для $T = 2$ дільники — $1$ і $2$ , і обидва випадки узгоджені; кожне $T$ фіксує розподіл, тож кількість дорівнює $2$ .

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

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