puzzle
A $3 \times 3$ arrangement of boxes is filled with one of the numbers one, seven, or nine. Prove that of the eight possible sums along the rows, the columns, and the diagonals, two sums must be equal.
I tried to use the pigeonhole principle, but there are ten possible ways to generate different sets/sums with cardinality three , and I am not able to eliminate enough possibilities. In addition, I tried to find a pattern by placing many possibilities without any luck.
An SSD-sequence is a sequence of positive integer numbers in which distinct subsets have distinct sums. If we fill our vectors with the binary representations of the elements of such a sequence, we clearly end with a sum-disjoint set of vectors. For istance, taking the SSD-sequence $3,5,6,7$ we have that $011,101,110,111$ are four sum-disjoint vectors in $\{0,1\}^3$. Erdos conjectured that $$M_n = \min\{\max(S)\;|\; S \mbox{ is a SSD sequence of length } n\}$$ satisfies $M_n \geq c\cdot 2^n$ for some constant $c$, and the problem is still open. On the other hand, it is easy to see that $M_n\leq\frac{1}{2}2^n$ by simply taking powers of two (or the identity matrix in our initial problem). Bohman proved in 1996 that the $k$ elements $s_i=a_k-a_{k-i}$ are an SSD-set, where $1\leq i\leq k$ and $\{a_n\}_{n\in\mathbb{N}}$ is the Conway-Guy sequence $$ 0, 1, 2, 4, 7, 13, 24, 44, 84, 161, 309, 594, 1164, 2284, 4484, 8807, 17305, 34301, 68008, 134852, 267420, 530356, 1051905, 2095003, 4172701, 8311101, 16554194, 32973536, 65679652, 130828948, 261127540, 521203175, 1040311347, 2076449993, \ldots$$ defined by $a_0=0,a_1=1$ and $$ a_{n+1} = 2a_n - a_{n-\lfloor\frac{1}{2}+\sqrt{2n}\rfloor}. $$ This gave the bound $M_n\leq 2^{n-2}$ for $n\geq 20$, for istance. Taking $k=11$ we get the eleven-elements SSD set: $$\{594,593,592,590,587,581,570,550,510,433,285\}$$ and by taking binary representations we have eleven sum-disjoint vectors in $\{0,1\}^{10}$ - in general, $n+2$ sum-disjoint vectors in $\{0,1\}^n$ for any $n\geq 20$ - not so many, but still better than the trivial bound.
We are clearly wasting a lot of information, since, for istance, $\{3,4,5,6,8\}$ is not an SSD-set (due to $5+6=8+3$), but the binary representations of $\{3,4,5,6,8\}$ give a five-elements sum-disjoint set of vectors in $\{0,1\}^4$.
Since there are $4$ sum-disjoint vectors in $\{0,1\}^3$, a clever tensor-trick gives that there are at least $\left\lfloor\frac{4n}{3}\right\rfloor$ sum-disjoint vectors in $\{0,1\}^n$. In the case $n=10$, these thirteen vectors are: $$\begin{array}{*10{c}} 1,0,0,0,0,0,0,0,0,0\\ 0,1,1,0,0,0,0,0,0,0\\ 0,1,0,1,0,0,0,0,0,0\\ 0,1,0,0,0,0,0,0,0,0\\ 0,0,1,1,0,0,0,0,0,0\\ 0,0,0,0,1,1,0,0,0,0\\ 0,0,0,0,1,0,1,0,0,0\\ 0,0,0,0,1,0,0,0,0,0\\ 0,0,0,0,0,1,1,0,0,0\\ 0,0,0,0,0,0,0,1,1,0\\ 0,0,0,0,0,0,0,1,0,1\\ 0,0,0,0,0,0,0,1,0,0\\ 0,0,0,0,0,0,0,0,1,1 \end{array}.$$ For the same reason, since there are $7$ sum-disjoint vectors in $\{0,1\}^5$, there are at least $14$ sum-disjoint vectors in $\{0,1\}^{10}$ and at least $\left\lfloor\frac{7n}{5}\right\rfloor$ sum-disjoint vectors in $\{0,1\}^n$.
Monte-Carlo computations below seem to suggest that there are at least $2n-3$ sum-disjoint vectors in $\{0,1\}^n$ for any $n\geq 4$. In order to fix notation, let $I_n$ be the maximum number of sum-disjoint vectors in $\{0,1\}^n$. If we manage to prove $$I_{n+1}\geq I_n+2,\tag{1}$$ we prove the $2n-3$-bound.
A simple way to achieve $(1)$ would be to take the vectors giving $I_n$, augment them with a zero in the first coordinate, then take the two additional vectors $(1,0,0,\ldots)$ and $(1,1,1,\ldots)$. Unluckyly, this naive construction does not work since $(1,1,1,1)=(1,0,0,0)+(0,1,0,0)+(0,0,1,1)$, but may be we can fix it.
There is also a graph-theoretic interpretation that may be useful. Consider a bipartite undirected graph $G$ with $m$ red nodes and $n$ ($10$ in the original problem) blue nodes (emitters), where distinct blue nodes have distinct neighbourhoods and there are only edges between a blue node and a red node. Every emitter can give a $+1$,$0$ or $-1$ weight to the elements of the set of its outcoming edges; the weight of a blue vertex is the sum of the weigths of its incoming edges. Sum-free property: if for every non-trivial weigth-assignment there exists a blue vertex with non-zero weight, we get $m$ sum-disjoint elements in $\{0,1\}^n$. For istance, the following "sum-free" graph:
gives $I_3\geq 4$ through the set of sum-free vectors $110,101,110,001$ corresponding to the neighbourhoods of the red nodes. The graph corresponding to the SSD-set $011,101,110,111$ is even nicer:
In the this paper Lev shows, through the probabilistic method, $$ I_n \geq \frac{1}{\log_2 9}\cdot(1+o(1))\cdot n\log_2(n), $$ and I think it is worth to reproduce its arguments in the specific $n=10$ case. Let $S=\{-1,0,1\}^{17}$. For any $s\in S$, let $m^+$ be the number of positive coordinates of $s$ and $m^-$ the number of negative coordinates of $s$. For a random chosen vector $d\in\{0,1\}^{17}$ the probability of being orthogonal to $s$ is equal to:
$$ \frac{1}{2^{m^+ + m^-}}\sum_{j=0}^{\min(m^-,m^+)}\binom{m^+}{j}\binom{m^-}{j}=\frac{1}{2^{m^+ + m^-}}\binom{m^+ + m^-}{m^+},$$
hence the probability for $10$ randomly chosen vectors to be simultaneously orthogonal to $s$ is very small. Since the number of elements of $S$ of a given $(m^-,m^+)$-type is just $\binom{17}{m^+ + m^-}\binom{m^+ + m^-}{m^+}$, in order to prove $I_{10}\geq 17$ it is sufficient to show that:
$$\sum_{1\leq m^+ + m^- \leq 17}\binom{17}{m^+ + m^-}\binom{m^+ + m^-}{m^+}\left(\frac{1}{2^{m^+ + m^-}}\binom{m^+ + m^-}{m^+}\right)^{10} <1,$$
that is true by direct computation. Moreover, I am now noticing that through a probabilistic argument (the Hoeffding bound) Seva on MO pushed the upper bound down to $30$.
Look at the obtained Young Tableau. Try characterizing its $(i,j)$-th element in terms of the elements of the initial Young tableau.
It is the $i$-th smallest element among all elements each of which is the $j$-th smallest element of some row in the initial Young tableau.
It is also the largest element in the upper left $i\times j$ matrix, in which each element is the $t$-th smallest element of some row in the initial Young tableaus where $t\le i$.
Let $B$ denote the Young tableau after arranging each row in ascending order.
Let $C$ denote the Young tableau after arranging each column of $B$ in ascending order.
The question is how we can prove $C$ is a standard Young tableau.
Since each column of $C$ comes from sorting the corresponding column of $B$, each column of $C$ is sorted.
Consider element $C_{i,j}$ and $C_{i,k}$ on the $i$-th row of $C$, where $j<k$. Since $C_{i,k}$ is the $i$-th smallest element in the $k$-th column of $B$, there are $i$ elements in the $k$-th column of $B$ that are at most than $C_{i,k}$. Supposed they are $B_{t_1,k}$, $B_{t_2,k}$, $\cdots$, $B_{t_i,k}$.
Hence, $B_{t_1,j}$, $B_{t_2,j}$, $\cdots$, $B_{t_i,j}$ are smaller than $C_{i,k}$. In other words, $i$ elements in the $j$-th column of $B$ are smaller than $C_{i,k}$. So must be the $i$-th smallest element in the $j$-th column of $B$. That is, $C_{i,j}< C_{i,k}$. We have proved each row of $C$ is sorted.
Best Answer
You can’t have two rows with three numbers the same. If you have $$111\\777\\ *\_\_$$ or $$111\\ \_*\_\\777$$ whatever number you put in the $*$ will make two duplicate lines.
Assume we use $111$, so don’t use $777$ or $999$. We have to use all the other possibilities. There needs to be another $1$ to make $117$ and $119$, so there are only five cells for $7$ and $9$. Say there are only two $9$s. You can’t have both $991$ and $997$