Recently I was told the following riddle:
Let $A=(a_1,...a_n,...a_{2n},a_{2n+1})$ a 2n+1-tuple of real numbers with the following property: Whatever number $a_i$ is removed from $A$ the remaining 2n Numbers can be divided into two n-tuples $A_1$ and $A_2$ such that $\sum\limits_{i=1}^n (A_{1})_i=\sum\limits_{i=1}^n (A_{2})_i$. Prove that in this case $a_1=a_2=...=a_{2n}=a_{2n+1}$.
The guy who told me the riddle suggested prooving the statement over the Rationals and then using the axiom of choice. As I was a bit irritated I asked again and he told me that the satement over the reals is indeed dependent of the axiom of choice.
Over the natural numbers (and by multiplying with all the divisors also over the rationals) the proof isn't really difficult. But neither I can prove it over the reals nor i can imagine how a statement about finite many numbers should be dependent on the axiom of choice. Does anyone have a poof or can explain how this could require the axiom of choice?
Thanks for your answers.
Too long for a comment: Certainly no choice can be required here. The comments sketch a solution, but even without knowing the solution, this follows from a general fact: Shoenfield absoluteness. Shoenfield absoluteness (among other things) isolates a class of statements which, if provable from ZFC, are also provable from ZF. Certainly not every statement has this "absoluteness" property (e.g. the Axiom of Choice certainly doesn't :P) but a wide class do: the $\Pi^1_2$ sentences. It is not hard to see that the result in the question is $\Pi^1_2$ (actually, even better - $\Pi^1_1$, so Mostowski absoluteness is already enough, but meh :P), so if we can prove it with choice, we can prove it without choice.
I haven't defined "$\Pi^1_2$" here because it's a bit lengthy; if you look around this site you'll find it explained. Roughly speaking, a $\Pi^1_2$ sentence has the form "For every real $r$, there is some real $s$ such that [property]," where the property in question involves quantification only over natural numbers. Finite tuples of reals can be coded by single reals, so the statement above is of this form. It turns out we don't even need the "there is some real $s$," if we're a bit clever!
To de-mystify a bit: in any model $V$ of $ZF$, we can define a sub-class $L$ and show that $L$ satisfies $ZFC$ (this was done by Godel). Now, Shoenfield absoluteness says that if $\varphi$ is $\Pi^1_2$, then - for each $V\models ZF$ - $\varphi$ is true in $V$ iff $\varphi$ is true in $L$ (really I should say "the thing $V$ thinks is $L$"). Since $L$ always satisfies ZFC, that means that if ZFC proves $\varphi$, then - since $\varphi$ will always be true in $V$'s $L$ - $\varphi$ will always be true in $V$. Hence $\varphi$ is true in any model of $ZF$.
Of course this doesn't touch the proof at all, which is quite hard, but that's a story for another question.