Ivan's island
  • Home
  • Blog
  • CATEGORIES
  • Rules

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

2/11/2016

13 Comments

 
Имаме везни и предмет с неизвестно целочислено тегло между 1 и 100 грама включително. Кой е минималният брой тежести (и теглото на всяка от тях) достатъчни за да се измери теглото на предмета?
Picture
13 Comments
tom
2/11/2016 11:00:39

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

Reply
Иван
2/12/2016 09:01:41

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

Reply
Иван
2/12/2016 09:08:12

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

Reply
Cliff_Burton
1/29/2019 17:43:16

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

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

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

Reply
Cliff_Burton
1/29/2019 18:56:52

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

Reply
Иван
1/29/2019 19:16:35

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

Reply
Cliff_Burton
1/29/2019 19:32:52

4, 6, 18, 18, 54

Иван
1/29/2019 21:33:20

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

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

Reply
Cliff_Burton
1/29/2019 22:25:18

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

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

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

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

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

Reply
Иван
1/30/2019 10:36:15

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

Reply
Cliff_Burton
1/30/2019 14:34:40

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

Reply
Cliff_Burton
2/5/2019 13:34:48

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

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

Reply
Иван
2/5/2019 14:30:55

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

Reply

Your comment will be posted after it is approved.


Leave a Reply.

    RSS Feed

    This website uses marketing and tracking technologies. Opting out of this will opt you out of all cookies, except for those needed to run the website. Note that some products may not work as well without tracking cookies.

    Opt Out of Cookies

    Categories

    All
    Alan Turing
    Aphorisms
    Art
    Asymmetries
    Bacillus Bulgaricus
    Economics
    Environment
    History
    Hr
    InEnglish
    Intelligence
    Language
    Mathematics
    Music
    Paradoxes
    Politics
    Psychology
    Reading&writing
    Seriouslessness

    Archives

    June 2023
    May 2023
    April 2023
    March 2023
    February 2023
    January 2023
    December 2022
    November 2022
    October 2022
    September 2022
    August 2022
    July 2022
    June 2022
    May 2022
    April 2022
    March 2022
    February 2022
    January 2022
    December 2021
    November 2021
    October 2021
    September 2021
    August 2021
    July 2021
    June 2021
    May 2021
    April 2021
    March 2021
    February 2021
    January 2021
    December 2020
    November 2020
    October 2020
    September 2020
    August 2020
    July 2020
    June 2020
    May 2020
    April 2020
    March 2020
    February 2020
    January 2020
    December 2019
    November 2019
    October 2019
    September 2019
    August 2019
    July 2019
    June 2019
    May 2019
    April 2019
    March 2019
    February 2019
    January 2019
    December 2018
    November 2018
    October 2018
    September 2018
    August 2018
    July 2018
    June 2018
    May 2018
    April 2018
    March 2018
    February 2018
    January 2018
    December 2017
    November 2017
    October 2017
    September 2017
    August 2017
    July 2017
    June 2017
    May 2017
    April 2017
    March 2017
    February 2017
    January 2017
    December 2016
    November 2016
    October 2016
    September 2016
    August 2016
    July 2016
    June 2016
    May 2016
    April 2016
    March 2016
    February 2016
    January 2016
    December 2015
    November 2015
    October 2015
    September 2015
    August 2015
    July 2015
    June 2015
    May 2015
    April 2015
    March 2015
    February 2015
    January 2015
    December 2014
    November 2014
    October 2014
    September 2014
    August 2014
    July 2014
    June 2014
    May 2014
    April 2014
    March 2014
    February 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013
    August 2013
    July 2013
    June 2013
    May 2013
    April 2013
    March 2013
    February 2013
    January 2013
    August 2012

Powered by Create your own unique website with customizable templates.