Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 15.11.2009, 17:49
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

pavlinux,
в бан собираешься?
  #12  
Старый 15.11.2009, 18:20
Аватар для pavlinux
Пользователь

Отправить личное сообщение для pavlinux Посмотреть профиль Найти все сообщения от pavlinux
 
Регистрация: 16.11.2008
Сообщений: 93

А по делу
  #13  
Старый 16.11.2009, 01:22
гость

 
Сообщений: n/a

pavlinux, дело говоришь!

Автор даешь доп. условия?
  #14  
Старый 30.06.2010, 22:38
Вячеслав

 
Сообщений: n/a

15 шариков
Задачка появилась в нашем весьма известном академическом институте лет 20 назад. Сопровождающий текст: из Киева; снята с олимпиады, как слишком сложная. Многие наши математики всех рангов обсуждали её какое-то время.
Некоторые заявили, что не будут тратить время на школьную ерунду. Другие быстро доказали "нерешаемость". А третьи столь же быстро предложили всевозможные схемы решения. Но решения не было!
А тут как раз нашлись другие задачки.
Но через какое-то время мне вдруг захотелось её решить.
И как-то вечером на даче при весьма забавных обстоятельствах, вполне "тянущих на сюжет для небольшого рассказа", (который я, конечно, не буду здесь разворачивать), возникло решение.

Задача. 15 шариков. 2 радиоактивных. Приборчик – указатель. Есть – нет. За 7 замеров. (105 возможных пар. 15´14/2.) Нумерую. 1…15. + есть. – нет.
1) 1,2,3,4,5 ® - ® Из 10 ш. за 6 з. Просто. 2) «4» 3) «4» 4) «2» и т.д.
+ (Комментарии. Ход делит на 60 и 45 пар. Плохо, оказывается,
¯ 1) 1,2,3,4, хотя деление более равное 50 и 55.)
2) 4,5,6 ® - ® Из 12 (С 1,2,3 +) Вторая ветвь. Смотри ниже.
(Делит ровно пополам 30 – 30 и решается.
¯+ А деление из решения с «четвёрками» 55 = 27 и 28. Из «8» за 5 – нет.
3) 7-14 («8») + ® 4) Один из пары 4 или 5 Ходы 5,6,7) Один из 7-14.
(Делит 14 – 16, 1,2,3,6,15 – нет.)
¯ -
4) 1,2 + ® 5) 1 или 2. 6,7) Выбираем из 4,5,6. (Делит 8 – 6. 3-ий, 15-ый – нет.)
¯ -
5) 4 + ® Один выбран. 6,7) Выбираем один из 3,5,6,15. (Далее всё время пополам -
¯ - точность.)
6) 3 + ® Один выбран. 7) Один из 5 и 6. (15 – нет.)
¯ - Один выбран, 5-ый.
7) Выбираем из 6-го и 15-го.

Вторая ветвь. Из 12-ти с (1,2,3.)+. Исключены 4,5,6. За 5 ходов.
3) 3,7,8 - ® 4) Один из 1,2. 5,6,7) Один из «8». 9-15 и остаток пары 1,2. (В случае 4)+).
+ (Этот вариант, из 9-ти (с первой «двойкой» +), 15 пар, очень прост (за 4).
¯ Но из 6-ти (тоже 15 пар) за 4 замера не получается.)
4) 9-15. («7») + ® 3-ий выбран. (1,2,4,5,6,7,8 – нет.) 5,6,7) Один из «семёрки» 9-15.
- ¯ (Деление 8 и 7.)
5) 3 - ® 6) Один из пары 1,2. 7) Один из пары 7,8. (3,4,5,6,9-15 («11») – нет.)
+ ¯ 3-ий выбран. (Деление 4 – 4.)
6,7) Один из «четвёрки» 1,2,7,8. (6-ой замер 1и2. + 7) 1 или 2. – 7) 7 или 8.)

Ну, решил и решил. Она же наверняка с решением была придумана.
Показал народу. Кто-то похвалил. Кто-то отказался смотреть.
"Олимпиадные" задачи не только не годятся для повторного использования, но и морально устаревают. Дирак говорил: не интересно решать задачки, у которых есть
решение.
"Учебная" польза. Назову это так (я не математик) – "микрозазор" между косностью и точностью. Косность, в данном случае, слепая убеждённость в оптимальности хода – разбиения "четвёртками". К этому подталкивает единственная (и простейшая) необходимая здесь формула. (2 в степени…)
Точность же в том, что как не рисуй – не группируй, измерения делаются последовательно и после каждого меняется "информационная ситуация". Не грех проверить на два хода вперёд. (Та же формула.)
Хочется, наконец, узнать достоверную биографию задачки, увидеть её первое решение и поблагодарить автора (авторов).
Задачка вовсе не мучила меня, наоборот, дважды, тогда, в начале девяностых, и сейчас подарила мне по несколько часов разнообразных приятных эмоций.
Вячеслав Владимирович Куроптев.
Скоро, уже очень скоро "озадачу" шариками своих внуков.
  #15  
Старый 01.07.2010, 09:01
гость

 
Сообщений: n/a

Цитата:
Задача. 15 шариков. 2 радиоактивных. Приборчик – указатель. Есть – нет. За 7 замеров.
За 7 замеров что? Определить радиоактивные?

Элементарно решается перебором на компьютере, тут же всего 2^15 состояний. Нечего нервные клетки тратить на перебор
  #16  
Старый 01.07.2010, 09:04
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
2^15 состояний.
не.. 3^15, что впрочем тоже не много
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм решения линейного уравнения n-й степени Destrifer Реализация, исходники, языки 9 07.07.2009 10:04
волновой алгоритм, подскажите как оптимизировать для задачи NewRon Реализация, исходники, языки 4 20.05.2009 19:03
нужен алгоритм решения задачи Neeka Математические алгоритмы 4 17.05.2008 19:09
подскажыте алгоритм решения задачи Pioneer Оффтопик 8 18.07.2007 03:52