Я когда-то загадывал эту задачу, но возможно тогда она была не ко времени, хотя попытки ее решить были и отчасти даже удавшиеся. Познакомился я с этой задачей на математической олимпиаде для 5 класса (по крайней мере с первой частью задачи). Ответ (минимальный) на вторую часть пришел лично ко мне много позже и после значительных усилий по его поиску. Мне эта задача нравится сочетанием простоты и сложности одновременно, поэтому решился выложить ее повторно.
Задача формулируется примерно так:
Я задумал число от 1 до 1000.
Вопросов два:
1)За какое минимальное количество ходов вы сможете его отгадать задавая мне вопросы, на которые я буду отвечать только "да" или "нет"?
2)тот же вопрос, только теперь я имею право 1 раз солгать.
Удачи.
Smith
Из мудрейших мудрейший

Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307
PeAcE
|
 |
� Ответ #105 : Март 26, 2010, 13:53:09 � |
|
Наши выстрелы 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 10 А вот где мышка: 1 2 3 4 5 6 7 8 9 8 9 8 9 8 9 8 9
А я о чем толкую  Смит, услышь нас.  выстрелы: 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10мышь (он):1 2 3 4 5 6 7 8 9 8 9 8 9 8 9 8 9 - бай, мышь! 
|
|
|
Записан
|
|
|
|
Lkob
Умник
  
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
 |
� Ответ #106 : Март 26, 2010, 14:00:45 � |
|
выстрелы: 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10мышь (он):1 2 3 4 5 6 7 8 9 8 9 8 9 8 9 10 9 - бай, мышь!  Скорее как-то так. 
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
Smith
Из мудрейших мудрейший

Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307
PeAcE
|
 |
� Ответ #107 : Март 26, 2010, 14:03:27 � |
|
карочиии... 2n-3 и 
|
|
|
Записан
|
|
|
|
Lkob
Умник
  
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
 |
� Ответ #108 : Март 26, 2010, 14:16:40 � |
|
карочиии... 2n-3 и  Согласен.  Хотя..... нет! Согласен на 2n-2 /А как же контрольный выстрел в голову? Так, чтобы наверняка/ 
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
buka
Гений
   
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
 |
� Ответ #109 : Март 26, 2010, 14:37:33 � |
|
Стреляем в N-1. (N-1, заметим, чётная) При предположении, что вначале мышка в чётной норке мы должны её убить. Если этого не произошло, значит вначале мышка была в нечётной норке и сейчас, следовательно, тоже в нечётной норке. И это значит что она сейчас, на N-2 шагу переместилась в чётную и мы опять начнём со 2-й норки. Но на сей раз мы точно знаем, что она - в чётной норке. Последнее предложение в этом отрывке не совсем понятно. Откуда нам будет это известно? Предлагаю частный случай в 9 норок, попробуем испытать вашу стратегию. По стратегии мы должны начинать со 2-ой норки, а мышка пусть у нас будет сидеть в первой. Поехали: 2-3-4-5-6-7-8-9 Ход мышки: 1-2-3-4-5-6-7-8 и когда был произведен выстрел по 9-ой мышка в нее перебегает. Второй проход по вашей стратегии выглядит так: 2-3-4-5-6-7-8-9 Ход мышки: 9-8-9-8-9-8-9-8 и после 8-го выстрела мышка опять перебегает в 9-ую. Ба!! Как так?! Мышка оказалась жива  Не совсем так. Моя стратегия для 9 норок: Первый проход: 2-3-4-5-6-7-8. В 9-ю норку я не стреляю! После выстрела в 8-ю она просто никак не может перебежать в 9-ю! В этом вся фишка! Это значит, что если мышка ещё жива, то она перебежала в ЧЁТНУЮ норку. И тогда я опять - 2-3-4-5-6-7-8 и   бедная мышка... Итого - 14 выстрелов на 9 норок. Обратите внимание: в случае нечётного числа норок, 1-я и последняя норки остаются не преострелеными после обоих проходов.
|
|
|
Записан
|
|
|
|
buka
Гений
   
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
 |
� Ответ #110 : Март 26, 2010, 14:41:25 � |
|
2Илья: если мне везет, то мышь в четной, и мои ходы 2,3,4,5,6,7,8,9 - хлоп! есть) но мне (как обычно, блин!) не везет, и мои дальнейшие ходы: 2,3,4,5,6,7,8,9,10 - хлоп! привет, мышь!! итого: 8+9=17  Ваши дальнейшие ходы - не 2,3,4,5,6,7,8,9,10, а 1,2,3,4,5,6,7,8,9.
|
|
|
Записан
|
|
|
|
buka
Гений
   
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
 |
� Ответ #111 : Март 26, 2010, 14:48:30 � |
|
2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 - вот так?
Да, это и есть стратегия для 10: 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 Обратите внимание: 9-1 нечётное на нечётное! Это - обязательно! Смена чётности: Для 9: 2-3-4-5-6-7- 8-2-3-4-5-6-7-8 8-2 чётное на чётное, опять смена чётности!!!
|
|
� Последнее редактирование: Март 26, 2010, 14:51:39 от buka �
|
Записан
|
|
|
|
Smith
Из мудрейших мудрейший

Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307
PeAcE
|
 |
� Ответ #112 : Март 26, 2010, 14:50:52 � |
|
2Илья: если мне везет, то мышь в четной, и мои ходы 2,3,4,5,6,7,8,9 - хлоп! есть) но мне (как обычно, блин!) не везет, и мои дальнейшие ходы: 2,3,4,5,6,7,8,9,10 - хлоп! привет, мышь!! итого: 8+9=17  Ваши дальнейшие ходы - не 2,3,4,5,6,7,8,9,10, а 1,2,3,4,5,6,7,8,9. та да, я исправил почти сразу 
|
|
|
Записан
|
|
|
|
Lkob
Умник
  
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
 |
� Ответ #113 : Март 26, 2010, 14:53:08 � |
|
Выстрелы: 2 3 4 5 6 7 8 2 3 4 5 6 7 8 Мышка(он): 3 4 5 6 7 8 7 8 7 8 7 8 9 8 Мышка(он): 1 2 1 2 1 2 3 4 5 6 7 8 9 8 Мышка(он): 1 2 3 4 5 6 7 8 9 8 9 8 9 8
Да, buka, все верно.
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
Smith
Из мудрейших мудрейший

Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 307
PeAcE
|
 |
� Ответ #114 : Март 26, 2010, 14:56:26 � |
|
мышь умер. да здравствует мышь! 
|
|
|
Записан
|
|
|
|
|