Задачка на логіку

[ronya]

Для любителів логічних головоломок пропоную наступну задачку:

Є дванадцять монет. Одна з них фальшива. Вона або чуть важча або чуть легша за інші.

У вас є терези з двома чашами.

Як можна визначити фальшиву монетку і точно взнати чи вона важча чи легша за інших, якщо дозволяється зробити максимум три зважування?

[LENS]

цікавить результат

[vicit]

12 монет ділим на три кучки по 4 монети і дві важимо. Потім берем ту кучку в якій фальшива і за два рази визначаєм

Вибачаюсь, невірно подумав, при цьму варіанті потрібно 4 рази зважити.

[ursa]

А она точно - или тяжелее, или легче? Такая неконкретика?

[ronya]

цікавить результат

Результат потім, якщо ніхто не розгадає.

А она точно - или тяжелее, или легче? Такая неконкретика?

Це потрібно визначити в процесі: чи важча чи легша.

[vicit]

ronya, при першому зважуванні повинні зважуватися всі 12 монет для визначення ваги?

з подальшим діленням її на 12 і визначенням легша чи важча фальшивка. Хоча потім за 2 зважування неможливо вичислити 1 монету

За 4 рази є декілька варіантів а за 3 неможу додуматися

[ronya]

ronya, при першому зважуванні повинні зважуватися всі 12 монет для визначення ваги?

Ні, не всі.

Але то вже підсказки :-)

За 4 рази є декілька варіантів а за 3 неможу додуматися

Є рішення за 3, але воно не таке очевидне.

[ursa]

Если монета ИЛИ легче, ИЛИ тяжелее - тогда решается за 3 взвешивания. Если неизвестно, тяжелее она или легче - не вижу способа

[Zheny@]

12/2=6 - перше зважування по 6 монет (тяжчу/легшу купку обираємо для наступних зважувань)

6/2=3 - друге зважування по 3 монети (так само)

3 зважування по 1-й монеті - якщо врівноважилися - одна лишиться не зважена у васв руках, якщо ж переважиться якась із ваг - то там і фальшивка.

Чи не так?

[ronya]

12/2=6 - перше зважування по 6 монет (тяжчу/легшу купку обираємо для наступних зважувань)

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

[Zheny@]

точно.

Чи важча чи легша..а не саму монетку визначити..

[Dima4s]

в идеалі покласти по 3 з одинаковою вагою, зняти 3 з одної сторони і покласти 2 рази по 3 ще...

довго розписувати всю суть...багато якщо

[fenmix]

В ідеалі піти в банк і не парити мізки)

[Dima4s]

В ідеалі піти в банк і не парити мізки)

Філософ з тебе......

[HWman]

А нам вчитель давав колись таку задачку, а от як вирішити я не нажаль пам'ятаю... вроді поділити треба на 4 кучкі по 3 монети далі зважити, якщо вага одинакова то фальшивої тут нема, якщо одна кучка важча чи легша то вона там є, далі взяти поділити дві кучкі на три по дві монети кожна... а далі не помню, карочє якось так

[Korosy]

а хз...

якщо

воно не таке очевидне.

якщо або важча, або легша...навіть звівши все до двох монет.

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

якщо не зрівноважаться, також будь-яку відкладаємо і ту, що лишилась на шальках, важимо з тією, що ще не важили.

і тут точно - або співпаде або ні.

якщо співпаде - фальшивка в тій купі, що відклали. якщо ні - ...мля, хз ... яку-небудь купу з другого зважування ділимо ще пополам і важимо третій раз... тобто по дві монети на шальках. далі - тупо на руках важити )))

[fog]

Для варіанту меншої ваги фальшивої монети:

Ділимо на 2 частини по 6 монет у кожній. Зважуємо.

Беремо легшу купу, ділимо на 2 частини по 3 монети. Зважуємо.

Беремо частину, яка легше і зважуємо.

Легша монета і є фальшивою. Якщо вага монет однакова - третя монета фальшива.

[igor]

Правильна відповідь в 3-му пості.

1-ше зважування по 4монети в кучці. Ми знайдемо кучку із 4-рьох монет, де фальшива. Вона або не зважиться (терези покажуть рівновагу, або буде на шальках).

2-ге зважування ділимо кучку на 2 частини по 2-і монети і важимо. Знаходимо кучку де є фальшива.

3-тє зважування важимо поділену кучку з фальшивою монетою знайденою в випадку 2.

Отже:

1-раз: 4+4+4

2-раз: 2+2

3-раз: 1+1

або

1-раз: 4+4+4

2-раз: 1+1

3-раз: 1+1

[HWman]

Правильна відповідь в 3-му пості.

1-ше зважування по 4монети в кучці. Ми знайдемо кучку із 4-рьох монет, де фальшива. Вона або не зважиться (терези покажуть рівновагу, або буде на шальках).

2-ге зважування ділимо кучку на 2 частини по 2-і монети і важимо. Знаходимо кучку де є фальшива.

3-тє зважування важимо поділену кучку з фальшивою монетою знайденою в випадку 2.

Отже:

1-раз: 4+4+4

2-раз: 2+2

3-раз: 1+1

або

1-раз: 4+4+4

2-раз: 1+1

3-раз: 1+1

Неканає

...Вона або чуть важча або чуть легша за інші.

Я думаю - нереально, якщо хтось розгадає то він Геній.

[ursa]

Кучки - 5 + 5 + 2

1. Взвесить 5 и 5.

2а. Если они равны - взять любую монету из 5 и взвесить с любой из 2.

Если вес равен - фальшивка оставшаяся из 2.

Если не равен - то фальшивка из кучки 2, которая на весах.

2 взвешивания до решения

2б. Если 5 и 5 не равны - надо больше взвешиваний, чем три.

Условие не должно быть таким неконкретным.

[Вoвчик]

у меня получилось решить:

Надо взвешивать сначала по 4, потом по 5(если разные)

вот примеры, от 1 до 12 монет,

то есть если 1-я монета тяжелее остальных процесс будет такой:

==========================
============ 1 ===========
1 2 3 4     5 6 7 8 >
1 2 3 8 7   4 9 10 11 12 >
1 	    2 >

и так далее для остальных 
==========================
============ 2 ===========
1 2 3 4     5 6 7 8 >
1 2 3 8 7   4 9 10 11 12 >
1 	    2 <

==========================
============ 3 ===========
1 2 3 4     5 6 7 8 >
1 2 3 8 7   4 9 10 11 12 >
1 	    2 =

==========================
============ 4 ===========
1 2 3 4     5 6 7 8 >
1 2 3 8 7   4 9 10 11 12 <
7 	    8 =

==========================
=========== 5 ============
1 2 3 4     5 6 7 8 <
1 2 3 8 7   4 9 10 11 12 =
5	    6 >

==========================
=========== 6 ============
1 2 3 4     5 6 7 8 <
1 2 3 8 7   4 9 10 11 12 =
5	    6 <

==========================
=========== 7 ============
1 2 3 4     5 6 7 8 <
1 2 3 8 7   4 9 10 11 12 >
7 	    8 >

==========================
=========== 8 ============
1 2 3 4     5 6 7 8 <
1 2 3 8 7   4 9 10 11 12 >
7 	    8 <

==========================
=========== 9 ============
1 2 3 4    5 6 7 8 =
1 2 3     10 11 12 =
9	  1 >

==========================
=========== 10 ===========
1 2 3 4    5 6 7 8 =
1 2 3     10 11 12 <
10	  11 >

==========================
=========== 11 ===========
1 2 3 4    5 6 7 8 =
1 2 3     10 11 12 <
10	  11 <
==========================

==========================
=========== 12 ===========
1 2 3 4    5 6 7 8 =
1 2 3     10 11 12 <
10	  11 =
==========================

может быть 3 результата взвешивания: больше, меньше, ровно. Соответственно у нас на 3-м шаге должно получиться выбор с 3-х монет(тоесть после 1-го и 2-го взвешивания должно быть только 3 варианта(3 монеты)),

понятно что 2-е взвешивание тоже имеет 3 результата(< > =), то есть оно должно отсеять по 3-и числа под каждый знак.

[vicit]

Якщо йти від "обратного" то, в третьому (останьому) зважувані, мають брати участь 3 монети - дві яких ложим на терези а третя збоку, при цьому потрібно вже знати, легша фальшивка чи важча. Тобто за два зважування потрібно визначити групу із трьох монет, вага яких буде різнитися від іншик кучок.

ronya, я правильно говорю?

[Вoвчик]

Якщо йти від "обратного" то, в третьому (останьому) зважувані, мають брати участь 3 монети - дві яких ложим на терези а третя збоку, при цьому потрібно вже знати, легша фальшивка чи важча. Тобто за два зважування потрібно визначити групу із трьох монет, вага яких буде різнитися від іншик кучок.

ronya, я правильно говорю?

собственно про это я и написал чуть выше...

[Arden]

задаче не хватает условия)

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

[Вoвчик]

задаче не хватает условия)

значит то что я решил выше - неправильно? =)

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

распишу ситуацию например с 3-й монетой:

==========================
============ 3 ===========
1 2 3 4     5 6 7 8 >
1 2 3 8 7   4 9 10 11 12 >
1 	    2 =
==========================

Если монета №3 тяжелее остальных (ясно что мы заранее про это не знаем)

1. Взвешиваем 1 2 3 4 и 5 6 7 8 (первая кучка перевесила)

2. Взвешиваем 1 2 3 8 7 и 4 9 10 11 12 (первая кучка перевесила)

может быть 3 результата на 2-м взвешивании:

1) первая куча тяжелее(на 3-е взвешивание остаются монеты 1 2 3; так как 4 переместилось но ситуация не изменилась; 
5,6 вообще ушли(а весы все еще не ровны); 
7,8 не могут быть так как левая кучка по прежнему тяжелее (если бы 7-я была легкой монеткой то после того как мы ее переместили первая кучка стала бы легче)
9,10,11,12 (роли не играют, так как были вычеркнуты после 1-го взвешивания и служат только для массовки)

2) вторая куча тяжелее, остаются монеты 4, 7, 8 - так как именно из-за них могла измениться ситуация
почему если бы 2-я куча стала тяжелее у нас остались монеты 4, 7, 8 объясняется так же как и в пред. пункте 

3) кучки равны, остаются монеты 5, 6 - сравниваем их
так как только мы их забрали - весы уровнялись

3. Взвешиваем 1 и 2 (они равны)

осталась 3-я - она была в той кучке что перевесила, значит она тяжелее;

можно так проверить правильный алгоритм взвешивания или нет:

монеты 1 и 2 не подходят так как они равны,
3 - подходит,
4 - нет, так как на 2-м шаге монету переместили а весы остались в том же положении
5,6 - нет, так как на 2-м шаге их вообще нет а весы остались в том же положении
7,8 - не могут быть легкими монетами, так как на 2-м шаге их переместили а веса остались в том же положении
9,10,11,12 - отпадают так как на 1-м взвешивании их не было

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

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

З,Ы. прям как диплом: решил, написал и защитил!

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