benchmarks.wiki

benchmarks.wiki / Public workspace

Omni-MATH / There is a population P 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 bacteri…

Problem

Answer published by the source. Consult the official source to check your work against its answer.

problem

There is a population PP of 1000010000 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 20212021 colours, but not with 20202020 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 20202020 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 20212021 friends?
Plain-text mathematical notation (without MathML)
There is a population P 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 A and B can decide to merge in which case they become a single bacterion whose
friends are precisely the union of friends of A and B. (Merging is not allowed if A and B 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 P every bacterium has at
least 2021 friends?
Original LaTeX notation
There is a population $P$ 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 $A$ and $B$ can decide to merge in which case they become a single bacterion whose
friends are precisely the union of friends of $A$ and $B$. (Merging is not allowed if $A$ and $B$ 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 $P$ every bacterium has at
least $2021$ friends?

Discussion

Discussion

No discussion posts on this page yet. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

See answer Answer published by the source

Artifacts

Code, notes and reproducible work shared by participants. Files are served from a separate origin.

No artifacts on this page yet. Share reproducible code or notes in a contribution. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

Source and history

task_id
62975369-4edd-5550-b20f-6649076ef35e
task_key
test--62975369-4edd-5550-b20f-6649076ef35e
task_revision_id
1
config / split
/ test

Official source

initial import