Проблем с везни

2/11/2016

Имаме везни и предмет с неизвестно целочислено тегло между 1 и 100 грама включително. Кой е минималният брой тежести (и теглото на всяка от тях) достатъчни за да се измери теглото на предмета?

13 Comments

tom

2/11/2016 11:00:39

A тежестите през 1 грам ли са или нещо от типа на 50-20-20-10-5-2-2-1?

Иван

2/12/2016 09:01:41

Тежестите са по избор на клиента. Ако бяха през грам и започваха от 1 г, то 14 тежести вършат работа (за предмети с тегло до 105 г), но 14 е много, защото тогава ще можем да измерим предмет с тегло 10 г по много начини: 2+8, 5+4+1 и т.н.

Иван

2/12/2016 09:08:12

Хората казват че чувството ми за хумор е странно, но като гледам предложението ти ми се струва че мислиш за пари :-)
Това са деноминациите на нашенските банкноти :-)

Cliff_Burton

1/29/2019 17:43:16

Не съм сигурен, че е оптимално решение, но с тежести от 1, 4, 8, 16, 32 и 64 грама би трябвало да може да се измери теглото на предмета.

Пояснение защо тежест с тегло 2 грама не ни е нужна - ако след няколко измервания сме установили, че предметът тежи 10 или 11 грама слагаме едната страна на везната въпросният предмет с тежест от 1 грам, а от другата страна тежести от 8 и 4 грама. Ако везната е в равновесие, предметът тежи 11 грама, а в противен случай 10 грама.

Аналогично за останалите гранични случаи.

Cliff_Burton

1/29/2019 18:56:52

Всъщност с четири тежести съответно по 4, 6, 18 и 54 грама може да се измери всеки предмет до 86 грама включително, така че задачата е решима с пет тежести.

Иван

1/29/2019 19:16:35

И кои са петте тежести?

Cliff_Burton

1/29/2019 19:32:52

4, 6, 18, 18, 54

Иван

1/29/2019 21:33:20

Може и да си прав, но определено ще пада много работа (мерене). Което ми напомня за Фрактран-алгоритъма на Джон Конуей за изчисляване на простите числа. Ако се напънеш и напишеш статия по темата, сигурно ще е много интересна.

Ако случайно не знаеш, стандартният отговор е: числата са 5 и са степените на 3, които са по-малки от 100 (везната има 3 положения: по-тежко, по-леко, равновесие).

Cliff_Burton

1/29/2019 22:25:18

Факт е, ще пада много работа, но в задачата се търсеше само най-оптимално решение като брой тежести, а не като брой операции.

Стандартният отговор не го знаех, но и предложеното решение стъпва на идеята, че везната има три положения.

Търсих най-малката двойка числа, от които мога да започна. Тази двойка е 4, 6 (от нея можем да намерим предмет с тегло 2) и съответно предмети с тегло 1, 3 и 5. Всяка следваща тежест смятаме по формулата: (сумата на тежестите до момент - 1) * 2 и с наличните тежести винаги можем да претеглим предмети с четно тегло и да преценим дали предмети с нечетно тегло са по-тежки или по-леки (с отклонение единица) от четно тегло.

Реално за тежестите като изключим първата тежест пак отиваме до степените на тройката => 2*3^(n-1) за всяка n-та тежест и само първият член на редицата е различен.

Плюсът на тази редица спрямо класическото решение е, че за предме

Иван

1/30/2019 10:36:15

Съжалявам, яви се проблемът с дължината на постовете, за който предупреждавам на страницата "Правила". Определено тук не е място за дълбоки разсъждения. И като казвам "дълбоки", ето нещо по темата: https://arxiv.org/pdf/1010.5486.pdf

Cliff_Burton

1/30/2019 14:34:40

Ще разгледам линка, благодаря. И огромни благодарности за блога, след има няма 20 години позанемаряване на математиката преглеждането на статиите тук ме накара пак да почна да се замислям :)

Cliff_Burton

2/5/2019 13:34:48

Ще си позволява да пусна и аз една задача. Този път обаче ще работим с кантар, а не с везни.

На царят на една страна му подшушнали, че в една от областите, които управлява го цакат с данъците. Уж плащат колкото трябва златни монети, но монетите вместо по десет грама били с по един грам по-малко.. Същата година се били събрал сто чувалчета, всяко с по сто златни монети. Царят имал голям хубав кантар и решил да провери слуховете на принципа "ръка да види, око да пипне". Царят знаел, че пет часа претегляния спестяват пет минути сметки, но въпреки това решил да се напъне малко и да помисли с колко най-малко претегляния може да намери чувала с фалшивите монети. Помислил, помислил, пък се сетил. С колко претегляния е успял да го открие?

Иван

2/5/2019 14:30:55

Знам я тази, хубава е.

Your comment will be posted after it is approved.

Проблем с везни

Leave a Reply.

Categories

Archives