Алгоритм обмінів склянок, що розпізнає кількість кульок
Умова задачі
Робот «Mag-o-matic» маніпулює 101 склянкою, розташованою в ряд, позиції якого пронумеровано від 1 до 101. У кожній зі склянок може знаходитися, а може й не знаходитися, кулька. Робот Mag-o-matic приймає лише елементарні інструкції виду , які він інтерпретує як
«розглянь склянку в позиції : якщо вона містить кульку, то поміняй місцями склянки, що знаходяться в позиціях і (разом з їхнім можливим вмістом), інакше перейди до наступної інструкції»
(мається на увазі, що — цілі числа від 1 до 101, причому і різні між собою, але не обов'язково відмінні від ). Програма — це скінченна послідовність елементарних інструкцій, заданих на початку, які Mag-o-matic виконує одну за одною.
Підмножина називається розпізнаваною, якщо існує програма, яка, починаючи з будь-якої початкової конфігурації, дає кінцеву конфігурацію, в якій склянка в позиції 1 містить кульку тоді й лише тоді, коли кількість склянок, що містять кульку, є елементом .
a. Доведіть, що підмножина множини , яка складається з непарних чисел, є розпізнаваною.
b. Визначте всі розпізнавані підмножини множини .