Про 200 webpack-плагінів для перформансу на конференції JavaScript fwdays'20 | 14 березня
×Закрыть

Сложная задача, 12 шаров 3 взвешивания

Выдано 12 одинаковых на вид шаров из которых, как вам сказали, только один отличается по весу. Ваша задача заключается в том, чтобы определить какой именно и легче он или тяжелее. Единственный инструмент в вашем распоряжении это весы с двумя чашками. На чашки можно класть только шары. Весы можно использовать не более трех раз.
//==============
Задача вроде свежая, и решение пока не гуглится.
Чуть голову не сломал пока решил, завтра еще раз проверю и опубликую решение. Если кто решит правильно раньше меня получит премию и признание

LinkedIn

Лучшие комментарии пропустить

Прошу прощенья, но вы пробовали искать не шары а монеты?

Задача вроде свежая, и решение пока не гуглится.
У этой задачи такая борода, что даже смотреть страшно.
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Ребята, нормальный ответ на эту задачу состоит из: 12-ти вариаций при 3-х взвешиваниях с одинаковыми значениями. У меня это на 2-х страницах А4 (текст) или 1 страница (графика).

Если снятие шара с весов не считается за отдельное использование, то ложим по 6 шаров на чашку (это будет первое использование весов). Потом одновременно снимаем по одному шару с каждой чашки. Когда веса уравняются — нестандартный шар будет в последней снятой паре.
Затем каждый шар из этой пары нужно сравнить с любым шаром из кучи (это будет второе и третье использование весов).

То що там? Хтось вже знає як це вирішувати?
Бо некроманти досі питають на співбесідах.

Эээ, я только сейчас заметил, что это некротема

Берешь весы, кладешь туда пару монет, если одинаковые -> то равновесие, кладешь еще пару пока не получишь пару монет в которой есть засранец который нарушает равновесие, это «одно» взвешивание.

У тебя пара монет в которой есть не верная монета (последняя пара которую ты бросал когда получилось не равновесие на весах) и 2 взевшивания. Просто берешь еще одну монетку из взвешенной кучки, там 100% правильные и вот взешиваешь с одной из пары, если весы не дают равновесие то искомая монетка на весах, тяжлее или легче, не важно, если весы в равновесии то не правильная монетка у тебя в руках.

Итого 2 взвешивания

Солюшен работает для любого количества монет\шаров\дровосеков со констатной сложностью О(1)

3-е взвешивание могу отдать обменять на оффер с зпвыше рынка ;-)

Берешь весы, кладешь туда пару монет, если одинаковые -> то равновесие, кладешь еще пару пока не получишь пару монет в которой есть засранец который нарушает равновесие, это «одно» взвешивание.

тогда уже каждую с каждой взвешиваешь и это 0 взвешиваний, просто подготовка

Можешь закинуть все сразу и убирать по паре.
Это как с интервьювером договоришься )))

У тебя пара монет в которой есть не верная монета (последняя пара которую ты бросал когда получилось не равновесие на весах) и 2 взевшивания. Просто берешь еще одну монетку из взвешенной кучки, там 100% правильные и вот взешиваешь с одной из пары, если весы не дают равновесие то искомая монетка на весах

Необовязково контрольною монету брати з тих що до цього зважували, так як неправильна лише одна і ти її виявив в парі. Можна і ту до якої черга на зважування не дійшла, вона буде важити стільки ж скільки і попередні зважені.

Я так розумію твоя це правильна відповідь?) Тоді задачка хитрожопа(( Якщо так таски видаватимуть на роботі, то треба звалювати доки не пізно. В результаті того хто попросив її вирішити на мило. Ось правильне вирішення головоломки.

Я так розумію твоя це правильна відповідь?

Я хз, просто как-то уже думал на этой сранью и надумал такой солюшен, верный или нет хз, да и пофиг как-то.:-))

Поймал еврей золотую рыбку, она ему предлагает стандартно исполнение любых трех желаний, еврей: «Миллион долларов на счету в швейцарском банке, жену красавицу, дом с видом на океан и это первое!»

1. Кладем в каждую чашу по 6 шаров, взвешиваем, берем шары с более тяжелой чаши для следующего взвешивания.
2. Кладем в каждую чашу 3 шара, берем шары с более тяжелой чаши для следующего взвешивания.
3. Кладем в каждую чашу по-одному шару, 3й откладываем.
Если весы равны, то отложенный шар отличается, если весы не равны, то наш шар что тяжелее на весах.
Подразумевается используем чашечные весы.

берем шары с более тяжелой чаши для следующего взвешивания

А если искомый шар легче нормы? Тогда надо брать легкую кучку.

Но в уловиях задачи не сказанно легче он или тяжлее. Так шо солюшен не работает.

Подразумевается используем чашечные весы.

А если электронные? :)

Взяти два і використовувати як звичайні)

Поділити на 2 групи по 6. Потім зважити і далі на 2 поділити важчу групу. Матимемо 3 з однієї і 3 з іншої. Зважування показує які 3 важчі. Беремо їх. Ще одне зважування в запасі. Потім беремо 2 зважуємо і якщо один важче то зрозуміло, а ні то той що не зважили важчий. Зайняло 1 хвилину. Де мій офер?

Мене аж гордість взяла за себе. Якщо це питання на співбесідах, то я недалеко від позиції архітекта.

Хм, а якщо 6 мужиків і 12 шарів. Як зважити щоб не дали в морду? А якщо 7 мужиків а 12 шарів... Один виходить трансгендер. Цю задачу я б не подужав. ХРам на замітку.

какой именно и легче он или тяжелее

:) Я колись подібну про 13 кульок розв’язував. Але там достатньо було знайти дефектну, а легша вона чи важча визначати не треба було.

Ох, тоді біда, бо незрозуміло яку групу брати після першого етапу зважування. Потрібно одне додаткове зважування для визначення шукаємо важче чи легше. Інакше таску не вирішити.

Upd побачив рішення нижче. Нормально. Якщо на першому зважуванні вдасться відкинути 2 групи з 3...)

Якщо до цієї рішення заспойлили — пробуйте 13 кульок. Визначати важча чи легша необов’язково (і не завжди можливо).

Не осилив. Або тут нема 100% рішення і прийдеться як в заспойленому варіанті припускати що перша група рівня другій(при цьому 1 лишній в ігнор і на нього вкаже наступна провірка). Завтра ще подумаю.

Рішення точно є, просто добратися до нього дещо муторно. Принаймні я не знаю красивого способу до нього прийти (в свій час «брав штурмом»).

А если не правильная монетка легче от нормы? Тогда более тяжелая кучка будет полностью состоять из одинаковых монет.

Так, на цьому я і попався. Але лише тому що неправильно завдання прочитав був))

неправильно завдання прочитав

Обычно это самое дроченное в этих задачках, потому как правильно поставленный вопрос уже почти решение.

Уважаемые, Вы, что шутите? Эта задачка элементарна даже для школьников.

Вже 6 років не можуть вирішити її.

Вощето задача не свежая, а старый баян от майкрософта
и не 12 шаров, а только 9..........

С 12-ю шарами/монетами задача усложняецца до невообразимых писдецов.

Но суть таже
Раздели на группы и взвешивай группами

С опозданием, но.
1) Берем 3 кучи по 4 шара. Взвешиваем. Если 4=4, то в 3й куче наш шар.
2) Берем из 8ми одинаковых 3 шара и взвешиваем с тремя из кучи 3. Соответственно получаем результат — тяжелее или легче один из 3х шаров в 3й куче. Если 3=3 — взвешиваем оставшийся с нормальным и узнаем легче он или тяжелее.
3) Если 3 != 3, взвешиваем по одному с 3х оставшихся (Мы уже знаем легче шар или нет).
Все.

Если в самом начале, 4 != 4, то решение ложиться. Слишком много условий в решении.

Подобная задача попадалась на собеседование в канторку сперотек. Там было так 8 шаров, необходимо определить минимальное количество взвешиваний.(2-3-3).Как и в этой задачке, количество шаров во второй попытке должно быть больше или равно 3...

Я не знаю что уже сказать. Нашел не доработку на один вариант.. Теперь точно все просчитал!!

p =[];
for (var i=0;i < 12;i++){
    p[i+1]=1;
}


p[7]=2;

var firstGroup = p[1]+p[2]+p[3]+p[4];
var secondGroup = p[5]+p[6]+p[7]+p[8];
var thirdGroup = p[9]+p[10]+p[11]+p[12];




if(firstGroup == secondGroup){

    if((p[9]+p[10]+p[6]) == (p[7]+p[8]+p[11])){

        if(p[9] > p[12]){
            console.log('p[12] the smallest ball in comparison with each of the other');
        }else if(p[9] < p[12]){
            console.log('p[12] biggest ball compared to each of the other');
        }

    }else if((p[9]+p[10]+p[6]) > (p[7]+p[8]+p[11])){

        if(p[9] == p[10]){
            console.log('p[11] the smallest ball in comparison with each of the other');
        }else if(p[9] > p[10]){
            console.log('p[9] biggest ball compared to each of the other');
        }else if(p[9] < p[10]){
            console.log('p[10] biggest ball compared to each of the other');
        }

    }else if((p[9]+p[10]+p[6]) < (p[7]+p[8]+p[11])){
        if(p[9] == p[10]){
            console.log('p[11] biggest ball compared to each of the other');

        }else if(p[9] > p[10]){
            console.log('p[10] the smallest ball in comparison with each of the other');
        }else if(p[9] < p[10]){
            console.log('p[9] the smallest ball in comparison with each of the other');
        }
    }

}else if(firstGroup < secondGroup){

    if((p[1]+p[2]+p[6])==(p[3]+p[5]+p[12])){
        if(p[7]==p[8]){
            console.log('p[4] the smallest ball in comparison with each of the other');
        }else if(p[7] < p[8]){
            console.log('p[8] biggest ball compared to each of the other');
        }else if(p[7] > p[8]){
            console.log('p[7] biggest ball compared to each of the other');
        }

    }else if((p[1]+p[2]+p[6]) < (p[3]+p[5]+p[12])){

        if(p[1] == p[2]){
            console.log('p[5] biggest ball compared to each of the other')
        }else if(p[1] > p[2]){
            console.log('p[2] the smallest ball in comparison with each of the other');
        }else if(p[1] < p[2]){
            console.log('p[1] the smallest ball in comparison with each of the other');
        }

    }else if((p[1]+p[2]+p[6]) > (p[3]+p[5]+p[12])){

        if(p[2]>p[3]){
            console.log('p[3] the smallest ball in comparison with each of the other');
        }else if(p[2]==p[3]){
            console.log('p[6] biggest ball compared to each of the other');
        }
    }

}else if(firstGroup > secondGroup){

    if((p[5]+p[6]+p[2])==(p[7]+p[1]+p[12])){
        if(p[3]==p[4]){
            console.log('p[8] the smallest ball in comparison with each of the other');
        }else if(p[3] < p[4]){
            console.log('p[4] biggest ball compared to each of the other');
        }else if(p[3] > p[4]){
            console.log('p[3] biggest ball compared to each of the other');
        }

    }else if((p[5]+p[6]+p[2]) < (p[7]+p[1]+p[12])){

        if(p[5] == p[6]){
            console.log('p[1] biggest ball compared to each of the other')
        }else if(p[5] > p[6]){
            console.log('p[6] the smallest ball in comparison with each of the other');
        }else if(p[5] < p[6]){
            console.log('p[5] the smallest ball in comparison with each of the other');
        }

    }else if((p[5]+p[6]+p[2]) > (p[7]+p[1]+p[12])){

        if(p[6]>p[7]){
            console.log('p[7] the smallest ball in comparison with each of the other');
        }else if(p[6]==p[7]){
            console.log('p[2] biggest ball compared to each of the other');
        }
    }
}

Б. А. Кордемский Математическая смекалка Москва 1965 год страница 206 (Держу книжку в руках) Задача разработана В. Давиде из Загреба. Даже не гуглил — сразу полез на полку — в децтве задрачивалсо.

Жуть, там ответ на 2 страницы в конце книжки.

Вы уверены, что условие верно записали? Если известно что один шар легче (или тяжелее), то взвешиваете по 3 шара. Если равны, то искомый шар в третьей куче. Если нет, то в той, что отличается. Далее взвешиваем по шару из той кучи, где искомый. Если равны, то искомый третий.

А вот если неизвестно легче он или тяжелее, тогда беда

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

Можно подбробнее? Какая третья куча? По сколько шаров в кучах?

Опять я неверно условие прочитал. Почему-то подумал, что там 9 шаров :) Сейчас подумаю еще...

как то знакомый рассказал случай тут на голладской передачи была дискуссия, шоу «3 черных ящика, в одном приз», игрока спрашивают какой ящик, чел выбирает, якубович говорит, салага, и открывает другой ящик и спрашивает — хотите ли поменять ваше мнение? Что бы сделал математик? Задачка проста как три копейки, но дискуссия на голландском телевидении была еще та :).

Парадокс Монти-Холла. Фильм «21»)

Итак, если шар в групее 2 (там 6 штук) — см. предыдущий пост.

Первое взвешивание было, поэтому дальше пункт 2.

2. Берём 3 шара из первой группы (мы знаем, что они все одинаковые в ней) и три шара из группы 2. Взвешиваем. Если 3 шара из группы 2 тяжелее — искомый шар тяжелее, если легче — то легче. Если вес равный, то искомый шар в оставшихся 3х шарах из группы 2.

3. Берём те 3 шара, которые, как мы выяснили отличаются по весу и повторяем шаг 3 из предыдущего моего сообщения. Взвешиваем два из них и, зная, легче ли искомый или тяжелее, находим искомый.

шаг 2: равны, и тогда вы не знаете от оставшихся 3х что там шар тяжелее или легче, со всеми вытекающими, но идея нормальная

Именно, это и есть та неточность :) При варианте, что наш шар в оставшихся, в 3м шаге я могу найти отличающийся по весу, но не узнаю, легче он или тяжелее.

и этого не можете.
третье взвешивание. один из шариков перевесил, только вот какой из них отличается то от остальных, более лёгкий или более тяжелый? не укладываетесь в 3 взвешивания никак

1. Взвешиваем первую группу из 6ти шаров. 1я чаша — 3 шара. 2я чаша — 3 шара. Если вес не равный, значит в группе 1 искомый шар. Если равны — искомый в оставшейся группе 2.

2. Если шар в группе 1. Запоминаем, какие из кучек по 3 шара (из шага1) тяжелее а какая легче. Взвешиваем все 6 шаров из первой групы с 6ю шарами из второй группы. Если первая группа тяжелее, значит искомый шар тяжелее и находятся в кучке, что тяжелее. В противном случае — искомый шар легче и находится в кучке, которая легче.

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

Сейчас напишу вариант, если после первого шага мы выяснили, что искомый шар в группе 2.

хорошее решение, но думаю для второй половины понадобится в худшем случае на 1 измерение больше (см. третий шаг, юзавший результат измерения 1го)

С первого раза
1) 5 — 5 — 2 — взвешиваем 2 кучки по 5, узнаем в какой куче шарик полегче
2) Если в кучке с 2-мя шариками — взвешиваем и узнаем ( за 2 хода)
3) Если в кучке 5 шариков делим на 3 группы 2 — 2 — 1
4) Взвешиваем 2 кучи по 2 шарика. Узнаем где шарик легче
5) Если шарик в кучке — взвешиваем два шарика из кучки (3 шага)

Вот только это именно про «легче»

А, якщо він 5<5 ? То в якій шукати далі?

В тому і суть, що він може бути важчим, а не легчим.

1. шар может быть как легче так и тяжелее

«Как сдвинуть гору Фудзи»? Алсо, есть версия с 8 монетами.

О! Со сменой аватарки вас :)

Как вас нексус в пользовании? :)

Все супер, всем знакомым советую)

А про «услышь хлопок одной ладони» есть задача?

И определить, на ком какая шапка и вероятность столкновения паровозиков)

1) Ділимо на 4 — 4 — 4
2) Важимо дві купки, якщо 4 = 4, то шар в 3ій четвірці, але ми вже маємо 8 однакових(варіант а). Якщо терези не рівні, то в нас однозначно є 4 однакових кулі (ті що не важили, варіант б).
Далі вся суть в тому(а в умові нам не заборонено, то використовуємо це на свою користь), що ми можемо запоминати(наприклад ложим збоку, зверху) ті кулі які ми перекладаємо на терезах.
3а)Відложимо 1 кулю від 4(в яких є брак) і зваажимо за схемою 2 + (1+1вірна з 8 ) і якщо не рівні, то міняєм на терезах місьцями 1вірну(ту яку добавляли з 8) і одну з двох на протележній чаші. Якщо терези не змінили покази, то брак залишився, якщо змінили, то це та, яку ми переклали.
3б) Міняємо місцями по одній кулі на протилежних чашах, і запомятовуєм їх.
Аналогічно попередній схемі тільки відкладаємо 2 кульки (по одній з кожної чаші), та перекладаєм 1 до протележних, а замість неї добавляєм 2 вірних.
В залежності чи змінили терези покази ми знаєм: 2 в яких є брак, або 3 в яких брак.
І далі методои відкладання 1 кульки та порівняння з завідомо вірними находим браковану.
Якщо, бракована в 3ьох, то одна з них або та яку ми запамятали, коли перекладали місцями(якщо терези змінили покази), або одна з двох які були з самого початку на тій чашці.

Как-то красиво у тебя выходит. я так пытался делать. но появляется загвоздка. В случае когда всегда нет равновесия, так как мы можем найти дефектный шар, но не знаем легче он или тяжелее. В любом случае первое взвешивание нужно делать, поделив шарики на 4 кучки по 3 штучки. Возьмем, что шары образцовые(в которых уже уверены) Q, а непонятные — O. Тогда при взвешивании любых кучек по 3 штучки у нас с 100% вероятностью есть ООО ООО QQQ QQQ, тоесть 6 образцовых шаров, а при взвешивании кучек по 4 штучки у нас есть вариант OOOO OOOO QQQQ. А потом уже мешать образцовые с не образцовыми.

Задача стара как мир. И её не устают спрашивать на соревнованиях из года в год

Это вброс такой или попытка пошутить?

в логической ветке 3б у вас 4 взвешевания, а надо 3

эту задачу нельзя решить за 3 взвешивания

погуглил, таки есть решение

Чуть голову не сломал пока решил

Вон из девелопмента.

В некоторых проектах хехе, девам думать вредно, так что зря вы так, на любой товар есть покупатель. И плюс откуда вы знаете как это «чуть голову не сломал» произошло. Может человек шел по лестнице, обдумывая задачку и прикидывая варианты, оступился и «чуть голову не сломал».

Задача проста как двери.
1. Делим шары на две партии по 6 штук.
2. Взвешиваем любую из них по три штуки на чашки: (первое взвешивание)
а) одна чашка тяжелее
б) обе чашки равны по весу

Осталось два взвешивание.

а.1 берем два шара с чашки которая оказалась тяжелее, третий кладем отдельено:
а.2 шары равны по весу — шар отличающийся по весу «третий»
а.3 одна чашка ушла вниз — снимаем один из шаров и сравниваем его вес с шаров с чашки которая оказалась легче в первом взвешивании:
а.4 если вес равен — значит отличается шар который мы сняли с чашки весов в пункте а.3
а.5 если вес не равен значит отличается шар который мы оставили в пункте а.3

б.1 берем вторую партию шаров которую мы не взвешивали в пункте 2 и повторяем для неее начиная с пункта 2.

Все.
=)

Кажется так.
Замечания предложения?

по взвешиваниям не укладываетесь... в пункте а — вы используете 2 из 2 оставшихся, хотя для пункта а — берете более тяжелые шары, хотя неизвестно — отличающийся легче или тяжелее — уйдете на пункт б — а там взвешиваний и не осталось.

в пункте а два взвешивания, укладываюсь

ап, ща подумаю

Поспешил =)

задача простая (очевиден подход к решению, а дальше все просто), вот остальные из списка намного интересней. www.maymounkov.org/...rom-battlefield

первый шаг 4 и 4, если равны — шар в третей четверке, дальше очевидно

а если не равны? взяли шары 1,2,3,4 меньше 5,6,7,8. какой следующий шаг?

ну это же очевидно.
допустим вес одинаковых шаров равен х

шаг 2: взвешиваем 1, 6, 7, 8 и 5, 9, 10, 11.
варианты развития событий:
2а 1, 6, 7, 8 < 5, 9, 10, 11. => 1 < 5, ну и дальше любой из них сравниваем с любым из остальных
2б 1, 6, 7, 8 = 5, 9, 10, 11 => 2, 3, 4 < 3*х
2в 1, 6, 7, 8 > 5, 9, 10, 11 => 6, 7, 8 > 3*x

Да, для меня это очевидно. Но по оригинальному комменту А Р (который он подправил, видимо после вашего коммента) мне показалось, что там совершенно не очевидно.

Кстати, я говорю про шары 1,2,3,4,5,6,7,8 а вы почему-то про

1, 6, 7, 8 и 5, 9, 10, 11.
. Что четко показывает, что вы просто посмотрели в гугле :). Спасибо!

Насчет очевидно я немного пошутил, не удержался.
В гугле смотреть не спортивно, задачку решили вдвоём с коллегой, ушло у нас на это 2 дня перекуров.

Кстати, я говорю про шары 1,2,3,4,5,6,7,8 а вы почему-то про
1, 6, 7, 8 и 5, 9, 10, 11
э... м... ну так в этом же ж и вся суть решения.

Если бы вы отвечали на мой вопрос, вы бы оперировали номерами от 1 до 8. Суть не в нумерации ведь, правда? :)

Парень, с тобой что-то не в порядке.
у тебя 12 шаров, соответсятвенно 12 номеров, которыми я оперирую. нигде в задаче не сказано что можно взвешивать только первые восем, более того при таком ограничении задачу и не решить. Когда ты взвешиваеш 4 на 4 и одна чашка перевешивает ты узнаёш не только что одна из чашек легче, но и то что искомый шар среди тех восьми что ты взвешивал, а следовательно оставшиеся 4, которые ты не взвешивал ещё — одинаковые, их можно использовать как эталонные в следующих взвешиваниях, что я и делаю.

Не надо судить о людях по себе :) думай как решить задачу а не как её можно хакнуть.

Я эту задачу решил в 9 классе, когда она мне попалась, так что «хакать» мне ее не надо :).

Суть не в нумерации ведь, правда? :)
тогда мне совсем непонятна суть вот этого коментария

Если кому-то тоже нечего делать на работе то вот www.smekalka.pp.ru/funny.html

Есть похожая задача 9 шаров — 2 взвешивания.
По аналогии можно решить.
www.quizful.net/...ms/w8dxoCTrzzAr

Не-не, тут совсем не похожая. Здесь вот как раз в условии написано, что шар ТЯЖЕЛЕЕ. А если точно известно, что он тяжелее или легче, то это решается за 10 секунд.

именно так, вы правы! Более того, 9 шаров и 2 взвешивания нельзя решить, если не знаешь тяжелее или легче. А вот 8 шаров можно :).

Мы такую решали еще в школе, точно помню какой был восторг когда решили.

задачка от школьной отличается тем, что в школьной было известно градиент массы шарика (плюс или минус) а тут это надо определить (как и сам шарик)

Нет, такого не было известно. В том то и дело было! Все сначала думали, что она не решается. Но потом, когда внимательно расписали варианты, стало ясно что решение есть.

Не не задача классная, просто мне в школе с мат. шкатулки (книжка такая была) давали задачку с известным градиентом, ну и там разные пирожки на сковородке, суммы рядов и прочее, вообщем со второго класса на мат. олимпиадах участвовал различного уровня. Первая грамота во втором классе, последняя на втором курсе политеха :) хаха, как давно это было, просто как тут описал человек решение типа делим на кучки 2-5-5 я не понял как он ее решил правильно, по крайней мере есть большие сомнения, а человек не признается, говорит что я его решения не понял. Может и не понял. Ну если с вариантом когда 5=5 то те два рулятся, путем двух взвешиваний с любым из кучки 5ти (ну скачет чел без детализации) я сам так писал на доске с кучей пропусков, что мой проф в политехе меня останавливал и просил делать промежуточные пометки и меньше в уме прикидывать. То вот если 5 !=5, то там темный лес как по мне, и решение дальше неправильное.

У нас в мат школе давали именно с неизвестным весом :)! Я очень хорошо помню, как пол класса ее решало, советовалось и т.д. Человек, кстати, уже написал, что невнимательно прочитал условие. Бывает.

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

Решение, я нашел и для условия, ушло 27 минут, если вам это интересно. Писать только много.

Хотя вы же все равно этого не признаете, участник многочисленных

мат. олимпиад со второго класса

2-5-5- вы не решили так как написали

писать как раз не так много ответ, тут ссылку кидали на компактное решение и на такие задачи дают меньше времени на олимпиадах чем 27 минут :)

Он вам писал, что не важно тяжелее или легче потому, что думал, что ИЗВЕСТНО что вес другой (а тогда тяжелее или легче действительно не важно).

важно для выбора правильного фокуса на следующий шаг как по мне, ну да ладно

и да, я в обычной школе учился, у нас таких задач не давали, но каким то чудным образом получалось занимать вплоть до областных олимпиад призовые места, у нас был спец. класс по физике с 8го класса, вот там наш класс и разгулялся вплоть до всесоюзных олимпиад, где кстати математика была на уровне школьной, в отличие от всеукраинских (после 1991) где уже надо было быть с физ мат лицеев с подготовкой в высшей мат. чтобы решить физ задачки и там наш класс с обычного провинциального Николаева сдал свои позиции до уровня областных. А раньше всем классом и республику брали и на всесоюзных вторые места были. Чем хороши такие задачки что кроме головы книжных знаний не нужно. Всему свое время, в школе школьное чтиво, в универе универское. Посмотришь чем забивают щас голову в физ-мат. интернате киевском ууу, слава богу мать не пустила в киев в далеком 1991 когда мне туда именное приглашение пришло хех.

Судя по длинне ваших постов, вам надо было на филологический :).

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

просто за вашей длинной комментов прячется суть. Именно поэтому вы так долго объяснялись с человеком. На самом деле хватило одного предложения.

оба первых коммента ему были не больше вашего кеп, если переходить на размерчики

кстати на филфаке рассадник гебешников учится :)

Ответ просто так и напрашивается
1. Ложим 2 шара в сторону и меряем 5 и 5
2. Если равно, меряем 2 оставшихся. Если нет, то в той кучке, что тяжелее, ложим в сторону 2 шара, затем еще шар в сторону и меряем оставшиеся 2.
3. Если ни один не тяжелее, меряем отложенные два. Вот и все. Если равны, то искомый шар это последний, отложенный.

P.S. Ответа не знал. Количество 12 прямо говорит, что надо откладывать по 2, слишком просто

2. Если равно, меряем 2.
Зачем их мерять если результат замера и так уже известен

кеп, а вы не забываете что один из шаров может отличаться не только в большую, но и в меньшую сторону? Как то по решению это не просматривается, по крайней мере снизу кажется, что вы заранее ограничили себя вариантом, что один шарик тяжелее чем все остальные, а это не та задачка

прочитал кеп, все равно не понял, в пункте 2 вы берете фокус на кучку, что тяжелее, а если шар легче, то искомое в другой кучке. которую вы уже не рассматриваете, а там 5 шаров. К легкой кучке вы не возвращаетесь вообще в вашем решении, так где правда.

Согласен, не читал внимательно условие

"

Если нет, то в той кучке, что тяжелее
" это почему? Кто сказал, что шар в той, что тяжелее?

Не прочел внимательно условие

ну вы же говорили что все равно совсем недавно

вы что прикалываетесь? борода у задачи длинше чем у старика хотабыча

А слабо решить в общем виде: для числа N монет — найти минимальное количество взвешиваний за которое можно найти фальшивую монету/шар/выпускника курсов головача?

Если я правильно понял эту бумагу, то там не определяется минимальное количество взвешиваний, а дается его нижняя оценка. Еще я попытался вникнуть в доказательство и уже первое предложение доказательства теоремы 1 мне кажется очень странным и непонятным.

да нефиг делать.
ну решил в своё время под новый год, похожую задачу. сколько масимум шаромонет можно проверить за 3 взвешивания. Математика говорит что вроде 13 можно. Долго думал, алгоритм на 13 такой же почти как и на 12, но есть один изъян — в одном из возможных кейсов мы находим фальшивую монуту, но не знаем легче она или тяжелее остальных, потому как не взвешивали её никогда.

Ну вот по формуле Бориса Синельского 14 тоже взвешивается ))

там что-то не так с той формулой. Я считал так:

k = (ln(N) + ln(2))/ln(3)

где k — количество взвешиваний N — количиство монет получается что можно 13 за 3 взвешивания, 14 не получается.

но здесь есть один ньюанс. в реальном алгоритме достаточно сложно разделить между взвешиваниями поровну количество нужной нам информации...

Твоя формула для 13 выдает 2.96564727304, а для 14-ти выдает 3.0331032563, как трактовать эти числа?

это количество взвешиваний необходимое, чтобы решить задачу заданной размерности. Так как дробного количества взвешиваний в природе не бывает, то полученное число надо бы округлить до большего-равного целого.

трактовать просто. задачу размерности 13 за 3 взвешивания теоретически решить можно, задачу размерности 14 уже нельзя

А можно пример дерева решений для 13 и 3?

А, хотя я уже сам догадался, нужно подумать над общим решением теперь.

я всё-таки расскажу. там есть одна закавыка
1. взвешиваем 4 и 4. если кто-то перевесил — то получаем то же самое что и в задаче с 12, тут всё просто

если же равно, тогда мы имеем 8 одинаковых шаров и 5 не взвешенных.
2. берём по 3 их каждой группы. Если перевесит одна из чашек весов то опять всё просто. Мы знаем в какой тройке отличающейся шар, знаем в какую сторону он отличается...

а вот если опять равно то у нас получается 11 одинаковых шаров и 2 невзвешиванных и всего одно взвешивание в запасе

3. тут мы сравниваем не взвешенный шар с одним из 12 эталонных, если весы перевесили то всё ок, а вот если опять равно есть одна неувязка с формулой выше — остался один не взвешенный шар, очевидно он отличается по весу, так как остальные одинаковые, но мы не знаем легче он или тяжелее.

Возвращаясь к формуле. По Шеноновскому определению количества информации я считаю количество информации необходимое для решения задачи как сумму
ln(N) — выбрать один шар из N
ln(2) — ну и выяснить легче он или тяжелее.

и формула говорит что 3 взвешивания должны дать для этого достаточно информации, а на практике у меня один не взвешенный шар...

Обсуждал это с более компетентным в математике коллегой — тот считает, что формула описывает идеальный случай, на практике его реализовать можно только в идеальных условиях. например когда у нас количество шаров кратное 3.

Другой вариант — что-то не корректно в моих расчетах. хотя там всё достаточно банально.

Ну и возможно есть лучьший алгоритм, который выдаёт всю нужную информацию за 3 взвешивания, я просто до него не додумался

Я думаю все-таки виявлення дефектної кулі потрібно вважати рішенням, навіть якщо не відомо, важча вони чи легша.

В оригинальной задаче само собой. Но я стараюсь проверить корректность своих расчетов, а для этого надо узнать и в какую сторону оно отличается.

Вроде можно сначала взвесить 5 на 5, а 3 отложить.
а1+а2+а3+а4+а5-
а6-а7-а8-а9-а10 = d1
Если d1 = 0 дальше елементарно,
если d1=1 (еще может быть −1, но эта логическая ветка симметрична)
то а11, а12, а13 — эталонные,
снимаем а6, а7, а8, на их место ложим три эталонных, а9 и а10 меняем местами с а4 и а5:
а1+а2+а3+а9+а10 -
3а — а4 — а5 = d2
сейчас особо времени нет, после работы попробую расписать

ха, я подумаю над этим вараинтом по дороге на работу.

та що ж таке, тепер на k=3 не паше.. ((
Зате у Трандиілича на великих числах затик :ь

Смысл этой формулы мне как-то совсем не понятен...

Так, зі звичайним округленням провтик, каюсь. Треба замінити його на щось на зразок логарифмічного підсилювача ))

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

Я же вверху написал про проблемму формулы. Я вообще шел другим путём, оригинальная, простая задача которую я знал это 9 шаров и 3 взвешивания, потом оказалось что за 3 взвешиваня можно решить задачу размерности 12, я удивился этому и решил посчитать, а сколько же всего можно теоретически. Потом сел и проверил формулу придумав решения для комбинаций от 8 до 13, потом нашел описанный выше артефакт, а потом новый год уже кончился и надо было идти назад на работу.

ля числа N монет — найти минимальное количество взвешиваний за которое можно найти фальшивую монету
Неправильна постановка задачі. Мінімальна кількість зважувань, за які можна знайти (а можна і не знайти) завжди 2. А от мінімальна кількість зважувань, за яку монета знаходиться з ймовірністю 1 = round (sqrt(N/3) + 1), де N — кількість монет, 3 — мінімальна кілкість, при якій задача має зміст.

Ок, а как доказать что твое решение — правильное? ))

Боюсь, что www.mathsisfun.com/...s_solution.html ;)
Но задачка мерзкая, факт.

Задача вроде свежая, и решение пока не гуглится.
Жесть какая. Ввел в гугл «12 шаров» и получил ответ по первой ссылке.

Прошу прощенья, но вы пробовали искать не шары а монеты?

Задача вроде свежая, и решение пока не гуглится.
У этой задачи такая борода, что даже смотреть страшно.

The Mathematical Gazette, 1945

Эм-м-м... По-моему, с таким условием задача решается просто в лоб, разве нет?

В лоб, но не так уж и просто. Надо внимательо расписать варианты, с наскока вряд ли решить (вот если известно, что шар тяжелее, тогда совсем просто).

Да, факт, это я недодумал вчера.

Если тяжелее, то за 2 взвешивания, вроде.

Подписаться на комментарии