Задача про три склянки

Задача про три склянки — це математична головоломка, яка не має розв'язку в найбільш поширеному формулюванні.

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

Вирішувана версія

Розв'язна версія задачі про три склянки. У нерозв'язній версії, склянки A та C стоять правильно, а склянка B — догори дном

Розв'язна (але тривіальна) версія цієї задачі в початковій позиції має одну склянку, що стоїть правильно, та дві — догори дном. Для розв'язання цієї задачі достатньо перевернути дві склянки в правильну позицію.

Доказ нерозв'язності

Для доведення нерозв'язності (коли початкова позиція — одна склянка догори дном), достатньо зосередитись на кількості склянок догори дном (W). Необхідно зменшити W від 1 до 0, тобто −1 (непарне число); однак кожен крок змінює W на парне число. Зокрема, для трьох склянок, кожен крок змінює W на +1 (якщо склянка стояла правильно) або −1 (в іншому випадку), тобто крок змінює W на суму двох непарних чисел, яка є парним числом, що завершує доведення.

У загальнішому випадку, це доведення показує, що для будь-якої кількості склянок неможливо змінити W на 0 (нуль), якщо початково це число було непарне, а умова задачі вимагає перевертати кожного кроку лише по дві склянки. Однак, якщо W — парне число, то потрібно перевертати по дві склянки, поки W не станем нулем.

Див. також

Примітки

    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.