Вхід і реєстрація
Розробка · 26 листопада 2013, 23:38 22108
Александр Колосов

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

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

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Теми: головоломка, співбесіда
👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn

Найкращі коментарі пропустити

Mike Gorchak 26.11.2013 23:44

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

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

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

Відповісти
Підтримати
fizz buzz 27.08.2019 18:34

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

Відповісти
Підтримати
Andriy Loboda 27.08.2019 17:30

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

Відповісти
Підтримати
Bot Bot 27.08.2019 13:14

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

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

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

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

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

Відповісти
Підтримати
Vadim Kopanev Architect 27.08.2019 13:33
Берешь весы, кладешь туда пару монет, если одинаковые -> то равновесие, кладешь еще пару пока не получишь пару монет в которой есть засранец который нарушает равновесие, это «одно» взвешивание.

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

Відповісти
Підтримати
Bot Bot
Bot Bot 27.08.2019 13:41

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

Відповісти
Підтримати
Vadim Kopanev
Bot Bot 27.08.2019 15:23
Я так розумію твоя це правильна відповідь?

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

Відповісти
Підтримати
anonymous
Віталій Мартиник Senior Software Engineer в United Software 27.08.2019 13:00

Сложний прєкол

Відповісти
Підтримати
Dmytro Hrebeniuk Mobile Software Enginner в Self-Employment 27.08.2019 06:27

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

Відповісти
Підтримати
Bot Bot 27.08.2019 13:22
берем шары с более тяжелой чаши для следующего взвешивания

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

Відповісти
Підтримати
Dmytro Hrebeniuk
Bot Bot 27.08.2019 13:32

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

Відповісти
Підтримати
Dmytro Hrebeniuk
Tymchyshyn Vitalii Researcher 27.08.2019 01:30
какой именно и легче он или тяжелее

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

Відповісти
Підтримати
anonymous
Tymchyshyn Vitalii Researcher 27.08.2019 01:57

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

Відповісти
Підтримати
anonymous
Tymchyshyn Vitalii Researcher 27.08.2019 02:58

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

Відповісти
Підтримати
anonymous
Bot Bot 27.08.2019 13:09

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

Відповісти
Підтримати
anonymous
Bot Bot 27.08.2019 14:59
неправильно завдання прочитав

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

Відповісти
Підтримати
anonymous
Alexander Vasylenko 27.08.2019 00:27

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

Відповісти
Підтримати
Junkie Monkey 16.06.2016 10:41

Коментар порушує правила спільноти і видалений модераторами.

IRD Software developer в PE 25.03.2014 13:02

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

Відповісти
Підтримати
marko dou 25.03.2014 13:05

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

Відповісти
Підтримати
IRD
IRD Software developer в PE 25.03.2014 13:29

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

Відповісти
Підтримати
marko dou
Сергей Smoke 24.03.2014 17:26

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

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

Відповісти
Підтримати
Seven Berg 28.11.2013 21:36

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

Відповісти
Підтримати
Sergey Afanasov студент-заочник 28.11.2013 00:54

+

Константин Викторович 28.11.2013 00:33

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

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');
        }
    }
}
Відповісти
Підтримати
Константин Викторович 28.11.2013 00:17

Коментар порушує правила спільноти і видалений модераторами.

Константин Викторович 27.11.2013 23:56

Коментар порушує правила спільноти і видалений модераторами.

Константин Викторович 27.11.2013 23:42

Коментар порушує правила спільноти і видалений модераторами.

Oleg Sergeev 27.11.2013 17:50

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

Відповісти
Підтримати
Oleg Sergeev 27.11.2013 17:58

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

Відповісти
Підтримати
Oleg Sergeev
Mykola Shatokhin Founder в Yellow Cartridge 27.11.2013 16:53

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

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

Відповісти
Підтримати
Mykola Shatokhin Founder в Yellow Cartridge 27.11.2013 16:57

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

Відповісти
Підтримати
Mykola Shatokhin
Олекса Мащиць засновник в QA Україна 27.11.2013 17:10

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

Відповісти
Підтримати
Mykola Shatokhin
Mykola Shatokhin Founder в Yellow Cartridge 27.11.2013 18:04

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

Відповісти
Підтримати
Олекса Мащиць
chronoman 27.11.2013 16:11

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

Відповісти
Підтримати
Artem K 09.12.2013 16:14

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

Відповісти
Підтримати
chronoman
Олекса Мащиць засновник в QA Україна 27.11.2013 15:53

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

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

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

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

Відповісти
Підтримати
Олекса Мащиць засновник в QA Україна 27.11.2013 15:57

Ха, нашёл одну неточность в 3м шаге...

Відповісти
Підтримати
Олекса Мащиць
chronoman 27.11.2013 16:00

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

Відповісти
Підтримати
Олекса Мащиць
Олекса Мащиць засновник в QA Україна 27.11.2013 16:03

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

Відповісти
Підтримати
chronoman
Леголас Трандуилович 27.11.2013 20:34

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

Відповісти
Підтримати
Олекса Мащиць
Олекса Мащиць засновник в QA Україна 27.11.2013 15:48

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

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

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

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

Відповісти
Підтримати
chronoman 27.11.2013 15:56

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

Відповісти
Підтримати
Олекса Мащиць
Slava Boichenko Full Stack Engineer в Elementum SCM 27.11.2013 13:55

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

Відповісти
Підтримати
Slava Boichenko Full Stack Engineer в Elementum SCM 27.11.2013 13:57

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

Відповісти
Підтримати
Slava Boichenko
Oleh Belkot 27.11.2013 13:59

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

Відповісти
Підтримати
Slava Boichenko
Oleh Belkot 27.11.2013 13:57

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

Відповісти
Підтримати
Slava Boichenko
Slava Boichenko Full Stack Engineer в Elementum SCM 27.11.2013 14:49

Не дочитал)

Відповісти
Підтримати
Oleh Belkot
Александр Колосов 27.11.2013 13:58

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

Відповісти
Підтримати
Slava Boichenko
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 27.11.2013 14:42

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

Відповісти
Підтримати
anonymous
Vitaliy Bondarenko Працює в Amazon 27.11.2013 14:44

Точно! Я аж прямо не узнал!

Відповісти
Підтримати
Mike Gorchak
Vitaliy Bondarenko Працює в Amazon 27.11.2013 23:04

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

Відповісти
Підтримати
anonymous
Bogdan Verbenets .NET 27.11.2013 16:54

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

Відповісти
Підтримати
anonymous
Oleh Belkot 27.11.2013 13:50

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ьох, то одна з них або та яку ми запамятали, коли перекладали місцями(якщо терези змінили покази), або одна з двох які були з самого початку на тій чашці.

Відповісти
Підтримати
Yevgen Philatov QC engineer (Shark Smile) 27.11.2013 14:44

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

Відповісти
Підтримати
Oleh Belkot
Alexander Zvonov Test Lead в DXC Luxoft 27.11.2013 13:49

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

Відповісти
Підтримати
Andrii Serhiienko 27.11.2013 13:41

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

Відповісти
Підтримати
Oleh Belkot 27.11.2013 13:38

Коментар порушує правила спільноти і видалений модераторами.

Александр Колосов 27.11.2013 13:50

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

Відповісти
Підтримати
Oleh Belkot
Włodzimierz Rożkow інфлюенсер в t.me/full_of_hatred 27.11.2013 13:20
Чуть голову не сломал пока решил

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

Відповісти
Підтримати
chronoman 27.11.2013 13:51

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

Відповісти
Підтримати
Włodzimierz Rożkow
Alexander Puhachev Engineer в EPAM 27.11.2013 13:11

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

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

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

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

Все.
=)

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

Відповісти
Підтримати
Pavel Yakimovich PHP Developer в G5 27.11.2013 13:19

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

Відповісти
Підтримати
Alexander Puhachev
Alexander Puhachev Engineer в EPAM 27.11.2013 13:22

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

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

Поспешил =)

Відповісти
Підтримати
Pavel Yakimovich
qweqwe 27.11.2013 13:01

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

Відповісти
Підтримати
А Р at 27.11.2013 12:19

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

Відповісти
Підтримати
Vitaliy Bondarenko Працює в Amazon 27.11.2013 12:53

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

Відповісти
Підтримати
А Р
Леголас Трандуилович 27.11.2013 20:53

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

шаг 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

Відповісти
Підтримати
Vitaliy Bondarenko
Vitaliy Bondarenko Працює в Amazon 27.11.2013 23:00

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

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

1, 6, 7, 8 и 5, 9, 10, 11.
. Что четко показывает, что вы просто посмотрели в гугле :). Спасибо!
Відповісти
Підтримати
Леголас Трандуилович
Леголас Трандуилович 27.11.2013 23:38

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

Кстати, я говорю про шары 1,2,3,4,5,6,7,8 а вы почему-то про
1, 6, 7, 8 и 5, 9, 10, 11
э... м... ну так в этом же ж и вся суть решения.
Відповісти
Підтримати
Vitaliy Bondarenko
Vitaliy Bondarenko Працює в Amazon 27.11.2013 23:46

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

Відповісти
Підтримати
Леголас Трандуилович
Леголас Трандуилович 28.11.2013 11:22

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

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

Відповісти
Підтримати
Vitaliy Bondarenko
Vitaliy Bondarenko Працює в Amazon 28.11.2013 11:27

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

Відповісти
Підтримати
Леголас Трандуилович
Леголас Трандуилович 28.11.2013 11:47
Суть не в нумерации ведь, правда? :)
тогда мне совсем непонятна суть вот этого коментария
Відповісти
Підтримати
Vitaliy Bondarenko
anonymous 27.11.2013 11:47

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

Відповісти
Підтримати
Yvgen Troshchiy Синиор Мяу Мяу! в https://letyshops.com/ua 27.11.2013 10:29

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

Відповісти
Підтримати
Чорний Список Юджина 27.11.2013 11:57

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

Відповісти
Підтримати
Yvgen Troshchiy
Vitaliy Bondarenko Працює в Amazon 27.11.2013 12:57

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

Відповісти
Підтримати
Чорний Список Юджина
Vitaliy Bondarenko Працює в Amazon 27.11.2013 09:43

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

Відповісти
Підтримати
chronoman 27.11.2013 09:49

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

Відповісти
Підтримати
Vitaliy Bondarenko
Vitaliy Bondarenko Працює в Amazon 27.11.2013 10:02

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

Відповісти
Підтримати
chronoman
chronoman 27.11.2013 10:13

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

Відповісти
Підтримати
Vitaliy Bondarenko
Vitaliy Bondarenko Працює в Amazon 27.11.2013 10:17

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

Відповісти
Підтримати
chronoman
chronoman 27.11.2013 10:22

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

Відповісти
Підтримати
Vitaliy Bondarenko
Чорний Список Юджина 27.11.2013 10:29

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

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

мат. олимпиад со второго класса
Відповісти
Підтримати
chronoman
chronoman 27.11.2013 10:32

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

Відповісти
Підтримати
Чорний Список Юджина
Vitaliy Bondarenko Працює в Amazon 27.11.2013 10:32

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

Відповісти
Підтримати
chronoman
chronoman 27.11.2013 10:35

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

Відповісти
Підтримати
Vitaliy Bondarenko
chronoman 27.11.2013 10:29

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

Відповісти
Підтримати
Vitaliy Bondarenko
Vitaliy Bondarenko Працює в Amazon 27.11.2013 10:34

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

Відповісти
Підтримати
chronoman
chronoman 27.11.2013 10:39

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

Відповісти
Підтримати
Vitaliy Bondarenko
Vitaliy Bondarenko Працює в Amazon 27.11.2013 10:42

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

Відповісти
Підтримати
chronoman
chronoman 27.11.2013 10:44

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

Відповісти
Підтримати
Vitaliy Bondarenko
chronoman 27.11.2013 10:50

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

Відповісти
Підтримати
Vitaliy Bondarenko
Чорний Список Юджина 27.11.2013 09:32

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

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

Відповісти
Підтримати
reality_hacker 27.11.2013 09:34
2. Если равно, меряем 2.
Зачем их мерять если результат замера и так уже известен
Відповісти
Підтримати
Чорний Список Юджина
chronoman 27.11.2013 09:47

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

Відповісти
Підтримати
Чорний Список Юджина
chronoman 27.11.2013 09:52

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

Відповісти
Підтримати
Чорний Список Юджина
Чорний Список Юджина 27.11.2013 10:08

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

Відповісти
Підтримати
chronoman
Vitaliy Bondarenko Працює в Amazon 27.11.2013 10:07

"

Если нет, то в той кучке, что тяжелее
" это почему? Кто сказал, что шар в той, что тяжелее?
Відповісти
Підтримати
Чорний Список Юджина
chronoman 27.11.2013 10:14

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

Відповісти
Підтримати
Чорний Список Юджина
Нестор Иванович 27.11.2013 03:15

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

Відповісти
Підтримати
reality_hacker 27.11.2013 01:54

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

Відповісти
Підтримати
reality_hacker 27.11.2013 03:05

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

Відповісти
Підтримати
code monkey
Леголас Трандуилович 27.11.2013 12:51

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

Відповісти
Підтримати
reality_hacker
reality_hacker 27.11.2013 18:24

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

Відповісти
Підтримати
Леголас Трандуилович
Леголас Трандуилович 27.11.2013 19:37

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

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

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

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

Відповісти
Підтримати
reality_hacker
reality_hacker 27.11.2013 21:07

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

Відповісти
Підтримати
Леголас Трандуилович
Леголас Трандуилович 27.11.2013 21:49

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

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

Відповісти
Підтримати
reality_hacker
reality_hacker 28.11.2013 03:25

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

Відповісти
Підтримати
Леголас Трандуилович
reality_hacker 28.11.2013 03:37

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

Відповісти
Підтримати
Леголас Трандуилович
Леголас Трандуилович 28.11.2013 11:06

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

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

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

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

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

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

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

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

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

Відповісти
Підтримати
reality_hacker
Борис Синельский 28.11.2013 11:11

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

Відповісти
Підтримати
Леголас Трандуилович
Леголас Трандуилович 28.11.2013 11:45

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

Відповісти
Підтримати
Борис Синельский
Александр Колосов 28.11.2013 11:17

Вроде можно сначала взвесить 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
сейчас особо времени нет, после работы попробую расписать

Відповісти
Підтримати
Леголас Трандуилович
Леголас Трандуилович 28.11.2013 11:46

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

Відповісти
Підтримати
Александр Колосов
Борис Синельский 28.11.2013 13:06

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

Відповісти
Підтримати
Борис Синельский
Леголас Трандуилович 28.11.2013 14:15

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

Відповісти
Підтримати
Борис Синельский
Борис Синельский 28.11.2013 01:48

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

Відповісти
Підтримати
reality_hacker
reality_hacker 28.11.2013 01:52

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

Відповісти
Підтримати
Борис Синельский
Леголас Трандуилович 28.11.2013 11:30

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

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

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

Відповісти
Підтримати
Борис Синельский
Tim Tretyak ASM, TS Consultant в Hewlett Packard Enterprise 27.11.2013 00:15

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

Відповісти
Підтримати
anonymous 26.11.2013 23:49
Задача вроде свежая, и решение пока не гуглится.
Жесть какая. Ввел в гугл «12 шаров» и получил ответ по первой ссылке.
Відповісти
Підтримати
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 26.11.2013 23:44

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

Задача вроде свежая, и решение пока не гуглится.
У этой задачи такая борода, что даже смотреть страшно.
Відповісти
Підтримати
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 26.11.2013 23:49

The Mathematical Gazette, 1945

Відповісти
Підтримати
Mike Gorchak
Andrii Degeler Tech journalist 26.11.2013 23:42

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

Відповісти
Підтримати
Vitaliy Bondarenko Працює в Amazon 27.11.2013 10:09

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

Відповісти
Підтримати
Andrii Degeler
Andrii Degeler Tech journalist 27.11.2013 10:13

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

Відповісти
Підтримати
Vitaliy Bondarenko
Paul Loyanich CTO в loyanich.com 27.08.2019 16:28

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

Відповісти
Підтримати
Vitaliy Bondarenko

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

Не підписуватись
Скористайтесь акаунтом
×
з умовами використання сайту і політикою конфіденційності.