Сообщение Re[4]: Задачке 45+ лет. от 25.02.2020 8:34
Изменено 25.02.2020 19:45 Erop
Re[4]: Задачке 45+ лет.
Здравствуйте, NovaMind, Вы писали:
NM>Меня опять терзают смутные сомнения! (с) Иван IV.
NM>Уже Семь недель висит задачка.
NM>Вы... как-то долго...
Я как увидел -- сразу написал. Но я эту задачку раньше знал уже, так что я вообще мгновенно в данном случае.
Правда я всё равно не понимаю, что там можно было тупить?
Там же дерево решений мизерное.
И всегда можно просто попробовать его перебрать с очевидными отсечениями, так, что бы либо доказать, что задачу решить нельзя, либо построить решение.
Очевидно, что из 27 теоретически возможных результатов трёх взвешиваний, надо разделить 24 ситуации. То есть "подклеить" к другой ситуации, или просто заранее знать, мы можем не более трёх комбинаций результатов взвешиваний.
Очевидно, что первых ход -- это взвешивание 4 х 4, так как для 3 х 3 и 5 х 5 потом не получится за 2 взвешивания (9 разных отчётов) выбрать из 10 или 12 ситуаций.
Если 4х4, то либо получаем в ре-те равенство, и надо выбрать из 8 оставшихся вариантов (какая из 4-х монет и тяжелее или легче) Если неравенство, то тоже из 8 (какая из участвовавших во взвешивании фальшивая, так как кто легче или тяжелее уже знаем). Ок.
Например, рассмотрим случай равенства.
Ясно, что нужно так взвешивать, что бы все три исхода были информативны. Поэтому, 2 х 2 из только оставшихся взвешивать неверно, так как не можем получить равенство, а 1 х 1 не верно, так как в случае равенства не понятно, как решить задачу про две монеты и одно взвешивание. Там вроде бы всего два хода остаётся возможных -- сравнить две оставшиеся или сравнить одну из оставшихся с нефальшивой. Ну и все 4 оставшиеся если сравнить с 4 настоящими, тоже мы узнаем тяжелее настоящая или легче, но как потом из 4 за одно взвешивание с тремя исходами выбрать не получится.
Значит максимум 3 подозрительные монеты можно отложить на третье взвешивание, а из оставшихся 5 выбрать за два.
Думаем о том, как связаны позиции монет при первом взвешивании и во втором.
Ясно, что монета может остаться там же, где была, может быть отложена и может оказаться на другой чашке весов.
Ясно, что каждая из групп не может превышать 3, так как, если результат второго взвешивания покажет на эту группу, то потом за третье мы из более 3 вариантов не выберем.
Ну и получаем, что или мы три оставляем на своих местах, две перекладываем и три откладываем. Или две оставляем на местах, три перекладываем и три откладываем, или три оставляем на местах, три перекладываем, а две откладываем. Добиваем до ровного числа монет 4 оставшимися, ну и дальше всё тривиально.
Но, даже если не догадаться до идеи о связи первого и второго взвешивания, и ограничить себя только вариантами, когда монета или не участвует во взвешивании, или остаётся на месте. Ок. Предположим мы так "заблудились", хотя мне не понятно, как так можно, если стремиться перебрать ВСЕ варианты (напоминаю, что мы пробуем найти решение или доказать, что его нет).
Но, положим, мы так ошиблись. То сразу возникает вопрос, а как так может получиться, что весы во втором взвешивании покажут другой результат, чем в первом?
Ясно, что позволить себе такую стратегию, при которой такой исход невозможен, мы себе не можем, так как за всего два возможных исхода мы лучше чем до 4 число подозрительных не уменьшим, и всё-таки придётся "изобрести" перекладывание монет между чашками
Вроде бы это полное рассуждение, и оно даёт ВСЕ возможные решения. О чём тут можно думать 2 недели и толпой мне решительно не ясно
NM>P.S.
NM>Это я за папу вступаюсь.
Не надо вступаться, надо попробовать решить таки НОРМАЛЬНО какую-нибудь похожую задачку. Например, для аналогичной задачи для 13 монет (26) вариантов, трёх взвешиваний (27 вариантов результатов взвешивания) можно определить фальшивую и знак её отличия от остальных?
NM>Меня опять терзают смутные сомнения! (с) Иван IV.
NM>Уже Семь недель висит задачка.
NM>Вы... как-то долго...
Я как увидел -- сразу написал. Но я эту задачку раньше знал уже, так что я вообще мгновенно в данном случае.
Правда я всё равно не понимаю, что там можно было тупить?
Там же дерево решений мизерное.
И всегда можно просто попробовать его перебрать с очевидными отсечениями, так, что бы либо доказать, что задачу решить нельзя, либо построить решение.
Очевидно, что из 27 теоретически возможных результатов трёх взвешиваний, надо разделить 24 ситуации. То есть "подклеить" к другой ситуации, или просто заранее знать, мы можем не более трёх комбинаций результатов взвешиваний.
Очевидно, что первых ход -- это взвешивание 4 х 4, так как для 3 х 3 и 5 х 5 потом не получится за 2 взвешивания (9 разных отчётов) выбрать из 10 или 12 ситуаций.
Если 4х4, то либо получаем в ре-те равенство, и надо выбрать из 8 оставшихся вариантов (какая из 4-х монет и тяжелее или легче) Если неравенство, то тоже из 8 (какая из участвовавших во взвешивании фальшивая, так как кто легче или тяжелее уже знаем). Ок.
Например, рассмотрим случай равенства.
Ясно, что нужно так взвешивать, что бы все три исхода были информативны. Поэтому, 2 х 2 из только оставшихся взвешивать неверно, так как не можем получить равенство, а 1 х 1 не верно, так как в случае равенства не понятно, как решить задачу про две монеты и одно взвешивание. Там вроде бы всего два хода остаётся возможных -- сравнить две оставшиеся или сравнить одну из оставшихся с нефальшивой. Ну и все 4 оставшиеся если сравнить с 4 настоящими, тоже мы узнаем тяжелее настоящая или легче, но как потом из 4 за одно взвешивание с тремя исходами выбрать не получится.
Значит максимум 3 подозрительные монеты можно отложить на третье взвешивание, а из оставшихся 5 выбрать за два.
Думаем о том, как связаны позиции монет при первом взвешивании и во втором.
Ясно, что монета может остаться там же, где была, может быть отложена и может оказаться на другой чашке весов.
Ясно, что каждая из групп не может превышать 3, так как, если результат второго взвешивания покажет на эту группу, то потом за третье мы из более 3 вариантов не выберем.
Ну и получаем, что или мы три оставляем на своих местах, две перекладываем и три откладываем. Или две оставляем на местах, три перекладываем и три откладываем, или три оставляем на местах, три перекладываем, а две откладываем. Добиваем до ровного числа монет 4 оставшимися, ну и дальше всё тривиально.
Но, даже если не догадаться до идеи о связи первого и второго взвешивания, и ограничить себя только вариантами, когда монета или не участвует во взвешивании, или остаётся на месте. Ок. Предположим мы так "заблудились", хотя мне не понятно, как так можно, если стремиться перебрать ВСЕ варианты (напоминаю, что мы пробуем найти решение или доказать, что его нет).
Но, положим, мы так ошиблись. То сразу возникает вопрос, а как так может получиться, что весы во втором взвешивании покажут другой результат, чем в первом?
Ясно, что позволить себе такую стратегию, при которой такой исход невозможен, мы себе не можем, так как за всего два возможных исхода мы лучше чем до 4 число подозрительных не уменьшим, и всё-таки придётся "изобрести" перекладывание монет между чашками
Вроде бы это полное рассуждение, и оно даёт ВСЕ возможные решения. О чём тут можно думать 2 недели и толпой мне решительно не ясно
NM>P.S.
NM>Это я за папу вступаюсь.
Не надо вступаться, надо попробовать решить таки НОРМАЛЬНО какую-нибудь похожую задачку. Например, для аналогичной задачи для 13 монет (26) вариантов, трёх взвешиваний (27 вариантов результатов взвешивания) можно определить фальшивую и знак её отличия от остальных?
Re[4]: Задачке 45+ лет.
Здравствуйте, NovaMind, Вы писали:
NM>Меня опять терзают смутные сомнения! (с) Иван IV.
NM>Уже Семь недель висит задачка.
NM>Вы... как-то долго...
Я как увидел -- сразу написал. Но я эту задачку раньше знал уже, так что я вообще мгновенно в данном случае.
Правда я всё равно не понимаю, что там можно было тупить?
Там же дерево решений мизерное.
И всегда можно просто попробовать его перебрать с очевидными отсечениями, так, что бы либо доказать, что задачу решить нельзя, либо построить решение.
Очевидно, что из 27 теоретически возможных результатов трёх взвешиваний, надо разделить 24 ситуации. То есть "подклеить" к другой ситуации, или просто заранее знать, мы можем не более трёх комбинаций результатов взвешиваний.
Очевидно, что первых ход -- это взвешивание 4 х 4, так как для 3 х 3 и 5 х 5 потом не получится за 2 взвешивания (9 разных отчётов) выбрать из 10 или 12 ситуаций.
Если 4х4, то либо получаем в ре-те равенство, и надо выбрать из 8 оставшихся вариантов (какая из 4-х монет и тяжелее или легче) Если неравенство, то тоже из 8 (какая из участвовавших во взвешивании фальшивая, так как кто легче или тяжелее уже знаем). Ок.
Например, рассмотрим случай равенства.
Ясно, что нужно так взвешивать, что бы все три исхода были информативны. Поэтому, 2 х 2 из только оставшихся взвешивать неверно, так как не можем получить равенство, а 1 х 1 не верно, так как в случае равенства не понятно, как решить задачу про две монеты и одно взвешивание. Там вроде бы всего два хода остаётся возможных -- сравнить две оставшиеся или сравнить одну из оставшихся с нефальшивой. Ну и все 4 оставшиеся если сравнить с 4 настоящими, тоже мы узнаем тяжелее настоящая или легче, но, потом из 4 за одно взвешивание с тремя исходами выбрать не получится. И ещё можно подозрительные взвешивать в духе 3х1 дополняя настоящими. Но тут тоже не получится узнать какая монета фальшивая и тяжелее ли она.
Значит надо три подозрительные сравнить с тремя настоящими. Если получим равенство, то фальшивая последняя невзвешенная, и за последний ход узнаём тяжелее она или легче.
Если три окажутся тяжелее (или легче) мы узнаем тяжелее ли фальшивая и за последнее взвешивание 1х1 выберем из этих трёх нужную.
Если же первое взвешивание показало неравенство, то у нас 8 подозрительных монет, про каждую из которых мы знаем тяжелее ли она, если она фальшивая.
Значит максимум 3 подозрительные монеты можно отложить на третье взвешивание, а из оставшихся 5 выбрать за два.
Думаем о том, как связаны позиции монет при первом взвешивании и во втором.
Ясно, что монета может остаться там же, где была, может быть отложена и может оказаться на другой чашке весов.
Ясно, что каждая из групп не может превышать 3, так как, если результат второго взвешивания покажет на эту группу, то потом за третье мы из более 3 вариантов не выберем.
Ну и получаем, что или мы три оставляем на своих местах, две перекладываем и три откладываем. Или две оставляем на местах, три перекладываем и три откладываем, или три оставляем на местах, три перекладываем, а две откладываем. Добиваем до ровного числа монет 4 оставшимися, ну и дальше всё тривиально.
Но, даже если не догадаться до идеи о связи первого и второго взвешивания, и ограничить себя только вариантами, когда монета или не участвует во взвешивании, или остаётся на месте. Ок. Предположим мы так "заблудились", хотя мне не понятно, как так можно, если стремиться перебрать ВСЕ варианты (напоминаю, что мы пробуем найти решение или доказать, что его нет).
Но, положим, мы так ошиблись. То сразу возникает вопрос, а как так может получиться, что весы во втором взвешивании покажут другой результат, чем в первом?
Ясно, что позволить себе такую стратегию, при которой такой исход невозможен, мы себе не можем, так как за всего два возможных исхода мы лучше чем до 4 число подозрительных не уменьшим, и всё-таки придётся "изобрести" перекладывание монет между чашками
Вроде бы это полное рассуждение, и оно даёт ВСЕ возможные решения. О чём тут можно думать 2 недели и толпой мне решительно не ясно
NM>P.S.
NM>Это я за папу вступаюсь.
Не надо вступаться, надо попробовать решить таки НОРМАЛЬНО какую-нибудь похожую задачку. Например, для аналогичной задачи для 13 монет (26) вариантов, трёх взвешиваний (27 вариантов результатов взвешивания) можно определить фальшивую и знак её отличия от остальных?
NM>Меня опять терзают смутные сомнения! (с) Иван IV.
NM>Уже Семь недель висит задачка.
NM>Вы... как-то долго...
Я как увидел -- сразу написал. Но я эту задачку раньше знал уже, так что я вообще мгновенно в данном случае.
Правда я всё равно не понимаю, что там можно было тупить?
Там же дерево решений мизерное.
И всегда можно просто попробовать его перебрать с очевидными отсечениями, так, что бы либо доказать, что задачу решить нельзя, либо построить решение.
Очевидно, что из 27 теоретически возможных результатов трёх взвешиваний, надо разделить 24 ситуации. То есть "подклеить" к другой ситуации, или просто заранее знать, мы можем не более трёх комбинаций результатов взвешиваний.
Очевидно, что первых ход -- это взвешивание 4 х 4, так как для 3 х 3 и 5 х 5 потом не получится за 2 взвешивания (9 разных отчётов) выбрать из 10 или 12 ситуаций.
Если 4х4, то либо получаем в ре-те равенство, и надо выбрать из 8 оставшихся вариантов (какая из 4-х монет и тяжелее или легче) Если неравенство, то тоже из 8 (какая из участвовавших во взвешивании фальшивая, так как кто легче или тяжелее уже знаем). Ок.
Например, рассмотрим случай равенства.
Ясно, что нужно так взвешивать, что бы все три исхода были информативны. Поэтому, 2 х 2 из только оставшихся взвешивать неверно, так как не можем получить равенство, а 1 х 1 не верно, так как в случае равенства не понятно, как решить задачу про две монеты и одно взвешивание. Там вроде бы всего два хода остаётся возможных -- сравнить две оставшиеся или сравнить одну из оставшихся с нефальшивой. Ну и все 4 оставшиеся если сравнить с 4 настоящими, тоже мы узнаем тяжелее настоящая или легче, но, потом из 4 за одно взвешивание с тремя исходами выбрать не получится. И ещё можно подозрительные взвешивать в духе 3х1 дополняя настоящими. Но тут тоже не получится узнать какая монета фальшивая и тяжелее ли она.
Значит надо три подозрительные сравнить с тремя настоящими. Если получим равенство, то фальшивая последняя невзвешенная, и за последний ход узнаём тяжелее она или легче.
Если три окажутся тяжелее (или легче) мы узнаем тяжелее ли фальшивая и за последнее взвешивание 1х1 выберем из этих трёх нужную.
Если же первое взвешивание показало неравенство, то у нас 8 подозрительных монет, про каждую из которых мы знаем тяжелее ли она, если она фальшивая.
Значит максимум 3 подозрительные монеты можно отложить на третье взвешивание, а из оставшихся 5 выбрать за два.
Думаем о том, как связаны позиции монет при первом взвешивании и во втором.
Ясно, что монета может остаться там же, где была, может быть отложена и может оказаться на другой чашке весов.
Ясно, что каждая из групп не может превышать 3, так как, если результат второго взвешивания покажет на эту группу, то потом за третье мы из более 3 вариантов не выберем.
Ну и получаем, что или мы три оставляем на своих местах, две перекладываем и три откладываем. Или две оставляем на местах, три перекладываем и три откладываем, или три оставляем на местах, три перекладываем, а две откладываем. Добиваем до ровного числа монет 4 оставшимися, ну и дальше всё тривиально.
Но, даже если не догадаться до идеи о связи первого и второго взвешивания, и ограничить себя только вариантами, когда монета или не участвует во взвешивании, или остаётся на месте. Ок. Предположим мы так "заблудились", хотя мне не понятно, как так можно, если стремиться перебрать ВСЕ варианты (напоминаю, что мы пробуем найти решение или доказать, что его нет).
Но, положим, мы так ошиблись. То сразу возникает вопрос, а как так может получиться, что весы во втором взвешивании покажут другой результат, чем в первом?
Ясно, что позволить себе такую стратегию, при которой такой исход невозможен, мы себе не можем, так как за всего два возможных исхода мы лучше чем до 4 число подозрительных не уменьшим, и всё-таки придётся "изобрести" перекладывание монет между чашками
Вроде бы это полное рассуждение, и оно даёт ВСЕ возможные решения. О чём тут можно думать 2 недели и толпой мне решительно не ясно
NM>P.S.
NM>Это я за папу вступаюсь.
Не надо вступаться, надо попробовать решить таки НОРМАЛЬНО какую-нибудь похожую задачку. Например, для аналогичной задачи для 13 монет (26) вариантов, трёх взвешиваний (27 вариантов результатов взвешивания) можно определить фальшивую и знак её отличия от остальных?