olymmath

BALKAN-SL 2021 C6

    There is a population PP of 10000 bacteria, some of which are friends (friendship is mutual), so that each bacterion has at least one friend and if we wish to assign to each bacterion a coloured membrane so that no two friends have the same colour, then there is a way to do it with 2021 colours, but not with 2020 or less.

    Two friends AA and BB can decide to merge in which case they become a single bacterion whose friends are precisely the union of friends of AA and BB. (Merging is not allowed if AA and BB are not friends.) It turns out that no matter how we perform one merge or two consecutive merges, in the resulting population it would be possible to assign 2020 colours or less so that no two friends have the same colour. Is it true that in any such population PP every bacterium has at least 2021 friends?

    Dataset text NuminaMath olympiads. Quoted with source.

    Solutions

    No solution is on olymmath yet. Official and human solutions come first when they arrive. AI solutions come after them, with a label.

    Add a solution

    Locator balkan-sl/2021/c6 · Tag 7Z6RZQ0VQF · Edit this page on GitHub · Keys: j next, k previous