|
давайте еще поколдуем над задачкой:) напр, за сколько взвешиваний можно гарантированно найти фальшивый алмаз? (допустим тролли весы в аренду сдали... ) |
81-Buhta >Смешаем бриллианты в кучу и решаем дихотомией. 17+21+27 = 65 1) Делим пополам 32+32 (1 в запасе) 2) 16 + 16 3) 8 + 8 4) 4 + 4 5) 2 + 2 6) 1 + 1 7) еще одно контрольное взвешивание, т.к. мы не знаем фальшивый легче или тяжелее. Итого 7 взвешиваний для гарантированного результата. |
82-victuan > так зачем все-таки взвешивать 32+32?;) что нам это даст? Файку недопоняли, обругали, в должности не повысили, а сами зачем-то взвешивают... |
83-Buhta >Контрольное взвешивание не последним пунктом, а там, где нарвемся на "чистую" половину. |
83-Buhta >Тьфу. Файку я не ругал. А ошибку свою вижу. Сейчас исправлю. |
68-Buhta >"...и вообще-то подсыпать ничего никуда нельзя..." Откладывать так можно, а подсыпать нельзя? :) Где это в условиях задачи? |
Делим на три части 21а + 21б + 21в (2 в запасе) 1) Взвешиваем 21а + 21б 2) Взвешиваем 21а + 21в Если вес одинаков, то фальшивая одна из двух в запасе: 3') 1(в запасе) + 1(проверенная) 4') 1(в запасе) + 1(проверенная) Иначе вычислили из 3 кучек одну с фальшивым бриллиантом и узнали, в какую сторону отличается ее вес 3) 11 + 11 (1 взяли из запаса) 4) 6 + 6 (1 взяли из запаса) 5) 3 + 3 6) 1 + 1 7) 1 + 1 Т.е. все равно 7 взвешиваний. |
84-rus66 > а дальше? |
86-rus66 > это новая задача:) |
87-victuan > еще хитрее;) |
90-Buhta >Т.е. есть более лучший вариант, чем 7 взвешиваний? |
87-victuan >Уфф, как сложно... еле осилил... :) У тебя в 82 нормальное решение. После п.1 берем "тяжелую" половину. Делим пополам, взвешиваем, если вес разный- значит фальшивка тяжелее и останется проделать манипуляции до п.6 выбирая тяжелые половины. А вот если фальшивка легче, тогда и придется добавить взвешивание второй части из 32 камушков, т.е. гарантия только из 7 взвешиваний. |
89-Buhta >Я понял что это новая, ты скажи почему в старой нельзя докладывать, если можно отсыпать :) |
92-rus66 > да какая разница, тяжелая она или легкая?;) я за 6 уложусь:) |
93-rus66 > если положил на весы, то уже ни отсыпать, ни докладывать:) если докладываешь или отсыпаешь на весах - это уже другое взвешивание |
95-Buhta >Я вижу, что меня не понимают:) По первой задаче я предложил другое решение, не откладывать из кучки а досыпать из одной в другую, чтобы уравнять количество, вот и все. :) По (94) ушел думать... |
96-rus66 > перед взвешиванием, а не в процессе, подсыпать можно:) не, ну если досыпать по 1-ой задаче (напр из 3-ей в 1-ую и взвешивать со 2-ой), то если уравновесятся, то 2-ая чистая, а если нет? тогда с уверенностью нельзя сказать, что 3-я или первая были чистыми и задача не решена за одно взвешивание:) |
94-Buhta >Я тоже за 6 уложился ))) |
Делим на три части 18а + 18б + 18в (11 в запасе) 1) Взвешиваем 18а + 18б 2) Взвешиваем 18а + 18в 3) 9 + 9 4) 4 + 4 (1 отложили в запас) 5) 2 + 2 6) 1 + 1 Если в пп.1-2 или в п.6 вес одинаковый, то фальшивый в запасе 11+1=12: 3') 6 + 6 4') 3 + 3 5') 2 + 2 6') 1 + 1 |
98-victuan > подсознание, однако, опять дает просчет:) в (82) не 7 взвешиваний:) но за 6 можно, я в тебя верила;) |
99-victuan > не верно:) если в 1-2 вес одинаковый, то мы не знаем, легче он или тяжелее |
известна формула Дайсона для определения фальшивой монеты неизвестного веса: m <= 1/2 * (3^n - 3) m - число монет n - количество взвешиваний при n=4 m <= 39 при n=5 m <= 120 |
100-Buhta >Ну тогда 3') 4 + 4 4') 4 + 4 (узнали легче или тяжелее) 5') 2 + 2 6') 1 + 1 |
лан, ушла работать:) |
не заморачивайтесь... из 65 монет можно за 5 взвешиваний найти фальшивку... формула Дайсона для 3-х взвешиваний: m = 1/2 * (3^3 - 3) = 12 одно из решений для 12-ти монет: [img]http://www.ega-math.narod.ru/Quant/Shestpl1.jpg[/img] |
97-Buhta >Не так. Уравнять 3-ю с 1-ой, их и взвешивать. Короче, это уже не интересно. Вот тут пришел Гена с известной формулой, и всех подмял. :) |
(106) зачем решать то, что давно известно... а вот задачка на внимательность мне очень понравилась |
107-Гена >Надо предложить решение с позиции 3-го класса. Формула Дайсона наверное поэтому здесь не подходит. |
доказательство формулы Дайсона просто по индукции... 1. понятно, что если три монеты, то нужно 2 взвешивания, что равносильно тому, что после первого взвешивания у нас есть 2 монеты на подозрении и 1 эталон 2. можно и 3+1=4 монеты разыграть двумя взвешивании, если есть в загашнике 1 эталон... взвешиваем номера 1 и 2... при равенстве эталоном определяем фальшивку 3 или 4... при неравенстве опять же имеем эталон и 2 монеты на подозрении = 1 взвешивание... 3. другими словами наличие в загашнике эталона позволяет класть на чашку уже не х монет, а х+1 4. определение на первом шаге эталона позволяет разыграть за три взвешивания не 3^2 монет, а (3+1)*3 = 12 5. аналогично для четырёх взвешиваний можно разыграть (12+1)*3 = 39 монет 6. для 5-ти взвешиваний - (39+1)*3 = 120 и т.д. видно, что имеем формулу Дайсона... |
108-victuan > с позиции третьего класса ) берём все чашечные весы в классе (32 штуки весов) и производим одновременное взвешивание )) если с первого взешивания не все весы уравнялись производим второе взвешивание уже на одних весах любой из монет с весов которые не уравнялись, с монетой с любой из других весов. итого - два взвешивания :-))) |
110-Зелёный тролль >Вот здесь ошибка "[em]одновременное взвешивание" -> "одновременн[u]ые[/u] взвешивани[u]я[/u][/em]" ))) |
109-Гена > а конкретно по этой задаче пример? |
(112) по какой? |
113-Гена > что за 5 взвешиваний можно выделить фальшивку из 65 брилиантов |
106-rus66 > смешать и поделить пополам? т.е. от одной отсыпать, в другую досыпать не трогая третью? ну да, пожалуй, прокатит:) ЗЫ: я пока не вижу, что Гена всех подмял... даже с формулой... может устала после 11 часов работы, но что-то при отсутствии эталона и неизвестности, легче или тяжелее, "доказательство" как-то не воспринимается... |
ИМХО, формула Гены работает только если знать легче или тяжелее... |
(114) лень маркёры всех монет рисовать... главное - принцип появления эталонов, с использованием которых уже определяется легче или тяжелее фальшивка... кстати формула Дайсона определяет фальшивую монету конкретно, т.е. в конце определённо узнаётся - легче она или тяжелее... если же в задаче просто сказано "определить фальшивку", то к формуле надо прибавить единицу: m = 1/2 * (3^n - 3) + 1 т.к. всегда одну монету сверху можно отложить в сторону... она сработает, когда при каждом взвешивании будет равенство... это будет означать, что отложенная фальшивка, но останется неизвестным - лёгкая она или тяжёлая... при такой постановке задачи максимум монет: 2 взвешивания = 3+1=4 монеты 3 взвешивания = 12+1=13 монет 4 взвешивания = 39+1=40 монет 5 взвешиваний = 120+1=121 монета ... |
117-Гена > определение по эталону легче оно или тяжелее - еще одно взвешивание:) не, если не согласен - приведи пример за 5 в конкретном случае. и по схеме в (105) я не вижу 3-х взвешиваний, при неизвестности - легче или тяжелее |
На рисунке для 12 монет какая ветвь решения непонятна? Например, пройдёмся по самым левым ветвям... 1. Положили 1,2,3,4 и 5,6,7,8 – левая вниз Под подозрением монеты: 1Т, 2Т, 3Т, 4Т, 5Л, 6Л, 7Л, 8Л т.е. уже однозначно выяснили, что среди первых четырёх нет лёгкой, а среди вторых – тяжёлой 2. Положили 1Т, 2Т, 5Л и 3Т, 4Т, 6Л – левая вниз Нормальные: 5, 3, 4 Под подозрением только три монеты, причём уже маркированные Л и Т: 1Т, 2Т, 6Л 3. Кладём 1Т и 2Т а) левая вниз: фальшивая монета 1 и она тяжёлая б) равенство: фальшивая монета 6 и она лёгкая в) правая вниз: фальшивая монета 2 и она тяжёлая ------------------- И так можно пройти сверху вниз по любой ветви рисунка. А теперь понятно, что из 120 монет, а тем более из 65-ти можно за два взвешивания спуститься к 12, а тем более к 8-ми монетам. На рисунке видно, что с ними расправимся за три взвешивания. 2 + 3 = 5 взвешиваний всего. |
119-Гена > ладно, с рисунком убедил:) про конкретные 65 мне тоже думать лень... может тогда приведешь формулу для задачи из соседней ветки?;) чему равен минимальный диаметр окружности, в которую без пересечений можно уложить 7 окружностей по 7 см? |
| Текущее время: 17:56. Часовой пояс GMT +3. |