* Как да разрежем хляба?
Публикувано на 07 февруари 2012 в раздел Математика.
Задачата е от потребител "YES":
Купувам си хляб във формата на паралелепипед с размери по xyz съответно 12/12/15 см. Режа си филии с дебелина 1 см. Мога да режа само цяла равнина от цял хляб или от парче хляб.
Искам да изпека възможно най-рационално хляба в тостер, който побира парчета с дебелина 1 см. Размера на тостера е 12/20 см. Нека и парчетата да не са твърде дребни, че трудно се вадят – не по-малки от 4/6 см. (5/5 см. не отговаря на изискването, нито 3/10 см.)
Как да си нарежа хляба най-оптимално, като може да има и остатъци, които да изям без да ги пека, още докато е пресен хляба? Критерий може да бъде минимален брой разрези.
Ако може задачата да се обобщи за размери на хляба a/b/c и на тостера d/e и дебелина на филията f, която е и на тостера вътрешната дебелина. Знам че има хляб, който е съобразен с тостерите и точно 2 филии = един тостер, но това е друга тема. Нека да се приеме, че тостера има едно гнездо.
Не трябва ли критерия да бъде с минимален брой цикли на тостера? Тоест при всяко печене да е максимално пълен.
В такъв случай, поставям хляба да лежи с дългата си страна на масата и почвам да режа. Първия път напречно като отрязвам филия с размери 12х12. Втория път надлъжно - 14х12. Така ги редувам всеки четен разрез е надължно, всеки нечетен напречно докато стигна размери на хляба 4х7х12. Тогава вече не мога да продължа да ги режа по същия начин защото ще получа филии с размер 3см. За това останалото поарче разрязвам на 7 филии 4х12см. Така съм получил филии с височина 12см и ширини:
12, 14, 11, 13, 10, 12, 9, 11, 8, 10, 7, 9, 6, 8, 5, 7, 4, 4, 4, 4, 4, 4, 4
тях ги комбинирам в 9 печения на тостера по следния начин:
12 и 8; 14 и 6; 11 и 9; 13 и 7; 10 и 10; 12 и 8; 9 и 11; 5, 7, 4 и 4; 4, 4, 4, 4 и 4.
Сещам се за още една интересна задача с разрязвания. Имаме n (не, n e много нека да е к), та имаме к математика, бутилка ракия и к чаши, чиято форма/големина е неизвестна (може дори 2 чаши да са с различна форма/големина). Предложете алгоритъм, по който да се разлее ракията така че да няма сърдити. Забележете че математиците са отишли да пият и за нещастие никой не носи пергели/линийки и др. измервателни уреди.
Решението в случая к=2 е тривиално - единият налива в чашите, а другият избира от коя чаша да пие. Така първият няма да се чувства измамен, защото си мисли че е сипал по равно, а вторият няма да се сърди, защото смята че е избрал по-голямата чаша. Този вариант обаче е неприложим за к>2
Хмм, липсва голям интерес (все пак постът е писан отдавна), но аз да си кажа отговрът:)
Въвежда се подредба (произволна) сред математиците. Първият си налива в чашата толкова, колкото смята че заслужава (около 1/к от бутилката, преценено "на око"). Ако някой смята че му е много, може да му намали дозата като върне в бутилката. Но с уговорката че който последен промени съдържанието на чашата, той я взима. Така никой няма смисъл да намалява твърде много от ракията на другия, защото после ще си я пие той. Същевременно, ако си замълчи, ще допусне някой да пие повече ракия. Така вече някой от присъстващите е с ракия и свеждаме задачата до к-1 математика.
Когато останат 2ма човека без питие, ползват алгоритъмът от предишния пост.