Maths Olympiad Prep

Library / /22 of 27

Combinatorics Difficulty 6.9 National olympiad Prove it Romania

Given positive integers m2m \ge 2, n2n \ge 2, consider the set
S(m,n)={x=(x1,x2,,xm);xZ+m,k=1mxk=n}. S(m, n) = \left\{ \mathbf{x} = (x_1, x_2, \dots, x_m) ; \mathbf{x} \in \mathbb{Z}_+^m, \sum_{k=1}^m x_k = n \right\}.
Determine N(m,n)N(m, n), the largest cardinality X|X| of a subset XS(m,n)X \subseteq S(m, n) with
X={xk;xX}, for all k=1,2,,m. |X| = |\{x_k ; \mathbf{x} \in X\}|, \text{ for all } k = 1, 2, \dots, m.
Vasile Pop & Dan Schwarz

Solution

Consider such a set XS(m,n)X \subseteq S(m, n). Clearly, S(m,n)S(m, n) and thus a fortiori XX are finite sets. Then
xXxki=1X(i1)=X(X1)/2, for all k=1,2,,m, \sum_{\mathbf{x} \in X} x_k \ge \sum_{i=1}^{|X|} (i-1) = |X|(|X| - 1)/2, \text{ for all } k = 1, 2, \dots, m,
and so
nX=xXk=1mxk=k=1mxXxkmX(X1)/2, n|X| = \sum_{\mathbf{x} \in X} \sum_{k=1}^{m} x_k = \sum_{k=1}^{m} \sum_{\mathbf{x} \in X} x_k \ge m|X|(|X| - 1)/2,
hence nm(X1)/2n \ge m(|X| - 1)/2, therefore X2nm+1|X| \le \left\lfloor \frac{2n}{m} \right\rfloor + 1. This bound is thus valid for all points, and we claim it is sharp in all cases,¹¹ so N(m,n)=2nm+1N(m, n) = \left\lfloor \frac{2n}{m} \right\rfloor + 1.

Let us now, for m=3m = 3, build a model set XX with X=2n3+1|X| = \left\lfloor \frac{2n}{3} \right\rfloor + 1.
When n=3k1n = 3k-1, the above expression evaluates at 2k2k, and one can use the triplets (0,k+1,2k2)(0, k+1, 2k-2), (1,k+2,2k4)(1, k+2, 2k-4), ..., (k1,2k,0)(k-1, 2k, 0), (k,0,2k1)(k, 0, 2k-1), (k+1,1,2k3)(k+1, 1, 2k-3), ..., (2k1,k1,1)(2k-1, k-1, 1).
When n=3kn = 3k, the above expression evaluates at 2k+12k+1, and one can use the triplets (0,k,2k)(0, k, 2k), (1,k+1,2k2)(1, k+1, 2k-2), ..., (k,2k,0)(k, 2k, 0), (k+1,0,2k1)(k+1, 0, 2k-1), (k+2,1,2k3)(k+2, 1, 2k-3), ..., (2k,k1,1)(2k, k-1, 1).
When n=3k+1n = 3k + 1, the above expression evaluates at 2k+12k + 1, and one can use the triplets (0,k,2k+1)(0, k, 2k+1), (1,k+1,2k1)(1, k+1, 2k-1), ..., (k,2k,1)(k, 2k, 1), (k+1,0,2k)(k+1, 0, 2k), (k+2,1,2k2)(k+2, 1, 2k-2), ..., (2k,k1,2)(2k, k-1, 2).

Denote now, in the general case, n=2nmn' = \left\lfloor \frac{2n}{m} \right\rfloor and m=m2m' = m - 2. Then N(2,n)=n+1N(2, n') = n' + 1. We will describe how to build a model inductively.

¹¹N(2,n)=n+1=S(2,n)N(2, n) = n + 1 = |S(2, n)|, as trivially seen, while N(2n,n)=2N(2n, n) = 2, given by e.g. (0,0,,0,1,1,,1)(0, 0, \dots, 0, 1, 1, \dots, 1) and (1,1,,1,0,0,,0)(1, 1, \dots, 1, 0, 0, \dots, 0).

Now 2(nn)m2nm\lfloor \frac{2(n-n')}{m'} \rfloor \ge \lfloor \frac{2n}{m} \rfloor, since 2(nn)m2nm\frac{2(n-n')}{m'} \ge \frac{2n}{m} is equivalent to m(nn)(m2)nm(n-n') \ge (m-2)n, or 2nmn2n \ge mn', or n2nmn' \le \frac{2n}{m}, patently true given the definition of nn', so the model for N(m,nn)N(m', n-n') yields enough elements that may be adjoined to those of the model realizing N(2,n)N(2, n'), in order to create one for N(m,n)N(m, n) (valid, since m=m+2m = m' + 2 and n=(nn)+nn = (n-n') + n').

For the quite interesting particular case m=nm = n, a model set X={x,y,z}X = \{\mathbf{x}, \mathbf{y}, \mathbf{z}\} with X=2nn+1=3|X| = \lfloor \frac{2n}{n} \rfloor + 1 = 3 is also easily built inductively.
Start with n=2n=2 and x=(0,2),y=(2,0),z=(1,1)\mathbf{x} = (0,2), \mathbf{y} = (2,0), \mathbf{z} = (1,1). Have x=(x1,,xk,2)\mathbf{x} = (x_1, \dots, x_k, 2), y=(y1,,yk,0)\mathbf{y} = (y_1, \dots, y_k, 0), z=(z1,,zk,1)\mathbf{z} = (z_1, \dots, z_k, 1) already built, for some 1k<n11 \le k < n-1, and build x=(z1,,zk,0,2)\mathbf{x} = (z_1, \dots, z_k, 0,2), y=(y1,,yk,1,0)\mathbf{y} = (y_1, \dots, y_k, 1,0), z=(x1,,xk,2,1)\mathbf{z} = (x_1, \dots, x_k, 2,1), until reaching the full nn coordinates.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.