Задача на взвешивание монет

[Geen]

lel0lel в сообщении #1238954 писал(а):

тоже для двух монет (с одной фальшивой)

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

[Sender]

Кстати, мою схему можно слегка изменить, чтобы она обобщалась на все $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 --

(Оффтоп)

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

[lel0lel]

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

[Geen]

Да, здорово!
Можно переходить к трём фальшивым

[grizzly]

Geen в сообщении #1239099 писал(а):

Можно переходить к трём фальшивым

Это Вы про вот эту задачу? Неплохо бы.
Пользуясь случаем, приглашу kknop'а, а то окажется через 10 лет, что мы ещё одну задачу про взвешивания без него решали

[kotenok gav]

grizzly в сообщении #1239136 писал(а):

приглашу kknop'а

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

[Sender]

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

[Geen]

grizzly в сообщении #1239136 писал(а):

Это Вы про вот эту задачу
? Неплохо бы.

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

[Sender]

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

Пусть имеется $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.$

[Geen]

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

[Sender]

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

[Iam]

Geen в сообщении #1239099 писал(а):

Да, здорово!
Можно переходить к трём фальшивым

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

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

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

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

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

[Sender]

Iam в сообщении #1239512 писал(а):

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

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

[Iam]

Sender в сообщении #1239522 писал(а):

Iam в сообщении #1239512 писал(а):

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

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

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

[Sender]

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