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

[Sender]

svv в сообщении #1238601 писал(а):

Не переносится на $41, 34, 33, 27, 26, 25, ...$.

5 монет.
Предполагается, что мы замечаем, какие именно монеты мы перекладываем из кучки в кучку и при необходимости можем вновь сформировать исходные.
Возьмём 2 кучки по 2.
1.=. В сравниваемых кучках по одной фальшивой монете, оставшаяся - настоящая. Тогда заменим на неё одну из монет 2-й кучки и вновь сравним с 1-й.
a) =, она тоже настоящая. Возьмём 2 настоящих и сравним с 1-й кучкой.
b) <>, эта была фальшивой. Сравним её с настоящей.
2. <>. Монеты в одной из сравниваемых кучек - настоящие. В другой - одна или обе фальшивые.
Возьмём одну монету из 1-й кучки и одну из 2-й. Они сформируют 3-ю.
Остальные 2 из 1-й и 2-й образуют 4-ю. Сравним 3-ю и 4-ю.
a)=. 5-я монета - настоящая. В одной из 1-й и 2-й кучек 2 фальшивые монеты, в другой 2 настоящие. Чтобы выяснить где настоящие, а где фальшивые, сравним одну из монет с 5-й.
b)<>. 5-я монета фальшивая. Заменим одну из монет 3-ей кучки на неё и вновь сравним со 2-й.
I)= в 3-ей кучке были 2 настоящие монеты.
II)<> в 3-ей кучке была одна фальшивая монета.

[Sender]

6 монет.
Возьмём 2 кучки по 2(назовём их кучка 1 и кучка 2, оставшиеся 2 монеты образуют кучку 3).
1.=. В кучках 1 и 2 по одной фальшивой монете, либо в кучке 3 обе фальшивые. Сравним между собой 2 монеты 1-й кучки.
a)=. Обе монеты 3-й кучки фальшивые. Сравним 2-ю кучку с 3-ей.
b)<>. В кучке 3 обе монеты настоящие. Сравним 2-ю кучку с 3-ей.
2.<>. В одной из кучек 1 и 2 все монеты настоящие, в другой хотя бы одна фальшивая, в 3-ей не более одной фальшивой. Сформируем 4-ю кучку, взяв по 1 монете из 1-й и 2-й кучек. Оставшиеся монеты 1-й и 2-й образуют 5-ю. Сравним 4-ю и 5-ю.
a)=. Обе монеты 3-ей кучки - настоящие, в 4-й одна настоящая и одна фальшивая. Сравним 3-ю с 4-й.
b)<>. В 3-й одна настоящая и одна фальшивая. Сравним её со 5-й:
I)=. В 5-й одна настоящая и одна фальшивая, в 4-й обе настоящие. Результат сравнения 4-й и 5-й известен.
II)<>. В 5-й обе настоящие, в 4-й одна настоящая и одна фальшивая. Результат сравнения 4-й и 5-й известен.

На этом применяемый хак, похоже, исчерпан.

[manul91]

maxal в сообщении #1238813 писал(а):

manul91, было уже topic46626.html

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

Еще две для 3-его класса (напоминаю нужно решать-прикидывать без ручки/бумаги/уравнений; только в уме и "из хитрых" соображений; лучше на застолье под пивом):

"Винная": есть два одинаковых стакана, у обоих одинаковое количество вина - только в первом стакане вино белое, а во втором красное. Ложечкой зачерпываем из стакане белого вина и выливаем в стакане с красном; хорошенько размешиваем, и из получившейся смеси той же ложкой зачерпываем смесь и выливаем в первом стакане с белым вином.
Вопрос после проделанных операций; какая из смесей "грязнее"; т.е. что больше: процент красного вина в белом, или процент белого вина в красном?

"Продуктовая": Продавец закупил 126 кг огурцов - у огурцов (как известно с детства) 99 процента воды. Огурцы просидели на солнце и в результат у них осталось не 99, а 98 процента воды. Каков в итоге стал вес огурцов (пусть и приблизительно, плюс-минус килограмма)?

[grizzly]

manul91 в сообщении #1238904 писал(а):

Еще две для 3-его класса

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

(Оффтоп)

Пожалуйста, оставьте тему для первоначальной задачи -- она вызывает отдельный интерес. У нас не принято такое смешение стилей в одной теме -- серию "загадок и остроумных вопросов" будет удобнее, наверное, формулировать в разделе "Загадок". Ну или просто в отдельной теме.

[wrest]

(Об огурцах)

manul91 в сообщении #1238904 писал(а):

Каков в итоге стал вес огурцов (пусть и приблизительно, плюс-минус килограмма)?

Да, это конечно задачка с неожиданным ответом. Вроде бы как из условия следует, что испарился один процент воды, но дальнейшее размышление приводит к ужасающим последствия огурцовой засухи.
Но я думаю это вряд ли для 3-го класса, скорее для 7-го или 8-го.

[manul91]

Ок, пишу решение для количества монет вида $6k+2$.

Откладываем две из монет, оставшиеся монеты разбиваем на три одинаковые кучки (назовем их A,B,C) с одинаковым количеством монет.

Сравниваем А с B и C с B.
1. Eсли одинаковы - то A=B=C и там фальшивых монет быть не может; стало быть две выделенные монеты и есть фальшивые. Подменяем в любую кучку одну из монет фальшивой и третьим сравнением видим тяжелее ли фальшивые или легче.
2. Имеем ситуацию A=B, C<B. Возможные варианты распределения: в А и B по одной фальшивой монете (а в С все настоящие) и тогда фальшивые тяжелее; либо в А и В все настоящие а в С по меньшей мере одна фальшивая и тогда фальшивые легче.
Делим кучку B на две равные части (с одинаковым количеством монет) и сравниваем - если одинаковы то фальшивые легче; если разные то в B (и А) ровно одна фальшивая и значит фальшивые тяжелее
Ситуации A=B, C>B; А<B, C=B; A>B,C=B (две из кучек одинакового веса, другие две разного) - все решаются аналогично
4. Имеем ситуацию A<B, C<B. Возможные варианты распределения: либо в А и С по одной фальшивой монете а в В все настоящие (и значит фальшивые легче), либо в А и С все настоящие а в В по меньшей мере одна фальшивая монета (и значит фальшивые тяжелее).
Опять делим кучку В на две равные части (две кучки с одинаковым количеством монет) - если одинаковы то фальшивые тяжелее, а если разные то фальшивые легче.
Ситуация A>B, C>B решается аналогично. (Ситуаций типа A<B, B<C где все три кучки разного веса быть не может, так что нет смысла их рассматривать)

svv в сообщении #1238601 писал(а):

Не переносится на $41, 34, 33, 27, 26, 25, ...$.

Метод выше дает решение для 26, 20, 14, 8

[Sender]

manul91,

manul91 в сообщении #1238910 писал(а):

Опять делим кучку В на две равные части (две кучки с одинаковым количеством монет) - если одинаковы то фальшивые тяжелее, а если разные то фальшивые легче.

Если в кучке B 2 фальшивые монеты, результат может зависеть от их распределения по половинкам. По-моему, продуктивнее поделить пополам одну из кучек A или C. В остальном похоже на правду.

Вот ещё один случай:

Общее количество монет N=8a+1.
Сравним 2 кучки по 4a монет.
1.=. В каждой из кучек по одной фальшивой. Возьмём 2a монет из 1-й кучки, разделим пополам и сравним между собой получившиеся кучки по a монет в каждой.
a)=. Все 2a настоящие. Сравним их с оставшимися монетами 1-й кучки.
b)<>. Одна из них фальшивая. Сравним их оставшимися монетами 1-й кучки.
2.<>. В одной из кучек 1 и 2 все монеты настоящие, в другой есть фальшивые. Разделим 1-ю кучку пополам на 3-ю и 4-ю и сравним 3-ю с 4-й.
a)=. В 1-й либо все настоящие(тогда во 2-й есть фальшивые), либо есть 2 фальшивые, попавшие по одной в 3-ю и 4-ю(тогда во 2-й все настоящие). Разделим 3-ю пополам и сравним, чтобы выяснить это.
b)<>. В 1-й кучке есть фальшивые монеты. Значит, во 2-й кучке их нет.

manul91, кстати, ваш алгоритм(с учётом моего замечания ) тривиально переносится на числа монет вида $6k$ и $6k+1$. Таким образом, множество количеств монет с неизвестным алгоритмом взвешивания сокращается ещё больше:
$10,11,27,34.$

[lel0lel]

Алгоритм для n=10 монет:
делаем три равные кучки и одна монета в остатке (возможно для $n=3l+1$);
возможные варианты без перестановок, где 1- настоящая, 0- фальшивая:
$A=\left\{110\right\}, B=\left\{110\right\}, C=\left\{111\right\}, D=\left\{1\right\}$,
$A=\left\{111\right\}, B=\left\{111\right\}, C=\left\{110\right\}, D=\left\{0\right\}$,
$A=\left\{111\right\}, B=\left\{111\right\}, C=\left\{100\right\}, D=\left\{1\right\}$.
Замечаем, что найдутся две кучки из A,B,C с равными весами (в наших обозначениях это кучки A,B). Найти кучку с весом, для которой найдется кучка с таким же весом, можно за одно взвешивание: если взвесили и кучки равны, то требуемую кучку нашли; если вес оказался разным, то берем кучку, оставшуюся в стороне. Далее рассматриваем найденную кучку и монету, лежащую в стороне. После одного взвешивания мы имеем три варианта: $A=\left\{110\right\}, D=\left\{1\right\}; A=\left\{111\right\}, D=\left\{0\right\}; A=\left\{111\right\}, D=\left\{1\right\}.$
В первых двух вариантах за два взвешивания (каждый раз деля монеты пополам) мы ответим на вопрос задачи. В третьем же случае делаем одно взвешивание (вес окажется равным и мы поймем, что у нас за случай). Тогда вернёмся к исходным кучкам, про которые, по первому взвешиванию, мы знаем либо $A=B$, либо $B>C$, либо $C>B$. В первом случае A сравниваем с кучкой C, а в двух других A можно сравнить c B или C.
Обобщается для $n=12k+10$.

(Оффтоп)

manul91 в сообщении #1238904 писал(а):

Еще две для 3-его класса

manul91 в сообщении #1238904 писал(а):

"Винная": есть два одинаковых стакана, у обоих одинаковое количество вина

Так я и полюбил математику

[manul91]

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

Если в кучке B 2 фальшивые монеты, результат может зависеть от их распределения по половинкам. По-моему, продуктивнее поделить пополам одну из кучек A или C. В остальном похоже на правду.

Да, это описка - в этом случае (A<B, C<B) конечно делим А (или С).

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

manul91, кстати, ваш алгоритм(с учётом моего замечания ) тривиально переносится на числа монет вида $6k$ и $6k+1$.

Да, похоже это так (дело в том что оригинальная задача была с 317 монет а это число не тех типов, так что я не пробовал).

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

множество количеств монет с неизвестным алгоритмом взвешивания сокращается ещё больше: $10,11,27,34.$

После решения lel0lel остаются вроде как минимум 11 и 27

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

Обобщается для $n=12k+10$.

Как?

[lel0lel]

Чтобы было три равные кучки и одна монета нужно чтобы $n=3l+1$. Ещё нужно чтобы количество монет в кучке с добавлением одной монеты делилось на 4, то есть $l+1=4k$. Это требование появляется отсюда

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

В первых двух вариантах за два взвешивания (каждый раз деля монеты пополам)

В остальном всё аналогично.

Сейчас внимательно посмотрел: условие делимости $l$ на 4 слишком жёсткое. Можно немного изменить вышеизложенное доказательство, чтобы оно было верно для всех $n=3l+1$. А если ещё немного изменить , то будет верно для $n=3l+2$.
P.S. суть задачи в разбиении всех монет на три равные кучки с остатком монет 1 или 2 и определении среди них кучки для которой есть равная по весу (можно сделать за одно взвешивание). В ней не может быть больше двух фальшивых монет.

[kotenok gav]

Тогда остается только 27!

[Geen]

А для 4-ёх уже решили?

[Sender]

Да, как и для двух.

[lel0lel]

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

А для 4-ёх уже решили?

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

[lel0lel]

Решение для 27 монет: (Ух, я поспешил, решение неверное)
делаем, конечно, три кучки по 9 монет. За два взвешивания сортируем их по весу (две окажутся одинакового веса). Возможные варианты разбиения: {8н+Ф}, {8н+ф}, {9н} или {9н}, {9н}, {7н+2ф}. Мы не знаем какой вариант вышел у нас, но можем выбрать кучку, которой не нашлось равной по весу, то есть выберем {9н} или {7н+2ф}. Выбираем 8 монет из этой кучки, делим пополам и проводим взвешивание. Результат может быть таким: либо весы уравновешены, тогда заключаем, что у нас {9н} (здесь я ошибся, равновесие может быть и для {7н+2ф}), либо не уравновешены, тогда мы имеем дело с {7н+2ф}. Поскольку за первые два взвешивания мы уже отсортировали кучки по весу, то нетрудно дать ответ.

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

Можно немного изменить вышеизложенное доказательство, чтобы оно было верно для всех $n=3l+1$. А если ещё немного изменить , то будет верно для $n=3l+2$.

Тут следовало быть более аккуратным, речь только о тех $n$, оставляющих формулировку задачи корректной.