100 собак в хорошие руки

Post reply

Tavern | Trade table

Pages: first | prev | << | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | next | last
Subscribe to our groups:
Go to forum:
Author Subject
Sir AmberSoler
+ + + + + + +
AmberSoler

HoMM III: Duke (10)
Messages: 1618
From: Russian Federation

Quote link Added: 2.10.2006 12:41
Сэр hister, 2.10.2006 08:53
Прошу каждому по своему алгоритму построить такую полную таблицу, а также посчитать общую сумму ходов по всем 27 вариантам...

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

1 GGG - 1       10 BGG - 2       19 SGG - 3
2 GGB - 4       11 BGB - 4       20 SGB - 4
3 GGS - 5       12 BGS - 5        21 SGS - 5
4 GBG - 3       13 BBG - 3       22 SBG - 3
5 GBB - 4       14 BBB - 4       23 SBB - 4
6 GBS - 5       15 BBS - 5        24 SBS - 5
7 GSG - 4       16 BSG - 4       25 SSG - 4
8 GSB - 4*     17 BSB - 4        26 SSB - 4
9 GSS - 5       18 BSS - 5         27 SSS - 5

* Вы в своем примере предложили решение из пяти ходов. На самом деле - четыре :)

1 ход - 1 вариант
2 хода - 1 вариант
3 хода - 4 варианта
4 хода - 12 вариантов
5 ходов - 9 вариантов

Общее количество ходов - 108

Вопрос автору задачи.

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

"1. Придумать [наилучший] алгоритм угадывания, так чтобы за минимум попыток гарантировано разгадать."

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

Мой ответ - минимум 5 попыток.

А потому, если решение Сэра St-RauS допускает менее 5-ти попыток для гарантированного определения любой комбинации - тогда вопрос давно снят. Если столько же - тогда определяющим является время предоставления решения...
AmberSoler
Special status:
Author of the best multiplayer L map for HMM3 (2006)Specialist of offline tournament "HeroesLands3" in 2011
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 2.10.2006 15:54
Народ просит - значит надо.
0biglol Идиотические случаи, когда сразу 3 совпало яя далее не упоминаю.
1) Будем считать, что называние отввета - не ход. Мне так удбнее.
2) В принятой терминологии ответ 4. То есть, в вашей - 5
3) п.1. Стратегия.
Договоримся, что это не карточки, а числа(не RGB, а 123). Рассмотрим чудесную тройку: 123, 231, 312. СУММА количеств совпаданий с задуманным числом - 3(по 1 в каждом разряде). Тогда, спросив про 2 числа, мы получим и про третье. Итак, мы знаем, в скольких разрядах числа 123 231 312 совпадают с исходным. 3 случая:
1. Одно из них(они циклические, поэтому будем считать, что это число 123) не имеет ни одного общего разряда с х(далее так будем обозначать задуманное число). Это не содержательно. Пока что мы потратили 2 хода и за 2 оставшихся я определю х. Рассмотрим число 122. 12 в первых двух разрядах заведемо неправильны. Тогда ясно, правильно ли число 2 в 3-ем разряде. Учитывая то, что мы знаем, что 3 в 3-ем разряде неправильно, мы узнаем правильное число в 3-ем разряде. Также делаем со 2-ым разрядом. Теперь вспоминаем что мы знаем, в скольких разрядах числа 123 231 312 совпадают с исходным. 2 из них мы просто нашли. Оттуда выявляется 3-ий: пусть мы нашли 2 последних разряда. Пучсть это разряды 13( то естть, число - *13). * - не единица. Мы уже знаем, сколько совпадений с х есть у чисел 231 и 312. Про 2 последних разряда(совпадают или нет) знаем. Значит, знаем и про первый.
2. Одно из них(опять же, пусть 123) имеет 2 общих разряда с х.
Если где-то совпало в двух разрядах, то где-то не совпало вообще, а далее см. п. 3.1
3. Самое содержательное. 1-1-1 совпадений в числах 123 231 312.
рассмотрим число 111. Если оно не совпадает ни в одном разряде с х, то есть в х нету единиц, то, нарисовав табличку из чисел 123 231 312 и то, что мы знаем, вот что получим:
123 - 1совп. - не в 1-ом разряде
231 - 1совп. - не в 3-ем разряде
312 - 1совп. - не во 2-ом разряде
Значит, это мб числа 222 или 333(полный перебор чисел из 2 и 3 убивает остальные случаи). Тогда рассмотрим число 222. Если совпало - отлично, если не совпало - значит х=333.
Аналогично поступим со случаем, когда в х 2 единицы:
Рассмотрим число 222. Тогда либо в 222 ливо в 333 1 совпадение с х. Далее см выше(последняя операция там такая же, что мы сделали здесь вначале).
Значит, в х одна единица.
Теперь, БЕЗО ВСЯКИХ ОПЕРАЦИЙ, мы усановим, что в числе одна 2 и аналогично одна 3. ПОСМОТРИМ на число 222. Тоже, нарисуем табличку такую же, как там и поймём это сами
123 - пусть в этом числе совпадение в 1(то, что единица одна см выше)
231 - тогда 2-ой разряд - 3.
312 - ну, а тогда 3 разряд - 2.
Значит, в числе одна 1 одна 2 и одна 3.
Какие это мб числа?
123 132 213 231 312 321. Числа 123 231 312 мы уже проверили. Осталось 132 321 и 213. Теперь надо рассмотреть(операцию сделать) число 331. Очевидно, что в одном из чисел 132 321 и 213 все разряды совпадают - в 2 других - ни одного. Число 331 - это такое число, что совпадает с 132 в одном разряде, с 321 - в двух, с 213 - ни в одном. Значит, если оно совпадает с х в одном разряде, то х=132 и тп.
4) Оценка
Я уже её сделал, только щас у меня комп забирают - подождите неск. часов.
5) табличка
-------//---------
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir AmberSoler
+ + + + + + +
AmberSoler

HoMM III: Duke (10)
Messages: 1618
From: Russian Federation

Quote link Added: 2.10.2006 16:16
Сэр St-RauS, 2.10.2006 16:54
1) Будем считать, что называние отввета - не ход. Мне так удбнее.
2) В принятой терминологии ответ 4. То есть, в вашей - 5

Ну уморил!  biglol

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

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

С математикой у Вас все нормально, хотя и объясняете слишком сложно и сумбурно. А вот только логика оценки своего решения немного странная... Итого, если я правильно Вас понимаю - те же пять ходов...
AmberSoler
Special status:
Author of the best multiplayer L map for HMM3 (2006)Specialist of offline tournament "HeroesLands3" in 2011
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 2.10.2006 16:37
Сэр AmberSoler, 2.10.2006 17:16
Сэр St-RauS, 2.10.2006 16:54
1) Будем считать, что называние отввета - не ход. Мне так удбнее.
2) В принятой терминологии ответ 4. То есть, в вашей - 5

Ну уморил!  biglol

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

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

С математикой у Вас все нормально, хотя и объясняете слишком сложно и сумбурно. А вот только логика оценки своего решения немного странная... Итого, если я правильно Вас понимаю - те же пять ходов...

Вы правильно понимаенте. Я щас сделаю табличку...
111 - 3
112 - 5
113 - 4
121 - 3
122 - 3
123 - 1
131 - 5
132 - 5
133 - 5
211 - 5
212 - 5
213 - 5
221 - 5
222 - 4
223 - 5
231 - 3
232 - 3
233 - 4
311 - 3
312 - 2
313 - 4
321 - 5
322 - 5
323 - 5
331 - 5
332 - 5
333 - 5

Если я правильно посчитал, то 27*4+16-23, ТО ЕСТЬ, 101. Я живой, а значит, могу ошибаться. Перепроверьте.
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir AmberSoler
+ + + + + + +
AmberSoler

HoMM III: Duke (10)
Messages: 1618
From: Russian Federation

Quote link Added: 2.10.2006 17:10
Сэр St-RauS, 2.10.2006 17:37
Если я правильно посчитал, то 27*4+16-23, ТО ЕСТЬ, 101. Я живой, а значит, могу ошибаться. Перепроверьте.

Не совсем понимаю что проверить? Что такое "27*4+16-23"?
AmberSoler
Special status:
Author of the best multiplayer L map for HMM3 (2006)Specialist of offline tournament "HeroesLands3" in 2011
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 2.10.2006 17:12
Сэр AmberSoler, 2.10.2006 18:10
Сэр St-RauS, 2.10.2006 17:37
Если я правильно посчитал, то 27*4+16-23, ТО ЕСТЬ, 101. Я живой, а значит, могу ошибаться. Перепроверьте.

Не совсем понимаю что проверить? Что такое "27*4+16-23"?

Не, правильно ли таблицу написал
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir AmberSoler
+ + + + + + +
AmberSoler

HoMM III: Duke (10)
Messages: 1618
From: Russian Federation

Quote link Added: 2.10.2006 17:17
Сэр St-RauS, 2.10.2006 18:12
Не, правильно ли таблицу написал

Давайте начнем с малого... Сначала подсчитаем сумму.
У меня Ваша сумма вышла 112. А проверять Ваш алгоритм я не стану. Мне мой больше нравится  biglol
AmberSoler
Special status:
Author of the best multiplayer L map for HMM3 (2006)Specialist of offline tournament "HeroesLands3" in 2011
Profile Hero history PM E-mail
Go to reply form Go to top
Sir hister

HoMM V: Landless
HoMM IV: Landless
HoMM III: Knight (2)
HoMM II: Landless
Messages: 173
From: Russian Federation

Quote link Added: 2.10.2006 17:24
Сэр St-RauS, 2.10.2006 17:37
Перепроверьте.

((^
Нехило так перепроверять - если за сэром AmberSoler это запросто, то за Вами тяжеловато...
Так, по порядку:
1) Пока только 2 версии алгоритма с макс. длиной в 5 попыток. Первая прозрачна, элементарно программируется и удобна в "ручном" использовании.
2) Вторая версия тоже работоспособная (проверил), чуть более сложная для понимания. Мне на самом деле понравилась, хоть и до жути неудобная. Числа не проверил пока, но охотно верю, что алгоритм статистически чуть выигрывает (много играю в похожую игру - попробовал оба метода - возникло ощущение статистического выигрыша). Кстати, этот подсчет чисел, против которого высказался сэр AmberSoler, я все же позволяю считать квалифицирующим. Положим, Вы играете в некоторую модификацию - сами загадываете, со скольких попыток отгадаете, причем при оправданном риске (заказав 3 попытки и выиграв) получаете весомое вознаграждение. Для такой модификации совершенно однозначно более интересным будет алгоритм, который статистически дает чаще более короткий путь (: Хотя это все, конечно, уже сторонние рассуждения...

Резюмируя, обоим пока что по 100 собак - это не уравнивание, а награда за два близких по результативности, но принципиально различных гарантированных алгоритма. Почему только по 100? Потому что пока никто из вас не обосновал, что его алгоритм наилучший (т.е. что 5 - минимум для такой игры). Это, видимо, не слишком просто.

Кстати, информация к размышлению персонально для Вас, сэр AmberSoler: 108/27=4 (:
hister
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 2.10.2006 17:25
А
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir hister

HoMM V: Landless
HoMM IV: Landless
HoMM III: Knight (2)
HoMM II: Landless
Messages: 173
From: Russian Federation

Quote link Added: 2.10.2006 17:31
Да, действительно, посчитал, у сэра St-RauS'а по таблице и впрямь 112 выходит - еще 50 собак из моего кармана перекочевывают сэру AmberSoler: при таком раскладе совершенно очевидно, что пока что его алгоритм все же превосходит предложенный сэром St-RauS'ом...
hister
Profile Hero history PM E-mail
Go to reply form Go to top
Sir AmberSoler
+ + + + + + +
AmberSoler

HoMM III: Duke (10)
Messages: 1618
From: Russian Federation

Quote link Added: 2.10.2006 17:42
Сэр hister, 2.10.2006 18:24
...много играю в похожую игру - попробовал оба метода - возникло ощущение статистического выигрыша...

Что-то у меня такое ощущение, что уважаемый Сэр hister решил снять Джек-Пот в солидном заведении... Дело за малым - отыскать выигрышную стратегию... biglol

Если не секрет - "похожая игра" это что именно?

Сэр hister, 2.10.2006 18:24
Кстати, информация к размышлению персонально для Вас, сэр AmberSoler: 108/27=4 (:

Мне кажется, проще доказать, что 5 - это минимум для гарантированного решения, чем искать более короткий путь. Только, надеюсь, сможем обойтись без Лоренца... :)
AmberSoler
Special status:
Author of the best multiplayer L map for HMM3 (2006)Specialist of offline tournament "HeroesLands3" in 2011
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 2.10.2006 17:42
Есть долее полный ответ на изначальный вопрос - минимальность. Заметим, что разряды живут своей жизнью, то есть, если рфь назвали число 123 с самого начала, переобозначим его в 111.
Итак, нам назвали число 111. Скажем, что в х нет единиц, то есть, число 111 не совпадает с х ни в одном разряде. Аналогично, второе названное число - 222 122 или 112(разряды можно поменять местами).
1сл. 222
Скажем, что 2 совпадения. Остались числа 322 232 223. За 1 ход последовательность не угадаешь.
2сл. 122
Скажем, что 1 совп. Ост чичла - 332 323 233. -----//-----
3сл. 112
нет совп. ост числа 223 233 333 323. ------//------
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 2.10.2006 17:44
Сэр hister, 2.10.2006 18:31
Да, действительно, посчитал, у сэра St-RauS'а по таблице и впрямь 112 выходит - еще 50 собак из моего кармана перекочевывают сэру AmberSoler: при таком раскладе совершенно очевидно, что пока что его алгоритм все же превосходит предложенный сэром St-RauS'ом...

Чж вы призы так быстро отдаете? Я только успел написать ПОЛНЫЙ ответ на начальный вопрос.... Обидно даже как-то.
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 2.10.2006 22:06
Сэр hister, 1.10.2006 16:48
Предлагаю задачку. Не слишком сложную, в какой-то мере связанную с математикой.
Итак, существует старая игра. Ведущий берет 3 кружочка из цветной бумаги и кладет их "рубашкой вверх", т.е. так, что игрок не видит, какого цвета какой кружок. Цвета выбираются среди трех, обозначим их G, B и S.
При выкладке важен порядок, т.е. GBS не равно BGS. Также возможно, что несколько кружков будут одного цвета, например BBB или SGG...
Игрок высказывает гипотезу о том, к каком порядке какие цвета лежат - ведущий озвучивает количество совпавших. Приведу пример:
загадано GBS
игрок, 1 попытка: GGG - ведущий: 1 правильно
игрок, 2 попытка: BBB - ведущий: 1 правильно
игрок, 3 попытка: BGS - ведущий: 1 правильно
игрок, 4 попытка: GBS - ведущий: 3 правильно, угадано
Итак, задача:
1. Придумать наилучший алгоритм угадывания, так чтобы за минимум попыток гарантировано разгадать.
2. Определить, сколько минимум попыток надо, чтобы из любой ситуации угадать.
3. Дополнительно - оценить/посчитать шансы игрока в зависимости от количества данных ему попыток (скажем, на игру наложено условие - 3 попытки, каковы тогда его шансы при использовании лучшей стратегии из п.1?)
Первому правильно и подробно ответившему плачу 200 собак.

Краткий обзор:
1. См. пост 2.10.2006 16:54
2. См. пост перед этим
3. Прстите, забыл.
Если нас попросили сразу угадать, шансы 1/27
табличка:
К-во попыток      шансы
2                        2/27
3                        1/6
4                        1/2
5 и больше         1


Итак, сделаны все пункты. Пожалуйста, вопросы.
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir hister

HoMM V: Landless
HoMM IV: Landless
HoMM III: Knight (2)
HoMM II: Landless
Messages: 173
From: Russian Federation

Quote link Added: 3.10.2006 15:19
Уважаемый сэр St-RauS, я, конечно, понимаю сложность Вашего финансового положения, но поймите - исчерпывающего ответа Вы не дали. Вспомните:
1. Придумать наилучший алгоритм угадывания, так чтобы за минимум попыток гарантировано разгадать.
2. Определить, сколько минимум попыток надо, чтобы из любой ситуации угадать.


1. Я не увидел, чтобы Вы где-то доказали, что Ваш алгоритм - наилучший. Напротив, пока что я вижу, что алгоритм сэра AmberSoler (те же 5 попыток) проще и то самое общее число попыток по всем вариантам у него ниже (108 против 112).
2. Вы НЕ определили минимум попыток. Согласитесь, число 5 нужно как минимум обосновать (: Собаки в размере 200 штук предназначались за полный и правильный ответ, и вообще говоря, всякий сторонний читатель этой темы скорее отдал бы их за решение сэра AmberSoler, а не Ваше. Я ценю оригинальность Вашего подхода, продуманную логику, и плачу Вам 100 собак, притом почтительно отзываясь о Вас и этом отнюдь неполном решении. Всего я уже выплатил 250 аробов, что и так превышает призовой фонд, заявленный для задачи. Тем не менее у Вас и сэра AmberSoler по-прежнему сохраняется возможность проявить свои способности и подзаработать, обосновав, например, то, что 5 попыток - это минимум для гарантированного решения. Если кто-то предложит алгоритм эффективней уже предложенных - он также может рассчитывать, что его работа будет оценена по достоинству...

2 сэр AmberSoler: Объяснять конкретику полюбившейся мне подобной игры долго - скажу просто, что там все основывается на угадываниях из множества вариантов с множеством заказов. Т.е., если ближе к нашему примеру, то Вы, положим, могли бы сказать, сколько карточек хотите, из скольких цветов выборка, со скольких попыток Вы обязуетесь это угадать и т.п. - чем сложнее ситуация, тем интересней приз (:
hister
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 3.10.2006 15:38
Сэр hister, 3.10.2006 16:19
Уважаемый сэр St-RauS, я, конечно, понимаю сложность Вашего финансового положения, но поймите - исчерпывающего ответа Вы не дали. Вспомните:
1. Придумать наилучший алгоритм угадывания, так чтобы за минимум попыток гарантировано разгадать.
2. Определить, сколько минимум попыток надо, чтобы из любой ситуации угадать.


1. Я не увидел, чтобы Вы где-то доказали, что Ваш алгоритм - наилучший. Напротив, пока что я вижу, что алгоритм сэра AmberSoler (те же 5 попыток) проще и то самое общее число попыток по всем вариантам у него ниже (108 против 112).
2. Вы НЕ определили минимум попыток. Согласитесь, число 5 нужно как минимум обосновать (: Собаки в размере 200 штук предназначались за полный и правильный ответ, и вообще говоря, всякий сторонний читатель этой темы скорее отдал бы их за решение сэра AmberSoler, а не Ваше. Я ценю оригинальность Вашего подхода, продуманную логику, и плачу Вам 100 собак, притом почтительно отзываясь о Вас и этом отнюдь неполном решении. Всего я уже выплатил 250 аробов, что и так превышает призовой фонд, заявленный для задачи. Тем не менее у Вас и сэра AmberSoler по-прежнему сохраняется возможность проявить свои способности и подзаработать, обосновав, например, то, что 5 попыток - это минимум для гарантированного решения. Если кто-то предложит алгоритм эффективней уже предложенных - он также может рассчитывать, что его работа будет оценена по достоинству...

2 сэр AmberSoler: Объяснять конкретику полюбившейся мне подобной игры долго - скажу просто, что там все основывается на угадываниях из множества вариантов с множеством заказов. Т.е., если ближе к нашему примеру, то Вы, положим, могли бы сказать, сколько карточек хотите, из скольких цветов выборка, со скольких попыток Вы обязуетесь это угадать и т.п. - чем сложнее ситуация, тем интересней приз (:

Читайте лучше:
Есть долее полный ответ на изначальный вопрос - минимальность. Заметим, что разряды живут своей жизнью, то есть, если рфь назвали число 123 с самого начала, переобозначим его в 111.
Итак, нам назвали число 111. Скажем, что в х нет единиц, то есть, число 111 не совпадает с х ни в одном разряде. Аналогично, второе названное число - 222 122 или 112(разряды можно поменять местами).
1сл. 222
Скажем, что 2 совпадения. Остались числа 322 232 223. За 1 ход последовательность не угадаешь.
2сл. 122
Скажем, что 1 совп. Ост чичла - 332 323 233. -----//-----
3сл. 112
нет совп. ост числа 223 233 333 323. ------//------
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir AmberSoler
+ + + + + + +
AmberSoler

HoMM III: Duke (10)
Messages: 1618
From: Russian Federation

Quote link Added: 3.10.2006 16:50
Сэр St-RauS, 3.10.2006 16:38
Читайте лучше:
Есть долее... если рфь назвали ... Ост чичла

Давайте сначала найдем словарь вашего языка... После давайте откажемся от цифр и любых аббревиатур вида SGB. Объясните ваши идеи на словах нормальным человеческим языком без цифр и всевозможных сокращений. Потом заново ответьте на три ниже указанных вопроса:

1. Каково минимальное количество попыток гарантированного вычисления любой комбинации имеет ваше решение?
2. Какова вероятность найти ответ с трех попыток?
3. Что именно Вас не устраивает в том, что сказано постом выше?

И не пишите ничего кроме того, что Вас просят написать. Не начинайте посторонние разговоры не в тему...
AmberSoler
Special status:
Author of the best multiplayer L map for HMM3 (2006)Specialist of offline tournament "HeroesLands3" in 2011
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 3.10.2006 19:44
По личке мне hister сказал, что мы ещё можем отличится, локазав минимальность. Исправляю ляпы и объясняю идею:
Заметим, что разряды живут своей жизнью, то есть, если нам назвали число 123 с самого начала, переобозначим его в 111.
Итак, нам назвали число 111. Скажем, что в х нет единиц, то есть, число 111 не совпадает с х ни в одном разряде. Аналогично, второе названное число - 222 122 или 112(разряды можно поменять местами).
1сл. 222
Скажем, что 2 совпадения. Остались числа 322 232 223. За 1 ход последовательность не угадаешь.
2сл. 122
Скажем, что 1 совп. Ост числа - 332 323 233. -----//-----
3сл. 112
нет совп. ост числа 223 233 333 323. ------//------

Идея: мы уже придумали упрощение: менять цвета на числа. Теперь мы понимаем, что число 1 в первом разряде и 1 во втором разряде - РАЗНЫЕ штуки. Значит, первое число - 111. Ну, а дальше всё1 раскручивается.
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir hister

HoMM V: Landless
HoMM IV: Landless
HoMM III: Knight (2)
HoMM II: Landless
Messages: 173
From: Russian Federation

Quote link Added: 3.10.2006 19:55
Действительно, сэр St-RauS! Право же, не имею против Вас и Вашего подхода никакого предубеждения!! Но по-прежнему пока непонятно. Вообще, само рассуждение мне представляется пока каким-то очень частным и сомнительным.  Просто объясните точнее, как Вы доказываете, что нет способа наверняка угадать число с 4 попыток. Покажите, что Ваш алгоритм превосходит или равнозначен другому предложенному. Мы с радостью Вам поапплодируем, и мои собаки организованной толпой ломанутся прямиком в Вашу анкету (:
hister
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 3.10.2006 20:22
Сэр hister, 3.10.2006 20:55
Действительно, сэр St-RauS! Право же, не имею против Вас и Вашего подхода никакого предубеждения!! Но по-прежнему пока непонятно. Вообще, само рассуждение мне представляется пока каким-то очень частным и сомнительным.  Просто объясните точнее, как Вы доказываете, что нет способа наверняка угадать число с 4 попыток. Покажите, что Ваш алгоритм превосходит или равнозначен другому предложенному. Мы с радостью Вам поапплодируем, и мои собаки организованной толпой ломанутся прямиком в Вашу анкету (:

Про алгоритм "лучше" всё сказано. По критериям таблички мой алгоритм "хуже". Про док-во с радостью повторю. Принцип такой: Разряды друг от друга не зависят. Приведу конкретный пример, может тогда вам станет ясно.
Нам сказали число 123. Для КАЖДОГО разряда введем свои обозначения: Скажем, что в 1-ом разряде единицу обозначаем единицей, во втором разряде ДВОЙКУ обозначаем единицей, а в третьем ТРОЙКУ обозначаем за единицу. Итак, нам назвали число 111. Скажем, что в нем нет ни одного совпадения с задуманным(то есть, в залуманном нет единиц).
Вторым ходом нам назвали следующее: Возможно нам назвали все другие цифры - тогда скажем, что это число 222, возможно нам назвали одну единицу(то есть, 1 в 1-ом разряде, 2 во 2-ом или 3 в 3-ем) и 2 других цифры. Тогда это число можно назвать 122, аналогично выходит случай с 112. Ну, а перебор см. выше. Теперь всё понятно?
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir AmberSoler
+ + + + + + +
AmberSoler

HoMM III: Duke (10)
Messages: 1618
From: Russian Federation

Quote link Added: 3.10.2006 20:49
Сэр St-RauS, 3.10.2006 21:22
...Теперь всё понятно?

Вывод, вывод какой?! Что ИМЕННО вы доказали? Я, например, не понимаю.
Сформулируйте не доказательство, а сам вывод.

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

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

Или на крайний случай:
"В записи трехзначного числа не может встретиться четыре единицы подряд" biglol
AmberSoler
Special status:
Author of the best multiplayer L map for HMM3 (2006)Specialist of offline tournament "HeroesLands3" in 2011
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 3.10.2006 20:56
Сэр St-RauS, 2.10.2006 18:42
Есть долее полный ответ на изначальный вопрос - минимальность. Заметим, что разряды живут своей жизнью, то есть, если нам назвали число 123 с самого начала, переобозначим его в 111.
Итак, нам назвали число 111. Скажем, что в х нет единиц, то есть, число 111 не совпадает с х ни в одном разряде. Аналогично, второе названное число - 222 122 или 112(разряды можно поменять местами).
1сл. 222
Скажем, что 2 совпадения. Остались числа 322 232 223. За 1 ход последовательность не угадаешь.
2сл. 122
Скажем, что 1 совп. Ост числа - 332 323 233. -----//-----
3сл. 112
нет совп. ост числа 223 233 333 323. ------//------


Вот и весь вывод. Меньше, чем за 4 нельзя.
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir AmberSoler
+ + + + + + +
AmberSoler

HoMM III: Duke (10)
Messages: 1618
From: Russian Federation

Quote link Added: 3.10.2006 21:01
Сэр St-RauS, 3.10.2006 21:56
Вот и весь вывод. Меньше, чем за 4 нельзя.

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

Так что это не доказательство. Пока мы с уверенностью можем предположить, что меньше чем за 5 попыток гарантировано угадать нельзя. Потому что ни разу этого не сделали :)
AmberSoler
Special status:
Author of the best multiplayer L map for HMM3 (2006)Specialist of offline tournament "HeroesLands3" in 2011
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 3.10.2006 21:22
Сэр AmberSoler, 3.10.2006 22:01
Сэр St-RauS, 3.10.2006 21:56
Вот и весь вывод. Меньше, чем за 4 нельзя.

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

Так что это не доказательство. Пока мы с уверенностью можем предположить, что меньше чем за 5 попыток гарантировано угадать нельзя. Потому что ни разу этого не сделали :)


Это В ОБЩЕМ СЛУЧАЕ!!!! Просто чило xyz сказанное вначале мы переименовываем в 111.
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir AmberSoler
+ + + + + + +
AmberSoler

HoMM III: Duke (10)
Messages: 1618
From: Russian Federation

Quote link Added: 3.10.2006 21:33
Вы утверждаете, что быстрее, чем за 4 хода решить задачу нельзя. В таком случае, следствием Вашего утверждения является, что ее гарантировано можно решить быстрее, чем за 5 ходов. Докажите.
AmberSoler
Special status:
Author of the best multiplayer L map for HMM3 (2006)Specialist of offline tournament "HeroesLands3" in 2011
Profile Hero history PM E-mail
Go to reply form Go to top
Sir hister

HoMM V: Landless
HoMM IV: Landless
HoMM III: Knight (2)
HoMM II: Landless
Messages: 173
From: Russian Federation

Quote link Added: 3.10.2006 21:44
Не знаю, кому как - мне не понятно, когда 123 переобозначают как 111 - мой старый закостенелый мозг это принимать отказывается, хоть убейте! Кому понятен этот метафизический бред - поднимите руки!!
Короче, сэр St-RauS, попытайтесь все же объяснить свое решение в более или менее приличной терминологии и обозначениях. Желаете заменить 123 на xyz - извольте, принимаем. Желаете обозначить 123 как 111 - позвольте, не принимаем!

PS: Пожелаете 123 обозначить как xxx, yyy, или zzz - тоже не примем (: Поверьте мне, это только вносит путанность в рассуждения, но нисколько не придает им общности. Можете спорить сколько угодно утверждать, что все дураки и не понимают Вас - право же, надоело. Доказательство должно быть понятным. Его должны принять пятиклассники средней школы! Это арифметика банальная: 27 возможных вариантов, после каждого хода это множество резко сужается - покажите мне, что какая-нибудь хитроумная стратегия не позволит мне за 4 хода сузить его до единственного правильного, причем покажите просто и доступно, не выдумывая всякого околонаучного бреда вроде переобозначения 123 тремя единицами - неужели это невозможно? Поверьте мне, даже самые сложные математические принципы часто легко обосновываются едва ли не на пальцах. И всем понятно! И никто не спорит!! Неравенство Коши доказать без формул и выкладок - просто 40 слов сказать!!! И все поймут, и никто возражать не будет - потому что идею ясно показали. А тут вижу только намеки на присутствие какой-то идеи в Вашей голове, и ничего более! Надоело спорить уже!!

PPS: Кстати, то что *меньше чем за 4 нельзя* - это как раз ясно, потому как для любой стратегии (т.е. любых двух первых ходов) можно подобрать такую тройку, чтобы ответы на первые 2 вопроса не давали полной определенности - это перебором выясняется (:
hister
Profile Hero history PM E-mail
Go to reply form Go to top
Sir St-RauS
+
St-RauS

HoMM III: Knight (1)
Messages: 713
From: Russian Federation

Quote link Added: 3.10.2006 22:07
Сэр hister, 3.10.2006 22:44
Не знаю, кому как - мне не понятно, когда 123 переобозначают как 111 - мой старый закостенелый мозг это принимать отказывается, хоть убейте! Кому понятен этот метафизический бред - поднимите руки!!
Короче, сэр St-RauS, попытайтесь все же объяснить свое решение в более или менее приличной терминологии и обозначениях. Желаете заменить 123 на xyz - извольте, принимаем. Желаете обозначить 123 как 111 - позвольте, не принимаем!

PS: Пожелаете 123 обозначить как xxx, yyy, или zzz - тоже не примем (: Поверьте мне, это только вносит путанность в рассуждения, но нисколько не придает им общности. Можете спорить сколько угодно утверждать, что все дураки и не понимают Вас - право же, надоело. Доказательство должно быть понятным. Его должны принять пятиклассники средней школы! Это арифметика банальная: 27 возможных вариантов, после каждого хода это множество резко сужается - покажите мне, что какая-нибудь хитроумная стратегия не позволит мне за 4 хода сузить его до единственного правильного, причем покажите просто и доступно, не выдумывая всякого околонаучного бреда вроде переобозначения 123 тремя единицами - неужели это невозможно? Поверьте мне, даже самые сложные математические принципы часто легко обосновываются едва ли не на пальцах. И всем понятно! И никто не спорит!! Неравенство Коши доказать без формул и выкладок - просто 40 слов сказать!!! И все поймут, и никто возражать не будет - потому что идею ясно показали. А тут вижу только намеки на присутствие какой-то идеи в Вашей голове, и ничего более! Надоело спорить уже!!

PPS: Кстати, то что *меньше чем за 4 нельзя* - это как раз ясно, потому как для любой стратегии (т.е. любых двух первых ходов) можно подобрать такую тройку, чтобы ответы на первые 2 вопроса не давали полной определенности - это перебором выясняется (:

Естественно, меньше, чем за 4.... Ну, не придирайтесь к словам, вы знаете, о чем речь.
Я вижу обозначения 123-----111 вы не понимаете? Не вопрос! Будем оперировать такими понятиями:
x y z - цвета. 1* 2* 3* - обозначение цвета в первом разряде. * - номер разряда. Одна * - первый разряд, две - второй, три - третий.

Пусть нам назвали первое число - xyz. Скажем, что 1*=х, 1**=y, 1***=z. В новых обозначениях, нам назвали число 1*1**1***. То есть, три единицы. Скажем, что совпадений нет.
Пусть второе названное чисо - x'y'z'. 3 случая:
1) x'y'z' совпадает с xyz в 2 разрядах. От перестановки порядка ничего не зависит, поэтому джалее будем считать, что все совпадения в первых разрядах. Тогда скажем, что 2***=z', так как z' не равно z. Тогда это число 1*1**2***.
2) x'y'z' совпадает с xyz в 1 разряде(опять же, считаем, что в первом). Это уже НОВЫЙ случай, поэтому старые обозначения из случая 1 не считаются. Тогда введем такие обозначения:  2**=y' 2***=z'
3) x'y'z' не совпадает c xyz ни в одном разряде. Тогда введем такие обозначения: 2*=x' 2**=y' 2***=z'. В новой записи число выглядит, как 2*2**2***.

Я разобрал эти случаи выше. Вот вам всё чисто и формально.
St-RauS
Special status:
Gray legion
Profile Hero history PM E-mail
Go to reply form Go to top
Sir AmberSoler
+ + + + + + +
AmberSoler

HoMM III: Duke (10)
Messages: 1618
From: Russian Federation

Quote link Added: 3.10.2006 22:07
2 hister.
Сэр, обозначьте один момент: Вы сами имеете доказательство минимальности количества ходов? Т.е. здесь все еще продолжается предложенный Вами проект или мы находимся в свободном полете? Может мы тут пытаемся решить некую завуалированную проблему - вроде "задачи четырех красок"?
AmberSoler
Special status:
Author of the best multiplayer L map for HMM3 (2006)Specialist of offline tournament "HeroesLands3" in 2011
Profile Hero history PM E-mail
Go to reply form Go to top
Sir AmberSoler
+ + + + + + +
AmberSoler

HoMM III: Duke (10)
Messages: 1618
From: Russian Federation

Quote link Added: 3.10.2006 22:11
2 St-RauS

Нет необходимости доказывать, что "меньше чем за 4 нельзя". Цель: доказать или опровергнуть утверждение о том, что "задача не решается менее чем за 5 ходов". Сколько можно говорить одно и то же?..
AmberSoler
Special status:
Author of the best multiplayer L map for HMM3 (2006)Specialist of offline tournament "HeroesLands3" in 2011
Profile Hero history PM E-mail
Go to reply form Go to top
Sir hister

HoMM V: Landless
HoMM IV: Landless
HoMM III: Knight (2)
HoMM II: Landless
Messages: 173
From: Russian Federation

Quote link Added: 4.10.2006 03:54
Сэр AmberSoler, 3.10.2006 23:07
2 hister.
Сэр, обозначьте один момент: Вы сами имеете доказательство минимальности количества ходов? Т.е. здесь все еще продолжается предложенный Вами проект или мы находимся в свободном полете? Может мы тут пытаемся решить некую завуалированную проблему - вроде "задачи четырех красок"?


Задача принципиально отлична от "задачи четырех красок" как минимум тем, что, очевидно, целиком разрешима полным перебором (: Так, например, для всякого из 27 возможных раскладов (на самом деле имеет смысл рассматривать только 3(!!) в силу симметрии) можно построить дерево всевозможных путей решения и найти кратчайший путь из путей по всем деревьям ((: Так что вопрос о неразрешимости не стоит... Перебор, разумеется, неинтересен - имеет смысл искать более красивое решение. Например, можно попробовать доказать, что для любого хода отгадывания можно трижды ответить "1", а потом показать, что в таком случае игрок остается "с носом". Можно еще как-то попробовать...
Но, конечно же, мы в свободном полете: я еще ни разу не предложил тут задачи, для которой бы заранее знал идеально правильный ответ из книжки (достаточно просто знать, что задача разрешима) - всегда сам вместе со всеми решал после предложения на обсуждение. Ведь еще Сократ указывал, что задача не обязательно должна предполагать наперед известный ответ - необходимо лишь быть уверенным в ее заведомой разрешимости (:
hister
Profile Hero history PM E-mail
Go to reply form Go to top
Go to forum:
Pages: first | prev | << | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | next | last

Post reply

Tavern | Trade table