Задача № 35

[Malone]

Вносител отива в банката с хиляда долара, като всички банкноти са с номинал един долар.

Носи и десет чанти.



При депозирането на сумата поставя условието:

"Моля да разпределите парите в чантите така, че когато дойда и желая да изтегля определена сума, да можете с предаването на една или няколко чанти без да ги отваряте, да ми предадете точно исканата от мен сума."



По какъв начин трябва да стане това?

Нужно е банката да има възможност да предаде при еднократно искане каквато и да е сума, като вносителят има право да поиска произволна сума в размер от един до хиляда долара, с условието броят на доларите да е цяло число.

<hr noshade size="1">

Това е задачата от мен. Мисля, че си струва.

Ако до утре по това време няма правилен отговор [в което се съмнявам] ще дам "джокер".

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

Колкото по подробно, толкова по добре.

За тези, които не успеят да намерят отговора ще е интересно, ще видите.



Успех!

[Sad Reader]

Най-лесният вариант на разпределяне на парите по чантите е:

1-ва чанта: 1 долар.

2-ра чанта: 2 долара.

3-та чанта: 4 долара.

4-та чанта: 8 долара.

5-та чанта: 16 долара.

6-та чанта: 32 долара.

7-та чанта: 64 долара.

8-та чанта: 128 долара.

9-та чанта: 256 долара.

10-та чанта: 512 долара.

т.е. в n-тата чанта да има 2^(n-1) долара.

Очевидно, с 10-разредно число представено в двойчна система може да бъде изразена стойност до 2^10 - 1 = 1023.

Т.Е. сумата може да бъде представена като сбор от наличните 10 чанти.

[Sad Reader]

П.С. за последната чанта ще останат само 489 долара, т.е. в чанта 10 ще има само 489 долара.

[Malone]

Очевидно е, че задачата ви затрудни.



Отговора на Sad Reader ще приема за верен [след допълнението], въпреки че му липсва нещо.



Прагматично погледнато, да, това е отговора на задачата, така ще бъдат разпределени банкнотите [след допълнението].



Липсва обаче "солта", "подправката" на задачата?



Каква е методиката на определянето на конкретните чанти, нужни да удовлетворят точно исканата сума от вносителя.



Примерно за 281 долара са нужни 1-ва, 4-та, 5-а и 9-а чанти.

Надявам се не мислите, че е чисто механично комбиниране на суми.

Има друг начин, много по бърз.[]



Дано ви е приятно!

Sad Reader и останалите помислете за отговор на този въпрос.

Приемете го като Bonus Level към задачата ми.



<font color="red">Пак повтарям, поради липса на друг отговор приемам отговора на Sad Reader за верен.

Негов ред е за следващата задача.</font id="red">

[Sad Reader]

Съжалявам че не обясних по-подобно как би следвало да бъдат избрани нужните чанти. Просто сумата би следвало да бъде представена в двоична бройна система, например:

281 долара = 100011001 (2) долара

понеже сумата в чантите е подредена според стойностите на всеки разряд от двоичната система, то най-младшия разряд съответства на първата чанта, следващия на втората и т.н. 10-тия разряд съответства на десетата чанта, по изключение (сумата е непълна).

При това съответствие, ако за разряда има единица то се взема съответстващата чанта, ако е нула то чантата не се взема.

[Sad Reader]

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

Вече е измислена.

[Malone]

Да, това прави отговора 100% пълен и верен.



Sad Reader не е пропуснал и уточнението си за сумата в отговора. BTW той намекна за него още в първия си пост. Неслучайно е избрана сумата 1000.



Решението ще бъде еднозначно, ако доларите бяха точно 2¹⁰-1 или 1023.

Тъй като те са само 1000, това допуска двузначни решения за суми над 489 долара. Например ако сумата е 489, тя може да се вземе само с една чанта – десетата, но може и чрез друга комбинация.

489 представено като двоично е 111101001, т.е.

1-ва, 4-та, 6-та, 7-ма, 8-ма и 9-а чанти

или

1+8+32+64+128+256 = 489.



Автор на тази задача е Хенри Ърнест Дюдни, един от големите автори и популяризатори на логически и математически главоблъсканици.



Ако при следващите задачи ми се удаде възможност ще ви представя и други негови задачи.



<font color="red">Sad Reader е наред!</font id="red">