Автор Тема: Радиоактивные шары  (Прочитано 5227 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн ALEXIN

  • Старожил
  • ****
  • Сообщений: 468
    • Просмотр профиля
    • E-mail
Re: Радиоактивные шары
« Ответ #15 : 13 Август 2012, 00:41:20 »
 :-[ Уважаемый evgen !
 Благодарю Вас за замечание. Сразу соглашаюсь на ещё один дополнительный ход (всего 15).
 Плохо , что вдохновение (Муза) посещает меня не каждые пять минут.
 Мы вторгаемся в область очень тонких и логичных рассуждений (не слабее чем шахматы).
  Так например , первый ход даёт возможность узнать местонахождение одного из четырёх шаров:
           ХХХ
           Х1Х
 если пусто , то обязательно будет
           ХШХ
           ХПХ
 И комбинации
           ХХ
             ХХ
не может быть.
 Вот как раз эту комбинацию я и упустил из вида при первоначальном решение.

Оффлайн evgen

  • Новичок
  • *
  • Сообщений: 8
    • Просмотр профиля
Re: Радиоактивные шары
« Ответ #16 : 13 Август 2012, 00:48:03 »
При проверке шести рядов и шести столбцов может возникнуть ситуация, когда будут выявлены три ряда и четыре столбца. Значит , надо будет найти четыре из двенадцати. На это может понадобиться 8 ходов. Итого 20.

Оффлайн ALEXIN

  • Старожил
  • ****
  • Сообщений: 468
    • Просмотр профиля
    • E-mail
Re: Радиоактивные шары
« Ответ #17 : 13 Август 2012, 01:11:26 »
 :-[Уважаемый evgen !
  Прошу прощения , но я не понимаю Вас.
  Изобразите схематично может возникнуть ситуация, когда будут выявлены три ряда и четыре столбца

Оффлайн evgen

  • Новичок
  • *
  • Сообщений: 8
    • Просмотр профиля
Re: Радиоактивные шары
« Ответ #18 : 13 Август 2012, 01:22:48 »
Если у Вас есть решение за 17 ходов, опишите его подробно. Пока из достоверных решений я увидел только решение за 19 ходов.

При выявлении шести рядов и шести столбцов может возникнуть ситуация
NNNY
NNYN
YYNN
И есть много других вариантов, при которых радиоактивными будут три ряда и четыре столбца. Если четыре ряда и четыре столбца, то будет легко разобраться. А в случае 3*4  может потребоваться 8 ходов.

Оффлайн ALEXIN

  • Старожил
  • ****
  • Сообщений: 468
    • Просмотр профиля
    • E-mail
Re: Радиоактивные шары
« Ответ #19 : 13 Август 2012, 01:40:51 »
 :-[Если шары будут стоять именно так ,  то я угадаю их за 12 (двеннадцать) ходов.Возможно и
меньше.Не думал. Так как точно буду знать координаты каждого радиоактивного шара.
  Если нумерация шаров по моему алгоритму:
1           2          3           4            5         6
7           8          9          10          11         12
13         14        15         16          17         18
19         20         21        22          23         24
25       26         27        28          29         30
31         32         33        34           35        36

Оффлайн evgen

  • Новичок
  • *
  • Сообщений: 8
    • Просмотр профиля
Re: Радиоактивные шары
« Ответ #20 : 13 Август 2012, 02:11:24 »
Теперь я не понял. Продемонстрируйте на практике. Допустим, Вы проверили за 12 ходов шесть рядов и шесть строк и получилось так:

красные - это радиоактивные ряды  и строки.  Красные столбцы слева 1,2,3,4, красные строки сверху -  а,б,в.  Если проверяются точки, обозначайте их пересечением( например а-1) Если несколько точек, то указывайте через запятую.  Я загадал схему расположения четырех фонящих точек в красных пересечениях. Попробуйте угадать меньше чем за 8 ходов. Я буду сообщать , фонят группы выбранных Вами точек или не фонят.

Оффлайн ALEXIN

  • Старожил
  • ****
  • Сообщений: 468
    • Просмотр профиля
    • E-mail
Re: Радиоактивные шары
« Ответ #21 : 13 Август 2012, 02:36:30 »
 :-[Уважаемый evgen !
  Мне видно только квадрат 5*5 .Поэтому лучше на словах:
 1.Ваш случай 4 столбца и 3 ряда означает , что в одном из рядов стоят 2 р.ш.
 2.По моей схеме (см.выше) снимаем число 6 и делаем замер .Если всё чисто , то снимаем число 17.
Если опять всё чисто -нет зумммера , то искомые два шара сдвоены только в третьем ряду.

Оффлайн evgen

  • Новичок
  • *
  • Сообщений: 8
    • Просмотр профиля
Re: Радиоактивные шары
« Ответ #22 : 13 Август 2012, 02:46:57 »
Это не 5 на 5 , а 6*6 . Все кубики - условно в пересечениях линий.  Красные строки  и столбцы  - это те которые зазвонили при проверке за первые 12 попыток . Найдите за 8 попыток 4 кубика в этих красных столбцах и строках.

Оффлайн ALEXIN

  • Старожил
  • ****
  • Сообщений: 468
    • Просмотр профиля
    • E-mail
Re: Радиоактивные шары
« Ответ #23 : 13 Август 2012, 03:58:43 »
 :-[ Я понял , что Вы хотите от меня .
 Но ведь это надуманное усложнение , только упрощает мне работу ,т.к. последовательность алгоритма сразу изменится.Мне не зачем делать лишние два хода по столбцам ,т.к. понятно
по 5-му и 6-му ничего не будет.Также по рядам начинаю с четных ,т.е. ещё выигрываю два хода
 Таким образом на Вашу группировку 3*4  я затрачу предварительно не более 7-8  ходов.
 Остается найти найти 4 из 12 .Вы отвели на это 8(восемь) ходов.Попробую в течение недели.
 
 Буду надеяться , что это Олимпиадная задача .Пусть дети учатся , на моих примерах. :bubble:
 

Оффлайн Леонид

  • Глобальный модератор
  • Эксперт
  • *****
  • Сообщений: 6806
    • Просмотр профиля
    • Домашняя страница
Re: Радиоактивные шары
« Ответ #24 : 13 Август 2012, 04:59:45 »
Таким образом на Вашу группировку 3*4  я затрачу предварительно не более 7-8  ходов.
 Остается найти найти 4 из 12 .Вы отвели на это 8(восемь) ходов.Попробую в течение недели.

Вы уже потратили 12 ходов на то, чтобы выявить группировку 3*4. Если вы не сможете закончить МЕНЬШЕ чем за 7 ходов, незачем тратить время и засорять тему: решение из 19 ходов уже есть.

Оффлайн ALEXIN

  • Старожил
  • ****
  • Сообщений: 468
    • Просмотр профиля
    • E-mail
Re: Радиоактивные шары
« Ответ #25 : 13 Август 2012, 05:03:22 »
 :-[Сразу ноу-хау , Муза кажется посетила , надо для экономии ходов сделать два замера по большим диагоналям.Тогда получится , что я знаю за два хода размеры группировки!! :yahoo:

Оффлайн zer0

  • Ветеран
  • *****
  • Сообщений: 688
    • Просмотр профиля
    • E-mail
Re: Радиоактивные шары
« Ответ #26 : 13 Август 2012, 15:06:55 »
Про музу родственникам расскажите :) А здесь надо просто изложить полное решение.

Оффлайн ALEXIN

  • Старожил
  • ****
  • Сообщений: 468
    • Просмотр профиля
    • E-mail
Re: Радиоактивные шары
« Ответ #27 : 13 Август 2012, 16:40:32 »
 :-[Спасибо   zer0 за поддержку !
 Я залез в такие дебри , что готовое решение (алгоритм) может не поместится и на 5 компьютерных
страницах.Но это ещё не завтра.
 Решение по алгоритму , о котором писал выше Леонид ,мне кажется очень сомнительным.Расчёты
сделаю позже. :bye:

Оффлайн zer0

  • Ветеран
  • *****
  • Сообщений: 688
    • Просмотр профиля
    • E-mail
Re: Радиоактивные шары
« Ответ #28 : 13 Август 2012, 19:16:47 »
А может, ну его, решение на 5 страницах?  ;D
Стоит взглянуть на фразу:   "На комбинацию №1  хватает 11 ходов; №2-11 ходов;  №3- 14 ходов и  №4-17 ходов."  и все становится ясно.

а) как можно найти решение за 11 ходов, если при замере квадрата 6x6 истрачено 12  :o

б) если эти 11 плюс к тем 12, то итого получается 23, а такое решение интереса не представляет (хоть на 5 страницах, хоть на 1).

в) вариант, когда сигнал идет на 4 строках и на 4 столбцах почему-то вообще не рассматривается (зато "рассматривается" вариант с 1 столбцом)  :)
« Последнее редактирование: 13 Август 2012, 21:32:56 от zer0 »

Оффлайн ALEXIN

  • Старожил
  • ****
  • Сообщений: 468
    • Просмотр профиля
    • E-mail
Re: Радиоактивные шары
« Ответ #29 : 14 Август 2012, 10:49:31 »
 :-[ Экскурс.Впервые в России задача как найти 2 радиоактивных шара из 19 за  8 замеров появилась
в журнале "Квант" 1971г. №3.(см.вложение).
 Дальше появились алгоритмы как найти 2р.ш. за 7 замеров из 20, 21 и даже 22 шаров.Позже дам ссылки.
 В конечном итоге я пытаюсь найти способ разбить 4р.ш. на составные:2+2;2+1+1;1+1+1+1 и дальше
решение по отработанным алгоритмам.Плохо ,что в Интернете я не нашёл никакой информации о
таких способах разбивки.Придётся домысливать самостоятельно.
 Ниже приведена переработанная статья из журнала "Квант".
                             
Условие
Из 19 шаров 2 радиоактивны. Про любую кучку шаров за одну проверку можно узнать, имеется ли в ней хотя бы один радиоактивный шар (но нельзя узнать, сколько их). Доказать, что за 8 проверок всегда можно выделить оба радиоактивных шара.

Скрыть решение
Решение
На рис. 1 представлен способ, позволяющий за 5 проверок выделить 2 радиоактивных шара из 7. Мы считаем, что шары занумерованы числами 1, 2, ..., 7, и в каждой клетке записываем кучку шаров, которые подвергаются проверке (иногда кучка состоит из одного шара). Например, первой проверяется кучка из трёх шаров {1, 2, 3}. У каждой проверки возможны два исхода: ``есть радиоактивность"" — тогда нужно идти по красной стрелке, и `` нет радиоактивности"" — тогда по ``чёрной"" стрелке. Если клетка заштрихована, значит, дальнейшие проверки не нужны. Для каждого пути, спускающегося по стрелкам сверху вниз, в результате всех проделанных на этом пути проверок можно установить, какая именно пара шаров радиоактивна (она указана под самой нижней стрелкой). Убедитесь в этом! Начнём с аналогичной, но более простой задачи. Пусть дано n шаров, среди которых один радиоактивен; за сколько проверок его можно выделить? Легко указать способ, позволяющий за k проверок выделить один из n = 2k шаров: вначале делим все шары на две равные кучки по 2k - 1 шаров в каждой, проверяем одну из них и тем самым определяем, в какой из них находится радиоактивный шар, затем эту кучку из 2k - 1 шаров снова делим пополам, проверяем одну из половин и т. д. — при каждой проверке число шаров уменьшается вдвое, и после k проверок мы найдём радиоактивный шар. Ясно, что если n < 2k, то тоже достаточно k проверок. Итак, для того чтобы выделить один радиоактивный шар из n, достаточно проделать f1(n) проверок, где f1(n) — наименьшее целое число k, для которого n  2k (другими словами, f1(n) — наименьшее целое число, большее или равное log2n). Ниже мы увидим, что меньшего числа проверок заведомо недостаточно. Теперь перейдём непосредственно к решению нашей задачи. Здесь уже не удаётся получить точный результат сразу для любого n, и мы выясним сначала, за сколько проверок можно выделить 2 радиоактивных шара из n, если n — небольшое число. Для n = 3 достаточно двух проверок; после того, как мы проверим один за другим два шара, будет уже ясно, радиоактивен ли оставшийся третий шар. Может, конечно, случиться, что первый же проверенный шар не радиоактивен, и тогда дальнейшие проверки не нужны; но нас интересует, за какое число проверок можно выделить радиоактивные шары наверняка, при любом, даже самом невыгодном для нас варианте их расположения. Точно так же, проверяя шары один за другим, можно выделить два шара из 4 за 3 проверки, из 5 — за 4, из 6 — за 5, из 7 — за 6 и т. д. Впрочем, для n = 7 можно обойтись и пятью проверками. Прежде чем читать решение дальше, попробуйте это доказать, то есть найти соответствующий способ поиска радиоактивных шаров. Один такой способ (их существует несколько) указан на рисунке 1. Этот рисунок помогает понять, что мы понимаем под словами ``способ поиска шаров""; чтобы задать какой-то способ, нужно указать кучку шаров, которая проверяется первой, а также указать, какую кучку проверять после каждого из возможных исходов очередного испытания на радиоактивность; другими словами, нужно начертить диаграмму из прямоугольных клеточек и стрелок — такую же, как на рисунке 1, только, если нужно, с другим числом k проверок — и вписать в каждую клетку какие-то номера шаров. Теперь постараемся ответить на два тесно связанных между собой вопроса: как найти способ поиска двух шаров среди n, состоящий из k проверок, если такой способ существует; если его не существует, то как это доказать? В принципе для любых конкретных n и k эти вопросы можно решить ``полным перебором"", перепробовать один за другим все возможные способы заполнить клетки диаграммы, соответствующей k проверкам, подмножествами на n шаров (ведь таких способов существует конечное число!) и для каждого из этих способов проверить, позволяет ли он выделить радиоактивные шары или нет (то есть будут ли разным предположениям: какая именно пара шаров радиоактивна — соответствовать разные пути по стрелочкам сверху вниз). Но число таких способов даже при небольших n и k настолько велико, что практически проделать ``полный перебор"" невозможно даже с помощью вычислительной машины (например, при n = 11 и k = 7 заполнить клетки диаграммы кучками можно более чем 10400 разных способов!). Мы покажем сейчас, как можно этот перебор сильно сократить. Вернёмся снова к рисунку 1. От самого нижнего ряда клеточек, соответствующего последней, пятой проверке, отходит 25 = 32 стрелки. В общем случае, для k проверок, их будет 2k. Если способ поиска, записанный на диаграмме, гарантирует выделение радиоактивных шаров, то каждой из этих стрелочек соответствует только один из возможных вариантов ответа: какие именно два шара радиоактивны (но, может быть, разным стрелочкам соответствует один и тот же вариант). Поэтому число различных возможных вариантов ответа заведомо не больше числа стрелочек, то есть не больше 2k. Сформулируем это основное соображение так: ``Если число возможных вариантов больше 2k, то не существует способа, позволяющего за k проверок выделить один из этих вариантов."" То же самое можно сказать так: ``Если существует способ, позволяющий за k проверок выбрать один вариант из N возможных, то N  2k."" (Последнее неравенство можно записать ещё и так: k  f1(N).) Конечно, это правило применимо к любой задаче, где нужно выбрать один вариант из N по результатам нескольких проверок; важно лишь то, что каждая проверка имеет два возможных исхода (в нашей задаче эти исходы таковы: ``есть радиоактивность"" и ``нет радиоактивности""). В частности, из этого правила следует, что нельзя выделить один радиоактивный шар из n менее чем за f1(n) проверок: если f1(n) = k, то 2k - 1 < n, а различных вариантов в этой задаче существует n (радиоактивен 1-й шар, радиоактивен 2-й шар, ..., радиоактивен n-й шар). Вернёмся снова к задаче, где имеется два радиоактивных шара. Сколько здесь различных вариантов? На рисунке 1, где мы выбираем 2 шара из 7, число вариантов равно 21. В общем случае существует С2n =  вариантов выбрать 2 шара из n. Из нашего основного правила, напечатанного выше, следует, что если можно за k проверок выделить 2 шара из n, то   2k. Условимся обозначать наименьшее число проверок, необходимое для выделения 2 шаров из n, через f2(n). Тогда последнее неравенство можно записать так:

f2(n)  f1().
n   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25
   3   6   10   15   21   28   36   45   55   66   78   91   105   120   136   153   171   190   210   231   253   276   300
f1(n)   2   2   3   3   3   3   4   4   4   4   4   4   4   4   5   5   5   5   5   5   5   5   5
f1()   2   3   4   4   5   5   6   6   6   7   7   7   7   7   8   8   8   8   8   8   8   9   9
f2(n)   2   3   4   5   5   6   6   6   7   7   7   7   7   8   8   8   8   8   8   8   9   9   9

Из таблицы видно, что при некоторых n (например, при n = 6, n = 8) здесь возможно и строгое неравенство. Действительно, для того чтобы за k проверок можно было найти 2 радиоактивных шара среди n, мало того, чтобы выполнялось неравенство   2k. Нужно ещё, чтобы таких вариантов, для которых первая проверка дала результат ``+"" (есть радиоактивность), было не больше 2k - 1 и таких, для которых она дала результат ``-"" (нет радиоактивности), тоже было бы не больше 2k - 1, — ведь иначе, согласно основному правилу, мы не сможем за k - 1 проверку выбрать из этих вариантов один! Точно так же каждому из исходов ``+ +"" (1-я проверка ``+"", 2-я проверка ``+""), ``+ -"", ``- +"", ``- -"" должно соответствовать не более 2k - 2 вариантов и т. д. Утверждение задачи 3 для 8 класса состоит в том, что f2(19)  8. а утверждение задачи 3 для 9-11 классов эквивалентно тому, что f2(11)  7. Ниже мы очень коротко докажем, что f2(6)  5; f2(8)  6; f2(11)  7; f2(10)  6; f2(15)  7; f2(21)  8. Читатели, которые хотят убедиться в том, что все числа в нижней строке таблицы верны, должны будут доказать, кроме того, что f2(16)  8; f2(22)  8; f2(23)  9; f2(25)  9 (действительно, ясно, что функция f2 неубывающая, то есть если m > n, то f2(m)  f2(n), поэтому достаточно правильно указать те значения n, для которых f2(n + 1) строго больше f2(n)). Прежде чем доказывать обещанные неравенства, заметим, что определение точного значения f2(n) для любого n в этой задаче, как и во многих других похожих задачах, не слишком интересно. Дело в том, что соответствующий способ выделения шаров, повидимому, очень сложен. С другой стороны, легко указать совсем простые алгоритмы выделения шаров, требующие лишь ненамного большего, чем f2(n), числа проверок. Например, если сначала выбрать один радиоактивный шар, затем выбросить его и из оставшихся выбрать другой, то на это уйдёт не более f1(n) + f1(n - 1) проверок, и, как нетрудно показать, разность f1(n) + f1(n - 1) - f1(C2n) всегда не больше 2, следовательно, разность f1(n) + f1(n - 1) - f2(n) тоже не больше 2. В практических задачах, подобных этой, если само число проверок k не слишком мало, одна или две лишние проверки скорее всего не будут играть особой роли, лишь бы способ проверки был попроще (скажем, для n = 15 мы уже не можем уместить на странице диаграмму, подобную рисунку 1, и разобраться в описании способа проверки становится нелегко). Ниже мы используем такие обозначения: знак ``-"" обозначает, что в проверяемой кучке нет радиоактивных шаров, а знак ``+"" — что они есть. За 4 проверки нельзя выделить 2 шара из 6 Пусть первой проверяется кучка из 6 - q шаров, где q = 2, 3, 4 или 5, Тогда исходу ``-"" соответствует С2q вариантов (оба радиоактивных шара среди q остальных), исходу ``+"" — (C62 - C2q) вариантов. Одно из этих чисел больше 23 = 8. За 5 проверок нельзя выделить 2 шара из 8 Если

Cq2 < 24 = 16 и C82 - Cq2 < 16,

то q может быть равно только 6. Если исход ``-"", то при этом осталось выделить 2 шара из 6, что невозможно за 4 проверки. За 6 проверок нельзя выделить 2 шара из 11 Если Cq2 < 25 = 32 и C112 - Cq2 < 82, то q = 8, но f2(8)  6. За 6 проверок можно выделить 2 шара из 10 Первая кучка — кучка из 4 шаров {1 - 4}. ``-"" за 5 проверок 2 шара из 6 {5 - 10}. ``+"" проверяем {4 - 6}. ``+ -"" за 4 проверки 2 шара из 7 {1 - 3, 7 - 10}, если известно, что {1 - 3} дают ``+"" (см. левую половину рис. 1). ``+ -"" проверяем {5, 6}. ``+ + -"" за 3 проверки 1 шар из {1 - 3, 7 - 10}. ``+ + +"" за 1 проверку 1 шар из {5, 6} и за 2 проверки 1 из {1 - 4}. За 7 проверок можно выделить 2 шара из 15 Первая проверка {1 - 5}. ``+"" проверяем {5 - 9}. ``+ -"" за 5 проверок 2 шара из 10 {1 - 4, 10 - 15}, среди которых {1 - 4} дают ``+"" (см. 10 шаров, ``+"" ). ``+ +"" проверяем {5}. ``+ + +"" за 4 проверки 1 шар из {1 - 4, 6 - 15}. ``+ + -"" за 2 проверки 1 шар из {1 - 4} и за 2 проверки 1 из {6 - 9}. За 8 проверок можно выделить 2 шара из 21 Первая проверка {1 - 6}. Кроме обозначенных на рисунке и очевидных проверок, укажем такие ``+ -"" за 6 проверок 2 из 15 {1 - 5, 12 - 21}, среди которых {1 - 5} дают ``+"" (см, 15 шаров, ``+""). ``+ + - -"" за 2 проверки 1 шар из {1 - 4} и за 2 проверки 1 из {8 - 11}. (Решение задачи М28 из журнала ``Квант"".)