Let $n \geq 2$ be a positive integer. On a spaceship, there are $n$ crewmates. At most one accusation of being an imposter can occur from one crewmate to another crewmate. Multiple accusations are thrown, with the following properties: • Each crewmate made a different number of accusations. • Each crewmate received a different number of accusations. • A crewmate does not accuse themself. Prove that no two crewmates made accusations at each other.
Problem
Source: Canada Repechage 2022/1 CMOQR
Tags: graph theory, Canada, repechage
Sross314
21.03.2022 07:23
I SOLVE AMONGUS
We induct on n with this claim: For n amount of amongi, Each amongus has in total n-1 amongi accusing them or being accused by them. This implies no two amongi accuse each other, and it is trivially true for n = 2.
Note that for each integer in the interval [0, n-1], there is one amongus who has accused other amongi that many times and one that has been "sussed" that many times exactly. Therefore, when we add another amongus, we must have this claim be true on the interval [0, n].
We also have, for every n, the total number of accusations being n(n-1)/2 using this claim.
Claim: Either everyone accuses this amongus OR the added amongus accuses everyone
Proof: We must have some amongus that accuses n amongi, and if this is the added amongus we are done. Otherwise, we must have the amongus who is accusing the other n-1 amongi accuse the new amongus, otherwise we have a contradiction as there must be an amongus who accuses n amongi. Using this method recursively, we find in this case that all the amongi accuse the new amongus.
With this claim, (whose proof is a little sus ngl) we have in total the number of accusations being n(n-1)/2 + n = n(n+1)/2, and therefore we cannot add another accusation as we must have exactly n(n+1)/2 accusations, therefore, our claim is maintained throughout this induction and we're done.
squareman
21.03.2022 15:23
Sus Induct on $n,$ base case trivial. Each crewmate makes at most $n-1$ accusations. So the crewmates accuse $0,1, \dots n-1$ of their crewmates respectively in some order, and receive $0,1, \dots n-1$ accusations respectively in some order. The crewmate getting $n-1$ accusations must be the one giving $0$ accusations, since everyone else makes at least one of them. Then just eject this crewmate and induct down on the remaining ones. $\blacksquare$
TortilloSquad
24.02.2023 03:38
What a sus problem We will induct on $n$. For the base case $n=2$ there is one crewmate who makes an accusation and the other who does not, so the condition is true. Now, given that for a group of $n$ crewmates, it is true that each crewmate makes a different number of accusations, each crewmate receives a different number of accusations and no two crewmates accuse each other, we will prove that for a group of $n+1$ crewmates that satisfies the first two conditions it is true that no two crewmates accuse each other. We first take the initial $n$ crewmates group and we add to it another member. Since the possible number of accusations are $0, 1, 2, \dots, n$, the newest member must have $n$ accusations since the other ones are already taken. Since the other crewmates received $0,1,2,\dots,n-1$ accusations before, with our new member they now receive $1,2,\dots,n$ accusations, so the newest crewmate must receive $0$ accusations. Clearly this new group satisfies the first two conditions. Since the new crewmate receives $0$ accusations we can ignore it. The other $n$ crewmates do not have two crewmates who accuse each other by the inductive step so no two crewmates from this group of $n+1$ accuse each other and we are done. $\blacksquare$