задачка

[avva]

Возьмем предыдущую задачку, про монеты и фокусника (там в комментариях есть и решение, если интересно) и изменим ее условие. Разрешим ассистенту не переворачивать ни одной монеты, если ему хочется; все остальное - как раньше. Тот же вопрос: для каких N возможно устроить такой трюк?

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

(я не знаю правильного ответа, пока почти и не думал над ней)

Comments

[spamsink]

Довольно очевидно, что в оригинальном решении монета с номером 0 была "пустышкой", чтобы ее можно было перевернуть, когда на самом деле ничего переворачивать не нужно. Поэтому в данном случае, если у нас N=2^k-1, то мы нумеруем монеты начиная не с нуля, а с 1, избегая "пустышки", и решение сводится к предыдущему.

[avva.livejournal.com]

Ага. А для других N?

[spamsink]

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

[avva.livejournal.com]

Кажется, все верно, да.

[avva.livejournal.com]

Хотя нет. Добавив пустышку, мы получаем не решение для N+1, а решение для N+1 монет, в котором разрешено загадывать числа только от 1 до N, а не от 1 до N+1.

[spamsink]

Почему? Я так понимаю, что количество монет всегда соответствует диапазону чисел, которые можно загадывать, иначе что за интерес? "Вот тебе 10 монет, но можно загадывать числа только от 1 до 9"?

[avva.livejournal.com]

Ну да, соответствует. Ты предлагаешь следующий аргумент: предположим, есть решение для N монет (позволяющее загадывать от 1 до N). Мы утверждаем, что есть решение для N+1 монет (позволяющее загадывать от 1 до N+1), с переворачиванием всегда. Оно работает следующим образом. Одну монету называем пустышкой, с остальными работаем так же, как в данном решении для N, только когда в данном решении помощник ничего не делает, мы переворачиваем пустышку. Фокусник отгадывает число по всем остальным монетам, не глядя на пустышку.

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

[spamsink]

Да, пожалуй. Меня сбило то, что я все еще помнил, как получилось решение для N-1.

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

[avva.livejournal.com]

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

[spamsink]

Для других не получится, потому что может не найтись бита для XOR.

[avva.livejournal.com]

Не получится с решением, основанным на XOR, но кто сказал, что это единственное решение?

[spamsink]

Так теперь рассуждение о пустышке становится прозрачным: пусть у нас есть Хаммингово решение, тогда, добавляя пустышку, мы позволяем ее загадывать путем приведения конфигурации к коду без ошибок (или переворотом пустышки, если он уже был без ошибок).

Вот так строго

[spamsink]

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

Re: Вот так строго

[avva.livejournal.com]

Нет; если оставшимся действием было перевернуть какую-то из первых N монет, то у тебя нет свободы использовать его теперь для кодирования числа N+1: ведь та комбинация, к которой оно приводит, вполне может оказаться зарезервированной для другого ответа в другой ситуации (т.к. в решении для N из исходной комбинации к этой никогда не шли).

Re: Вот так строго

[spamsink]

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

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

Re: Вот так строго

[avva.livejournal.com]

Это то, что я имею в виду.

У тебя есть решение для N, которое ты пытаешься приспособить для N+1. В имеющемся решении каждая комбинация приписана к числу от 1 до N, либо не приписана ни к чему.

Возьмем некую комбинацию C; из N+1 возможных действий она использует только N для перехода по N числам. Комбинации из N+1 монет, соответствующие ей - C0 и C1. Пусть то действие, которое C не использует - перевернуть монету номер 5, и это приводит к комбинации C'. Ты предлагаешь теперь использовать это действие для кодирования числа N+1, когда мы видим комбинации C0 или C1. Значит, тебе придется приписать как C'0, так и C'1, к N+1. Но что если исходное решение для комбинации C' использовало пустое действие для отгадывания, скажем, числа 10? Тогда ты предлагаешь вместо этого переворачивать монету номер N+1; это означает, что C'0->C'1 и C'1->C'0, но ни одна из этих комбинаций не кодирует 10, они обе кодируют N+1...

Как ни погляди, для редукции с "пустышкой" у тебя не хватает комбинаций.



; но комбинация C', к которой оно приводит, уже, возможно, кодирует какое-то число от 1 до N. Правда, без новой монеты (номер N+1); так что ты можешь выбрать оба варианта

Re: Вот так строго

[spamsink]

Пусть то действие, которое C не использует - перевернуть монету номер 5, и это приводит к комбинации C'.... Но что если исходное решение для комбинации C' использовало пустое действие для отгадывания, скажем, числа 10?

Это значит всего лишь, что закодировать число 10 при комбинации C можно двумя способами - тем, который уже был учтен в первых N, и тем, который приводит к C'. Ну так разрешить эту неоднозначность просто: число 10 будет означать лексикографически меньшая из двух, а другая - N+1.

Re: Вот так строго

[avva.livejournal.com]

Если из C можно было перейти в 10, как переворачивая монету 5, так и переворачивая монету 6, приходя в C' и C'' соответственно, это все равно не дает тебе свободы назначить N+1 ни для C'0,C'1, ни для C''0, C''1. Ведь может быть, что и для C', и для C'' единственным переходом в 10 было пустое действие.

Re: Вот так строго

[spamsink]

Ведь может быть, что и для C', и для C'' единственным переходом в 10 было пустое действие.

Значит, для них было какое-то значение (не обязательно одинаковое), для которых было возможно два действия. Ну так отберем у него одно для обозначения 10, и т.п. пока не дойдем до неиспользованной конфигурации.

Re: Вот так строго

[avva.livejournal.com]

Ну, это уже не серьезное предложение, а hand-waving. Их значения тоже кому-то могли быть нужны итд. Нет никакой гарантии, что все это сходится к чему-то полезному.

Re: Вот так строго

[spamsink]

По построению, т.к. мы "занимаем" или переназначаем неиспользованные/избыточные конфигурации, двигаясь лексикографически вверх, оно сойдется.

Re: Вот так строго

[avva.livejournal.com]

Нет возможности двигаться лексикографически вверх - лексикографический выбор возможен только между двумя дупликатами внутри одной комбинации, а то, как к этим двум относятся два дупликата другой конфигурации, не известно. В частности, могут быть циклы. И это еще не учитывая другой возможности несостыковки: когда C'0, C'1 заняты не потому, что у C' есть пустое действие на другое число, а потому, что у какой-то D есть действие на третье число, ведущее в C'. Поэтому, занимая C'0, C'1 под N+1, потенциально надо переназначать выборы в куче комбинаций одновременно, и никто не гарантирует отсутствие конфликтов между ними.

Re: Вот так строго

[spamsink]

Так мы сначала перечислим все дупликаты, а потом начнем двигаться с наименьшего.

когда C'0, C'1 заняты не потому, что у C' есть пустое действие на другое число, а потому, что у какой-то D есть действие на третье число, ведущее в C'.

Как нетрудно видеть, это значит, что C'0, C'1 заняты потому, что у C' есть пустое действие на это третье число.

Re: Вот так строго

[avva.livejournal.com]

я устал :) строго доказательства редукции никак не вижу.

Re: Вот так строго

[spamsink]

Странно, что на первую задачу набросились многие, а здесь нам никто не помогает.

Re: Вот так строго

[buddha239.livejournal.com]

Дык, сложно!:) И не факт, что решится.:)

А эксперимент что дает?:)

[buddha239.livejournal.com]

Кстати, я за то и не люблю комбинаторику, что фиг угадаешь - какие задачи легко решаются, а какие - нет.:) А если интересен ответ - советую запостить на ru_math - авось, профессиональные комбинаторы не поленятся вынести вердикт.:)