задачка

[avva]

У вас есть N монет. Вы выкладываете их в ряд одну за другой, какую решкой, какую орлом, как хотите. Вы показываете эти монеты ассистенту фокусника, а также загадываете число, от 1 до N, и говорите его ассистенту. После этого ассистент указывает на одну из монет и просит вас перевернуть ее (но перевернутая монета остается в ряду среди других). Ассистент всегда обязан попросить перевернуть ровно одну монету. Затем ассистент выходит из одной двери, а в другую дверь входит сам фокусник - они между собой никак не общаются. Фокусник смотрит на монеты и говорит вам, какое число вы загадали.

Вопрос: для каких значений N возможно организовать такой фокус, и как?

Комментарии не скрываю.

Comments

[dmarck.livejournal.com]

Это ж ECC натуральный ;)

[amarao-san.livejournal.com]

Я буду реально тупить, но 2.

[buddha239.livejournal.com]

Для степеней 2? Вроде видел такую задачу, но не помню ответ - помню только, что надо красить вершины гиперкуба.:)

[amarao-san.livejournal.com]

И как это инвертировав один бит можно в случайной последовательности гарантированно закодировать больше 1 бита информации?

[muchacho.livejournal.com]

Вершины N-мерного гиперкуба красим в N цветов таким образом, чтобы у каждой вершины её соседние (N вершин) были покрашены ровно в N цветов. Если получится, значит НЕслучайно меняя один из N бит случайной последовательности, мы можем закодировать log2(N) бит информации. Ну а нет - значит нет. 4-хмерный - красится.

[amarao-san.livejournal.com]

ну, "нет, значит нет" предполагают и более простые варианты (например, договорится, что "монета с числом равным загаданному будет орлом, ну а если больше одного орла - ну нет, значит нет").

[buddha239.livejournal.com]

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

[amarao-san.livejournal.com]

чееего? И как ты бить собрался? Если "заранее", то всегда можно будет сделать такую подборку, чтобы одно инвертирование не помогло. Если "на месте", то чисто теоретически твоя последовательность закончится на второй монете.

[robel.livejournal.com]

гениально! спасибо!

[buddha239.livejournal.com]

Кстати, красить очень просто - сопоставить каждому номеру последовательность битов длины log2(N) и сложить "без переносов" те последовательности, на чьих номерах "орлы".

У меня ностальгия по детству!:) Как все-таки просто решать олимпиадные задачи!:)

[faceted-jacinth.livejournal.com]

Слушайте, я не понял Ваше решение, причём я не один такой даже здесь в комментах! =)

[haraz-bey.livejournal.com]

А монеты одинакового достоинства?

[avva.livejournal.com]

да

[haraz-bey.livejournal.com]

Гм... Если взять все комбинации, к примеру, из четырёх орлов-решек, их получится 2 в степени 4, то есть 16. Присвоить каждой комбинации число от 1 до 4:
0000 1
0001 2
0010 3
0011 4
0100 1
0101 2
0110 3
0111 4
1000 1
1001 2
1010 3
1011 4
1100 1
1101 2
1110 3
1111 4
В результате ассистент будет должен перевернуть одну монету так, чтобы получилась одна из комбинаций, соответствующих загаданному числу. Вероятно, сработает только для тех N, где для каждого числа от 1 до N будет N комбинаций.

[seann.livejournal.com]

Фокусник дает ассистенту систему кодов: 1 - почесать левое ухо, 2 - кашлянуть и проч. Поэтому значение N ограничено их способностью запоминать коды и их комбинации.

[dimrub.livejournal.com]

Просто, как идея. Пусть будет дано N и k в диапазоне 1..N. При выполнении определенных условий в отношении N в любом N-битном числе можно изменить один бит так, чтобы остаток при делении на N стал равен k. Доказывать надо, видимо, из соображений того, что кол-во разных остатков равно кол-ву битов, и что (при выполнении этих непонятных условий) флипы разных битов обязательно приводят к разным остаткам. (т.е. что 2^l != 2^m mod N). Если мне не изменяет память, это должно выполняться, если 2 и N - взаимно простые (т.е. N - нечетное).

[buddha239.livejournal.com]

Так не стоит: заранее не известно, как лежат монеты, поэтому результат переворота k-ой меняет остаток или на +2^k, или на -2^k, знаки случайные. Лучше складывать побитово, т.е. без переносов, см. выше.:)

[spamsink]

Увы, контрпример: N = 3, тогда для загаданного 0 нам нужно получить 000 или 011 или 110, что из 101 невозможно.

[dimrub.livejournal.com]

Да, действительно :(

[migmit.vox.com (from livejournal.com)]

Степени двойки.
Пусть a_k - число таких позиций, увидев которые фокусник назовёт число k. Рассмотрим множество пар, где первый элемент - начальная позиция (выложенная зрителем), а второй элемент - конечная позиция (после переворачивания монеты), при условии, что зритель задумал число k. С одной стороны, таких пар не меньше 2^{N, поскольку зритель может выложить любую позицию. С другой - не больше a_kN, поскольку для каждой конечной позиции существует не более N начальных. Отсюда a_k≥2N/N, и, так как a_k - целое число, оно не меньше [2N/N], где квадратные скобки обозначают округление вверх до целых. Суммируя по всем k, получаем, что 2N≥N[2N/N], или, иначе говоря, 2N/N≥[2N/N]. Следовательно, 2N делится на N. Следовательно, N - степень двойки.
Если же N=2k, то алгоритм действий ассистента таков: ему нужно, чтобы для любого i от 0 до k-1 выполнялось следующее условие: число монет, лежащих орлом вверх, номера которых в двоичном представлении имеют i-ю цифру, равную 1, должно быть нечётным тогда и только тогда, когда i-я цифра в двоичном представлении загаданного числа равна 1. Это правило даёт ему i-ю цифру в номере той монеты, которую следует перевернуть.}

[avva.livejournal.com]

Ага.

[qaraabayna.livejournal.com]

Другой способ объяснить последний абзац:

Каждая монета входит в k групп монет, размера 1,2,...,2k-1. Эти k типов групп могут быть использованы для кодировки битов загаданного числа. Очевидно, что переворачивая одну монету, мы устанавливаем желаемую четность орлов во всех типах групп.

[qaraabayna.livejournal.com]

2^k-1

Re: офф: Gmail bug

[avva.livejournal.com]

Спасибо, я передам.