НГУ

Форумы НГУ
Текущее время: Вс фев 18, 2018 10:03 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Фальшивая монета и нежные весы
СообщениеДобавлено: Пн фев 07, 2005 6:32 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Имеется несколько монет не отличимых по внешнему виду, но одна из них фальшивая. Все настоящие монеты одного веса, а фальшивая легче. Вам дается не более 4-х попыток для определения фальшивой монеты.
Вопрос - сколько вам дать монет?

Спросите, зачем двое весов? :)
А весы очень нежные - они могут уравновешивать сколь угодно раз одинаковые грузы, но как только вы увидели, что чаши не уравновесились, весы тут же и ломаются.

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Фальшивая монета и нежные весы
СообщениеДобавлено: Чт фев 10, 2005 10:45 pm 
Не в сети
Опытный автор

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
bolbot писал(а):
Спросите, зачем двое весов? :)

Ну как мы можем это спросить, если до этого нигде не говориться, что весов двое?

_________________
Я попал в окружение.
Кто там с белыми флагами?
Покупайте прощение.
А я исчезну оврагами.
(c) ДДТ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 10, 2005 10:56 pm 
Не в сети
Опытный автор

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
Ответ: 25. Правильно?

_________________
Я попал в окружение.
Кто там с белыми флагами?
Покупайте прощение.
А я исчезну оврагами.
(c) ДДТ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 10, 2005 11:19 pm 
Не в сети
Опытный автор

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
Э-э, нет. Я немного погорячился. Пока что я только умею определять фальшивую из 29 монет; и умею доказывать, что из 34 монет фальшивую определить не удастся.

_________________
Я попал в окружение.
Кто там с белыми флагами?
Покупайте прощение.
А я исчезну оврагами.
(c) ДДТ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 10, 2005 11:49 pm 
Не в сети
Опытный автор

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
Всё, правильный ответ 33, я придумал алгоритм угадывания для 33 монет, что совпало с моей верхней оценкой.

Итак, покажем, как угадать фальшивую из 33 монет. Делим их на 7 кучек:

7 м. + 7м. + 5м. + 5м. + 3м. + 3м. +3м.

Теперь сначала взвешиваем кучки по 7 монет на первых весах. Если равновесие, то взвешиваем кучки по 5 монет, если опять равновесие, то взвешиваем по 3 монеты. В итоге, когда первые весы будут испорчены (или не испорчены, но мы потратим 3 взвешивания на них), то мы перейдём ко вторым весам с одной из следующих ситуаций:

1. У нас 7 монет --- кандидатов на фальшивую, и 3 взвешивания в запасе. Тогда мы ложим на чашки по одной монете. Если неравенство, то фальшивая определена. Если равенство, то ложим другие две. Если неравенство, то фальшивая определена. Если опять равенство, то ложим ещё две и тратим последнее взвешивание. Если неравенство, то фальшивая определена. Если равенство, то фальшивой будет та оставшаяся седьмая монета, которую мы не вешали.

Аналогичным манерам разбираемся с остальными двумя случаями.

2. У нас 5 монет и 2 взвешивания.

3. У нас 3 монеты и 1 взвешивание.

Итак, из 33 монет определять фальшивую мы умеем.

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

В самом деле, предположим противное. Т.е. предположим, что мы изобрели некую методу, позволяющую из 34 монет на двух весах за 4 взвешивания найти фальшивую монету. Это означает, что мы, располагая лишь результатами этих взвешиваний сможем указать эту монету (разумеется методу мы держим в голове). Но результата у каждого взвешивания может быть только 3, которые мы условно обозначим "<", ">", "=". Причём ни в какой последовательности результатов не может быть символов "<" и ">" в сумме больше двух (ибо каждый такой символ ломает весы). Посчитаем, сколько всего таких последовательностей. Очевидно их 4*3/2+4*3/2+4*3/2+4*3/2+4+4+1=33. Мне лень объяснять, что в этой формуле что означает, поэтому я просто выписал все эти 33 последовательности:

<<
<>
<=<
<=>
<==<
<==>
<===
>>
><
>=>
>=<
>==>
>==<
>===
=<<
=<>
=<=<
=<=>
=<==
=>>
=><
=>=<
=>=>
=>==
==<>
==<<
==>>
==><
==<=
==>=
===<
===>
====

Итак, мы только по результатам взвешиваний, т.е. по одной из последовательностей, перечисленных выше, сможем показать пальцем на фальшивую монету. Но последовательностей 33, а монет 34. Следовательно, на какую-то монету мы не будем показывать пальцем ни при каком исходе взвешиваний. Сделав эту монету фальшивой и запустив нашу методу, мы должны будем показать пальцем на что-то (ибо какие-то результаты у взвешиваний будут), но мы точно ошибёмся. Итак, мы видим, что наша метода ведёт к ошибке. Доказательство можно считать законченным.

Итак, окончательный ответ в задаче: 33 монеты.

_________________
Я попал в окружение.
Кто там с белыми флагами?
Покупайте прощение.
А я исчезну оврагами.
(c) ДДТ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Фальшивая монета и нежные весы
СообщениеДобавлено: Пт фев 11, 2005 6:26 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Михаил Макаров писал(а):
Ну как мы можем это спросить, если до этого нигде не говориться, что весов двое?

Действительно, выпали двое весов при редактировании. :)

Ответ верный - 33.

Пусть f(n,k) - это максимальное число монет из которых можно выявить фальшивую за максимум n попыток, имея k нежных весов.

Тогда
1) f(n, 0) = 1
2) f(n, k) = 3^n при k>=n
3) f(n, k) = 2f(n-1, k-1) + f(n-1, k) при 0<k<n

Первое очевидно, второе - это все равно, что весы одни, но крепкие, а потому это давно известная классика, ну а третье довольно просто.

1)-3) напоминает треугольник Паскаля, из которого вычисляется f(n, k) для небольших n и k. Отсюда довольно просто показать, что f(n, k) при 0<k<n есть многочлен k-ой степени от n. Вот первые три:
f(n, 1) = 2n + 1
f(n, 2) = 2n^2 + 1
f(n, 3) = (4n^3 + 8n)/3 - 2n^2 + 1
f(n, 4) я тоже сосчитал, но не привожу - красивой формулы в общем случае ждать не приходится.

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 22


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB