Competition problem — Combinatorics

Library / /82 of 86

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it United States

Problem:

Four friends, Anna, Bob, Celia, and David, exchanged some money. For any two of these friends, exactly one gave some money to the other. For example, Celia could have given money to David but then David would not have given money to Celia. In the end, each person broke even (meaning that no one made or lost any money).

a. Is it possible that the amounts of money given were $\$ 10, \$ 20, \$ 30, \$ 40, \$ 50$ , and $\$ 60$ ?

b. Is it possible that the amounts of money given were $\$ 20, \$ 30, \$ 40, \$ 50, \$ 60$ , and $\$ 70$ ?

For each part, if your answer is yes, show that the situation is possible by describing who could have given what amounts to whom. If your answer is no, prove that the situation is not possible.

Solution

Solution:

a. The answer to (a) is yes. For example, the transactions could be as follows:

b. The answer to (b) is no. Let's reason by contradiction: assume that it is possible for the four friends to exchange the amounts $\$ 20, \$ 30, \$ 40, \$ 50, \$ 60$ , and $\$ 70$ . Without loss of generality, assume that $A$ gave $\$ 60$ to $B$ . Then $A$ must have received payments of $\$ 20$ and $\$ 40$ (since $60=20+40$ is the only way to write $60$ as a sum or difference of two numbers among $20,30,40,50$ , and $70$ ). By the exact same reasoning, $B$ must have given away $\$ 20$ and $\$ 40$ ; and yet those amounts were received by $A$ . Hence, $B$ must have given $\$ 20$ or $\$ 40$ to $A$ , contradicting that $A$ gave $B$ money. This shows that our assumption is false, and that it is not possible for the four friends to exchange the amounts $\$ 20, \$ 30$ , $\$ 40, \$ 50, \$ 60$ , and $\$ 70$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.