Here’s a slightly badly written proof to a competitive math problem. I guess I could expand it slightly if readers find it unreadable.

The following is a question from the International Mathematics Competition, 1994.

Prove that in any set S of 2n-1 different irrational numbers, there exist n irrational numbers \{s_1\dots,s_n\} such that for any \{a_1,\dots,a_n\}\in \Bbb{Q} such that

(1)  a_i\geq 0,\forall i\in\{1,\dots,n\} and (2)  \sum\limits_k a_k>0
\sum\limits_{i=1}^n a_is_i is also irrational.

Proof: We will prove this by induction. This is obviously true for n=1. Now let us assume that this is also true for n. We shall now prove the case for n+1: that amongst any 2(n+1)-1 different irrational numbers, there exist n+1 numbers such that the given condition is satisfied. We will prove this by contradiction. Let us call this 2(n+1)-1 element set A_{n+1}.
Remove any two elements from A_{n+1}. We get 2n-1 elements. By the inductive hypothesis, there exist n elements \{s_1,\dots,s_n\} such that for any \{a_1,\dots,a_n\} non-negative rational numbers amongst which at least one is strictly positive, \sum\limits_{i=1}^n a_is_i is irrational. Let us call this set of elements S_n. Now one by one, add each element of A_{n+1}\setminus S_n, to S_n to form n+1 element sets. If each of these n+1 element sets can be put into some linear combination to give us a rational number, then we can subtract the right rational linear combination of A_{n+1}\setminus S_n (which by our assumption should also be rational) to give us S_n back, which should again be a rational number. But that is a contradiction. Hence, there has to exist an n+1 tuple of elements in A_{n+1} too such that no linear combination with non-negative rational coefficients, such that at least one coefficient is positive, can give us a rational number.

Published by -

Graduate student

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: