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

[E.K.]

1 hour ago, Рогожников Евгений said:

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

Хмм.. За 2 взвешивания определяется фальшивая (без тяжелее-легче) из 4 монет. Т.е. N(2)=4. Но тогда N(3) по формуле будет 13 (верно), а N(4)=40. Вот бы эту 40 как-то проверить?

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

Итак, обещанное доказательство.

 

Напомню формулировку задачи, что мы решаем:

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

 

Ответ: N(k) = (3^k - 1)/2

 

Доказательство:

 

Заметим, что 

N(k+1) = 3*N(k)  + 1 ( соотношение 1)

 

Будем называть монету настоящей если нам достоверно известно что она нефальшивая.

Будем называть монету подозрительной если нам достоверно неизвестно фальшивая она или нет.

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

 

Рассмотрим теперь набор состояний.

 

Состояние 1   P1(k)  У нас имеется N(k) + 1 подозрительная монета и 1 настоящая

 

Состояние 2   P2(k)  У нас имеется N(k) легких подозрительных и N(k) тяжелых подозрительных и 1 настоящая

 

Состояние 3  P3(k)  У нас имеется N(k) + 1 легких подозрительных и N(k) тяжелых подозрительных (или наоборот) и 2 настоящая

 

Основная лемма.  Если мы находимся в состоянии Pi(k+1) то можно сделать взвешивание, что мы перейдем в состояние Pj(k). Здесь i - любое число от 1 до 3, а j - некоторое число

 

Доказательство леммы:

 

Пусть мы находимся в состоянии P1(k+1).  Значит у нас  N(k+1) + 1 подозрительная монета и 1 настоящая

Из соотношения 1 у нас  3*N(k) +2 подозрительных монеты.

Отложим N(k) + 1 из них.  Останется 2*N(k) +1 подозрительная и 1 настоящая. Сформируем две кучки по N(k) + 1 монете и взвесим их. Возможно 3 исхода взвешивания, каждый из которых приведет нас в состояние Pj(k) для некоторого j. В самом деле,

если равновесие, то подозрительными у нас будут та кучка что не взвешивалась. А там  N(k) + 1 монета. И настояшая монета у нас также есть. Т.е мы перешли в состояние P1(k)

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

 

Пусть мы находимся в состоянии P2(k+1). Значит у нас имеется  N(k+1) легких подозрительных и N(k+1) тяжелых подозрительных. Или, по соотношению 1  - по 3*N(k) +1 легких и тяжелых подозрительных. Отложим N(k) +1 легких и N(k)  тяжелых.

На одну чашу N(k) легких и N(k)+1 тяжелую. На другую чашу по N(k) легких и тяжелых и одну настоящую.

Возможно 3 исхода взвешивания, каждый из которых приведет нас в состояние Pj(k) для некоторого j.

В самом деле, если равновесие, то подозрительными у нас будут та кучка что не взвешивалась. А там   мы перешли в состояние P3(k). Если неравновесие, то у нас часть монет станет настоящими так как они станут легко-тяжелыми.

Если тяжелее будет чаша с настоящей монетой то переходим в состояние P2(k)

Если легче будет чаша с настоящей монетой то переходим в состояние P3(k)

 

Пусть мы находимся в состоянии P3(k+1). Без ограничения общности  у нас имеется  N(k+1) + 1 легких подозрительных и N(k+1) тяжелых подозрительных. Или, по соотношению 1  -  3*N(k) +2 легких и 3*N(k) + 1 тяжелых подозрительных. Отложим  N(k) + 1 легкую  и  N(k) тяжелую. На одну чашу положим  N(k) + 1 легких и тяжелых. На другую N(k)  легких и тяжелых и 2 настоящих.

Возможно 3 исхода взвешивания, каждый из которых приведет нас в состояние Pj(k) для некоторого j.

В самом деле, если равновесие, то подозрительными у нас будут та кучка что не взвешивалась. А там   мы перешли в состояние P3(k). Если неравновесие, то у нас часть монет станет настоящими так как они станут легко-тяжелыми.

В обоих случаях мы перейдем в состояние  P3(k). 

Если тяжелее будет чаша с настоящими монетами то переходим в состояние P3(k) когда легких монет меньше

Если легче будет чаша с настоящими монетами  то переходим в состояние P3(k) когда легких монет больше

 

Лемма доказана

 

Теперь заметим, что если у нас изначально N(k+1) монета. Т.е по соотношению 1 у нас 3*N(k) + 1 монета, то делим на 3 кучки.

Откладываем N(k) + 1 монет. На чаши весов кладем по N(k) монет.

Если равновесие то переходим в состояние P1(k)

Если неравновесие то переходим в состояние P2(k)

 

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

 

Осталось доказать, что если монет больше, то k взвешиваний может быть недостаточно.

(Продолжение следует)

 

 

 

 

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

Забавно. Я думал, что максимальность смог доказать по индукции. Но когда стал тут подробно расписывать, то упёрся в одно мелкое несоответствие. Поэтому и сделал вчера заминку. Чем больше пытался обойти несоответствие, тем больше крепла уверенность, что есть такие более максимальнон число. 

 

Сегодня я нашёл, что для k =4 можно найти фальшивую для 42 монет. Тогда как формула даёт только 40!!! 

 

Сейчас иду на работу, но потом распишу взвешивания для 42

 

Кроме того. Теперь я уверен, что простой формулы нет. С ростом k у нас N будет асимптотически стремиться к 3^k

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

[E.K.]

Наверное, пора уже дать правильный ответ. На самом деле он есть в википедии вот здесь: Задачи на взвешивание.

 

Если нужно найти фальшивую монету и определить её вес (легче-тяжелее), то максимальное число монет за k взвешиваний ->

N = (3^k - 3)/2.

То есть, за 4 взвешивания можно определить какая из 39 фальшивая и её вес.

 

Если же определять отклонение по весу не требуется, то ->

N = (3^k - 1)/2.

За 4 взвешивания можно разобраться с 40 монетами.

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

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

Если же определять отклонение по весу не требуется, то ->

N = (3^k - 1)/2.

За 4 взвешивания можно разобраться с 40 монетами.

Не верно. Я могу дать пример как разобраться с 42 монетами. Формула выше дает нижнюю грань и я чуть выше это доказал. 

 

Для упрощения объяснений введу следующую нотацию.

 

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

 

легкая монета - та для которой неизвестно настоящая она или фальшивая, но она участвовала во взвешиваниях и всегда была на легкой чаше весов. Будет обозначать ее буквой Л

 

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

 

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

 

Нотация для взвешиваний буду писать вот так:

7Т4Н3Л-14Н,  3Т2Л

Это означает, что на левой чаше весов 7 тяжелых, 4 настоящих и 3 легких. На правой чаше весов 3 тяжелых и 2 легких.

 

Лемма 1. Если есть 5 П и 1 Н. Фальшивую можно найти за 2 взвешивания.

док-во: 

 

взвешивание 1.   2П-1П1Н,  2П  

 

Если равновесие: тогда имеем что стало 4Н и 2П. 

взвешивание 2:  1П-1Н,  1П4Н.  И при любом исходе определяем фальшивую. Если равновесие - то та что не взвешивалась. Иначе та, что взвешивалась.

 

Если легче левая чаша, то стало 2Л1Т3Н

взвешивание 2: 1Л1Т-2Н, 1Л1Н.  Если равновесие - то фальшивая та что не взвешивалась. Если левая чаша легче, то та легкая что была в ней. Иначе та тяжелая, что была в ней

 

доказательство леммы 1 закончено

 

 

 

Лемма 2. Если есть 14 П и 1 Н. Фальшивую можно найти за 3 взвешивания.

док-во: 

 

взвешивание 1.   5П-4П1Н,  5П  

 

если равновесие, то стало 5П и 10Н. По лемме 1 за два взвешивания найдем фальшивую

 

-----------

Если неравновесие, то без ограничения общности можно считать, что  левая легче

имеем 5Л , 4Т, 5Н

взвешивание 2. 2Л2Т-1Л1Т1Н,  2Л1Т4Н.

 

При любом исходе получим: или 2Л 1Т 12Н  или 2Т 1Л 12Н.

без ограничений общности считаем, что имеем 2Л 1Т 12Н. 

 

взвешивание 3: 1Л1Т-2Н, 1Л10Н  - очевидно, что находим фальшивую

-----------

доказательство леммы 2 закончено

 

 

Лемма 3. Если есть 42П . Фальшивую можно найти за 4 взвешивания.

док-во: 

 

взвешивание 1.   14П-14П,  14П  

 

если равновесие, то стало 14П и 28Н. По лемме 2 за три взвешивания найдем фальшивую

 

-----------

Если неравновесие, то без ограничения общности можно считать, что  левая легче

имеем 14Л , 14Т, 14Н

 

взвешивание 2. 5Л5Т-4Л5Т1Н,  5Л 4Т 13Н

Если равновесие то будут 5Л 4Т

Если левая легче то будут 5Л 5Т

Если левая тяжелее то будут 4Л 5Т

 

без ограничения общности 2 подслучая: 5Л 4Т  и 5Л 5Т

 

 

разберем сначала 5Л 5Т

взвешивание 3

2Л2Т-1Л1Т2Н,  1Л1Т

если равновесие, то останется 1Л1Т  и за одно взвешивание с ними разбираемся

иначе без ограничения общности останется 2Л1Т.  А этот случай уже был. За одно взвешивание тут разберемся

 

Теперь случай 5Л 4Т. Он еще проще.

взвешивание 3 - на чаши весов также, а не взвешиваем вообще одну монету. Так что то же что и в предыдущем случае.

2Л2Т-1Л1Т2Н,  1Л

 

доказательство леммы 3 закончено !!!

 

Итого - для 42 найдено решение за 4 взвешивания.

 

 

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

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

 

как только у нас пошел кейс, когда взвешивание было неравновесным, то у нас более нет П. Только Т и Л. И взвешивание делаем по следующему принципу.

Каждую из групп Т и Л отдельно делим на 3 "равные" кучки. Кавычки тут по той причине, что если число не делится на 3, то в некоторых кучках будет на 1 монету больше. Каждую из трех подкучек кладем на 3 места: левая и правая чаша весов и мимо весов. В итоге, каждый вариант взвешивания оставляет под подозрением строго треть монет !!! Есть маленький, но важный нюанс. Так как кучки не всегда равные, в некоторых монет может быть больше. 

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

 

Последние рассуждения показывают, что с ростом k у нас N будет асимптотически стремиться к 3^k. Ведь на большинстве взвешиваний у нас число подозрительных монет падает почти ровно в 3 раза ( +- одна монета). 

 

 

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

[E.K.]

10 minutes ago, Рогожников Евгений said:

Не верно. Я могу дать пример как разобраться с 42 монетами. Формула выше дает нижнюю грань и я чуть выше это доказал. 

А можно не формулой, а как-то по-простому. Есть монеты 1-2-... Группируем их вот так... Потом вот так... И ещё два раза. Понимаю, что 3^4 варианта взвешиваний это как-то многовато, но хочется понять про 42.

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

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

А можно не формулой, а как-то по-простому.

Я изменил сообщение выше и привел развернутое объяснение

[E.K.]

Хмммм... Действительно 42. Врёт википедия!

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

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

Действительно 42. Врёт википедия!

Я сам удивился, когда больше 40 получилось. Изначально то кажется бредом. Ведь при первом взвешивании мы не можем отложить более 14 монет. Значит, взвешиваем аж 28 монет!!! И, если неравновесие то у нас остается 3 взвешивания и 28 подозрительных моент , что больше 27 = 3^3 . Казалось бы, все. Ведь одно взвешивание в худшем случае оставляет неокученными не менее трети монет.  Однако, тут у нас для оставшихмя подозрительных монет есть допинформация  - тяжелее они или легче

И соотношение о сохранении трети неокученных действует отдельно на группу тяжелых и на группу легких подозрительных

[_Иван]

Погоди, я не улавливаю.

 

>разберем сначала 5Л 5Т

>взвешивание 3

>2Л2Т-1Л1Т2Н, 1Л1Т

 

Тут восемь не-настоящих монет, а должно быть десять. Вне весов остаётся 2Л2Т, кажется (и это не решается --- четыре монеты одним взвешиванием не разделить). Даже если на весы что-то иначе взвалить, всё равно один из исходов будет содержать четыре не-настоящих монеты.

 

> И соотношение о сохранении трети неокученных действует отдельно на группу тяжелых и на группу легких подозрительных

 

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

 

Собственно, таким информационным подходом можно показать, что из тринадцати монет нельзя найти фальшивую и вес за три взвешивания. От противного. Первое взвешивание: либо вешаем восемь монет, тогда вне весов будет 5 монет (а это десять состояний), либо вешаем 10 монет (снова десять состояний). За два оставшихся взвешивания можно разделить не более девяти состояний. Всё, не влезает.

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

7 часов назад, _Иван сказал:

 

>разберем сначала 5Л 5Т

>взвешивание 3

>2Л2Т-1Л1Т2Н, 1Л1Т

 

Тут восемь не-настоящих монет, а должно быть десять.

Да. Косяк. Получается, что и для 4-х взвешиваний формула работает.  Возможно, она всё таки верна. 

 

7 часов назад, _Иван сказал:

Не совсем так. Соотношение действует независимо, но (не более трети всех лёгких монет) + (не более трети всех тяжёлых монет) всё ещё меньше, либо равно треть

Это то ясно.  Я имел ввиду более сильное утверждение, что на больших кучках оно почти равно трети. Т. е относительная погрешность невелика. Тем не менее, я ошибался и на счёт асимптотики. Если формула верна, то это не даст противоречия. Ведь в этом  случае на первом взвешивании для N(k+1) мы не взвесить можем только N(k) монет, что ~0.5*3^k. Соответственно, взвешиваем ~2.5*3^k. Так что, отсеивая на каждом взвешивании почти целую треть, нам как раз и понадобится  k взвешиваний

 

 

Итого: если я не допустил ошибки в доказательстве про то, что формула даёт нижнюю границу, то остаётся доказать, что больше монет взять нельзя

 

 

 

[E.K.]

Так, вроде с монетами разобрались - можно и отдохнуть. Как раз мой ребёнок готовится к олимпиаде по математике, оказалось что в прошлогодних примерах за 6й класс есть несколько вполне хороших задачек. Они очень простые, решаются в уме - но неплохие. Тем более для 6-го класса 🙂

 

Но просьба сразу ответы не выкладывать - вдруг кому-то самостоятельно захочется порешать. Давайте подождём до вторника?

 

1. Найдите шестизначное число, у которого первая цифра в 6 раз меньше суммы всех цифр справа от неё и вторая цифра в 6 раз меньше суммы всех цифр справа от неё.

 

2. Тане и Ване дали одинаковые многоугольники из бумаги. Таня отрезала от своего листа кусок, и остался квадрат. Ваня отрезал точно такой же (и по форме, и по размеру) кусок по-другому, и у него остался треугольник. Нарисуйте пример, как это могло быть.

 

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

 

 

Всё на этом.

[E.K.]

[7Glasses]

а теперь вопрос знатокам мемов: сколь будет 8+8+8? 😁

[santax]

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

А почему не  ?