Помогите решить загадку.

  • Автор темы Автор темы Ser-J
  • Дата начала Дата начала
Ser-J

Ser-J

New Member
2 Июл 2007
179
26
0
Одесса мама
Загадка номер 1:

10 ящиков с монетами, в каждом ящике 100 монет. Одна монета весит 1 грамм. Среди этих 10 ящиков есть 1 ящик с фальшивыми монетами, вес 1 фальшивой монеты 2 грамма. Нужно за 1 взвешивание найти ящик с фальшивыми монетами.

(Эту загадку я разгадал, ответ не пишу пока что мож комуто интересно)

Загадка номер 2 (загадка на основе предыдущей, не разгаданная):

Условия теже самые, только теперь 2 ящика с фальшивками, и 2 взвешивания. Неделю ломаю голову никак не пойму.
 
Ser-J написал(а):
Загадка номер 1:

10 ящиков с монетами, в каждом ящике 100 монет. Одна монета весит 1 грамм. Среди этих 10 ящиков есть 1 ящик с фальшивыми монетами, вес 1 фальшивой монеты 2 грамма. Нужно за 1 взвешивание найти ящик с фальшивыми монетами.
Нажмите для раскрытия...


Сказка какая-то, имхо. Вот стоит 10 абсолютно одинаковых с виду ящиков. Мы подходим и вытаскиваем один ящик. Если этот ящик весит 200 грамм, то нам повезло, иначе менее чем за 1 попытку мы не определим никогда.

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

Скажем если взвесить 5 на 5, то тот который фальшивый перевесит другую сторону весов, но как понять который из 5-ти фальшивый, хз...

Получается сокращаем вероятность ошибки, но лишь на 50%
 
Последнее редактирование:
Musical Instinct написал(а):
Сказка какая-то, имхо. Вот стоит 10 абсолютно одинаковых с виду ящиков. Мы подходим и вытаскиваем один ящик. Если этот ящик весит 200 грамм, то нам повезло, иначе менее чем за 1 попытку мы не определим никогда.

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

Условия верны. Это возможно... а вто вторая задача... пока никак не решается.
 
Siluet написал(а):
Тема по ходу в взвешивании ящиков в определенной пропорции одновременно на разных сторонах весов, больше ниче пока в голову не пришло...
Нажмите для раскрытия...

А весы двусторонние что-ли?
Я подумал про электронные.
В таком случае нужно в условиях указывать.
Иначе я ренгеном как на таможне за одно измерение тогда измерю и на снимке увижу. Если плотность материала одинакова(один и тот же материал) - то значит объём монеты больше - это будет видно на снимке, значит это фальшивая.
Если объём одинаков, значит плотность у фальшивых больше - значит цвет у фальшивых другой будет.
 
Задачка фигня:
1. Решение известно - количество взвешиваемых монет = номеру ящика (n). далее по разнице в перевесе (1-10) определяется его номер.
2. Тоже самое - но количество монет = степень двойки. 2^(n). А так как 2 в 10 стенени = 1024, то взвешиваем сначала первые 5 ящиков, и берем первый ящик за "0".
Получаем 2^0=1, ...2... 4... 8... 16
разница составляет соответственно:
1, 2, 4, 8, 16
а все возможные комбинации укладываются в:
1+2 (3), 1+3 (5), 1+4 (9), 1+5 (17)
2+3 (6), 2+4 (10), 2+5 (18)
3+4 (12), 3+5 (20)
4+5 (24)
Вуаля.

P.S. А все от того, что программирование синтезаторов sysex-ами рулит! )))
 
Musical Instinct написал(а):
А весы двусторонние что-ли?
Нажмите для раскрытия...

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

Нова мне кажется, что тут подвох какой то есть, ибо название топа не "Помогите решить задачку", а "Помогите решить загадку", а что за загадка без подвоха.... ))))
 
Последнее редактирование:
Подвох в том, что ящики как правильно сказал P00H должны быть распечатаны, а весы нормальные (электронные), а не двусторонние (с гирьками) - тут уже эти гирьки подкладывать нужно будет, за один раз не уложишься по определению ))))
 
Ну, не очень тоже понял условия самого взвешивания, но я бы сделал так: брал бы из каждого ящика кол-во монет, соответствующее номеру ящика. дальше отвечать пока не буду, чтобы не сдавать ответ, если мы с женой правы, ты и так поймешь. По крайней мере у нас вроде вышло высчитать, сошлось в конце.


А, блин, пока с телефона писал, тут уже все разгадали. Точнее, знали и сдали ответ))) Но так не интересно же!
 
Последнее редактирование:
Угу, знали и сдали... Ага, помню я щас, что мы там в школе 15 лет назад решали, да??? Все как в первый раз пришлось разгадывать - ибо склероз одолел! :rofl: А как решил - тут и вспомнил молодость ))))
 
Novation написал(а):
Задачка фигня:
1. Решение известно - количество взвешиваемых монет = номеру ящика (n). далее по разнице в перевесе (1-10) определяется его номер.
2. Тоже самое - но количество монет = степень двойки. 2^(n). А так как 2 в 10 стенени = 1024, то взвешиваем сначала первые 5 ящиков, и берем первый ящик за "0".
Получаем 2^0=1, ...2... 4... 8... 16
разница составляет соответственно:
1, 2, 4, 8, 16
а все возможные комбинации укладываются в:
1+2 (3), 1+3 (5), 1+4 (9), 1+5 (17)
2+3 (6), 2+4 (10), 2+5 (18)
3+4 (12), 3+5 (20)
4+5 (24)
Вуаля.

P.S. А все от того, что программирование синтезаторов sysex-ами рулит! )))
Нажмите для раскрытия...

Разбираю решение, пока не догнал. Жаль кнопки спасибо нету.
 
взвешиваем сначала первые 5 ящиков, и берем первый ящик за "0".
что значит сначала?!

взвешивание всё равно одно
:training1: Не въеду.
 
Про степени двойки - это ничо так :) Но задачку можно тупо решать так же как и первую. Ну т.е. первое взвешивание никак не отличается. Понабрал из каждого ящика по номеру кол-во монет, взвесил. Получился перевес. В лучшем случае сразу выяснилось какие ящики фальшивые, в худшем часть ящиков отпала, а из остальных получились пары! Дальше второе взвешивание любого набора ящиков пары по этому же принципу дает финальный результат.
 
Подробно по второму:
Первый способ не проходит, так как для 10 ящиков - максимальное количество совпадений по парам - это 5 (для перевеса 11 грамм!!!)(1+10, 2+9, 3+8, 4+7, 5+6) т.е. 5 совершенно разных пар! Причем эти пары могут включать любой из ящиков.
Мучился полчаса, сначала сообразил что нужно разделить для начала все ящики на две половины, так для первого способа решения снижалось максимальное количество совпадений перевеса для различных пар ящиков (с разными номерами) с 5-ти до 2х. Но все равно требовалось максимум 4 взвешивания.

Тогда помучился еще с разными последовательностями, сначала пробовал последовательность "1, 3, 5, 7, 11...", но там были совпадения в результатах для пар и одиночных ящиков и пришлось отметать, дошел до степени 2-ки и все решилось )))

1 ящик - 1 монета (2 в степени n-1, т.е. 2 в степени 0)
2 ящик - 2 монеты (2 в степени 1)
3 ящик - 4 ...
4 ящик - 8
5 ящик - 16

итак, вес монет для этих 5-ти ящиков:
вес для нормальных ящиков: 01, 02, 04, 08, 16
вес для фальшивых ящиков: 02, 04, 08, 16, 32
разница в весе для каждого: 01, 02, 04, 08, 16

всего весить все эти монеты должны 01+02+04+08+16=31 грамм

если среди этих ящиков не будет перевеса - то в них нет фальшивых монет. если перевес 01, 02, 04, 08, 16 - то по величине определяем фальшивый ящик.

Если нам попалось сразу 2 фальшивых ящика среди 5-ти?

Возможные варианты (скажите спасибо что не 10 ящиков!!!))))):
1+2, 1+3, 1+4, 1+5
2+3, 2+4, 2+5
3+4, 3+5
4+5
Результаты по перевесу:
(складываем значения из "разница в весе для каждого")
03, 05, 09, 17
06, 10, 18
12, 20
24

итого имеем всего вариантов для 5 ящиков (половины из 10):
01, 02, 03, 04, 05, 06, 08, 09, 10, 12, 16, 17, 18, 20, 24
И ни одного совпадения!!! Ни между парами, ни между парами и одиночными ящиками! Ура! По величине перевеса можно 100% определить номер ящика (если он один), либо сразу для пары (это бонус, так как остальные 5 взвешивать не придется и можно все найти за 1 взвешивание).
2. Повторяем процедуру для оставшихся 5 ящиков.
 
Подробно дальше все твои рассуждения не понял. Вот у тебя наихудший перевес в 11 грамм. Кто мешает взвесить 1, 2, 3, 4, 5 ящики среди который ТОЛЬКО 1 фальшивый? Второй точно в другой куче ящиков? Ты определяешь все тем же способом этот фальшивый и пару к нему. Вуаля.
 
Novation написал(а):
Подробно по второму:
Первый способ не проходит, так как для 10 ящиков - максимальное количество совпадений по парам - это 5 (для перевеса 11 грамм!!!)(1+10, 2+9, 3+8, 4+7, 5+6) т.е. 5 совершенно разных пар! Причем эти пары могут включать любой из ящиков.
Мучился полчаса, сначала сообразил что нужно разделить для начала все ящики на две половины, так для первого способа решения снижалось максимальное количество совпадений перевеса для различных пар ящиков (с разными номерами) с 5-ти до 2х. Но все равно требовалось максимум 4 взвешивания.

Тогда помучился еще с разными последовательностями, сначала пробовал последовательность "1, 3, 5, 7, 11...", но там были совпадения в результатах для пар и одиночных ящиков и пришлось отметать, дошел до степени 2-ки и все решилось )))

1 ящик - 1 монета (2 в степени n-1, т.е. 2 в степени 0)
2 ящик - 2 монеты (2 в степени 1)
3 ящик - 4 ...
4 ящик - 8
5 ящик - 16

итак, вес монет для этих 5-ти ящиков:
вес для нормальных ящиков: 01, 02, 04, 08, 16
вес для фальшивых ящиков: 02, 04, 08, 16, 32
разница в весе для каждого: 01, 02, 04, 08, 16

всего весить все эти монеты должны 01+02+04+08+16=31 грамм

если среди этих ящиков не будет перевеса - то в них нет фальшивых монет. если перевес 01, 02, 04, 08, 16 - то по величине определяем фальшивый ящик.

Если нам попалось сразу 2 фальшивых ящика среди 5-ти?

Возможные варианты (скажите спасибо что не 10 ящиков!!!))))):
1+2, 1+3, 1+4, 1+5
2+3, 2+4, 2+5
3+4, 3+5
4+5
Результаты по перевесу:
(складываем значения из "разница в весе для каждого")
03, 05, 09, 17
06, 10, 18
12, 20
24

итого имеем всего вариантов для 5 ящиков (половины из 10):
01, 02, 03, 04, 05, 06, 08, 09, 10, 12, 16, 17, 18, 20, 24
И ни одного совпадения!!! Ни между парами, ни между парами и одиночными ящиками! Ура! По величине перевеса можно 100% определить номер ящика (если он один), либо сразу для пары (это бонус, так как остальные 5 взвешивать не придется и можно все найти за 1 взвешивание).
2. Повторяем процедуру для оставшихся 5 ящиков.
Нажмите для раскрытия...

Спасибо. Разобрался. Сам бы доперал долго.
 
Ser-J
У kLP его рекурсивный способ еще лучше вышел! )))
Меня в тупик поставил выбор сразу из 5 пар ящиков, а вот то что номера ящиков в парах "зеркально" распределяются, я что-то не заметил ))))))))

P.S. Правда чего не отнять - так это мой алгоритм эффективнее выявляет пары за один проход, т.е. больше шансов закончить процедуру за одно взвешивание:
- классический способ: первое взвешивание может выявить только 4 пары (из 45 возможных): 1+2, 1+3, 8+10, 9+10
- способ со степенью 2-ки сразу 10: 1+2, 1+3, 1+4, 1+5, 2+3, 2+4, 2+5, 3+4, 3+5, 4+5.
 
kLP написал(а):
Подробно дальше все твои рассуждения не понял. Вот у тебя наихудший перевес в 11 грамм. Кто мешает взвесить 1, 2, 3, 4, 5 ящики среди который ТОЛЬКО 1 фальшивый? Второй точно в другой куче ящиков? Ты определяешь все тем же способом этот фальшивый и пару к нему. Вуаля.
Нажмите для раскрытия...

А откуда ты знаешь где 1 фальшивый?
 
Ну как откуда. Пары же определились? Да. Других вариантов нет ибо известно, что ящиков с фальшаком ровно 2. Значит взвесив монетки все тем же способом, когда их кол-во соотвествует номеру ящика в множестве ящиков, являющихся половинами комплементарных пар (гыгыгы:lol:) мы узнаем по кол-ву грамм перевеса номер ящика из этого множества, и соответственно пару к нему. Чего непонятно то?
 
kLP написал(а):
Ну как откуда. Пары же определились? Да. Других вариантов нет ибо известно, что ящиков с фальшаком ровно 2. Значит взвесив монетки все тем же способом, когда их кол-во соотвествует номеру ящика в множестве ящиков, являющихся половинами комплементарных пар (гыгыгы:lol:) мы узнаем по кол-ву грамм перевеса номер ящика из этого множества, и соответственно пару к нему. Чего непонятно то?
Нажмите для раскрытия...

А если в одной из пар 2 ящика с фальшивками. Обьясни плих подробней. =)
 
Последнее редактирование:
правильно. Первым взвешиванием мы выбираем возможные варианты пар с фальшивками. Второе взвешивание половин этих пар определяет ту самую ПАРУ ящиков с фальшивками.
 
Ser-J там все просто:
Если подсчитать все варианты, вот такая таблица получается:

-----2--3---4--5---6--7--8---9-10

1 - 03 04 05 06 07 08 09 10 11
2 - .....05 06 07 08 09 10 11 12
3 - ..........07 08 09 10 11 12 13
4 - ...............09 10 11 12 13 14
5 - ....................11 12 13 14 15
6 - .........................13 14 15 16
7 - ..............................15 16 17
8 - ...................................17 18
9 - ........................................19

по вертикали и горизонтали - номера ящиков, в ячейках значение для перевеса.
для значения перевеса "11" = пары: 1+10, 2+9, 3+8, 4+7, 5+6
Всего 10 ящиков и 5 пар.
Первый ящик как видно находится где-то в первой половине списка (ящики 1-5), второй - во второй ))))) (6-10)
Теперь внимание! Если мы знаем величину перевеса (1 замер) и номер ящика из любой половины, например 1-5 (это 2ой замер) мы автоматом узнаем номер второго ящика, составляющий ему пару с помощью уравнения:
*перевес* - *номер ящика* = *номер ящика его пары*
И так с любыми парами.
Например, перевес составил 15.
Это ящики: 5, 6, 7, 8, 9, 10
делим их на две части: 5-7, 8-10
Выявляем лишний среди 5, 6, 7 и вуаля! ))))
 
Матрица - красиво!:crazy: Матрица - это всегда красиво:biggrin:
 
Войдите или зарегистрируйтесь для ответа.

Сейчас просматривают

Всего: 1 (пользователей: 0, гостей: 1)
Сверху Снизу