Задача на логику. Помогите разобраться с формулировками.

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

ХО
ОХ

ХХ
ОО

ОХ
ХХ

ОО
ХХ

ХО
ОХ

ОХ
ХХ

всё врубился как такие задачи решаются, спс.

Воистину так. Только на последнем шаге:

Переворачиваем 3 любых

таки достаточно перевернуть только одну.

спс) точно 1

самая клёвая задача из подобных, которые я видел:

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

Я, конечно, дурак, но думал не меньше 2ух недель (не непрерывно) с перерывом где-то в год, честно думая, что решения не существует.

при поступление на какую должность получили такую задачу?

3^3 = 27 - три взвешивания дают 27 вариантов.

2*12 = 24 - вариантов конфигураций монет.

Решаема же.

да решаема, я даже решение, за минут 5 вспоть смогу. но всё же решил предложить её лоросообществую, как не совсем тривиальную. Могу в общем-то в отдельную тему.

P.S. выкладок не понял.

TDrive

при поступление на какую должность получили такую задачу?

Java developer.

Да, спасибо за решение.

3^1 - одно взешивание даёт 3 варианта. Давай реши задачу с одним взвешиванием и тремя монетами!

Да, а про 12 монет задача за пять минут решается.

Делим кучу на 4 группы. За первые 2 взвешивания, комбинируя группы как AB-CD (1 взв-е) и AC-BD (2-е), узнаём 3-ку, где фальшивая монета и то, легче она или тяжелее. Взвешиваем любые 2 из тройки, определяем фальшивую.

пусть в A монета весит меньше. тогда

AB < CD AC < BD

пусть в D монета весит больше. тогда

AB < CD AC < BD

что делать дальше?

При знании о весе фальшивой монеты (чтобы число конфигураций монет также было равно 3)? Легко. Взвешиваем 1 и 2, 3 в стороне. Если равны - фальшивая 3, если не равны, то 1 или 2 в зависимости от веса.

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

если надо минимизировать кол-во раундов - то надо подумать, но выше по треду уже нашли решение.

интересней обратная задача: найти стратегию которая в заданных условиях обеспечит «вечную тьму», причём эффективней чем другие стратегии.

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

переворачивать по 2 диагональные монеты, если на 1 шаге не включится - то никогда не включится

я подозреваю, что это в данных условиях чит и так нельзя :)

за 2 взвешивания можно найти фальшивую монету из 4 монет, из 5 уже не получится. => после первого взвешивания из 12 монет нужно уменьшить круг до 4 монет.

Выключить и больше ничего не трогать, не? (:

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

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

P.S. я решение забыл, придйтся вспоминать :)

диагонали это пожалуй правильный подход..а если число углов нечётно и простое ? чтобы не было варианта когда выборка перейдёт в себя при повороте кроме 360 град. Скажем пятигранный стол :) Или тайная вечеря на 13 человек..

p.s. это так - гимнастика ума..а то что-то на ЛОРе последнее время встречаются только школьные задачи или вопросы от HR :(

за 4 взвешивания уже 2 варианта придумал, за 3 хз.

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

реши Задача на логику. Помогите разобраться с формулировками. (комментарий) она повеселее.

А ну да, ты же ещё на два умножал. Ладно, тогда за три взешивания с 13 монетами (с неизвестным весом фальшивой).

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

я кстати вспомнил, не факт, что совпадает с тем решением, которое придумывал раньше

буду пилить цепочку, так как, чтобы решиться перепилить лодыжку, потребуется минимум 5 минут самоконцентрации

Тем более, что не факт, что в процессе отпиливания лодыжки ты не потеряешь сознание от потери крови или тупо от боли. Хотя в кино они да, «отпилить ногу? да без проблем! мы же дети Чака Норриса! тем более, там такая нога...».

оно же не отличается от решения с 12, только в одном месте доп шаг.

http://www.notfunny.ru/2009/10/30/kak-najti-falshivuyu-monetu-13-monet-3-vzve...

Есть некая комната с паркетным полом, в углу которой насыпана куча песка. В некоторый момент паркет начинает гореть. Как будут действовать инженер, физик и математик? Инженер: входит в комнату, засыпает огонь песком, уходит. Физик: входит в комнату, насыпает песок вокруг огня, садится и наблюдает процесс. Математик: входит в комнату, видит, что задача имеет решение, и уходит.

А что сложного?

a) <-> (два раза перевернуть все) 2 соседние ; <-> 2 диаметральные ; <-> (перебрали 6 вариантов) 2 соседние ; <-> (8 или 6 с возвращением в исходный) 2 диаметральные ; <-> (8)

если не зажглось - перевернуть одну и повторить.

// если что, прошу извинить - весь тред не читал

что делать дальше?

Действительно... =(
надо подумать...

Тоже думал когда-то эту задачу пару часов... А потом применил тактику «забей на условие» и все получилось. Ведь основная заковырка, которая сильно путает, именно в условии...

за 2 взвешивания можно найти монетку из 7-ми, а не из 4 :) А этом и трюк :)

я бы сказал, что даже из 8-ми, но при дополнительном условии, что известно, что 1234<5678, ну или >, на общности не отражается.

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

Просто из 7 монет найти фальшивую за 2 взвешивания не получится.
По задаче из 12 монет так получается потому, что за первое взвешивание находим часть информации + несколько настоящих монет.

как раз за два взвешивания 7 монет и обрабатываются :)

Твое «дополнительное условие» и есть еще одно взвешивание.
7 монет потолок для двух взвешиваний.

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

в том то и дело что не известно, по этому потолок 4 монеты.

Вроде дошло. На 1-ом сравниваем по 4: a,b,c,d и e,f,g,h. Если равны, из оставшихся 4-х поиск тривиален. Иначе - сравниваем a,b,c,h и i,j,k,d (i,j,k - обычные, h и d поменялись местами). Если равны, из снятых 3-х при знании легче/тяжелее фальшивая поиск опять тривиален. Ежели показания весов не изменились, ищем из a,b,c. Если изменились - из h и d.

Твое «дополнительное условие» и есть еще одно взвешивание.
7 монет потолок для двух взвешиваний.

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

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

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

Ежели показания весов не изменились, ищем из a,b,c.

почему из a,b,c, а не из i,j,k? но путь верный.

Это на 2-ом шаге, где известно, что фальшивая среди abcdefgh.

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

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

Программно вот.

abcd == efgh?
  i == j?
    a == k?
      l - фальшивая
    a != k?
      k - фальшивая
  i != j?
    a == i?
      j - фальшивая
    a != i?
      i - фальшивая
abcd > efgh?
  abch = ijkd?
    e = f?
      g - ф
    e > f?
      f - ф
    e < f
       e - ф
  abch > ijkd?
    a = b?
      c - ф
    a > b?
       a - ф
    a < b?
       b - ф
  abch < ijkd?
    a = h?
      d - ф
    a != h?
      h - ф
abcd < efgh?
  abch = ijkd?
    e = f?
      g - ф
    e < f?
      f - ф
    e > f
       e - ф
  abch < ijkd?
    a = b?
      c - ф
    a < b?
       a - ф
    a > b?
       b - ф
  abch > ijkd?
    a = h?
      d - ф
    a != h?
      h - ф

это чем-то отличается от исходной?