2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Задача на взвешивание монет
Сообщение07.08.2017, 20:26 
Заслуженный участник
Аватара пользователя


01/09/13
4318
lel0lel в сообщении #1238954 писал(а):
тоже для двух монет (с одной фальшивой)

С двумя фальшивыми тоже ;-) :-)

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение08.08.2017, 12:07 


14/01/11
2916
Кстати, мою схему можно слегка изменить, чтобы она обобщалась на все $N \geqslant 8.$ Пусть $N=8k+r$, $k \geqslant 1$, $r<8.$
Разделим монеты на 3 кучки: $4k$, $4k$, $r.$
Сравним 1-ю и 2-ю.
1. =. В первых двух по одной фальшивой, либо обе фальшивые в 3-ей. Разделим 1-ю пополам (на 4-ю и 5-ю) и сравним.
a) =. Все фальшивые в 3-ей. Возьмём $r$ монет из 1-й и 2-й и сравним с 3-ей.
b) <>. Фальшивая либо в 4-й, либо в 5-й. Разделим 4-ю пополам и сравним, чтобы выяснить, где.
2. <>. В одной из 1-й и 2-й есть фальшивые, в другой нет. Разделим 1-ю пополам (на 4-ю и 5-ю) и сравним.
a) =. Либо в 1-й все настоящие, либо в 4-й и 5-й по одной фальшивой. Разделим 4-ю пополам и сравним, чтобы выяснить.
b) <>. В 1-й есть фальшивые, а во 2-й их нет. Результат их сравнения уже известен.

-- Вт авг 08, 2017 12:11:24 --

(Оффтоп)

Всё-таки разгадывание данеток не прошло даром :lol:

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение08.08.2017, 12:27 


20/04/10
1776
Отличная схема, всё просто и эффективно.

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение08.08.2017, 12:31 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Да, здорово!
Можно переходить к трём фальшивым :mrgreen:

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение08.08.2017, 14:43 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Geen в сообщении #1239099 писал(а):
Можно переходить к трём фальшивым :mrgreen:
Это Вы про вот эту задачу? Неплохо бы.
Пользуясь случаем, приглашу kknop'а, а то окажется через 10 лет, что мы ещё одну задачу про взвешивания без него решали :D

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение08.08.2017, 17:13 


21/05/16
4292
Аделаида
grizzly в сообщении #1239136 писал(а):
приглашу kknop'а

Kknop это Константин Кноп, который публикует подавляющее большинство математических задач на Элементах?

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение08.08.2017, 17:38 


14/01/11
2916
Да он и в Кванте публикуется, похоже. Судя по статьям о взвешивании, вот его страничка.

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение08.08.2017, 19:02 
Заслуженный участник
Аватара пользователя


01/09/13
4318
grizzly в сообщении #1239136 писал(а):
Это Вы про вот эту задачу
? Неплохо бы.

Ну, я имел ввиду что фальшивых монет k, всего монет N, надо найти тяжелее фальшивые или легче за минимальное число взвешиваний... :roll:

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение09.08.2017, 13:32 


14/01/11
2916
Ну вот что-то такое вырисовывается, надо будет ещё проверить.

Пусть имеется $k$ фальшивых монет. Способ работает при $N\geqslant 2^{k+1}$. Представим количество монет в виде $N=p\cdot 2^{k+1}+r$, где $r<2^{k+1},$ $p>0.$
Отложим в сторону кучку в $r$ монет, с остальными перейдём к начальному шагу.

Начальный шаг. Если есть кучка A, о которой известно, что в ней не более $x$ фальшивых, делим её пополам на B и C и сравниваем.
1. =. В любой из B и C не более $\lfloor \frac{x}{2} \rfloor$ фальшивых.
1.1. Если $\lfloor \frac{x}{2} \rfloor=0,$ в кучке A все монеты настоящие. Смотрим на результат сравнения с первой надкучкой выше по цепочке сравнений, где было неравенство. Если везде равенство, надо сравнивать с остатком.
1.2. Если $\lfloor \frac{x}{2} \rfloor>0,$ берём кучку B и переходим к начальному шагу.
2. <>. Разделим кучку B пополам и сравним.
2.1. =. Действуем аналогично п. 1.
2.2. <>. В кучке B есть фальшивые. Значит, в кучке C их не более, чем $x-1$ (0, если $x=2$). Если $x=1$ или $x=2$, результат известен. Иначе берём кучку C и переходим к начальному шагу.

Если не ошибаюсь, общее количество сравнений не превысит $2k-1.$

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение09.08.2017, 13:55 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Вы на каждом шаге делите пополам - выглядит не очень эффективно - вроде бы на каждом шаге можно чуть-чуть отложить в сторону....
Правда довести до ответа мне пока не удалось :D

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение09.08.2017, 14:28 


14/01/11
2916
Хм, целью каждого этапа является максимально возможное сокращение не общего количества рассматриваемых монет, а числа фальшивых монет, пока что не очень представляю, как откладывание в сторону могло бы помочь в этом. :roll:

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение09.08.2017, 20:36 


01/11/14
195
Geen в сообщении #1239099 писал(а):
Да, здорово!
Можно переходить к трём фальшивым :mrgreen:

Есть серьезная задача с двумя фальшивыми монетами с очевидным обобщением. Желающие могут попробовать.

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

1. Какое минимальное число взвешиваний необходимо, чтобы найти фальшивые монеты, если они имеются, или установить, что их нет.

2. Какое минимальное число взвешиваний необходимо, чтобы найти фальшивые монеты, если они имеются, и определить их относительный вес или установить, что фальшивых монет нет.

Можно сразу обратить внимание на особенность исходных данных задачи, обеспечивающих уникальность параметров, соответствующих нижней информационной границе числа взвешиваний. Решение известно (есть публикации), но интереснее поразбираться самому.

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение09.08.2017, 21:02 


14/01/11
2916
Iam в сообщении #1239512 писал(а):
причем вес каждой из фальшивых монет (если они есть) может отличаться от веса настоящей монеты в большую или меньшую сторону на одну и ту же величину (например, на 1 грамм).

Т.е. может оказаться так, что одна из фальшивых монет легче настоящей на 1г, а вторая - тяжелее на 1 г?

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение09.08.2017, 21:14 


01/11/14
195
Sender в сообщении #1239522 писал(а):
Iam в сообщении #1239512 писал(а):
причем вес каждой из фальшивых монет (если они есть) может отличаться от веса настоящей монеты в большую или меньшую сторону на одну и ту же величину (например, на 1 грамм).

Т.е. может оказаться так, что одна из фальшивых монет легче настоящей на 1г, а вторая - тяжелее на 1 г?

Да, если их так положить.

 Профиль  
                  
 
 Re: Задача на взвешивание монет
Сообщение09.08.2017, 21:31 


14/01/11
2916
Кстати, исходная задача ещё далека от завершения. Пока что есть только один алгоритм с неясной оптимальностью, пригодный только для больших $N.$

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

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



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

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


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

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