Let $n>2$ be a given positive integer. There are $n$ guests at Georg's bachelor party and each guest is friends with at least one other guest. Georg organizes a party game among the guests. Each guest receives a jug of water such that there are no two guests with the same amount of water in their jugs. All guests now proceed simultaneously as follows. Every guest takes one cup for each of his friends at the party and distributes all the water from his jug evenly in the cups. He then passes a cup to each of his friends. Each guest having received a cup of water from each of his friends pours the water he has received into his jug. What is the smallest possible number of guests that do not have the same amount of water as they started with?
Problem
Source: Baltic Way 2020, Problem 6
Tags: combinatorics, combinatorics proposed
Diego17
12.04.2021 18:36
Answer deleted
JustSomeName
15.04.2021 18:57
Notice that the water is distributed EVENLY. This is not possible and the answer is 2. Diego17 wrote: a gives 1L to b, 2L to c;
kvanta
18.04.2021 03:54
As mentioned above, the answer is 2. Construction: Arrange the guests in a row, and let two people be friends iff they are next to each other. n even: Let the guests have 0, 1, 2, ..., n-3, n-2, (n-1)/2 litres of water respectively (note that the last value is not an integer, so it doesn't overlap with any of the previous ones) n odd: Let the guests have 0.5, 2, 3, ..., n-2, n-1, n/2 litres of water respectively (again, n/2 is not an integer). Bound: We shall show that there is a guest who ends up with less water than they started with. Suppose otherwise. Consider the value (starting amount of water)/(number of friends) for each guest; pick any guest who maximises this; let his (starting amount of water)/(number of friends) be M. Then he receives at most M litres of water from each friend, and so his amount of water does not increase. For equality to hold, all his friends must also have (starting amount of water)/(number of friends) equal to M. Repeating this argument for each of them, we get that everyone in this connected component in the friendship graph has (starting amount of water)/(number of friends) equal to M. Applying Euler's Handshaking Lemma on this connected component, two people have the same number of friends, and so the same starting amount of water, contradiction. Since the total amount of water is invariant, someone also ends up with more water than they started with. Hence, at least 2 people don't end up with the same amount of water they started with.