Finding set of triplets which sum to N with additional constraints.

Question

Given a number n, we construct a set S with triplets $(x_i, y_i, z_i)$ such that $x_i+y_i+z_i = n$ $\forall$ $ 1 \le i \le |S| $. Also $x_i\ge 0, y_i\ge 0, z_i\ge 0$. Additionally we must satisfy the constraint that all $x_i's$ in S are unique and all $y_i's$ in S are unique and all $z_i's$ in S are unique.

Find the maximum size of set S and find any such set S.

This problem was part of a contest here: Beautiful Set 3 which has ended. There is tutorial section which is very terse. Although I understand what is being done there it is not very clear why that algorithm would give a correct answer.

So if you help in understand the tutorial or give another answer/algorithm, I would greatly appreciate it.

Answer 1

First we argue that $|S| \leq \frac{2n}{3} + 1$.

To see this, note that $$n|S| = \sum_i (x_i + y_i + z_i) \geq 3\frac{|S|(|S|-1)}{2}$$

Then we show how to find an $S$ with $|S| = \lfloor\frac{2n}{3} \rfloor + 1$. Suppose $n = 3k + j$ for $j = 0,1,2$

1. If $j = 0$, take the triples $(2i,k-i,2k-i)$ where $i = 0,1,2,\dots, k$ and $(2i+1,2k-i,k-i-1)$ where $i = 0,1,2,\dots, k-1$.
2. If $j=1$, take the above triples for $j = 0$ and add one to each $x_i$.
3. If $j=2$ then take the above triples for $j = 0$, add one to each $x_i$ and each $y_i$ and append the triple $(0,0,n)$.

Note that in each case there are $\lfloor\frac{2n}{3}\rfloor + 1$ triples, no $x_i,y_i,z_i$ repeats, and each triple sums to $n$.