Цифровой 2018 - часть 5.

Previous Entry Поделиться Next Entry
20 декабря, 2017
e_kaspersky
Девочки и мальчики,

математические приседания с призами на тему наступающего 2018-го продолжаются. Предыдущая задачка оказалась совсем не сложной - решение за 8 шагов нашли сразу несколько победителей соревнований:

vekk
sir_derryk
kray_zemli

А также "ку!" в адрес tsaregorodtsev1 за удачно нарисованное решение препредыдущей задачки.

Всем призы и респекты, за 8 взвешиваний из 2018 делением на три вычленяется одна фальшивка, пять за выход, итого = 2018 - 8 - 1 - 5 = 2004 биткоина монеты. Ура! Есть на что Новый год отпраздновать :)

А поскольку натренированные извилины смогли справиться с 2018 монетами, то вычленить фальшивку из 13 монет за три взвешивания они точно смогут. Это моя любимая задачка :)

Ещё раз условие: на столе 13 монет и простые весы (тяжелее, легче или одинаково). Одна монета другого веса (легче или тяжелее - неизвестно).

Задача: за три (только за три!) взвешивания надо найти "неправильную" монету.

Решили? Отлично. Тогда вот ещё задачка на тему "2018".

Однажды уважаемый и пользующийся спросом винодел получил заказ на 2018 бочек вкусного напитка к Новому году (гуляют некоторые, да...). Винодел оказался ответственным и за неделю до Нового года все бочки стояли в подвале. Через 5 дней они должны быть отправлены заказчику, чтобы доехать вовремя.

Итак, ещё раз: подвал, 2018 бочек породистого напитка, 5 дней до отгрузки. Примерно вот так:

P1000187

P1000188

Но тут стало известно, что анонимные алкоголики поборники абсолютной нравственности взломали замки на дверях, тайком проникли в погреба бездонных запасов винодела и засыпали отраву в одну (но только одну!) из 2018 бочек того самого главного напитка. Тот, кто попробует отравленное пойзоном питья - ему в тот же день поздно вечером или на следующий день рано утром станет совсем уж очень плохо. Он где-то ночером провозгласит себя трезвенником и после того - всё. Спиртного ни-ни ни капли вообще. Вот такие дела...

Итак: 2018 бочек напитка, одна дезинфицирована отравлена антиалкогольным зельем. После пробы отравленного питья на следующий день - трезвенник.

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

То есть, 1й день их было восемь, а потом уже только пьющие работники (если они не отравились безалкогольной заразой в первый день).

Внимание, вопрос:

Успеют ли они за 5 дней вычислить отравленную бочку - или им потребуется внешняя помощь? Как считаете?

Удачи в дегустациях! :)
Метки:
Previous Entry Поделиться Next Entry

Записи из этого журнала по тегу «chtogdekogda»

  • Римская разминка.

    Я давно привык, что мои переходы, перепрыги, переплывы и другие средства передвижения по глобусу этого мира укладываются в шаблон чемодан -…

  • Цифровой 2018 - часть 4. О деньгах.

    Отлично получается! Совершенно необычные и удивительно красивые решения выдают на-гора наши самые мат-продвинутые читатели. Спасибо и поздравляю!…

  • Цифровой 2018 - часть 3.

    Всем привет, Как я уже понял, для активного решения интересных задачек требуется некоторая небольшая мотивация - так мне не жалко! Но об этом чуть…


Успеют.

В восемь чаш сливаем пробы из 253 бутылок.
Смещаемся на 84 штуки и снова разливаем в восемь чаш по 253 пробы.
И ещё раз так.

Трое отравились. Значит на второй день известны 85 бочек, в которых может быть зелье.
Делим на пять, по 17 бутылок. Вторую партию сдвигаем на 8.
Пропадают двое, остаются трое и, максимум, 9 бочек под подозрением.

Делим на троих. Один навсегда трезвеет.
Остаются двое и три бочки.

Двое в последний день берут на грудь по последней бочке. Оба спиваются на смерть - зелье в третьей, если выжил один, то в его.

Edited at 2017-12-20 08:15 (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)

Извините, но в этом потоке мыслей я на заметил старомодного "main() {}"

int main()
{
  for (int i=0; i < 13; ++i) c[i] = 0;
  c[rand() % 13] = 2*(rand() % 2) - 1;
  cout << weightall() << endl;
}

бочки, готовы!

diverf1

2017-12-20 14:18 (UTC)

логика в том, что если останутся в 1-й день все работники, то и работы у них должно быть больше, отсюда вылазит формула 3*X+X+5*Y=2018, где X=кол-во бочек на пробу начальства, а Y-работникам.

если все работники будут в норме, то останется на 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)

В последний (пятый) день N алкашей могут найти отраву среди N+1 бочек (одну не пьют).

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

13 монет есть за 3 взвешивания.
Тоже хорошая задачка.
(там выше по тексту :)

Если не оговорено сколько может продегустировать один работник за один день, то предположим что либо возможности безграничны, либо для "отравления" достаточно одной капли/ложки/глотка из неправильной бочки.
Вспоминаем теорию кода Хэмминга - и понимаем что у нас есть 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)

А что делать, если отравлена одна из 1024 бочек? На следующий день останется всего 4 дегустатора.. Незачёт.

Нам на второй день нужно всего три дегустатора - на места 8, 16, 32 .

Что, только они?
Другие ветки алгоритма отбрасываются как...типа неполиткорректные? Или почему 1024 бочки просто игнорируются вообще?

Для продолжения дискуссии о задачке я настоятельно намекаю, что хотя бы один вопрос выше - хоть одно надо ответить.

Все -таки рискну предложить вариант решения задачи с монетами. Скажу сразу, что ожидаемого изначально решения найти не удалось, поэтому пришлось углубиться в сам процесс взвешивания - то есть ключ в ответе на вопрос - что есть взвешивание?
1. 13-ю монету откладываем.
2. Первое взвешивание. Оставшиеся 12 монет делим на 2 равные части и ставим на весы. Если веса равны, то фальшивая - 13-я монета и процесс окончен.
3. Второе взвешивание "хитрое". Задача этого взвешивания - выровнять веса чаш с их содержимым или без него путем последовательного одновременного снятия по одной монете с каждой из чаш.
Непосредственно перед выравниванием весов у нас в руках будут 2 монеты, одна из которых фальшивая.
4. Третье взвешивание. Зная, что 13-я монета не фальшивая и имея на руках 2 монеты, одна из которых фальшивая, кладем на одну чашу 13-ю монету, на другую - любую из двух.
Если веса равны, то фальшивая - та что не на весах, если нет, то та что на весах, но не 13-я.

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

Тогда дубль два, если позволите.
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)

> 10. Если веса не равны

Ой, а можно определиться - сколько взвешиваний уже было? Я хочу три. Три штуки. Ровно три!

На самом деле их там и так только 3, остальное - подготовка и анализ результатов, но действительно это не очевидно, поэтому исправляю описание (добавил подпункты и причесал формулировки), плюс добавил визуализацию:

Взвешивание 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)

Второе взвешивание:
2 убрали, 2 переставили.
Если равно, то одна из убранных.
Если весы в другую сторону, то одна из переставленных.
Но если весы показывают всё то же неравенство, то получается 6 монет (3+3) и одно взвешивание. Как из 6 монет за одну пробу вычленить фальшивку - я так и не понял...

"3.1 Отбрасываем монеты, которые на первом взвешивании были в легкой части, а на втором оказались в тяжелой и наоборот. Осталось 2 части по 2 монеты в каждой, одна из частей легче другой." - то есть после второго взвешивания мы убираем 4 монеты из 8, которые в нем участвовали и на третье остается 4 монеты, плюс история их взвешиваний. Если смотреть картинку, то выбрасываются монеты 1,2,7 и 8, так как монеты 1 и 2 в первом взвешивании находились в составе более тяжелой группы (соответствующая полоска изображена ниже, это как бы чаша весов), а во втором - в составе более легкой; монеты 7 и 8, наоборот - в первом - в более легкой группе, во втором - в более тяжелой.

Ну, допустим..

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.
И что дальше?

А дальше 13-9 и 5-10 и уж как повезет. А повезет с вероятность 3/13+10/13*(2/10+8/10*(1/4+3/4*1/2)), то есть примерно 0.77, "никогда ещё Штирлиц не был так близок к провалу".
Как выясняется, разбивать нужно на 3 группы, по 4, 4, и 5 монет. Далее только ключевой момент решения. Взвешиваем (первое взвешивание) 2 группы по 4 монеты. Если веса не равны, заменяем в любой чаше 3 монеты на монеты из 3-й группы (они точно не фальшивые), а оставшуюся на чаше монету меняем местами с любой монетой из другой чаши. Снова взвешиваем (второе). Тогда, если чаши выровняются, то фальшивка - одна из 3-х замененных на заведомо не фальшивые монет из 3-й группы, причем мы вдобавок можем сказать, легче или тяжелее фальшивка, исходя из чаши, с которой проходила замена - если с более тяжелой, то тяжелее и наоборот. Если чаши останутся на месте, то фальшивка - одна из 3-х монет, замена которых не производилась, причем мы так-же можем сказать, тяжелее она или легче. Если же чаши при взвешивании поменяются местами, то фальшивая - одна из двух монет, которые мы меняли между чашами, причем тяжелее она или легче - неизвестно, но это и не критично. Дальше - дело техники, остальные моменты тоже.

Edited at 2017-12-23 12:35 (UTC)

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

Edited at 2017-12-23 17:08 (UTC)

Идея первая. Нужно максимально использовать 3-х человек, которые уходят после первого дня.

Мы разбиваем все бочки на 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)

Добрый день.
Нашел еще более быстрое решение задачи. Но все уйдет 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-го дня (то есть еще быстрее).

Все задача решена.


?

Log in

No account? Create an account