C, PHP, VB, .NET

Дневникът на Филип Петров


* Бароните в кралството

Публикувано на 16 юни 2009 в раздел Математика.

Едно кралство имало 32ма рицари. Някои от тях са роби на други. Един роб може да има само 1 господар, като всеки господар е по-богат от който и да е негов роб. Рицар с поне 4 роби се нарича барон. По закон "роба на роба ми не е мой роб".

Какъв е максималният възможен брой на бароните?

Задачата е на Alex Tolpygo, Kiev
Моля опишете подробно решението си

 



8 коментара


  1. Ако B6 и B7 ги вземеш на мястото на двама роби от робите на B2 ще се освободят още двама роби, но все още не е достатъчно за 8ми барон.

    По-интересно за мен обаче е доказателството. Аз имам едно, но се надявам някой да може да изведе друго.

  2. B1, B6, B7 и последния R са свободни, само им трябва още един да им е барон, доказателството е следното:
    за да има възможно най-много барони, те трябва да имат възможно най-малко роби и понеже всеки роб има само един господар, се дефинира дърво, и от там се извлича формулата за броя барони, прави впечатление, че условието, че бароните са по-богати не променя с нищо задачата, по-скоро е подсказка, че трябва да има йерархична структура

  3. А ако B2, B3, B4 и B5 имат различни господари или са 2 или 3 броя? Може още малко да се освободят и да се върже за 8-и.

  4. b1(sss) -> b2(sss) -> b3(sss) -> b4(sss) -> b5(sss) -> b6(sss) -> b7(sss) -> потенциален b8(sss)

    всеки барон трябва да има 4 подчинени, връзките на подчинение трябва да са 8x4=32, => за решение с 8 барона е необходимо всеки рицар да е подчинен някому.

    моето решение не съобразява, че b8->b1 е забранено от условието за богатство.

  5. dzver - Чудесно последователно решение :) Именно така го доказах и аз - допуснах, че са 8 и доказах, че не може :)

Добави коментар

Адресът на електронната поща няма да се публикува


*