mini.weblabkealon(Ruslan),

ну когда табличку привели, объяснили, что и как нужно нажимать, то решение додумать уже не проблема :-)
идея метода в 18701187 (это в моем понимании, хотя, может, Александр и не согласится)

ПС:
честно говоря, пока не увидела решение Александра, даже в голову не пришло посмотреть на задачу именно в таком ключе
:)

Вы неявно предполагаете, что такая таблица существует для любого количества переключателей.
На самом деле это не доказано и опираться на это нельзя.
Пока лишь доказано, что таблица существует для (2^N)-1 переключателей, где N - любое натуральное.

mini.weblabпереформулирую, допустим, для беглого ознакомления с вопросом, что гуглить?
основы криптографии? что-нибудь по основам CS? что?

Достаточно общих знаний по:
теории множеств (операции, включения-исключения),
двоичной системе (биты, xor),
комбинаторике (биномиальные коэффициенты, основное тождество).

Чтобы досконально разобраться попробуйте по-честному
построить все функции перехода для N=4 бит номера комнаты через xor.
Это не так трудно, поверьте.

mini.weblabmini.weblabAleksandr Sharahov,
хм.., т.е. если у вам будет 3 переключателя, то задачу с 4 комнатами вы не решите?
правильно будет так:

если у вас будет 4 переключателя, то задачу с 5 комнатами вы не решите?

Не знаю, но почти уверен, что 6-ти переключателей на 7 комнат не хватит.

mini.weblabDima T,

я неправильно сформулировала, я могу применить формулу и посчитать по ней нужное количество переключателей,
но я не понимаю, как выводится формула

Доказывается необходимость и достаточность.

Давайте сначала мы докажем в ту сторону, куда проще.
В нашем случае необходимость для 2^N дверей как минимум 2^N-1 переключателей. За одну операцию кодирования двери мы можем переключить только 1 переключатель или не переключать ни одного. Из некоторого исходного положения мы должны иметь возможность закодировать 2^N дверей различных дверей. Значит нужно иметь не менее 2^N-1 различных переключателей.

Теперь в обратную сторону, достаточность.
Мы просто укажем способ кодирования, который всегда позволяет от произвольного случайного значения кода перейти к одному из кодов любой заранее заданной двери (вы, разумеется, понимаете что каждая дверь может имеет несколько двоичных кодов, состоящих из 2^N-1 бит). Нам достаточно найти только один подходящий код.
Вот тут и есть то самое место, которое, как мне кажется, всех сбивает с толку. По счастливой случайности битов в нашем распоряжении ровно столько, сколько нужно чтобы закодировать все подмножества (за исключением пустого) множества из N битов. И мы так и поступим. Т.е. каждый бит у нас будет соответствовать некоторому подмножеству.
Таким образом, у нас будет свой кодирующий бит для каждого исходного бита множества, свой кодирующий бит для каждой пары исходных битов, для каждой тройки, ... и, наконец, кодирующий бит для всех N битов исходного множества. Это важно твердо понимать.
Теперь двинемся дальше. Попробуем понять, что означает некоторый двоичный код, который мы видим перед собой. Давайте посмотрим на все эти подмножества и соответствующие им биты кода как на операции, которые позволяют перейти от пустого множества к тому, которое кодирует эта операция. Но тогда весь код означает суперпозицию операций. С последовательностью применения закодированных операций не возникнет вопросов, если мы выберем XOR над элементами множества (теми самыми N битами). Важно понимать, что код также задает некоторое подмножество, полученное из пустого.
Опять же по счастливой случайности такое определение операции позволит нам изменением всего одного бита случайного кода в получить код, который в результате последовательного применения всех закодированных в нем операций в конце концов позволит получить любое заданное подмножество исходных N бит.
Понятно, что мы всегда сможем найти такой кодирующий бит, т.к. у нас есть свой бит для любого подмножества, в том числе и для подмножества, закодированного упомянутым случайным кодом и подмножеством, которое мы хотим получить.
Вот и все )

Сорри, исправлю здесь же самые дикие опечатки:

Доказывается необходимость и достаточность.

Давайте сначала докажем в ту сторону, куда проще.
В нашем случае необходимость для 2^N дверей иметь как минимум 2^N-1 переключателей. За одну операцию кодирования двери мы можем переключить только 1 переключатель или не переключать ни одного. Из некоторого исходного положения мы должны иметь возможность закодировать 2^N различных дверей. Значит нужно иметь не менее 2^N-1 различных переключателей.

Теперь в обратную сторону, достаточность.
Мы просто укажем способ кодирования, который всегда позволяет от произвольного случайного значения кода перейти к одному из кодов любой заранее заданной двери (вы, разумеется, понимаете что каждая дверь имеет несколько двоичных кодов, состоящих из 2^N-1 бит). Нам достаточно найти только один подходящий код.

Вот тут и есть то самое место, которое, как мне кажется, всех сбивает с толку. По счастливой случайности битов в нашем распоряжении ровно столько, сколько нужно чтобы закодировать все подмножества (за исключением пустого) множества из N битов. И мы так и поступим. Т.е. каждый бит у нас будет соответствовать некоторому подмножеству.

Таким образом, у нас будет свой кодирующий бит для каждого исходного бита множества, свой кодирующий бит для каждой пары исходных битов, для каждой тройки, ... и, наконец, кодирующий бит для всех N битов исходного множества. Это важно твердо понимать.

Теперь двинемся дальше. Попробуем понять, что означает некоторый двоичный код, который мы видим перед собой. Давайте посмотрим на все эти подмножества и соответствующие им биты кода как на операции, которые позволяют перейти от пустого множества к тому, которое кодирует эта операция. Но тогда весь код означает суперпозицию операций. С последовательностью применения закодированных операций не возникнет вопросов, если мы выберем XOR над элементами множества (теми самыми N битами). Важно понимать, что код также задает некоторое подмножество, полученное из пустого.

Опять же по счастливой случайности такое определение операции позволит нам изменением всего одного бита случайного кода в получить код, который в результате последовательного применения всех закодированных в нем операций в конце концов позволит получить заданное подмножество исходных N бит.

Понятно, что мы всегда сможем найти такой кодирующий бит, т.к. у нас есть свой бит для любого подмножества, в том числе и для подмножества, полученного XOR'ом подмножества, закодированного упомянутым случайным кодом, и подмножества, которое мы хотим получить.
Вот и все )[/quot]

mini.weblabМеня смутили числа 2^N и 2^N - 1, и я долго думала, откуда они взялись и как их получить.
Насколько я поняла, нужно связывать побитовое инвертирование последовательности чисел
(допустим, от 1 до 8, как в задаче) и заданную кодировку (инвертирование 1 бита в ключе)


Первое из чисел - количество подмножеств множества из N элементов.
В нашем случае элементами являются отдельные биты некоторого числа.
В нашем случае некоторым числом является номер комнаты.

Второе из чисел - количество подмножеств множества из N элементов,
за исключением пустого подмножества. Оно нам не нужно,
т.к. с его помощью мы не будем задавать никаких операций,
ведь XOR с нулем не меняет числа. Тождественная операция у нас и так
всегда есть по условию - мы имеем право в качестве кода использовать
само исходное случайное значение.

Важно понимать, что инвертирование битов числа является следствием
операции XOR над множеством его битов. Именно поэтому проще всего
программа получится когда интервал возможных значений начинается с 0
и заканчиваться числом, в двоичной записи которого все биты равны 1.
В противном случае если вы хотите получить минимальную длину кода,
вам могут потребоваться дополнительные сдвиги диапазона,
чтобы попасть в указанный интервал.

mini.weblabОпределим ключ как последовательность значимых переключателей
Пусть имеются числа от 1 до n.
Требуется закодировать заданное число от 1 до n.
Метод кодировки: изменение одного бита в произвольно заданном ключе
Задача: Рассчитать необходимый и достаточный размер ключа

Это хороший повод поговорить по душам с тестирующим )
Плюс в том, что разговор может получиться длинным и своем поле.
Минус в том, что при этом его легко обидеть.
Ваши шансы возрастают, если разговор будет на троих )

Dima TAleksandr SharahovПервое из чисел - количество подмножеств множества из N элементов.
Этим ты и запутал. Элементов не N а 2^N
Т.е. N это количество бит, которое необходимо чтобы пронуменовать все элементы. Если дверей 8 то N=3

Просьба не навязывать мне свои обозначения.
Можете считать, что мне лень в них вникать.

В моем тексте используются мои обозначения.
Хотите критиковать меня - пожалуйста, но используйте при этом мои обозначения.

Dima T,

см. 18704296 , где написано

Первое из чисел - количество подмножеств множества из N элементов.
В нашем случае элементами являются отдельные биты некоторого числа.
В нашем случае некоторым числом является номер комнаты.

SashaMercuryAleksandr Sharahov, простите, но мне непонятно ваше доказательство, более того, я плохо понял что вы пытались доказать.


Доказывается необходимость и достаточность 2^N-1 переключателей для 2^N дверей.
Какое место в доказательстве непонятно?