?

Log in

No account? Create an account
задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [дек. 27, 2007|06:59 pm]
Anatoly Vorobey
Возьмем предыдущую задачку, про монеты и фокусника (там в комментариях есть и решение, если интересно) и изменим ее условие. Разрешим ассистенту не переворачивать ни одной монеты, если ему хочется; все остальное - как раньше. Тот же вопрос: для каких N возможно устроить такой трюк?

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

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

Comments:
[User Picture]From: spamsink
2007-12-27 05:15 pm
Довольно очевидно, что в оригинальном решении монета с номером 0 была "пустышкой", чтобы ее можно было перевернуть, когда на самом деле ничего переворачивать не нужно. Поэтому в данном случае, если у нас N=2k-1, то мы нумеруем монеты начиная не с нуля, а с 1, избегая "пустышки", и решение сводится к предыдущему.
(Ответить) (Thread)
[User Picture]From: avva
2007-12-27 05:25 pm
Ага. А для других N?
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-27 05:38 pm
Других N нет, потому что если бы они были, отличные от 2k-1, то добавив пустышку, мы получили бы решение оригинальной задачи для N отличного от 2k, что, как там было доказано, невозможно.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-12-27 05:50 pm
Кажется, все верно, да.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-12-27 05:57 pm
Хотя нет. Добавив пустышку, мы получаем не решение для N+1, а решение для N+1 монет, в котором разрешено загадывать числа только от 1 до N, а не от 1 до N+1.
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-27 06:23 pm
Почему? Я так понимаю, что количество монет всегда соответствует диапазону чисел, которые можно загадывать, иначе что за интерес? "Вот тебе 10 монет, но можно загадывать числа только от 1 до 9"?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-12-27 06:30 pm
Ну да, соответствует. Ты предлагаешь следующий аргумент: предположим, есть решение для N монет (позволяющее загадывать от 1 до N). Мы утверждаем, что есть решение для N+1 монет (позволяющее загадывать от 1 до N+1), с переворачиванием всегда. Оно работает следующим образом. Одну монету называем пустышкой, с остальными работаем так же, как в данном решении для N, только когда в данном решении помощник ничего не делает, мы переворачиваем пустышку. Фокусник отгадывает число по всем остальным монетам, не глядя на пустышку.

Так я понял твой аргумент. Но он не работает потому, что имеющееся решение для 1..N не получается использовать, когда я загадываю число N+1.
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-27 06:57 pm
Да, пожалуй. Меня сбило то, что я все еще помнил, как получилось решение для N-1.

В таком случае такой аргумент: решение должно быть возможно для N равных длинам кодов Хамминга: если последовательность уже представляет собой код с ошибкой в бите, равном задуманному числу, то ничего переворачивать не надо. Если она представляет код без ошибки, то нужно внести ошибку в бите с задуманным номером, а если с ошибкой в другом бите, то нужно внести еще одну ошибку в бит с номером, равным XOR от задуманного и от места уже имеющейся ошибки. Но длины кодов Хамминга как раз и есть степень двойки минус один.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-12-27 07:09 pm
Но это доказывает, можно для степень двойки минус один, что мы и так знаем (в эту сторону твой аргумент работает). Не доказывает, что нельзя для других.
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-27 07:53 pm
Для других не получится, потому что может не найтись бита для XOR.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-12-27 07:58 pm
Не получится с решением, основанным на XOR, но кто сказал, что это единственное решение?
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-27 08:24 pm
Так теперь рассуждение о пустышке становится прозрачным: пусть у нас есть Хаммингово решение, тогда, добавляя пустышку, мы позволяем ее загадывать путем приведения конфигурации к коду без ошибок (или переворотом пустышки, если он уже был без ошибок).
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-27 11:13 pm

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

Пусть у нас есть решение этой задачи для N отличного от степени двойки минус 1. Для любой комбинации существует N+1 разное действие (перевернуть одну из N монет или не переворачивать не одной), из которых какие-то N кодируют N задуманных чисел. Тогда оставшееся действие будет кодировать пустышку, а если это действие на самом деле было бездействием, то перевернем пустышку.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-12-27 11:24 pm

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

Нет; если оставшимся действием было перевернуть какую-то из первых N монет, то у тебя нет свободы использовать его теперь для кодирования числа N+1: ведь та комбинация, к которой оно приводит, вполне может оказаться зарезервированной для другого ответа в другой ситуации (т.к. в решении для N из исходной комбинации к этой никогда не шли).
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-27 11:37 pm

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

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

Пардон, у нас простой фокусник, а не телепат. Комбинация может быть зарезервирована только для одного ответа, потому что фокусник видит только результат.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-12-27 11:49 pm

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

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

У тебя есть решение для 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); так что ты можешь выбрать оба варианта
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-27 11:59 pm

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

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

Это значит всего лишь, что закодировать число 10 при комбинации C можно двумя способами - тем, который уже был учтен в первых N, и тем, который приводит к C'. Ну так разрешить эту неоднозначность просто: число 10 будет означать лексикографически меньшая из двух, а другая - N+1.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-12-28 12:07 am

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

Если из C можно было перейти в 10, как переворачивая монету 5, так и переворачивая монету 6, приходя в C' и C'' соответственно, это все равно не дает тебе свободы назначить N+1 ни для C'0,C'1, ни для C''0, C''1. Ведь может быть, что и для C', и для C'' единственным переходом в 10 было пустое действие.
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-28 12:13 am

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

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

Значит, для них было какое-то значение (не обязательно одинаковое), для которых было возможно два действия. Ну так отберем у него одно для обозначения 10, и т.п. пока не дойдем до неиспользованной конфигурации.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-12-28 12:20 am

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

Ну, это уже не серьезное предложение, а hand-waving. Их значения тоже кому-то могли быть нужны итд. Нет никакой гарантии, что все это сходится к чему-то полезному.
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-28 12:38 am

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

По построению, т.к. мы "занимаем" или переназначаем неиспользованные/избыточные конфигурации, двигаясь лексикографически вверх, оно сойдется.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-12-28 12:45 am

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

Нет возможности двигаться лексикографически вверх - лексикографический выбор возможен только между двумя дупликатами внутри одной комбинации, а то, как к этим двум относятся два дупликата другой конфигурации, не известно. В частности, могут быть циклы. И это еще не учитывая другой возможности несостыковки: когда C'0, C'1 заняты не потому, что у C' есть пустое действие на другое число, а потому, что у какой-то D есть действие на третье число, ведущее в C'. Поэтому, занимая C'0, C'1 под N+1, потенциально надо переназначать выборы в куче комбинаций одновременно, и никто не гарантирует отсутствие конфликтов между ними.
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-28 01:27 am

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

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

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

Как нетрудно видеть, это значит, что C'0, C'1 заняты потому, что у C' есть пустое действие на это третье число.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2007-12-28 08:55 am

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

я устал :) строго доказательства редукции никак не вижу.
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2007-12-28 08:58 am

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

Странно, что на первую задачу набросились многие, а здесь нам никто не помогает.
(Ответить) (Parent) (Thread)
[User Picture]From: buddha239
2007-12-28 09:38 am

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

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

А эксперимент что дает?:)
(Ответить) (Parent) (Thread)
[User Picture]From: buddha239
2007-12-31 12:39 am
Кстати, я за то и не люблю комбинаторику, что фиг угадаешь - какие задачи легко решаются, а какие - нет.:) А если интересен ответ - советую запостить на ru_math - авось, профессиональные комбинаторы не поленятся вынести вердикт.:)
(Ответить) (Thread)