Страниц: [1] 2
  Печать  
Автор Тема: Найдите максимальное N  (Прочитано 9712 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Черная кошка
Гений-Говорун
*
Offline Offline

Сообщений: leet

СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215


я не ангел, но ведь и жизнь- не рай.


Просмотр профиля
: Август 05, 2013, 12:59:48 �

Возможно и была. Но вот я сколько не просмотрела,  развернутого ответа нигде не нашла, сама решала, получилось 99 монет, а по ответу гораздо больше . Если можно дать не просто ответ, а развернутое решение. Просто интересно.

Даны чашечные весы, имеющие особенность — они могут выдержать ровно 3 взвешивания (неважно в каком порядке) неравных грузов, после чего ломаются. Одинаковые веса можно уравновешивать на этих весах бесконечное количество раз. Среди N монет есть одна фальшивая, вес которой меньше настоящих.

Найдите максимальное N при котором можно найти фальшивую не более, чем за 7 взвешиваний на этих весах.
Записан

//текст доступен после регистрации//
☭-Изделие 20Д
Ум
*****
Offline Offline

Сообщений: 7915

СПАСИБО
-вы поблагодарили: 6291
-вас поблагодарили: 2516


[img] http://s016.radikal.ru/i337/1409/6a/5b2b5c71

614445846
Просмотр профиля Email
Ответ #1 : Август 05, 2013, 14:14:03 �

Возможно и была. Но вот я сколько не просмотрела,  развернутого ответа нигде не нашла, сама решала, получилось 99 монет, а по ответу гораздо больше . Если можно дать не просто ответ, а развернутое решение. Просто интересно.

Даны чашечные весы, имеющие особенность — они могут выдержать ровно 3 взвешивания (неважно в каком порядке) неравных грузов, после чего ломаются. Одинаковые веса можно уравновешивать на этих весах бесконечное количество раз. Среди N монет есть одна фальшивая, вес которой меньше настоящих.

Найдите максимальное N при котором можно найти фальшивую не более, чем за 7 взвешиваний на этих весах.
Crazy Roll Eyes Embarrassed
Очень оригинальная трактовка вопроса  Стена
Очевидно 7 и есть максимальное число если в фильтрах - "не более чем за 7
Да и имхо в таких задачач искать МАКСИМАЛЬНОЕ ЧИСЛО - чушь - однозначно - бесконечность, сиди и взвешивай 1-1, 2-2 ну и т.д.
"

Последнее редактирование: Август 05, 2013, 14:23:12 от Изделие 20Д Записан

Руслан Дехтярь
Гость
Ответ #2 : Август 05, 2013, 14:43:56 �

У меня тоже пока 99 получается.
иду от обратного: в конце должно быть 3 монеты.

Эти пользователи сказали вам СПАСИБО :

Черная кошка

За это сообщение 1 пользователь сказал спасибо!
Записан
iPhonograph
Гений-Говорун
*
Offline Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #3 : Август 05, 2013, 16:45:11 �

379

решение:
Показать скрытый текст

Эти пользователи сказали вам СПАСИБО :

zhekas

За это сообщение 1 пользователь сказал спасибо!
Записан

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
Черная кошка
Гений-Говорун
*
Offline Offline

Сообщений: leet

СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215


я не ангел, но ведь и жизнь- не рай.


Просмотр профиля
Ответ #4 : Август 06, 2013, 07:24:26 �

.


 Crazy Roll Eyes Embarrassed
Очень оригинальная трактовка вопроса  Стена
Очевидно 7 и есть максимальное число если в фильтрах - "не более чем за 7
Да и имхо в таких задачач искать МАКСИМАЛЬНОЕ ЧИСЛО - чушь - однозначно - бесконечность, сиди и взвешивай 1-1, 2-2 ну и т.д.
"


я же просила решение, а не мнение, чушь это или не чушь, если не понимаете, зачем захламлять тему?
Записан

//текст доступен после регистрации//
Черная кошка
Гений-Говорун
*
Offline Offline

Сообщений: leet

СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215


я не ангел, но ведь и жизнь- не рай.


Просмотр профиля
Ответ #5 : Август 06, 2013, 07:27:58 �

379

решение:




в ответе написано 527, а вот решения там нет, как они пришли к этому числу.
Записан

//текст доступен после регистрации//
Руслан Дехтярь
Гость
Ответ #6 : Август 06, 2013, 13:51:25 �

Фиг его знает.
я до 219 досчитал:)
1 взвешивание: 33 и 33. 153 остается. Если в одной из кучек по 33 есть фальшивая- находим еще за 6 взвешиваний. Если 33 = 33, берем из оставшейся кучи 153  по 27(нужно, чтоб в случае равенства весов, осталось еще 1 взвешивание неравных весов). Взвешиваем. Показывают неравенство. Находим фальшивую. Нет. Берем из большей оставшейся кучи по 21 монет (за 5 взвешиваний, включая 2 возможности взвесить неравный вес).
и так далее...

Эти пользователи сказали вам СПАСИБО :

Черная кошка

За это сообщение 1 пользователь сказал спасибо!
Последнее редактирование: Август 06, 2013, 13:53:00 от RD Записан
Черная кошка
Гений-Говорун
*
Offline Offline

Сообщений: leet

СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215


я не ангел, но ведь и жизнь- не рай.


Просмотр профиля
Ответ #7 : Август 06, 2013, 13:56:07 �

RD
Цитировать
Фиг его знает.
я до 219 досчитал:)

Уже прогресс. Попробую посчитать с конца. Undecided с 527 , только вот как  это число разбить. Roll Eyes
Записан

//текст доступен после регистрации//
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #8 : Август 06, 2013, 20:33:28 �

Прочтите ещё раз решение iPhonograph и вникните в него.
Даю подсказки.
Если нам можно К раз взвешивать, но только 1 раз из этих К допускается неравенство, то мы можем выделит лёгкую из 2К+1 монет: каждый раз взвешивается пара, неравенство даёт ответ, равенство -> берём следующую пару и т.д.
Если все 2К взвешиваний дали равенство, то последняя (2К+1)-я монета фальшивая.
Теперь рассмотрим в-т когда дважды допускается неравенство и можно К раз взвешивать.
1-е взвешивание:
2К-1 монета на одной чашке и столько же на другой.
В случае неравенства - у нас ещё есть К-1 взвешивание для 2К-1 монеты.
В случае равенства - 2-е взвешивание - по 2К-3 монеты на каждой чашке и т.д.
То есть всего можно взвесить: 2К-1 + 2K-3 + 2K-5... и т.д. - сумму найти просто.
По аналогичному принципу определяется общее кол-во монет, когда допустимы 3 взвешивания с неравенством и т.д.
iPhonograph привёл рекурсивное решение общего вида (или рекуррентное, уж и не помню как верно).

Эти пользователи сказали вам СПАСИБО :

☭-Изделие 20Д

За это сообщение 1 пользователь сказал спасибо!
Записан
Черная кошка
Гений-Говорун
*
Offline Offline

Сообщений: leet

СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215


я не ангел, но ведь и жизнь- не рай.


Просмотр профиля
Ответ #9 : Август 08, 2013, 06:52:44 �

buka
а васне смущает вот это условие?
Цитировать
Найдите максимальное N при котором можно найти фальшивую не более, чем за 7 взвешиваний
Записан

//текст доступен после регистрации//
Руслан Дехтярь
Гость
Ответ #10 : Август 08, 2013, 15:46:37 �

Прочтите ещё раз решение iPhonograph и вникните в него.
Даю подсказки.
Если нам можно К раз взвешивать, но только 1 раз из этих К допускается неравенство, то мы можем выделит лёгкую из 2К+1 монет: каждый раз взвешивается пара, неравенство даёт ответ, равенство -> берём следующую пару и т.д.
Если все 2К взвешиваний дали равенство, то последняя (2К+1)-я монета фальшивая.
Теперь рассмотрим в-т когда дважды допускается неравенство и можно К раз взвешивать.
1-е взвешивание:
2К-1 монета на одной чашке и столько же на другой.
В случае неравенства - у нас ещё есть К-1 взвешивание для 2К-1 монеты.
В случае равенства - 2-е взвешивание - по 2К-3 монеты на каждой чашке и т.д.
То есть всего можно взвесить: 2К-1 + 2K-3 + 2K-5... и т.д. - сумму найти просто.
По аналогичному принципу определяется общее кол-во монет, когда допустимы 3 взвешивания с неравенством и т.д.
iPhonograph привёл рекурсивное решение общего вида (или рекуррентное, уж и не помню как верно).
К сожалению то, что написал iPhonograph, для меня китайская грамота. Пусть он хоть тысячу раз прав. Ваши примеры мне более понятны.
Но решение iPhonograph у меня что- то не получается:)
Решаю так:
Пусть сразу после 2- х взвешиваний неравных весов осталось X монет. То есть, после 2- го взвешивания Х монет. Тогда на втором взвешивании можно было бы взвесить X и X монет. X осталось бы в запасе. Тогда после первого взвешивания можно было бы взвесить 3X и 3X.
X = 2*(K - 2) + 1 - где K - кол- во взвешиваний.
То есть, кол- во монет при 7 попытках для взвешивания было бы: 6*(2*(K - 2) + 1) = 66
Если бы весы показали равенство при взвешивании 33 и 33, взяли бы 6 * (2(K-3)+1) = 54
на последних двух попытках для взвешивания можно оставить 9 монет для первого взвешивания (3+3+3), и (1+1+1), для последнего взвешивания оставим 3 монеты.
Итого считаю и получаю: 231

Последнее редактирование: Август 08, 2013, 15:57:35 от RD Записан
zhekas
Гений-Говорун
*
Offline Offline

Сообщений: 1035

СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 486



Просмотр профиля Email
Ответ #11 : Август 08, 2013, 16:30:04 �


Тогда на втором взвешивании можно было бы взвесить X и X монет. X осталось бы в запасе.

В запасе осталось бы не X, а больше.
Записан
Руслан Дехтярь
Гость
Ответ #12 : Август 08, 2013, 16:35:02 �


Тогда на втором взвешивании можно было бы взвесить X и X монет. X осталось бы в запасе.



В какой момент больше?
В запасе при втором взвешивании я имел в виду.
То есть : X = 2*(K-2)+1
на 2- м взвешивании можно было взвесить X и X, На первом - 3X и 3X.
Записан
zhekas
Гений-Говорун
*
Offline Offline

Сообщений: 1035

СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 486



Просмотр профиля Email
Ответ #13 : Август 08, 2013, 16:41:09 �


на 2- м взвешивании можно было взвесить X и X, На первом - 3X и 3X.


Почему из утверждения
Цитировать
на 2- м взвешивании можно было взвесить X и X,
ты делаешь вывод, что
Цитировать
На первом - 3X и 3X.
?

На втором взвешивании ты взвешиваешь X и X, но в запасе у тебя остаётся не X, а какое-то Y большее X. Так что на первом взвешивании ты моешь взвесить 2X+Y и 2X+Y
Последнее редактирование: Август 08, 2013, 16:44:05 от zhekas Записан
Руслан Дехтярь
Гость
Ответ #14 : Август 08, 2013, 16:44:48 �

Так: я на первом взвешивании взвешиваю 33 и 33 монеты (3X и 3X). В случае их неравенства
проверяю кучку 3X с фальш. монетой взвешиванием X и X.
Записан
Страниц: [1] 2
  Печать  
 
Перейти в: