Вгадай, що я задумав • Костянтин Кноп • Науково-популярні завдання на "Елементи" • Математика

Вгадай, що я задумав

завдання

Костя задумав натуральне число K від 1 до 2013 і готовий відповідати "так" або "ні" на будь-які питання, які допускають такі відповіді. При цьому він має право дати помилковий відповідь не більше одного разу (за всі відповіді).

Саша хоче задати Кості не більше 15 питань, з відповідей на які він завжди зможе вгадати задумане число. Допоможіть йому це зробити.


Підказка 1

Зазвичай в подібних завданнях намагаються задавати «питання-порівняння», тобто «Чи правда, що твоє число менше такого-то» (або «більше такого-то»). Однак Саші зовсім нема чого обмежувати себе саме такими питаннями. Більш загальний тип питань виглядає так: Саша записує будь-яка множина чисел (до якого входять якісь з чисел від 1 до 2013) і питає Костю: «Чи правда, що ти задумав одне з цих чисел?».


Підказка 2

Якби Костя не міг помилятися, то Саші вистачило б 11 питань (подумайте, чому). Значить, у Саші є чотири питання "в запасі", і він повинен постаратися задавати питання так, щоб якщо в якийсь момент відповіді Кістки стали суперечити один одному, то далі можна було вгадувати число K стандартним чином, кожен раз ділячи навпіл кількість варіантів, що залишилися.


Підказка 3

Спробуйте придумати безлічі для перших 11 питань Саші так, щоб після відповідей на них Саша міг залишити в «списку підозрілих» тільки 12 чисел – одне за умови, що Костя ще не помилявся, і ще по одному числу на кожну можливу помилку Кістки.


Рішення

Спочатку зробимо те, що було запропоновано в підказці 3.

Найпростіше для цього скористатися двійковій системою. Оскільки 2013 менше, ніж 211 = 2048, то двійковий запис будь-якого з можливих задуманих чисел містить не більше 11 розрядів. Оскільки цифра в кожному розряді – це 0 або 1, то Саша може першими питаннями безпосередньо питати: "Чи вірно, що цифра в i-м (праворуч) розряді двійкового запису задуманого числа дорівнює 1?", Послідовно перебираючи все i від 1 до 11.

Якщо Костя не помилиться у відповідях ні на один з цих питань, то Саша дізнається все розряди задуманого числа, тобто дізнається число K (Правда, оскільки він не знає, помилявся чи Костя, то він не може зробити висновок про те, що він знає задумане число). Якщо ж Костя помилиться у відповіді на якесь питання, це буде означати, що задумане число K відрізняється від даних Костею відповідей в якомусь одному розряді.Але таке число теж тільки одне – і так як помилка могла бути зроблена в будь-якому з 11 розрядів, то є ще рівно 11 підозрілих чисел.

Позначимо 12 чисел з отриманого списку K0, K1, … , K11 (Перше – при відсутності помилок, інші – при помилці у відповіді на відповідне питання).

Як тепер повинен діяти Саша? Якщо він задасть наступне питання (див. Підказку 1 про структуру питань) про безліч з d чисел (все одно яких, але не включають K0; наприклад, K1, … , Kd) І отримає відповідь "так", це може означати одне з двох: або загадане дійсно одне з цих d чисел, або Костя помилився у відповіді на це питання. Але якщо Костя помилився, то він міг згадати тільки K0, Тому що інші варіанти Kd+1, … , K11 означають, що Костя вже помилявся у відповіді на якийсь з попередніх питань, а другий помилки він допустити не може! Значить, при відповіді "так" у Саші залишається рівно d + 1 варіантів, причому він точно розуміє, що в одному з попередніх відповідей Костя помилився. Оскільки після цього питання у Саші залишаються в запасі ще 3 питання, він зможе вгадати задумане число з 8 варіантів. Тому можна покласти d + 1 = 8, тобто d = 7, і розглянути тільки відповідь "ні" на 12-й питання.

Відповідь «ні» означає, що Костя дійсно не міг задумати числа K1, … , K7 (Інакше це було б другий його помилкою). Значить, після такої відповіді список підозрілих чисел зменшився до 5: K0, K8, K9, K10, K11. Міркуючи так само, як вище, переконаємося, що 13-м питанням Саша може запитувати про числа K8, K9, K10: В разі відповіді "так" він повинен буде вгадати одне з чотирьох чисел K0, K8, K9, K10, Для чого йому вистачить двох питань, що залишилися, а в разі відповіді "ні" в списку підозрілих залишаться тільки K0 і K11.

Тепер (14-м питанням) досить запитати про одне число K11. Як і в розібраних вище ситуаціях, відповідь "так" означатиме, що Костя вже точно помилявся, – і тоді Саша вгадає одне з двох чисел за останній, 15-й, питання. Ну а після відповіді "ні" 15-го питання можна вже і не ставити – Саша може відразу зробити висновок про те, що Костя задумав K = K0.


Післямова

1. Чи можна було обійтися без застосування двійкової системи? Так, безсумнівно.

Зауважимо, що в кожен момент "гри" між Костею і Сашею ситуація ( "стан гри") повністю описується двома числами [a; b]: a – кількість чисел, які міг згадати Костя за умови, що він ще не робив помилок, а b – кількість чисел, які Костя міг загадати за умови, що він допустив вже помилку в одному з попередніх відповідей.Гра починається зі стану [2013; 0], а закінчитися має в той момент, коли "підозрювану" число залишилося єдиним – тобто або на стані [1; 0], або на [0; 1].

Нехай перше питання Саші ставився до безлічі з d чисел. Тоді після відповіді "так" новим станом гри стало [d; 2013 – d], А після відповіді "ні" – [2013 – d; d] (Подумайте, чому це так). Якщо Саша розділить безліч з 2013 чисел на дві майже рівні частини, то він отримає один зі станів [1007; 1006] і [1006; 1007]. Другим питанням він може розділити навпіл кожну з цих частин – і отримати або [504; 1006], або [503; 1007] (тут 1007 чисел виходять наступним чином: по-перше, це ті 504 числа з b = 1007, які Саша включив в свою безліч, а по-друге, це ті 503 чисел з a = 1006, які він у безліч не включив – але якщо Костя припустився помилки при відповіді на це питання, то ці числа могли бути їм загадали).

Продовжуючи задавати питання таким же чином, отримуємо послідовно

[504; 1006] → [252; 755] → [126; 504] → [63; 315] → [32; 189] → [16; 111] → [8; 64] → [4; 36] → [2; 20] → [1; 11]

(Або [503; 1007] → [251; 755], що менше, ніж у вищенаведеній ланцюжку. Ще кілька аналогічних варіантів в цьому ланцюжку я відразу дозволив собі опустити.)

Таким чином, до описаної в нашому рішенні ситуації "1 + 11" можна було прийти і без жодних згадок двійковій системи.Ну а далі [1; 11] → ([1; 4] або [0; 8]) → ([1; 1] або [0; 4]) → ([1; 0] або [0; 2]) → [0; 1].

2. Наше рішення демонструє, що замість чисел від 1 до 2013 Саша міг дозволити Кості загадувати числа від 0 до 2047, і все одно укластися з вгадування за 15 питань. Однак воно залишає без відповіді дуже природний узагальнюючий питання. Нехай Саші дозволено ставити не 15, а N питань. В якому діапазоні (від 0 до M) Він може дозволити Кості загадувати числа, щоб цих питань вистачило для гарантованого вгадування?

Повна відповідь на це питання (точніше, доказ вірності цієї відповіді) далеко не так простий, як здається на перший погляд. Його можна записати так: якщо (Тут [x] – ціла частина числа x, Тобто найбільше ціле число, яке не перевищує x) Парно, то M = s, а якщо s непарній, то M = s – 1. Цікаво й те, що від моменту постановки завдання до отримання повного її рішення пройшло більше 20 років!

Мабуть, вперше задачу вгадування з можливістю робити помилки у відповідях сформулював чудовий угорський математик Альфред Рен `ї в статті 1961 року угорською мовою. Через кілька років (у своїй автобіографії "Пригоди математика") її популяризував американський математик Станіслав Улам.

"Ми з Хокінсом [Девід Хокінс, філософ, згодом автор чудової науково-популярної книги" Мова природи ". – Прим. авт.] Міркували над наступною пов'язаної з цим завданням: варіація гри "Двадцять питань". Одна людина задумує число в інтервалі від одиниці до одного мільйона (який як раз менше, ніж 220). Іншій людині дозволяється задати до двадцяти питань, на кожен з яких перший учасник повинен відповідати тільки "так" або "ні". Очевидно, що число можна вгадати, якщо спочатку запитати: це число в першій половині мільйона? У наступному питанні знову переполовинити вийшов інтервал чисел і так далі. В кінцевому підсумку, число можна вгадати менш ніж за log21000000 раз. Припустимо тепер, що учасник має право збрехати один або два рази. Скільки питань потрібно, щоб отримати правильну відповідь? Ясно, що для того, щоб вгадати одне з 2n чисел, потрібно більш n питань, оскільки про те, коли була сказана неправда, невідомо. У загальному вигляді ця задача не вирішена ".

Повне рішення задачі Улама для випадку однієї помилки було отримано Анджеєм Пельц в 1986 році, а для двох помилок – в 1990 році. Ще через 10 років математикам вдалося повністю вирішити задачу для "права на три помилки". Для завдань з бпрольшим числом помилок вирішені тільки окремі окремі випадки, а повних рішень поки не знайдено.

3. Якщо не вимагати оптимальних рішень і мінімального числа питань, то все стає набагато простіше. Так, в 1991 році на Всесоюзній олімпіаді з математики пропонувалася наступна задача (автори – А. Анджанс, І. Соловйов, В. Слітінскій.)

Слідчий придумав план допиту свідка, який гарантує розкриття злочину. Він збирається ставити запитання, на які можливі тільки відповіді "так" або "ні" (то, яке питання буде поставлено, може залежати від відповідей на попередні). Слідчий вважає, що всі відповіді будуть вірними, він підрахував, що при будь-якому варіанті відповідей доведеться поставити не більше 91 питання. Доведіть, що слідчий може скласти план не більше ніж з 105 питаннями, що гарантує розкриття злочину і в разі, якщо на одне питання може бути дана невірна відповідь (але може бути, що всі відповіді вірні).

Вирішення цього завдання було засновано на іншу ідею: як можна модифікувати вихідний план питань, додаючи в нього "контрольні питання". Спочатку слідчий задає перші 13 питань початкового плану, а потім задає 14-е питання "Збрехали Ви в попередній серії питань?".Отримавши відповідь "ні", він може продовжувати задавати серії з 12, 11, 10, …, 1 питань плану, повторюючи контрольне запитання після кожної серії (подумайте, чому відповідь "ні" на контрольне запитання гарантує, що відповіді на питання серії дійсно були вірними). Якщо ж на якийсь із контрольних питань отримана відповідь "так", то повторюється вся попередня серія, при цьому більше контрольних питань можна не ставити. Якщо відповідь "так" отримано на k-й контрольне запитання, то понад вихідного плану доведеться поставити k + (14 – k) = 14 питань. Відзначимо, що брехня могла бути і у відповіді на контрольне запитання – в цьому випадку відповіді на повторно задану серію будуть точно такими ж, як і в перший раз.

Чому "модифікація плану" не є оптимальною стратегією і не гарантує мінімальності числа поставлених запитань? Наприклад, тому, що вихідна задача слідчого була рівносильна вгадування задуманого числа з діапазону від 0 до 291 – 1. Але для цього, як ми вже знаємо, вистачає не 105, а всього 98 питань: 298/99 > 298/27 = 291. Проте запропонована в олімпіадної задачі модифікація збільшує довжину плану з N(N – 1) / 2 питань не більше ніж на N, Тобто на величину порядку квадратного кореня з подвоєною вихідної довжини. Що, загалом, теж не так і погано.

4. Чому серйозні математики взагалі займаються такими "іграшковими" завданнями? Справа в тому, що ця задача дуже близька до класичних задач теорії кодування і тісно пов'язана з ними (див .: Виявлення та виправлення помилок, Код Хеммінга). Дійсно, в описаній нами грі Костя і Саша можуть заздалегідь (до вибору Костею задуманого числа) домовитися про список запитань (в тому числі – домовитися про те, яке питання буде поставлено другим у відповідях "так" на перше питання, а який – при відповіді "ні", і аналогічно домовитися про наступні питання). Це означає, що Костя може просто послати Саші послідовність з 15 відповідей – або, якщо завгодно, послідовність з 15 символів "0" і "1". По кожній такій послідовності Саша зможе відгадати ( "реконструювати") задумане Костею число, а значить – визначити, у відповіді на яке питання Костя помилився. Це і є код Хеммінга, що виправляє одну помилку.

Стаття Р. Хеммінга "Коди, які виявляють і виправляють помилки" була опублікована в 1950 році (оригінал можна побачити, наприклад, тут, PDF, 3,1 Мб). У той час вихідні дані в комп'ютери завантажувалися за допомогою перфокарт, і пристрої введення перфокарт були настільки ненадійними, що практично жодна досить товста колода НЕ зчитувалася без помилок.Запуск програми, що містить помилку, приводив в кращому випадку до збою, після якого обчислення зупинялися і колоду доводилося прочитувати ще раз, а в гіршому – до повної зупинки машини. Придумані Хеммінга коди дозволяли не тільки виявляти помилки, але і автоматично виправляти їх. Це була справжня революція!

З тих пір, звичайно, надійність комп'ютерних систем зросла багаторазово, проте коди, що виправляють помилки, не стали від цього менш затребуваними: нині вони становлять основу протоколів передачі сигналів по лініях зв'язку. Коли-небудь напевно лінії зв'язку теж удосконалюються, однак необхідність в коригувальних кодах навряд чи коли-небудь зникне: помилки – вічні супутники будь-якої людської діяльності.


Like this post? Please share to your friends:
Залишити відповідь

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: