Prove that among any $2n+1$ irrational numbers there are $n+1$ numbers such that the sum of any $k$ of them is irrational, for all $k \in \{1,2,3,\ldots, n+1 \}$.
Problem
Source: Bulgarian IMO TST 2004, Day 3, Problem 3
Tags: algebra proposed, algebra, number theory
10.07.2013 00:26
Order the irrational numbers in some way, say that they're $a_1, a_2, a_3, \ldots$. Build up a set $A$ by starting with $B=\{1\}$. Then for each $i$, if there is no set of rational numbers $c_j$ so that $c_1b_1+c_2b_2+\ldots+c_kb_k+a_i=0$ for the numbers $b_j\in B$, that is if $a_i$ is linearly independent of $B$ over $\mathbb{Q}$, then add $a_i$ to $B$. So suppose after this process is done that there's $k$ elements in $B$, say $\{b_1, b_2, b_3\ldots b_k\}$ where $b_k=1$. Then for each $a_i$, there is exactly one set of rational numbers $r_{i, j}$ so that $a_i=r_{i, 1}b_1+r_{i, 2}b_2+\ldots+r_{i, k}b_k$. This is because if there were more than one, taking the two values for $a_i$ to be equal and moving all $b_j$ to one side gives $c_1b_1+c_2b_2+\ldots+c_kb_k=0$ for at least two nonzero $c_j$. This contradicts our choice of the $b_j$. So we can associate with each number $a_i$ a set of coefficients $r_{i, j}$. Let us look at $r_{i, 1}$. Either more $r_{i, 1}$ are positive, more are negative, or there are the same number of positive and negatives. In the first and third cases, create a set $A$ containing those $a_i$ with positive $r_{i, 1}$, and in the second case, create a set $A$ containing those $a_i$ with negative $r_{i, 1}$. Now forget about the $a_i$ with nonzero $r_{i, 1}$ and only focus on those with zero $r_{i, 1}$. We can do the same thing with $r_{i, 2}$: if there's more positive $r_{i, 2}$ or there's the same number of positive and negative, add the $a_i$ with positive $r_{i, 2}$ to $A$. Otherwise, add the $a_i$ with negative $r_{i, 2}$ to $A$. Now forget about the $a_i$ with nonzero $r_{i, 2}$ and work only with those with zero $r_{i, 2}$. Repeat this same procedure with $r_{i, 3}, r_{i, 4}$ and so on, until every number is either in $A$ or forgotten about. This happens before we reach $r_{i, k}$ because each number contains some irrational part. At each step in this procedure, there were at least as many $a_i$ thrown into $A$ as there were forgotten about, so at the end there's at least as many $a_i$ in $A$ as there are forgotten about. That is, there is at least $n+1$ elements in $A$. And given the sum of any $a_i$ in $A$, we find the lowest $j$ so that $r_{i, j}\neq 0$ for some $i$ in the sum. Clearly $j<k$. Then we have that all such $r_{i, j}$ are either nonnegative or nonpositive, so their sum is either strictly positive or strictly negative. Hence the sum cannot be rational because there's no other piece of the sum to cancel out the $b_j$ contribution and make it rational. This is not true if we switch $n+1$ for any higher number, as $n+1$ copies of $\sqrt{2}$ and $n$ copies of $-\sqrt{2}$ shows.
16.10.2019 23:57
Call a subset of the irrational numbers tangy if some linear combination of its elements with nonnegative rational coefficients (which are not all zero) is rational. More specifically, $\{a_1, a_2, \cdots, a_k\}$ is tangy if there exist $q_1, q_2, \cdots, q_k \in \mathbb{Q}^{\ge 0}$ so that $\sum q_i a_i \in \mathbb{Q}$ and $\sum q_i^2 > 0.$ Call a subset of the irrational numbers super tangy if the sum of its elements is rational. Take the largest subset of the $2n+1$ irrational numbers which is not tangy, say $S$. Let $S = \{s_1, s_2, \cdots, s_t\}.$ We consider two cases. Case 1. $|S| > n$ Then, it's clear that there cannot exist any subset $A \subseteq S$ so that $\sum_{a \in A} a \in \mathbb{Q}$, as otherwise $S$ would be tangy. This means that taking any $(n+1)-$element subset of $S$ provides the desired $n+1$ numbers. Case 2. $|S| \le n$ Let $T$ be the set comprising of the other irrational numbers (so that $|S| + |T| = 2n+1$). If $T$ has no super tangy subset, we win (just take a $(n+1)-$element subset of $T$). Otherwise, suppose that $\{e_1, e_2, \cdots, e_k\} \subseteq T$ is super tangy. Notice that each of $\{e_1\} \cup S, \{e_2\} \cup S, \cdots, \{e_k\} \cup S$ has a tangy subset. This is by the maximality of $S.$ For each $1 \le i \le k$, let $q_{i, j} \in \mathbb{Q}_{\ge 0}$ for $1 \le j \le t+1$ be so that: $$q_{i, 1} s_1 + q_{i, 2} s_2 + \cdots + q_{i, t} s_t + q_{i, t+1} e_i \in \mathbb{Q},$$ $$q_{i, t+1} > 0,$$ and $$\sum_{j = 1}^{t} q_{i, j}^2 > 0.$$ Observe then that $$\sum_{i = 1}^{k} e_i + \sum_{i = 1}^{k} \sum_{j = 1}^{t} \frac{q_{i, j} s_j}{q_{i, t+1}} \in \mathbb{Q}.$$ Hence, as $\sum_{i = 1}^{k} e_i \in \mathbb{Q},$ subtracting this from both sides of the above give that: $$\sum_{j = 1}^{t} \frac{q_{i, j} s_j}{q_{i, t+1}} \in \mathbb{Q}.$$ Since $\frac{q_{i, j}}{q_{i, t+1}}$ is always nonnegative and sometimes positive, it's clear that not all coefficients of all $s_i$'s on the LHS are zero. However, this means that $S = \{s_1, s_2, \cdots, s_t\}$ is tangy, contradiction. As we've obtained our desired contradiction, we win. $\square$