Да се докаже,че с 3k+1 претегляния можем да намерим монета

[thear]

Дадени са 3(на степен 2k) монети, една от които е фалшива.Разполагаме с три везни, една от които е фалшива-тя показва произволно кой от двата товара е по-тежък или са равни. На всеки ход поставяме два товара на някоя везна и тя показва кой е по-тежкия или дали са равни.Да се докаже,че с 3k+1 претегляния можем да намерим фалшивата монета.(монетите и везните са еднакви на външен вид)

един приятел ми изпрати тая задача,все едно е написанa на китайски Някакви идеи?

[ptj]

Ако теглеше само с една нормална везна от [tex]3^{2k}[/tex] монети можеше точно с [tex]2k[/tex] претегляния да намериш фалшивата монета. Това е свързaно един вид с представянето на числата от [tex]1[/tex]до [tex]3^{2k}-1[/tex] в 3-ична бройна система (при основа 3).

Вероятно си изтървал нещо от условието, може би се има предвид, че на всяко теглене не се знае коя везна е правилна или нещо друго си объркал. Коригирай се и ще ти напиша решението.

П.П. Задачата могат да я решат и петокласници, стига да знаят какво е степен на цяло число.

[allier]

Питай го твоя приятел дали се знае фалшивата монета по-лека или по-тежка е.

[thear]

много бързи отговори бе http://www.math10.com/forumbg/viewtopic.php?t=4948 задачата е била от тоя сайт

[allier]

ptj, объркал си се нещо. Задачата е доста сериозна ... разбира се, че не се знае коя е неправилната везна.

[ptj]

Караш ме да мисля ли?

[allier]

Хаха, не, не те карам да мислиш. Ама задачата наистина е сериозна. Ти сам каза, с една везна са 2к хода, а пък сега трябва да познаеш и вярната везна от три опции. Плюс това, с 2к хода трябва да знаеш и къде да я търсиш монетата, т.е. дали е по-лека или по-тежка, а доколкото виждам в условието и това не е дадено.

[ptj]

Не мисля, че е трудна. Просто не ми е напълно ясно условието, по-точно дали невярната везна може да е фантом или не си сменя мястото. Също може ли на различните везни едновременно да има товар.

[allier]

Невярната везна не си сменя мястото. Само че реално не можеш никога да я познаеш със сигурност, тъй като тя дава случайно резултат т.е. може да даде и верния резултат. На различни везни няма смисъл едновременно да има товар, ще се брои за съответния брой претегляния просто.

[ptj]

Оригиналното условие е друго:

[allier]

Аз не разбирам много много руски, но да разбирам ли, че в това пише, че монетата е по-лека от останалите? Тогава 9 с 4 хода става доста лесно и съответно по индукция се пренася за [tex]3^{2n }[/tex].