This has solutions to the Equal coins puzzle posted earlier.
A brief description of the problem:
There are $2n+1$ reals numbers, $r_1, r_2, \dots, r_{2n+1}$. Given any $r_i$, you can split the remaining $2n$ into two groups of $n$ each, such that the sum of elements of one group is the same as the sum of elements of the other group.
Show that $r_i = r_j$ (i.e. all must be equal).
Solutions
All the solutions that I know use Linear Algebra (if you know/can think of one without using Linear Algebra, please share!).
Solution 1)
This is the solution I had come up with when I first saw this problem.
The property basically means that there is a $(2n+1)\times(2n+1)$ matrix $A$ such that
Every row of $A$ has exactly $n$ ones and $n$ minus ones.
The main diagonal of $A$ is $0$
$Ax = 0$ has a non-trivial solution.
Since $x = [1,1, \dots, 1]$ is an obvious solution, in order to show that all the coins/real numbers must be equal, it is enough if we show that the rank of $A$ is $2n$.
Consider the characteristic polynomial of $A$, $P_{A}(t) = \det(A - tI)$.
It is enough to show that coefficient of $t$ in $P_{A}(t)$ is non-zero.
Consider the formula for the determinant of an $N \times N$ matrix $M$
$$ \det M = \sum_{\sigma} \text{sign}(\sigma)\prod_{i=1}^N M_{i\sigma(i)}$$
where $\sigma$ runs over the permutations of $\{1,2, \dots, N\}$ and $\text{sign}$ gives the sign (based on the parity of the permutation).
For the $P_{A}(t)$, the coefficient of $t$ is given by those permutations such that there is exactly one $i$ such that $\sigma(i) = i$.
Since each product $\prod A_{j \sigma(j)}$ is $\pm 1$, the coefficient of $t$ is a sum of ones and minus ones.
It is thus enough to show that there is an odd number of such permutations.
This number is basically $(2n+1)D_{2n}$, where $D_{2n}$ is the number of derangments of $1,2 \dots, 2n$!
This is easily shown to be odd (based on a recursive formulas) and is left as an exercise :-).
I was quite happy with this solution, when Professor David Zuckerman of UT Austin showed me this neat proof:
Solution 2)
Like 1), we start with matrix $A$, but consider it over $\mathbb{F}_2$, the field of ${0,1}$. One can show that $rank(A)$ over $\mathbb{R} \ge rank(A)$ over $\mathbb{F_2}$.
Now use the fact that $rank(A) + rank(B) \ge rank(A+B)$
In $\mathbb{F}_2$, A is just the all ones matrix, except the diagonal, which is all zeros.
To that, we add the all ones matrix $B$, giving the identity. The all ones matrix $B$ trivially has rank 1.
Thus we get $rank(A) + 1 \ge 2n+1$.
Since $rank(A) \ne 2n+1$ (it has a non-trivial solution), we are done.
And the third solution, which is quite neat too and generalizes to $kn+1$ numbers.
Solution 3)
First assume that the $r_i$ were integers. We can also assume they are all non-negative, as adding a fixed constant does not change the property.
Now consider the $r_i$ which has the smallest maximum.
If $ S = r_1 + r_2 + \dots + r_{2n+1}$, then the property gives us that $S = r_i \mod 2$ for every $i$.
Thus all are even or all are odd. If all are even, we can divide by $2$. If all are odd, we can subtract the smallest number.
Thus they must be equal. This easily extends to the case when the numbers are rational.
Now the Linear Algebra application: the reals are a vector space over the rationals! (See Hamel Basis). Writing the reals as a (finite) linear combination of the basis numbers, with coefficients in $\mathbb{Q}$, gives us that the coefficients of each basis vector/number should satisfy similar properties, and thus must be equal, implying the $r_i$s are equal!
A brief description of the problem:
There are $2n+1$ reals numbers, $r_1, r_2, \dots, r_{2n+1}$. Given any $r_i$, you can split the remaining $2n$ into two groups of $n$ each, such that the sum of elements of one group is the same as the sum of elements of the other group.
Show that $r_i = r_j$ (i.e. all must be equal).
Solutions
All the solutions that I know use Linear Algebra (if you know/can think of one without using Linear Algebra, please share!).
Solution 1)
This is the solution I had come up with when I first saw this problem.
The property basically means that there is a $(2n+1)\times(2n+1)$ matrix $A$ such that
Every row of $A$ has exactly $n$ ones and $n$ minus ones.
The main diagonal of $A$ is $0$
$Ax = 0$ has a non-trivial solution.
Since $x = [1,1, \dots, 1]$ is an obvious solution, in order to show that all the coins/real numbers must be equal, it is enough if we show that the rank of $A$ is $2n$.
Consider the characteristic polynomial of $A$, $P_{A}(t) = \det(A - tI)$.
It is enough to show that coefficient of $t$ in $P_{A}(t)$ is non-zero.
Consider the formula for the determinant of an $N \times N$ matrix $M$
$$ \det M = \sum_{\sigma} \text{sign}(\sigma)\prod_{i=1}^N M_{i\sigma(i)}$$
where $\sigma$ runs over the permutations of $\{1,2, \dots, N\}$ and $\text{sign}$ gives the sign (based on the parity of the permutation).
For the $P_{A}(t)$, the coefficient of $t$ is given by those permutations such that there is exactly one $i$ such that $\sigma(i) = i$.
Since each product $\prod A_{j \sigma(j)}$ is $\pm 1$, the coefficient of $t$ is a sum of ones and minus ones.
It is thus enough to show that there is an odd number of such permutations.
This number is basically $(2n+1)D_{2n}$, where $D_{2n}$ is the number of derangments of $1,2 \dots, 2n$!
This is easily shown to be odd (based on a recursive formulas) and is left as an exercise :-).
I was quite happy with this solution, when Professor David Zuckerman of UT Austin showed me this neat proof:
Solution 2)
Like 1), we start with matrix $A$, but consider it over $\mathbb{F}_2$, the field of ${0,1}$. One can show that $rank(A)$ over $\mathbb{R} \ge rank(A)$ over $\mathbb{F_2}$.
Now use the fact that $rank(A) + rank(B) \ge rank(A+B)$
In $\mathbb{F}_2$, A is just the all ones matrix, except the diagonal, which is all zeros.
To that, we add the all ones matrix $B$, giving the identity. The all ones matrix $B$ trivially has rank 1.
Thus we get $rank(A) + 1 \ge 2n+1$.
Since $rank(A) \ne 2n+1$ (it has a non-trivial solution), we are done.
And the third solution, which is quite neat too and generalizes to $kn+1$ numbers.
Solution 3)
First assume that the $r_i$ were integers. We can also assume they are all non-negative, as adding a fixed constant does not change the property.
Now consider the $r_i$ which has the smallest maximum.
If $ S = r_1 + r_2 + \dots + r_{2n+1}$, then the property gives us that $S = r_i \mod 2$ for every $i$.
Thus all are even or all are odd. If all are even, we can divide by $2$. If all are odd, we can subtract the smallest number.
Thus they must be equal. This easily extends to the case when the numbers are rational.
Now the Linear Algebra application: the reals are a vector space over the rationals! (See Hamel Basis). Writing the reals as a (finite) linear combination of the basis numbers, with coefficients in $\mathbb{Q}$, gives us that the coefficients of each basis vector/number should satisfy similar properties, and thus must be equal, implying the $r_i$s are equal!
No comments:
Post a Comment