* Бароните в кралството
Публикувано на 16 юни 2009 в раздел Математика.
Едно кралство имало 32ма рицари. Някои от тях са роби на други. Един роб може да има само 1 господар, като всеки господар е по-богат от който и да е негов роб. Рицар с поне 4 роби се нарича барон. По закон "роба на роба ми не е мой роб".
Какъв е максималният възможен брой на бароните?
Задачата е на Alex Tolpygo, Kiev
Моля опишете подробно решението си
7 барона:
B1 / / / | | / | | / | | B2 B3 B4 B5 B6 B7 /|| /|| /|| /|| /|| /|| RRRR RRRR RRRR RRRR RRRR RRRR Rформулата е floor((n-1)/4)
Ако B6 и B7 ги вземеш на мястото на двама роби от робите на B2 ще се освободят още двама роби, но все още не е достатъчно за 8ми барон.
По-интересно за мен обаче е доказателството. Аз имам едно, но се надявам някой да може да изведе друго.
B1, B6, B7 и последния R са свободни, само им трябва още един да им е барон, доказателството е следното:
за да има възможно най-много барони, те трябва да имат възможно най-малко роби и понеже всеки роб има само един господар, се дефинира дърво, и от там се извлича формулата за броя барони, прави впечатление, че условието, че бароните са по-богати не променя с нищо задачата, по-скоро е подсказка, че трябва да има йерархична структура
А ако B2, B3, B4 и B5 имат различни господари или са 2 или 3 броя? Може още малко да се освободят и да се върже за 8-и.
дам, на листче го нарисувах с 8 барона.
b1(sss) -> b2(sss) -> b3(sss) -> b4(sss) -> b5(sss) -> b6(sss) -> b7(sss) -> потенциален b8(sss)
всеки барон трябва да има 4 подчинени, връзките на подчинение трябва да са 8x4=32, => за решение с 8 барона е необходимо всеки рицар да е подчинен някому.
моето решение не съобразява, че b8->b1 е забранено от условието за богатство.
dzver - Чудесно последователно решение :) Именно така го доказах и аз - допуснах, че са 8 и доказах, че не може :)