Математическое и загадочное

[E.K.]

Тогда вот ещё задачка:

 

У фанклубня есть восемь монет: семь настоящих и одна фальшивая, которая отличается по весу. Тяжелее или легче - неизвестно. У админа есть чашечные весы, которыми можно взвешивать монеты. За каждое взвешивание админ берёт одну монету [на пиво]. Если монета оказалась настоящей (админ умеет это определять), то он сообщает настоящий результат взвешивания. Если фальшивой - то случайный. Может ли фанклубень определить пять настоящих монет и сохранить их?

[den]

6 часов назад, E.K. сказал:

Тогда вот ещё задачка:

 

У фанклубня есть восемь монет: 

За взвешивание 4-ой монеты у админа уже 4 монеты и у фанклубня (хотя сейчас просто клуб, а не фанклуб) на руках останется 4 монеты, узнать результат 5-ти монет он сможет, но тогда на руках у него будет уже 3 монеты.

[E.K.]

6 minutes ago, den said:

(хотя сейчас просто клуб, а не фанклуб)

Ну да.. но можно по традиции буду обращаться "фанклубни"?

 

7 minutes ago, den said:

на руках останется 4 монеты, узнать результат 5-ти монет он сможет, но тогда на руках у него будет уже 3 монеты.

Это зависит от правильности алгоритма взвешивания 🙂

[Рогожников Евгений]

Как всегда удивляюсь, сколько разных интересных задач есть с этими взвешиваниями. Такую не слышал. Интересная. Решал сейчас, пока гулял с собакой. Так что и её заслуга в решении 😅

 

Ключевым соображением будет следующее очевидное соображение: если результат взвешивания будет равновесие весов, то это означает, что взвешивались настоящие монеты.  В самом деле, если мы дали админу настоящую монету, то он нам сказал правду и монеты а равновесии. А такое может быть если среди них нет фальшивой. Если же мы дали админу фальшивую монету, то остались только настоящие. В том числе и среди взвешиваемых. 

 

 

На первое взвешивание берем 4 монеты. По две на чашу. Тратим одну монету. Есть два варианта:

 

Вариант 1. Равновесие. 

Тогда 4 монеты, что взвешивались настоящие. Осталось 3 подозрительных. 

На следующее взвешивание берем одну подозрительную и одну настоящую. Платим подозрительной

 

Вариант 1.1 равновесие

Значит к 4 уже известным настоящим добавилась ещё одна. Та подозрительная, что была выведена. Т. Е знаем 5. Победа

 

Вариант 1.2 неравновесие. В этом случае, та подозрительная монета, что не взвешивалась точно является настоящей. И опять победа!! 

 

Вариант 2 неравновесие. В этом случае 3 монеты, что не взвешивались точно настоящие. Есть также две лёгких ми две тяжёлых подозрительных

 

На второе взвешивание на одну чашу весов кладём две настоящих, на другую по одной лёгкой и тяжёлой подозрительной. Платим подозрительной

 

Вариант 2.1 равновесие

Тогда обе взвешиваемые подозрительные теперь становятся точно настоящими. И они добавляются к трём уже известным. Победа!!! 

 

Вариант 2.2 неравновесие. 

Тогда одна подозрительная, что не взвешивалась становится настоящей. И знаем уже о четырёх. 

Если чаша с подозрительными была легче, то тяжёлая подозрительная также может быть только настоящей. Итого опять знаем о 5 . Победа!! ! 

Аналогично, если чаша с подозрительными тяжелее, то подозрительная лёгкая точно настоящая. Опять победа!!! 

 

Всё!!! 

Изменено 29 января, 2023 пользователем Рогожников Евгений

[E.K.]

Верно. Теперь же можно чуть усложнить условие.

 

Пусть у нас N монет, из которых одна фальшивая (отклонение по весу) и собственные весы. Какое максимальное N чтобы найти фальшивую за три взвешивания? А за m взвешиваний?

[Рогожников Евгений]

 

1 час назад, E.K. сказал:

Теперь же можно чуть усложнить условие.

по последнему условию не до конца понял. теперь у нас нет админа? т.е классическая задача, когда есть весы с бесплатным взвешиванием? Но она простая - моему ребенку давали в 4-м классе. Т.е тут условие упрощается.

 

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

 

Логичным расширением будут  следующие:

 

Вместо 8 монет у нас N монет. Какое максимальное число монет можно сохранить, узнав достоверно что они настоящие?

Это довольно сложная уже задача. Ранее было доказано, что можно сохранить 5 монет, но не было даже доказано, что нельзя сохранить 6.

Попутно можно еще запросить минимальное число взвешиваний. Это также сильно усложнит задачу.

 

Еще более сложная версия получится, если допустить, что у нас не одна, а m фальшивых монет. Но это, мне кажется, вообще уже "гроб". В том плане, что потянет на научную проблему

 

[E.K.]

Нет-нет, без админа и ренты. Просто кучка монет среди которых одна фальшивая. Какое максимальное количество монет решабельно за 3 взвешивания? За m взвешиваний?

[Рогожников Евгений]

3 часа назад, E.K. сказал:

Просто кучка монет среди которых одна фальшивая. Какое максимальное количество монет решабельно за 3 взвешивания? За m взвешиваний?

 

Рассмотрим сначала более простой случай, когда известно, что фальшивая монета легче настоящей.

 

Пусть у нас N монет. Разделим их на три "равные" кучки. В двух кучках монет будет поровну, а в третьей число может отличаться, но не более чем на одну монету. Взвешивать будем те кучки, где монет поровну. Может быть 3 исхода:

- равновесие. Тогда фальшивая монета в кучке, что не взвешивалась.

- левая чаша легче. Тогда фальшивая монета в левой чаше

- правая чаша легче. Тогда фальшивая монета в правой чаше

 

По итогу, за одно взвешивание мы свели задачу к предыдущей, но теперь у нас монет в 3 раза меньше.

А, значит, по индукции мы получаем, что если  3^k < N <= 3^(k+1), то фальшивую можно всегда найти за (k+1) взвешивание

 

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

 

Рассмотрим теперь случай, когда известно только, что фальшивая монета отличается по весу.

Во первых, тут сразу будет особый случай, когда N=2. Ясно, что тут мы вообще не сможем определить фальшивую монету.

 

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

Для этого мы просто взвесим легкую кучку с той кучкой, что не взвешивалась. Возможно три исхода:

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

- легкая кучка снова легче. Значит, фальшивая монета в легкой кучке. Значит, она легче.

- легкая кучка теперь тяжелее. Такого не может быть

 

Таким образом, за одно дополнительное взвешивание мы решили и эту задачу.

 

Но тут есть нюанс.  Это дополнительное взвешивание мы делали со всеми монетами легкой кучки. И для взвешивания нам нужна вторая кучка в которой известно, что все  монеты настоящие и их столько же, сколько в легкой кучке. Монеты мы брали из кучки, что не взвешивали, так как после итерации нам стало известно, что они настоящие. Однако, в невзвешиваемой кучке монет может быть на одну меньше!!! Это не проблема, если у нас не первая итерация. Мы просто возьмем еще монету, отсеянную на предыдущей итерации.

 

Если же у нас первая итерация, то мы будем делить не на три "равные" кучки. На самом деле, там нам главное, чтобы в каждой из кучек было не более 3^k монет ( чтобы работал шаг индукции). И мы поделим так, чтобы во взвешиваемых кучках монет было поровну, а в той что не взвешивается монет было больше ( но не больше чем  3^k). Это можно сделать всегда, кроме случая, когда N= 3^(k+1) - 1.  В последнем случае нам потребуется два взвешивания на установления того легче или тяжелее фальшивая монета.

 

 

Итого: ответ такой. 

Если N=2, то нельзя найти фальшивую.

Если 3^k < N < 3^(k+1) - 1, то будет нужно k+2 взвешивания

Если  N= 3^(k+1) - 1, то будет нужно k+3 взвешивания

Если  N= 3^(k+1) , то будет нужно k+2 взвешивания

 

 

[E.K.]

Неа..

4 монеты (3^(k=1) + 1) решаются за 2 взвешивания.

13 монет (3^(k=2) + 4) решаются за 3 хода...

[Рогожников Евгений]

50 минут назад, E.K. сказал:

4 монеты (3^(k=1) + 1) решаются за 2 взвешивания.

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

если же не требовать, то где то можно сэкономить одно взвешивание. подумаю тогда. сейчас на работе

[E.K.]

Да, вроде бы правильно.. А теперь в условиях когда нам не нужно выяснять легче фальшивка или тяжелее. 4 монеты решаются за 2 взвешивания, 13 монет за 3. Рабочая гипотеза, что максимальное количество монет за k взвешиваний определяется по формуле N = (3^k - 1)/2. То есть, за 4 взвешивания мы можем вычислить какая фальшивая из 40 монет.

[Рогожников Евгений]

Всё никак нет времени нормально подумать. Так урывками. Но у меня складывается ощущение, что этот вариант, потяжелее, и, возможно, простой формулы не будет. Сейчас пока размышляю в следующем направлении: когда известно легче монета или нет, то с ростом числа монет число взвешиваний монотонно растёт со скачком в 3^ k. Т. е ситуация простая. Если же неизвестно легче монета или нет, то ясно, что монотонность числа взвешиваний также сохраняется. Надо найти закономерность точек роста. Ясно, что они будут уже между степеней тройки и ясно что между двух степеней только одна точка. Надеюсь, что есть тут простая закономерность. 

 

Хоть и не люблю перебор, но, возможно, надо попробовать его. Хотя бы до 3^8.может, тогда получится угадать закономерность

[E.K.]

On 31.01.2023 at 10:59, Рогожников Евгений said:

Если N=2, то нельзя найти фальшивую.

Если 3^k < N < 3^(k+1) - 1, то будет нужно k+2 взвешивания

Если  N= 3^(k+1) - 1, то будет нужно k+3 взвешивания

Если  N= 3^(k+1) , то будет нужно k+2 взвешивания

Увы, метод не оптимальный. За 3 взвешивания можно определить фальшивую среди 12 монет и выяснить тяжелее она или легче.

 

Делим на три кучки 4+4+4 (A+B+C).

(1) взвешивание: A?B.

Если равны, то A+B настоящие, фальшивая в C. Делим её на 3+1.

 

(2) взвешивание трёх настоящих с тремя подозрительными.

Если равны, то фальшивая оставшаяся, третьим взвешиванием (3) определяем тяжелее она или легче.

Если не равны, то знаем тяжелее или легче. (3) сравниваем две оставшиеся. Если равны, то фальшивая третья. Если больше-меньше, то вот она.

 

Если после (1) взвешивания не равны, то C - настоящие. Снимаем три монеты из B и заменяем из на настоящие из C. Оставшуюся на весах монету из B меняем местами одной монетой из A. То есть, на одной чашке весов три монеты из А и одна из B, на второй одна из A и три "честных" из C.

 

(2) сравниваем их.

Если равны, то фальшивая одна из снятых трёх B. Если не равны и весы не поменяли положение больше-меньше, то фальшивая одна из трёх A. При этом по результату взвешивания (1) понятно легче она или тяжелее. (3) Сравниваем две из этих трёх. Если не равны, то которая больше/меньше - фальшивая. Если равны, то фальшивая оставшаяся.

 

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

 

Всё. Есть ещё заумное решение вон там.

 

То есть, 12 монет: за 3 взвешивания  можно определить фальшивую монету и легче она или тяжелее. Аналогично за 3 взвешивания можно определить фальшивую монету среди 13 монет, но есть риск не понять легче она или тяжелее.

[E.K.]

За два взвешивания можно определить фальшивую и её вес на трёх монетах. Аналогично среди 4 монет за два взвешивания определяется фальшивая, но без веса.

 

Итого, вес и фальшивость за k взвешиваний можно определить для N монет:

N = 3^(k/2), если k - чётное.

N = 4*3^((k-1)/2), если k - нечётное.

[Рогожников Евгений]

21 час назад, E.K. сказал:

Рабочая гипотеза, что максимальное количество монет за k взвешиваний определяется по формуле N = (3^k - 1)/2.

Кажется, удалось доказать, что для такого N хватит k взвешиваний. На счёт максимальности вопрос пока открыт, но очень похоже на то, судя по доказательству. Там каждый шаг на "тонкой"  грани. 

 

Само доказательство приведу позже. С телефона неудобно писать. Оно не такое сложное оказалось, но длинноватое. 

 

Кину только идею достаточно подробнуб. Через N(k) обозначим то что в формуле. Тогда

N(k+1) =3*N(k) +1

 

На первое взвешивание берем по  N(k) монет. При равновесии у нас  N(k) +1 подозрительная остаётся. Т. е больше максимального на k   взвешиваний. Но зато есть ещё набор монет, что точно настоящие.  При неравновесии у нас будут  по N(k) лёгких и тяжёлых подозрительных. Далее будет рекурсия вниз трех типов. на k  взвешиваний будет либо N(k) +1 подозрительная, либо по N(k) подозрительно лёгких и тяжёлых, либо N(k) и N(k) -1. 

 

Как только рекурсия получена, то всё. База уже есть и решение готово