2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 16 монет и гирька, задача на алгоритм
Сообщение05.04.2011, 20:55 


01/10/10

2116
Израиль (племянница БизиБивера)
Среди 16 монет одна фальшивая. Но не известно, в какую сторону она отличается весом от настоящих. Все настоящие монеты весят по одному грамму. За какое минимальное число взвешиваний на чашечных весах можно найти фальшивую монету и узнать, легче она или тяжелее настоящей, если у Вас есть гирька в 4 грамма?

Найти алгоритм взвешивания и доказать, что меньшим числом взвешиваний не обойтись.

 Профиль  
                  
 
 
Сообщение05.04.2011, 21:20 


24/01/11
207
Я умею за 4 действия, надо подумать, как доказать.
Назовём их все 1, 2, … 16
1. Сравниваем 1..4 с 5…8, если равны, идём в 2, иначе сравниваем 1..4 с гирькой, если равны, то фальшивая в 5..8, иначе в 1..4, а затем идём в 3
2. Сравниваем 9..12 с гирькой, если равны, то фальшивая в 13..16, иначе в 9..12
3. Мы знаем, в какой четверке есть бяка, пронумеруем её элементы 1..4. Возьмём 1..2 и сравним с любыми двумя из четверок, в которых нет бяки. Определили две монетки, среди которых есть бяка.
4. Сделали аналогично предыдущему пункту и нашли фальшивую

 Профиль  
                  
 
 Re:
Сообщение05.04.2011, 21:25 


01/10/10

2116
Израиль (племянница БизиБивера)
Вот дказать-то, как раз, проще, чем алгоритм найти!
Подсказка: используйте троичную систему счисления.

-- Вт апр 05, 2011 21:35:51 --


Каждое взвешивание имеет ровно 3 возможных исхода:

1. перетянула левая чаша
2. правая
3. равноденствие равновесие

Если взвешиваний не более трёх, то возможных исходов не более $3\cdot 3\cdot 3=27$, а нам нужно 32 (одна из 16 монет бяка и 2 варианта отличия по весу).

 Профиль  
                  
 
 
Сообщение05.04.2011, 21:40 


24/01/11
207
А, не учла различия по весу… Теперь понятно :)

 Профиль  
                  
 
 Re: 16 монет и гирька, задача на алгоритм
Сообщение05.04.2011, 21:45 
Заслуженный участник


04/05/09
4589
Меньше чем за 4 точно нельзя (максимум - 12, если нужно узнать, легче или тяжелее фальшивая монета). А за 4 можно проверить аж 39 и без гирьки.

Отставить. С гирькой можно и меньшим количеством обойтись. Скорее всего 3-х хватит.

 Профиль  
                  
 
 Re: 16 монет и гирька, задача на алгоритм
Сообщение05.04.2011, 21:48 


01/10/10

2116
Израиль (племянница БизиБивера)
venco в сообщении #431620 писал(а):

Отставить. С гирькой можно и меньшим количеством обойтись. Скорее всего 3-х хватит.

Это как это?

У Вас в любом случае три исхода на одно взвешивание - хоть с гирькой, хоть без неё.

 Профиль  
                  
 
 Re: 16 монет и гирька, задача на алгоритм
Сообщение05.04.2011, 22:04 
Заслуженный участник


04/05/09
4589
Xenia1996 в сообщении #431622 писал(а):
venco в сообщении #431620 писал(а):

Отставить. С гирькой можно и меньшим количеством обойтись. Скорее всего 3-х хватит.

Это как это?

У Вас в любом случае три исхода на одно взвешивание - хоть с гирькой, хоть без неё.
А нет. Ошибся.
Таки надо 4 взвешивания, и тогда непонятно, зачем гирька, и почему монет только 16.

 Профиль  
                  
 
 Re: 16 монет и гирька, задача на алгоритм
Сообщение05.04.2011, 22:05 


01/10/10

2116
Израиль (племянница БизиБивера)
venco в сообщении #431631 писал(а):
А нет. Ошибся.
Таки надо 4 взвешивания, и тогда непонятно, зачем гирька, и почему монет только 16.

А как без гирьки, если нужно и монету найти, и узнать, легче она или тяжелее?

 Профиль  
                  
 
 Re: 16 монет и гирька, задача на алгоритм
Сообщение05.04.2011, 22:16 
Заслуженный участник


04/05/09
4589
Без гирьки можно за 3 взвешивания найти фальшивую из 12-ти монет, а за 4 - из 39 монет. В общем виде $3\cdot\left[\dfrac {3^k} 6\right]$.

 Профиль  
                  
 
 Re: 16 монет и гирька, задача на алгоритм
Сообщение05.04.2011, 22:18 


01/10/10

2116
Израиль (племянница БизиБивера)
venco в сообщении #431637 писал(а):
Без гирьки можно за 3 взвешивания найти фальшивую из 12-ти монет, а за 4 - из 39 монет. В общем виде $3\cdot\left[\dfrac {3^k} 6\right]$.

Это вот так, что ли?

 Профиль  
                  
 
 Re: 16 монет и гирька, задача на алгоритм
Сообщение05.04.2011, 22:22 
Заслуженный участник


04/05/09
4589
Да. Метод можно расширить на любое количество взвешиваний.

-- Вт апр 05, 2011 14:27:50 --

А формулу можно так записать:
$\dfrac {3^k-3}2$

 Профиль  
                  
 
 Re: 16 монет и гирька, задача на алгоритм
Сообщение05.04.2011, 22:29 


01/10/10

2116
Израиль (племянница БизиБивера)
venco в сообщении #431641 писал(а):
Да. Метод можно расширить на любое количество взвешиваний.

-- Вт апр 05, 2011 14:27:50 --

А формулу можно так записать:
$\dfrac {3^k-3}2$

Спасибо!
Теперь буду знать.

 Профиль  
                  
 
 Re: 16 монет и гирька, задача на алгоритм
Сообщение05.04.2011, 23:24 
Заслуженный участник


09/02/06
4401
Москва
С гирей 4 грамма 3 взвешиваний достаточно, так как при взвешивании с гирей мы получаем и информацию тяжелее или легче фальшивая монета. Первое взвешивание ставится 8 монет против 4монет+гиря 4гр.

 Профиль  
                  
 
 
Сообщение05.04.2011, 23:52 


24/01/11
207
Руст, и что? Если одна половина будет тяжелее, другая легче, от этого действия мы узнаем лишь то, что среди этих 12 монет есть плохая, в моём варианте с первого взвешивания мы узнаем 8 монет, среди которых есть плохая.
И потом, что Вы имеете против док-ва Ксении недостаточности 3х взвешиваний?

 Профиль  
                  
 
 Re: 16 монет и гирька, задача на алгоритм
Сообщение05.04.2011, 23:57 


01/10/10

2116
Израиль (племянница БизиБивера)
Руст в сообщении #431659 писал(а):
С гирей 4 грамма 3 взвешиваний достаточно, так как при взвешивании с гирей мы получаем и информацию тяжелее или легче фальшивая монета. Первое взвешивание ставится 8 монет против 4монет+гиря 4гр.

Предположим, перетянула та, на которой 8. Значит, либо фальшивая там, и она тяжелее, либо фальшивая среди четырёх других, и она легче.
Что мы имеем?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: YandexBot [bot]


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group