Contradiction Problem 2

Solution

Suppose not. That is, suppose that (1) all trades are profitable for both or neither person; and (2) no two people make profitable trades with the same number of other people. Note that if a trade is profitable for neither person, it has no effect on the number of profitable trading partners, so let's restrict our attention to only trades profitable for both people.

Since there are 103 people at the convention, each person made profitable trades with somewhere between 0 and 102 other people. By assumption (2), each person made profitable trades with a different number of other people and the range from 0 to 102 contains exactly 103 different values. So one person A made 0 profitable trades and some other person B made 102 profitable trades.

But if B made profitable trades with 102 people, he must have made a profitable trade with A. So there was a trade that profited B but not A. This contradicts assumption (1).

Since our initial assumption led to a contradiction, at least one of these must be true: (1) some trades are profitable for only one person; (2) at least two people made profitable trades with the same number of other people. QED.

Variations

There are several possible variations for this proof. There are three key steps:

  1. Suppose the negation of the claim, which in this case is a logical AND of two statements.
  2. See that the second statement requires all values from 0 to 102 to be filled (similar to pigeonhole principle).
  3. See that the first statement doesn't allow both values 0 and 102 to be filled.

Another possible version is to apply the reasoning from the first statement that values 0 and 102 cannot both be used and then apply pigeonhole principle to show the contradiction with the second statement.

You can also make a graph representation. That is, vertices are people, people are adjacent iff they traded profitably with each other. From this, you can show a contradiction with the handshaking theorem. That is, the node degrees sum up to an odd number. But the sum of node degrees in a graph is always even, because it's twice the number of edges.

Or, notice that each person made a different number of profitable trades, using up exactly all the numbers in the range 0 through 102. So the total number of profitable trades is \(\displaystyle \sum_{k=0}^{102} k = \frac{102\cdot 103}{2} = 61 \cdot 103\). This number is odd, so there must have been at least one trade that was profitable for only one of the two people involved.