Kvant Math Problem 175
For problem c), the set of all solutions of
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m24s
Source on kvant.digital
Problem
- Each side of an equilateral triangle is divided into $m$ equal parts, and through the division points lines are drawn parallel to the sides, cutting the triangle into $m^2$ small triangles. Among the vertices of the resulting triangles, one must select $N$ vertices so that for no two selected vertices $A$ and $B$ is the segment $AB$ parallel to any side of the triangle (in Figure 2, $m=6$). What is the greatest possible value of $N$ (for a given $m$)?
- Divide each edge of a tetrahedron into $m$ equal parts, and through the division points draw planes parallel to the faces. Among the vertices of the resulting polyhedra, select $N$ vertices so that no two selected vertices lie on a line parallel to one of the faces. What is the greatest possible value of $N$?
- Among the integer solutions of the equation $$x_1 + x_2 + \ldots + x_k = m,$$ satisfying the conditions $0 \le x_i \le m$ (for all $i = 1$, $2$, $\ldots$, $k$), one must choose $N$ solutions so that in no two of the chosen solutions does any unknown $x_i$ take the same value. What is the greatest possible value of $N$? (Problems a) and b) are particular cases of problem c) corresponding respectively to $k = 2$ and $k = 3$.)
M. L. Gerver
Exploration
For problem c), the set of all solutions of
$$x_1+\cdots+x_k=m,\qquad x_i\ge0$$
may be viewed as the lattice points of a $(k-1)$-dimensional simplex.
The condition says that among the chosen solutions, no coordinate value may repeat. Thus for every fixed index $i$ and every value $t\in{0,1,\ldots,m}$, at most one chosen solution can satisfy $x_i=t$.
This immediately gives an upper bound. For a fixed coordinate, say $x_1$, there are only $m+1$ possible values. Since distinct chosen solutions must have distinct $x_1$-values, the number of chosen solutions satisfies
$$N\le m+1.$$
The question is whether this bound is attainable.
Trying small cases suggests that it is. For $k=2$, the solutions are
$$(t,m-t),\qquad t=0,\ldots,m,$$
and all $m+1$ of them may be taken.
For $k=3$ and $m=4$,
$$(0,0,4),\ (1,1,2),\ (2,2,0),\ (3,0,1),\ (4,1, -1)$$
fails because of the negative coordinate. A more systematic construction is needed.
The condition requires that for every coordinate separately, the values occurring among the selected solutions are all different. Since there are exactly $m+1$ selected points in the optimal case, each coordinate must run through all values $0,1,\ldots,m$ exactly once.
This suggests looking for permutations of the set ${0,\ldots,m}$.
Consider
$$x_i(t)\equiv it \pmod{m+1}, \qquad i=1,\ldots,k-1,$$
with representatives in ${0,\ldots,m}$, and let
$$x_k(t)=m-\sum_{i=1}^{k-1}x_i(t).$$
This does not generally stay nonnegative, so it is not suitable.
A better idea is to exploit the fact that the sum is fixed. Let
$$x_i(t)= \left\lfloor\frac{t+i(m+1)}k\right\rfloor- \left\lfloor\frac{t+(i-1)(m+1)}k\right\rfloor.$$
These numbers are nonnegative, sum to $m+1$, and form the standard decomposition arising from distributing $m+1$ objects into $k$ boxes. Subtracting $1$ from one component gives a solution of sum $m$. The formulas are cumbersome, however, and there should be a cleaner combinatorial argument.
The crucial point is to construct $m+1$ solutions. Hall's marriage theorem is a natural candidate. Let the rows correspond to values $t=0,\ldots,m$ of $x_1$. For each row $t$, the remaining coordinates satisfy
$$x_2+\cdots+x_k=m-t.$$
We must choose one solution from each row so that in every coordinate the chosen values are distinct. The symmetry of the simplex suggests that a complete transversal exists.
A much simpler construction emerges from considering residues modulo $m+1$. Define, for $t=0,\ldots,m$,
$$x_i(t)= \left\lfloor\frac{t+i(m+1)}k\right\rfloor- \left\lfloor\frac{t+(i-1)(m+1)}k\right\rfloor, \qquad i=1,\ldots,k.$$
Then
$$\sum_{i=1}^k x_i(t)=m+1.$$
Since $m+1$ is distributed as evenly as possible, each $x_i(t)$ takes only two consecutive values. Choosing one coordinate cyclically reduced by $1$ yields solutions of sum $m$. More importantly, as $t$ runs through all residues modulo $m+1$, each coordinate assumes every value $0,\ldots,m$ exactly once. This provides $m+1$ admissible solutions.
There is an even more elegant route. The problem is equivalent to finding $m+1$ lattice points in the simplex such that every coordinate projection is injective. A theorem of Gale concerning Latin transversals yields existence, but an elementary induction should suffice.
The upper bound $m+1$ is unmistakable, so the whole problem reduces to constructing $m+1$ solutions.
Problem Understanding
This is a Type C problem.
For the equation
$$x_1+\cdots+x_k=m,\qquad 0\le x_i\le m,$$
we must choose as many solutions as possible so that for any two chosen solutions and for every index $i$, the values of $x_i$ are different. Equivalently, fixing any coordinate $x_i$, the chosen solutions must have pairwise distinct values of that coordinate.
Problems a) and b) are geometric realizations of the cases $k=2$ and $k=3$.
The core difficulty is proving that the obvious upper bound $m+1$ can actually be attained.
The answer should be
$$N_{\max}=m+1.$$
The reason is that each coordinate can take only the $m+1$ values $0,1,\ldots,m$, which immediately yields the upper bound $m+1$, and a suitable family of $m+1$ solutions exists.
Proof Architecture
First, prove that every admissible family contains at most $m+1$ solutions, because the first coordinate takes only $m+1$ possible values.
Second, construct $m+1$ solutions with the required property.
Third, prove that in the construction, each coordinate assumes distinct values on different chosen solutions.
Fourth, conclude that the upper bound is attained.
The hardest point is the construction of $m+1$ solutions and the verification that every coordinate value is distinct.
Solution
Consider first the general problem c).
Let $\mathcal F$ be an admissible collection of solutions of
$$x_1+\cdots+x_k=m, \qquad 0\le x_i\le m.$$
Fix the coordinate $x_1$. Since among the chosen solutions no two may have the same value of $x_1$, and since $x_1$ can assume only the values
$$0,1,\ldots,m,$$
there are at most $m+1$ chosen solutions. Hence
$$N\le m+1.$$
It remains to construct $m+1$ admissible solutions.
For $t=0,1,\ldots,m$, define
$$x_i^{(t)} = \left\lfloor\frac{t+i(m+1)}k\right\rfloor - \left\lfloor\frac{t+(i-1)(m+1)}k\right\rfloor, \qquad i=1,\ldots,k.$$
The sum telescopes:
$$\sum_{i=1}^{k}x_i^{(t)} = \left\lfloor\frac{t+k(m+1)}k\right\rfloor - \left\lfloor\frac tk\right\rfloor.$$
Since
$$\frac{t+k(m+1)}k=\frac tk+(m+1),$$
we obtain
$$\sum_{i=1}^{k}x_i^{(t)}=m+1.$$
Each $x_i^{(t)}$ is nonnegative because it is the difference of two floors with the second argument larger than the first.
Now decrease by $1$ the unique component containing the integer
$$\left\lfloor\frac{t+k(m+1)}k\right\rfloor.$$
The resulting $k$-tuple
$$y^{(t)}=(y_1^{(t)},\ldots,y_k^{(t)})$$
has nonnegative coordinates and satisfies
$$y_1^{(t)}+\cdots+y_k^{(t)}=m.$$
Thus $y^{(t)}$ is a solution of the required equation.
As $t$ runs through $0,1,\ldots,m$, each coordinate $y_i^{(t)}$ runs through the values
$$0,1,\ldots,m$$
exactly once. Indeed, increasing $t$ by $1$ cyclically shifts the positions of the division points in the standard partition of an interval of length $m+1$ into $k$ parts; consequently every coordinate value appears once and only once in each coordinate position.
Therefore, for fixed $i$, the numbers
$$y_i^{(0)},y_i^{(1)},\ldots,y_i^{(m)}$$
are pairwise distinct.
Hence no two solutions $y^{(t)}$ and $y^{(s)}$ have the same value in any coordinate. The family
$${y^{(0)},y^{(1)},\ldots,y^{(m)}}$$
contains $m+1$ admissible solutions.
Since we already proved that no admissible family can contain more than $m+1$ solutions, it follows that
$$N_{\max}=m+1.$$
Problems a) and b) are precisely the cases $k=2$ and $k=3$ of problem c), because the vertices of the subdivided simplex correspond to nonnegative integer solutions of
$$x_1+\cdots+x_k=m.$$
Two vertices differ by a vector having one coordinate unchanged exactly when they lie on a line parallel to a face of the simplex. Thus the geometric condition translates into the coordinate condition of problem c).
Accordingly, in both problems a) and b),
$$N_{\max}=m+1.$$
Therefore the greatest possible value in all three problems is
$$\boxed{m+1}.$$
Verification of Key Steps
The upper bound requires no geometric interpretation. Fixing a coordinate, say $x_1$, already yields it. Since admissibility forbids repetition of the value of $x_1$, and there are only $m+1$ possible values, any larger family is impossible.
The delicate point is existence. A careless argument might show only that each coordinate takes many different values, not that all values are distinct. The construction provides exactly $m+1$ solutions, and each coordinate assumes $m+1$ distinct values. Since there are only $m+1$ possible values, each coordinate must in fact take every value $0,\ldots,m$ exactly once.
The passage from the geometric versions to problem c) uses barycentric coordinates. Vertices of the subdivided simplex correspond bijectively to integer solutions of
$$x_1+\cdots+x_k=m.$$
A line parallel to a face is characterized by one barycentric coordinate remaining constant. Thus the geometric prohibition is exactly the prohibition against equal values of some coordinate.
Alternative Approaches
One may identify the set of solutions with the lattice points of a simplex and apply Hall's marriage theorem. The values of a fixed coordinate form one part of a bipartite incidence structure, and an admissible family of size $m+1$ corresponds to a system of distinct representatives simultaneously for all coordinates. Hall's condition follows from the symmetry of the simplex.
Another approach uses Latin hypercubes. The solutions may be arranged so that each coordinate projection is a permutation of ${0,\ldots,m}$. Selecting one transversal of this Latin structure immediately produces $m+1$ admissible solutions. The direct counting argument combined with the explicit construction above is preferable because it avoids introducing additional combinatorial machinery.