Е, да си жив и здрав за “сламката”! Май вдянах!
Оказа се, че задачата била много по-дебела, отколкото си мислех, когато я давах.
Ще опитам пълен анализ на задачата: измежду колко най-много монети (N) може да се намери точно една фалшива, ако не знаем, дали е по-лека или по-тежка от останалите, с помощта на не повече от k тегления?
Ще въведа следните означения:
Монета “Х” – такава, за която не знаем нищо;
Монета “Л” – такава, за която знаем, че е или по-лека от истинските, или е истинска;
Монета “Т” – такава, за която знаем, че е или по-тежка от истинските, или е истинска;
Монета “И” – истинска монета.
Ще докажа три твърдения:
1. С k тегления може да се намери фалшивата монета измежду 3^k монети “Л” (или, което е все едно, “Т”).
Доказателството е очевидно – по индукция. Ако k=1, N=3, лемата е вярна, защото можем да сложим по 1 монета на блюдата. Ако теглата им се окажат равни, фалшивата е третата (нетеглената). Ако не са равни, понеже знаем, че всички монети са (примерно) “Л”, то фалшивата е по-леката. Ако k>1, делим монетите на 3 групи по 3^(k-1) монети. Теглим две от групите. С помощта на горните разсъждения определяме, в коя група е фалшивата монета, с което задачата се свежда до k-1 тегления на 3^(k-1) монети и т.н.
2. С k тегления може да се намери фалшивата монета измежду 3^k монети, от които (3^k+1)/2 монети са “Л” (и знаем кои) и останалите (3^k-1)/2 монети са “Т” (или, което е все едно, със смяна на “Т” и “Л”).
Доказателството е по индукция. Нека k=1, т.е. имаме 2 монети “Л” и 1 монета “Т”. Теглим двете монети “Л”. Ако теглата им са равни, фалшива е монетата “Т”. Ако не са, по-леката е фалшивата. Сега да допуснем, че твърдението е вярно за всички k<p. Ще докажа, че то е вярно и за k=p. Имаме 3^p монети, от които (3^p+1)/2 монети са “Л” и останалите (3^p-1)/2 монети са “Т”. Разделяме ги на 3 групи, така че в първите две да има по (3^(p-1)+1)/2 монети “Л” и (3^(p-1)-1)/2 монети “Т”, а в третата – (3^(p-1)-1)/2 монети “Л” и (3^(p-1)+1)/2 монети “Т”. Теглим група 1 и група 2. Ако теглата им са равни, фалшивата монета е в група 3, с което задачата се свежда до k=p-1. Ако група 1 е по-лека, фалшивата монета е между тези (3^(p-1)+1)/2 монети “Л”, които са в група 1 и тези (3^(p-1)-1)/2 монети “Т”, които са в група 2, с което задачата пак се свежда до k=p-1.
3. С k (k>1) тегления може да се намери фалшивата монета измежду (3^k-1)/2 монети “Х”, ако разполагаме с още 3^(k-1) монети “И”.
Доказателството е по индукция. За k=2 очевидно може да се открие фалшивата монета между 4 монети “Х” дори и да нямаме никакви монети “И”. Нека k>2. Да допуснем, че твърдението е вярно за всички k<p. Ще докажа, че то е вярно и за k=p. Първо теглим 3^(p-1) монети “Х” и 3^(p-1) монети “И”. Ако теглата им са равни, фалшивата монета е в нетеглените монети “Х”, които са на брой (3^(p-1)-1)/2, с което задачата се свежда до k=p-1. В противен случай фалшивата монета е в теглените монети “Х”, които обаче вече стават “Л” или “Т” и от верността на твърдение 1 следва верността на 3.
Сега сме готови да намерим това, което търсим. Последното твърдение е:
4. С k (k>1) тегления може да се намери фалшивата монета измежду (3^k-3)/2 монети “Х”. Иначе казано, търсеното N(k)= (3^k-3)/2.
Доказателството е по индукция. За k=2 очевидно може да се открие с 2 тегления фалшивата монета между 4 монети “Х”. Нека k>2. Да допуснем, че твърдението е вярно за всички k<p. Ще докажа, че то е вярно и за k=p. Имаме (3^p-3)/2 монети “Х”, които ще разделим на 3 групи по (3^(p-1)-1)/2 монети във всяка. Теглим две от групите. Ако теглата им са равни, фалшивата монета е в нетеглените монети и задачата се свежда до действията, описани при твърдение 3. В противен случай задачата се свежда до действията, описани при твърдение 2. В този случай монетите са даже с една по-малко, което не е пречка (можем просто да добавим 1 монета от монетите в нетеглената група, които със сигурност са “И”).
Всъщност този алгоритъм е много ефективен и вероятно е най-ефективният възможен. При него N(k) се оказва само с 1 монета под теоретичния абсолютен максимум, който е (3^k-1)/2!
Така с 2 тегления можем да се справим с 4 монети, т.е. N(2)=4,
N(3)=12
N(4)=39
N(5)=120
N(6)=363
N(7)=1092
N(8)=3279…
Наистина 7 тегления за достатъчни за 1000 монети!