Задача про три склянки
Задача про три склянки — це математична головоломка, яка не має розв'язку в найбільш поширеному формулюванні.
Початкова позиція задачі: одна склянка перевернута догори дном, а дві інших — стоять правильно. Необхідно перевернути всі склянки у правильне положення не більші ніж за шість кроків, кожного кроку перевертаючи по дві склянки.
Вирішувана версія[ред. | ред. код]
Розв'язна (але тривіальна) версія цієї задачі в початковій позиції має одну склянку, що стоїть правильно, та дві — догори дном. Для розв'язання цієї задачі достатньо перевернути дві склянки в правильну позицію.
Доказ нерозв'язності[ред. | ред. код]
Для доведення нерозв'язності (коли початкова позиція — одна склянка догори дном), достатньо зосередитись на кількості склянок догори дном (W). Необхідно зменшити W від 1 до 0, тобто −1 (непарне число); однак кожен крок змінює W на парне число. Зокрема, для трьох склянок, кожен крок змінює W на +1 (якщо склянка стояла правильно) або −1 (в іншому випадку), тобто крок змінює W на суму двох непарних чисел, яка є парним числом, що завершує доведення.
У загальнішому випадку, це доведення показує, що для будь-якої кількості склянок неможливо змінити W на 0 (нуль), якщо початково це число було непарне, а умова задачі вимагає перевертати кожного кроку лише по дві склянки. Однак, якщо W — парне число, то потрібно перевертати по дві склянки, поки W не станем нулем.