Девочки и мальчики,
математические приседания с призами на тему наступающего 2018-го продолжаются. Предыдущая задачка оказалась совсем не сложной - решение за 8 шагов нашли сразу несколько победителей соревнований:
vekk
sir_derryk
kray_zemli
А также "ку!" в адресtsaregorodtsev1 за удачно нарисованное решение препредыдущей задачки.
Всем призы и респекты, за 8 взвешиваний из 2018 делением на три вычленяется одна фальшивка, пять за выход, итого = 2018 - 8 - 1 - 5 = 2004биткоина монеты. Ура! Есть на что Новый год отпраздновать :)
А поскольку натренированные извилины смогли справиться с 2018 монетами, то вычленить фальшивку из 13 монет за три взвешивания они точно смогут. Это моя любимая задачка :)
Ещё раз условие: на столе 13 монет и простые весы (тяжелее, легче или одинаково). Одна монета другого веса (легче или тяжелее - неизвестно).
Задача: за три (только за три!) взвешивания надо найти "неправильную" монету.
Решили? Отлично. Тогда вот ещё задачка на тему "2018".
Однажды уважаемый и пользующийся спросом винодел получил заказ на 2018 бочек вкусного напитка к Новому году (гуляют некоторые, да...). Винодел оказался ответственным и за неделю до Нового года все бочки стояли в подвале. Через 5 дней они должны быть отправлены заказчику, чтобы доехать вовремя.
Итак, ещё раз: подвал, 2018 бочек породистого напитка, 5 дней до отгрузки. Примерно вот так:
Но тут стало известно, что анонимныеалкоголики поборники абсолютной нравственности взломали замки на дверях, тайком проникли в погреба бездонных запасов винодела и засыпали отраву в одну (но только одну!) из 2018 бочек того самого главного напитка. Тот, кто попробует отравленное пойзоном питья - ему в тот же день поздно вечером или на следующий день рано утром станет совсем уж очень плохо. Он где-то ночером провозгласит себя трезвенником и после того - всё. Спиртного ни-ни ни капли вообще. Вот такие дела...
Итак: 2018 бочек напитка, однадезинфицирована отравлена антиалкогольным зельем. После пробы отравленного питья на следующий день - трезвенник.
У винодела пятеро пьющих работников, да и сам он тоже не совсем праведник. В первый день он сам сделал пробы вместе с рабочими, позвал свего брата и отца. То есть, в первый день они делали пробы ввосьмером. Но на следующий и далее дни... они как бы не смогли вообще участвовать в следственных экспериментах.
То есть, 1й день их было восемь, а потом уже только пьющие работники (если они не отравились безалкогольной заразой в первый день).
Внимание, вопрос:
Успеют ли они за 5 дней вычислить отравленную бочку - или им потребуется внешняя помощь? Как считаете?
Удачи в дегустациях! :)
математические приседания с призами на тему наступающего 2018-го продолжаются. Предыдущая задачка оказалась совсем не сложной - решение за 8 шагов нашли сразу несколько победителей соревнований:
vekksir_derrykkray_zemliА также "ку!" в адрес
tsaregorodtsev1 за удачно нарисованное решение препредыдущей задачки.Всем призы и респекты, за 8 взвешиваний из 2018 делением на три вычленяется одна фальшивка, пять за выход, итого = 2018 - 8 - 1 - 5 = 2004
А поскольку натренированные извилины смогли справиться с 2018 монетами, то вычленить фальшивку из 13 монет за три взвешивания они точно смогут. Это моя любимая задачка :)
Ещё раз условие: на столе 13 монет и простые весы (тяжелее, легче или одинаково). Одна монета другого веса (легче или тяжелее - неизвестно).
Задача: за три (только за три!) взвешивания надо найти "неправильную" монету.
Решили? Отлично. Тогда вот ещё задачка на тему "2018".
Однажды уважаемый и пользующийся спросом винодел получил заказ на 2018 бочек вкусного напитка к Новому году (гуляют некоторые, да...). Винодел оказался ответственным и за неделю до Нового года все бочки стояли в подвале. Через 5 дней они должны быть отправлены заказчику, чтобы доехать вовремя.
Итак, ещё раз: подвал, 2018 бочек породистого напитка, 5 дней до отгрузки. Примерно вот так:
Но тут стало известно, что анонимные
Итак: 2018 бочек напитка, одна
У винодела пятеро пьющих работников, да и сам он тоже не совсем праведник. В первый день он сам сделал пробы вместе с рабочими, позвал свего брата и отца. То есть, в первый день они делали пробы ввосьмером. Но на следующий и далее дни... они как бы не смогли вообще участвовать в следственных экспериментах.
То есть, 1й день их было восемь, а потом уже только пьющие работники (если они не отравились безалкогольной заразой в первый день).
Внимание, вопрос:
Успеют ли они за 5 дней вычислить отравленную бочку - или им потребуется внешняя помощь? Как считаете?
Удачи в дегустациях! :)
2017-12-20 08:14 (UTC)
В восемь чаш сливаем пробы из 253 бутылок.
Смещаемся на 84 штуки и снова разливаем в восемь чаш по 253 пробы.
И ещё раз так.
Трое отравились. Значит на второй день известны 85 бочек, в которых может быть зелье.
Делим на пять, по 17 бутылок. Вторую партию сдвигаем на 8.
Пропадают двое, остаются трое и, максимум, 9 бочек под подозрением.
Делим на троих. Один навсегда трезвеет.
Остаются двое и три бочки.
Двое в последний день берут на грудь по последней бочке. Оба спиваются на смерть - зелье в третьей, если выжил один, то в его.
Edited at 2017-12-20 08:15 (UTC)
2017-12-20 09:33 (UTC)
2017-12-20 10:31 (UTC)
int c[13]; int weight3(int i, int j, int k, int diff) { int d = c[i] - c[j]; if (d == 0) return k; else return d == diff ? i : j; } int weight2(int i, int j, int k) { return c[i] != c[k] ? i : j; } int weightall() { int w1 = (c[0] + c[1] + c[2] + c[3] ) - (c[4] + c[5] + c[6] + c[7]); if (w1 == 0) { int w2 = (c[8] + c[9] + c[10]) - (c[0] + c[1] + c[2]); if (w2 == 0) return weight2(11, 12, 0); else return weight3(8, 9, 10, w2); } else { int w2 = (c[0] + c[1] + c[2] + c[4]) - (c[3] + c[8] + c[9] + c[10]); if (w2 == 0) return weight3(5, 6, 7, -w1); else if (w1 == w2) return weight3(0, 1, 2, w1); else return weight2(3, 4, 8); } }Edited at 2017-12-20 10:32 (UTC)
2017-12-20 17:52 (UTC)
2017-12-20 17:55 (UTC)
int main() { for (int i=0; i < 13; ++i) c[i] = 0; c[rand() % 13] = 2*(rand() % 2) - 1; cout << weightall() << endl; }бочки, готовы!
2017-12-20 14:18 (UTC)
если все работники будут в норме, то останется на 2-й день им X, иначе Y.
т.к. с каждым днём число пробующих уменьшается, то легко заметить, что изначальные возможности у 5-х в 3 раза больше чем у 4-х (6*5*4*3=360 и 5*4*3*2=120), что приводит к выводу X=3*Y, округленно Y=119, X=356, а для простоты дальнейших объяснений можно даже взять 120 и 360, что позволяет провести эту процедуру до 2040 года
1) если все работники в норме, то 360/6/5/4=3 бочки на 3х на посл. день
2) если 1 работник сразу вышел, то 120/5/4/3=2 бочки на 2х на посл. день
ура, классная задача!
Edited at 2017-12-20 14:19 (UTC)
2017-12-20 16:27 (UTC)
В предпоследний (четвертый) день N алкашей пьют порции, собранные каждая из N бочек и N+1 бочку не трогают, т.е. могут найти среди N2+N+1 бочек. Тогда в последний день, либо N-1 алкашей разбираются с N бочками, либо N алкашей с N+1 бочкой.
Третий день. N порций по (N-1)2+(N-1)+1 бочек и в стороне N*N+N+1 бочек, всего N3+2N+1 бочек.
Второй день. N4-2N3+5N2+1 бочек. Если осталось 5 алкашей, то найдут среди 501 бочки, если осталось 4, то найдут среди 209 бочек.
Первый день. 5 алкашам наливаем из 209 бочек, остальным дегустаторам наливаем из 501 бочки, в стороне оставляем 501 бочку. Итого, можно найти среди 5*209+4*501 = 3049 бочек.
Всего их, правда, 2018. Значит, 1031 заведомо годных бочек придётся позаимствовать с другого завода.
2017-12-20 18:07 (UTC)
Тоже хорошая задачка.
(там выше по тексту :)
2017-12-20 22:06 (UTC)
Вспоминаем теорию кода Хэмминга - и понимаем что у нас есть 2018 разрядов и один из них "содержит ошибку"
Далее по коду Хэмминга, для простоты:
1) ставим всех в ряд, и работников и бочки. Проверяющие занимают место степеней двойки:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024
бочки ставим на места:
3, 5, 6, 7, 9-15, 17-31, 33-63, 65-127, 129-255, 257-511, 513-1023, 1025-2029
Соответственно, номер места говорит о том, кто какие бочки пробует:
в зависимости от двоичного представления номера бочки в этом ряду: если в нужном разряде есть единица - пробуем, нет - идем дальше.
2) так как проверяющих у нас маловато, то:
2,1) первый день: винодел и его сыновья встают на на места 1, 2, 4
работники на места 64, 128, 256, 512, 1024 (побережем их для дальнейшей работы и снизим вероятность что все разом нарвутся на отравленную бочку)
пробуют.
2,2) Дальше выбывает винодел и сыновья, оставшиеся работники (если могут пить) проверяют места 8, 16, 32 и узнают кто уже пить не может.
2,3) находим отравленную бочку.
Больше всего пробуют винодел с сыновьями - у них и больше риск нарваться на отравленную бочку, но и участвуют они один день только.
Edited at 2017-12-20 22:09 (UTC)
2017-12-21 10:33 (UTC)
2017-12-21 14:49 (UTC)
2017-12-21 18:04 (UTC)
Другие ветки алгоритма отбрасываются как...типа неполиткорректные? Или почему 1024 бочки просто игнорируются вообще?
Для продолжения дискуссии о задачке я настоятельно намекаю, что хотя бы один вопрос выше - хоть одно надо ответить.
2017-12-21 07:35 (UTC)
1. 13-ю монету откладываем.
2. Первое взвешивание. Оставшиеся 12 монет делим на 2 равные части и ставим на весы. Если веса равны, то фальшивая - 13-я монета и процесс окончен.
3. Второе взвешивание "хитрое". Задача этого взвешивания - выровнять веса чаш с их содержимым или без него путем последовательного одновременного снятия по одной монете с каждой из чаш.
Непосредственно перед выравниванием весов у нас в руках будут 2 монеты, одна из которых фальшивая.
4. Третье взвешивание. Зная, что 13-я монета не фальшивая и имея на руках 2 монеты, одна из которых фальшивая, кладем на одну чашу 13-ю монету, на другую - любую из двух.
Если веса равны, то фальшивая - та что не на весах, если нет, то та что на весах, но не 13-я.
2017-12-21 10:32 (UTC)
2017-12-21 13:24 (UTC)
1. Отбрасываем 3 монеты.
2. Оставшиеся 10 монет разбиваем на 2 равные части и взвешиваем, если равны, то из 3-х отброшенных за 2 оставшихся взвешивания элементарно находим фальшивку.
Если не равны, то запоминаем, которая из групп тяжелее, а которая легче.
3. Снимаем части с весов, не перемешивая, отбрасываем из каждой части по 1 й монете, в результате в каждой части остается по 4 монеты.
4. Заменяем по 2 монеты между частями, запоминая, при этом, какая из монет к какой части принадлежала в предыдущем взвешивании.
5. Взвешиваем полученные на предыдущем этапе 2 части по 4 монеты. Если веса равны, то из отброшенных на предыдущем этапе 2-х монет за 1 оставшееся взвешивание определяем фальшивку.
6. Отбрасываем монеты, которые на первом взвешивании были в легкой части, а оказались в тяжелой и наоборот. Осталось 2 части по 2 монеты в каждой, одна из частей легче другой.
7. Заменяем по 1-й монете между частями, запоминая, какая из монет в какой части была.
8. Здесь у нас 2 части по 2 монеты, одна легче, другая тяжелее, причем в каждой из частей есть по 1 монете, которая в результате замены осталась на своем месте - заменяем любую из них
на одну из отброшенных в пункте 1.
9. Взвешиваем - если веса равны, то фальшивка - замененная в предыдущем пункте монета.
10. Если веса не равны, то останется только одна монета, которая одновременно была или в более тяжелой или в более легкой части во всех трех взвешиваниях с учетом замен и она фальшивая.
Edited at 2017-12-21 13:27 (UTC)
2017-12-21 17:59 (UTC)
Ой, а можно определиться - сколько взвешиваний уже было? Я хочу три. Три штуки. Ровно три!
2017-12-22 00:47 (UTC)
Взвешивание 1.
1.1 Отбрасываем 3 монеты.
1.2 Оставшиеся 10 монет разбиваем на 2 равные части и взвешиваем, если части равны, то из 3-х отброшенных монет за 2 оставшихся взвешивания элементарно находим фальшивку, а если не равны,
то запоминаем, какая из групп тяжелее, а какая легче.
Взвешивание 2.
2.1 Снимаем части с весов, не перемешивая, отбрасываем из каждой части по одной монете, в результате в каждой части остается по 4 монеты.
2.2 Заменяем по 2 монеты между частями, запоминая, при этом, какая из монет к какой части принадлежала в первом взвешивании.
2.3 Взвешиваем полученные на предыдущем этапе 2 части по 4 монеты. Если веса равны, то из отброшенных в пункте (2.1) 2-х монет за 1 оставшееся взвешивание определяем фальшивку.
Взвешивание 3.
3.1 Отбрасываем монеты, которые на первом взвешивании были в легкой части, а на втором оказались в тяжелой и наоборот. Осталось 2 части по 2 монеты в каждой, одна из частей легче другой.
3.2 Заменяем по 1-й монете между частями, запоминая, какая из монет в какой части была.
3.3 Здесь у нас 2 части по 2 монеты, одна легче, другая тяжелее, в каждой из частей есть по 1 монете, которая в результате замены из пункта (3.2) осталась в своей части - заменяем любую из них
на одну из отброшенных в пункте (1.1).
3.4 Взвешиваем - если веса равны, то фальшивка - замененная в предыдущем пункте монета.
3.5 Если веса не равны, то останется только одна монета, которая одновременно была или в более тяжелой или в более легкой части во всех трех взвешиваниях с учетом замен и она фальшивая ("кю!").
Визуализация:
Edited at 2017-12-22 02:29 (UTC)
2017-12-22 08:18 (UTC)
2 убрали, 2 переставили.
Если равно, то одна из убранных.
Если весы в другую сторону, то одна из переставленных.
Но если весы показывают всё то же неравенство, то получается 6 монет (3+3) и одно взвешивание. Как из 6 монет за одну пробу вычленить фальшивку - я так и не понял...
2017-12-22 08:53 (UTC)
2017-12-22 13:47 (UTC)
1) 1-2-3-4-5 > 6-7-8-9-10.
левая чашка тяжелее правой.
1-6 выкинули, 2-7 и 3-8 переставили.
2) 7-8-4-5 > 2-3-9-10.
Опять левая тяжелее.
На 3е взвешивание остаются:
4-5 и 9-10.
И что дальше?
2017-12-22 17:42 (UTC)
Как выясняется, разбивать нужно на 3 группы, по 4, 4, и 5 монет. Далее только ключевой момент решения. Взвешиваем (первое взвешивание) 2 группы по 4 монеты. Если веса не равны, заменяем в любой чаше 3 монеты на монеты из 3-й группы (они точно не фальшивые), а оставшуюся на чаше монету меняем местами с любой монетой из другой чаши. Снова взвешиваем (второе). Тогда, если чаши выровняются, то фальшивка - одна из 3-х замененных на заведомо не фальшивые монет из 3-й группы, причем мы вдобавок можем сказать, легче или тяжелее фальшивка, исходя из чаши, с которой проходила замена - если с более тяжелой, то тяжелее и наоборот. Если чаши останутся на месте, то фальшивка - одна из 3-х монет, замена которых не производилась, причем мы так-же можем сказать, тяжелее она или легче. Если же чаши при взвешивании поменяются местами, то фальшивая - одна из двух монет, которые мы меняли между чашами, причем тяжелее она или легче - неизвестно, но это и не критично. Дальше - дело техники, остальные моменты тоже.
Edited at 2017-12-23 12:35 (UTC)
2017-12-23 15:28 (UTC)
А если равны??
2017-12-23 17:07 (UTC)
На одну чашу помещаем любые 3 монеты из 5, на другую 3 заведомо нефальшивые монеты - любые 3 из двух первых групп.
Взвешиваем (второе взвешивание), если веса равны, то фальшивая - одна из двух оставшихся из 3-й группы монет.
Если не равны, то фальшивая монета среди 3-х монет из 3-ей группы, находящихся на весах, причем нам теперь известно, тяжелее она или легче остальных.
Все эти ситуации легко разрешимы за одно оставшееся взвешивание.
В случае равенства весов второго взвешивания, в третьем взвешивании ставим на весы одну из двух монет-кандидатов в фальшивки и заведомо нефальшивую. Если
веса равны, то фальшивая та, что не на весах, иначе - та что на весах.
В случае неравенства весов во втором взвешивании, в третьем нам предстоит найти фальшивую монету из 3-х кандидатов, при этом нам уже известно, легче
она или тяжелее нефальшивых. Для этого ставим на весы любые 2 монеты из 3-х. Если веса равны, то фальшивая та, что не на весах, если нет, то фальшивая та
что легче или тяжелее, в зависимости от того, легче или тяжелее остальных фальшивая монета, о чем нам стало известно по результатам второго взвешивания.
Edited at 2017-12-23 17:08 (UTC)
Решение задачи
2017-12-22 14:38 (UTC)
Мы разбиваем все бочки на 8 групп бочек по 252-253 бочки.
Из 3 человек мы создаём 7 тестовых групп, которые пробуют первые 7 групп бочек. Вино из последней группы бочек не пробует никто.
Тестовые группы :
1-ая группа - 1-ый человек
2-ая группа - 2-ой человек
3-ая группа - 3-ий человек
4-ая группа -1-ый и 2-ой человек
5-ая группа - 1-ый и 3-ий человек
6-ая группа - 2-ой и 3-ий человек
7-ая группа - 1-ый и 2-ой и 3-ий человек
8-ая группа - без людей
Все группы бочек не пересекаются. Каждую группу бочек пробует только одна тестовая группа.
Так как отравленное вино только в одной бочке. То только в одной группе будут все отравленные.
К примеру, если отравились 1-ый и 3-ий человек, то отравленное вино в "5-ой группе" бочек.
Если не травился никто, то отравленное вино в "8-ой группе бочек".
Могут отравиться и все 3 человека, значит отравленное вино в "7-группе" бочек.
Таким образом мы найдём одну группу бочек, где есть отравленная. В этой группе будет максимально 253 бочкти (округляя в большую сторону).
И гарантированно осталось 5 человек после первого дня (они не участвовали в дегустации в первый день).
Во второй день мы делим бочки на 6 групп по 42-43 бочки, где 5 человек пробуют первые 5 групп, один человек пробует вино только из одной группы, а последнею не пробует никто. Так мы сократим количество возможных бутылок до 43. И уберём одного рабочего.
В третий день у нас есть 43 подозрительных бочки и 4 человека. По той же схеме делим бочки на 5 групп по 8-9 бочек, проводим дегустацию. У нас останется 9 возможных бутылок, и 3 дегустатора.
В четвёртый день, делим 9 бочек на 4 группы по 2-3 бочки.
Три дегустатора и пустая группа. Находи подозрительную группу из 3 бочек.
В пятый день мы имеем 3 подозрительные бочки, и 2 дегустатора. По той же схеме, 1-ыю пробует 1-ую бочку, 2-ой пробует 2-ую бочку. Последнюю бочку не пробует никто.
Так мы находим отравленную бочку.
Задача решена.
За 5 дней мы нашли отравленную бочку.
Во всех днях для простоты мы выбирали самый "неудачный вариант", то есть большую группу бочек.
Гробер Михаил, Ростов-на-Дону, 10 класс.
Edited at 2017-12-26 12:52 (UTC)
Новое решение
2018-01-07 18:44 (UTC)
Нашел еще более быстрое решение задачи. Но все уйдет 4 дня и одна ночь.
За основу берем прошлое решение, но меняем чуть алгоритм.
Итак.
Идея первая. Нужно максимально использовать 3-х человек, которые уходят после первого дня.
И сразу используем 5 рабочих.
Разбиваем все бочки на две большие группы.
Группа А - 1818 бочек и группа Б - 200 бочек.
В первый день начальники пробуют вино из группы А рабочие пробуют вино из Группы Б.
Мы разбиваем все бочки группы А на 8 групп бочек по 227-228 бочек.
Из 3 человек начальников мы создаём 7 тестовых групп, которые пробуют первые 7 групп бочек. Вино из последней группы бочек не пробует никто. То есть всего 8 виртуальных групп.
Тестовые группы :
1-ая группа - 1-ый человек
2-ая группа - 2-ой человек
3-ая группа - 3-ий человек
4-ая группа -1-ый и 2-ой человек
5-ая группа - 1-ый и 3-ий человек
6-ая группа - 2-ой и 3-ий человек
7-ая группа - 1-ый и 2-ой и 3-ий человек
8-ая группа - без людей
Все группы бочек не пересекаются. Каждую группу бочек пробует только одна тестовая группа.
Так как отравленное вино только в одной бочке. То только в одной группе будут все отравленные.
К примеру, если отравились 1-ый и 3-ий человек, то отравленное вино в "5-ой группе" бочек.
Если не травился никто, то отравленное вино в "8-ой группе бочек".
Могут отравиться и все 3 человека, значит отравленное вино в "7-группе" бочек.
В первый же день рабочие проводят дегустацию 200 бочек на 5 человек, по 40 бочек на человека.
Дальше задача распадается на две. Или отравление будет в группе А или в группе Б.
Если в группе А, то далее:
Таким образом мы найдём одну группу бочек, где есть отравленная. В этой группе будет максимально 228 бочек ( 1818/8 округляя в большую сторону).
И гарантированно осталось 5 человек после первого дня (они не участвовали в дегустации в первый день).
Во второй день мы делим бочки на 6 групп по 228/6=38 бочек, где 5 человек пробуют первые 5 групп, один человек пробует вино только из одной группы, а последнею не пробует никто. Так мы сократим количество возможных бочек до 38. И уберём одного рабочего.
В третий день у нас есть 38 подозрительных бочки и 4 человека. По той же схеме делим бочки на 5 групп по 8 бочек, проводим дегустацию. У нас останется 8 возможных бутылок, и 3 дегустатора.
Теперь еще раз создаем тестовые группы дегустаторов, 8 групп из 3 человек.
1-ая группа - 1-ый человек
2-ая группа - 2-ой человек
3-ая группа - 3-ий человек
4-ая группа -1-ый и 2-ой человек
5-ая группа - 1-ый и 3-ий человек
6-ая группа - 2-ой и 3-ий человек
7-ая группа - 1-ый и 2-ой и 3-ий человек
8-ая группа - без людей
Проводим дегустацию 8 бочек 8-ми группами. И сразу находим отравленную бочку. (об этом мы узнаем га утро пятого дня).
Задача решена. Дегустации проводились 4 дня, а ответ мы получаем на пятый день.
Задача решена.
За 5 дней мы нашли отравленную бочку.
Если отравленная бочка в группе бочек Б, то уже на второй день мы имеем 40 подозрительных бочек и 4 рабочих.
На второй день проводим дегустацию 40 бочек, 32 бочки пробуют 4 человека по 8 бочек и 8 бочек не пробует никто. То есть 40 бочек на 5 виртуальных групп.
На третий день имеем 8 бочек под подозрением и 3 рабочих. Такой расклад у нас уже есть. Создаем 8 групп и находим отравленную бочку уже на утро 4-го дня (то есть еще быстрее).
Все задача решена.