Assume that $k$ triples may be found. The sum of the elements of these triples is clearly not smaller than $3\cdot0+3\cdot1+3\cdot2+\dots+3\cdot(k-1)$, since $0,1,2,\dots,k-1$ appear at most three times, once for each possible position inside the triple. But the sum is $kn$, or $k\leq\lfloor\frac{2n+3}{3}\rfloor$ (note that you may substitute $3$ by $\ell$ and work this part of the problem for $\ell$-tuples instead of for triples), obtaining that $k\leq\lfloor\frac{2n+\ell}{\ell}\rfloor$. Consider now $n=3m$ for some integer $m$, we can find $2m+1$ triples that satisfy the condition, taking the first element of the triples to be $0,1,2,\dots,m,m+1,m+2,\dots,2m-1,2m$, the second element to be $m,m+1,m+2,\dots,2m,0,1,\dots,m-2,m-1$, and the third element $2m,2m-2,2m-4,\dots,0,2m-1,2m-3,\dots,3,1$, and there cannot be more. For $n=3m+1$, the maximum number of triples is exactly the same, so just add $1$ to, for example, the third element of all triples found for $n=3m$, and we get again $2m+1$ triples. For $n=3m-1$, we can have at most $2m$ triples; remove for example the triple that contains $0$ in its third position in the triples found for $n=3m$, and subtract $1$ from the third element of the rest of the triples, and we get $2m$ triples. Hence the bound found in the first paragraph may be reached for all $n$, or $N(n)=\lfloor\frac{2n+3}{3}\rfloor$.

http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1306270&sid=69aec5b1fd82c1e89192c5e5d7241472#p1306270

It is not exactly proposed by me - I just arranged an idea of Vasile Pop. Indeed, the more difficult question of determining the maximum number of $\ell$-tuples, $2\leq \ell \leq n$ (rather than just triplets) was also asked. The bound $\left \lfloor \dfrac {2n} {\ell} \right \rfloor + 1$ is easily found, as above, but the models showing the bound is sharp are much more difficult to exhibit. The special case $\ell = 3$ has a nice combinatorial interpretation: find the maximum number of non-mutually-attacking "bishops" situated at nodes of a triangular array made by partitioning an equilateral triangle into $n^2$ congruent small equilateral triangles by parallels to its sides (the triplets are their trilinear coordinates with respect to the sides). Also, the case $\ell = n$, for which the maximum value of $n$-plets is $3$, is a pleasant, easier version, where the models are easily built inductively.

mavropnevma wrote: It is not exactly proposed by me - I just arranged an idea of Vasile Pop. Indeed, the more difficult question of determining the maximum number of $\ell$-tuples, $2\leq \ell \leq n$ (rather than just triplets) was also asked. The bound $\left \lfloor \dfrac {2n} {\ell} \right \rfloor + 1$ is easily found, as above, but the models showing the bound is sharp are much more difficult to exhibit. I found this to be a problem where the solution is easy to visualise, but difficult to translate into a comprehensible argument.

Raja Oktovin wrote: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1306270&sid=69aec5b1fd82c1e89192c5e5d7241472#p1306270 mavropnevma wrote: It is not exactly proposed by me - I just arranged an idea of Vasile Pop. Let me politely ask you, my dear Mr. Schwarz: why bother sending this problem to the IMO when it had only been used in a contest the year before? Last time I checked, the IMO requests that problem submissions be original. Or has that recently changed, and I missed the news?

Quote: Let me politely ask you, my dear Mr. Schwarz: why bother sending this problem to the IMO when it had only been used in a contest the year before? Let me politely answer you, my dear mymath7 (Vladi ?), in a number of short paragraphs, mostly extracted from my previous post. $\S$ It is not exactly proposed by me - I just arranged an idea of Vasile Pop. So any questions about originality should be addressed to him. I am not supposed to know every problem that has at anytime been used, in any contest, in any country. As can be inferred by the Problem Selection Committee putting it on the ShortList, they were as unawares about its previous appearance as I was. $\S$ The more difficult question of determining the maximum number of $\ell$-tuples, $2\leq \ell \leq n$ (rather than just triplets) was in fact asked, with the models showing the bound $\left \lfloor \dfrac {2n} {\ell} \right \rfloor + 1$ is sharp much more difficult to exhibit. $\S$ The combinatorial interpretation for the special case $\ell = 3$ is not mentioned, now that I know about, and I check the earlier version. $\S$ The mentioned case $\ell = n$, for which the maximum value of $n$-plets is $3$, is a pleasant, easy version, for which there may also be some precedent. To sum it up, after a lifetime of immaculate ethics in what concerns giving credit to existing ideas, and not plagiarizing an iota of previously published materials, I find your innuendo just a tad offensive, sorry for that.

mavropnevma wrote: The special case $\ell = 3$ has a nice combinatorial interpretation: find the maximum number of non-mutually-attacking "bishops" situated at nodes of a triangular array made by partitioning an equilateral triangle into $n^2$ congruent small equilateral triangles by parallels to its sides (the triplets are their trilinear coordinates with respect to the sides). Can someone please clarify?

It means something like this: Suppose you have an equilateral triangle grid of points, with $n+1$ points to a side (so there are $1+2+\cdots+(n+1)$ points in all). Suppose we call some of these points KimK, so that no two KimK points form a line parallel to one of the edges of the equilateral triangle. Find the maximum number of red points possible.

Take $n=6$. You can place at most 4 such red points, but we have 5 possible triples?

SFScoreLow wrote: Take $n=6$. You can place at most 4 such red points, but we have 5 possible triples? Fixed.

CantonMathGuy wrote: SFScoreLow wrote: Take $n=6$. You can place at most 4 such red points, but we have 5 possible triples? Fixed. So the following configurations would correspond to which sets of triples? Which configuration of points would correspond to $(0, 3, 3), (1, 4, 1), (2, 0 ,4), (3, 1, 2), (4, 2, 0)$? My main concern is the correspondence between points and triples...Thanks.

Here's how you do it: 600 510 501 420 411 402 330 321 312 303 240 231 222 213 204 150 141 132 123 114 105 060 051 042 033 024 015 006

IMO ShortList 2009 C2 wrote: For any integer $n\geq 2$, let $N(n)$ be the maxima number of triples $(a_i, b_i, c_i)$, $i=1, \ldots, N(n)$, consisting of nonnegative integers $a_i$, $b_i$ and $c_i$ such that the following two conditions are satisfied: $a_i+b_i+c_i=n$ for all $i=1, \ldots, N(n)$, If $i\neq j$ then $a_i\neq a_j$, $b_i\neq b_j$ and $c_i\neq c_j$ Determine $N(n)$ for all $n\geq 2$. Proposed by Dan Schwarz, Romania Answer: $\boxed{N(n)=\left \lfloor \frac{2n}{3} \right \rfloor +1}.$ For brevity, let $k=N(n)$. To see $k \le \left \lfloor \frac{2n}{3} \right \rfloor+1$ notice that $$kn=\left(\sum^k_{i=1} a_i \right)+\left(\sum^k_{i=1} b_i \right)+\left(\sum^k_{i=1} c_i \right) \ge 3 \left(0+1+\dots +(k-1) \right)=\frac{3k(k-1)}{2} \implies k \le \left( \frac{2n}{3}+1\right).$$We shall provide a construction for each of the cases $n \equiv \{0, 1, 2\} \pmod{3}$ separately. $\boxed{n=3m}$: Consider all triples $(k, 2m-1-2k, m+1+k)$ for $0 \le k \le m-1$ and $(k, 4m-2k, k-m)$ for $m \le k \le 2m$; they work. $\boxed{n=3m+1}$: Consider all triples $(k, 2m-2k, m+1+k)$ for $0 \le k \le m$ and $(k, 4m+1-2k, k-m)$ for $m+1 \le k \le 2m$; they work. $\boxed{n=3m+2}$: Consider all triples $(k, 2m-2k, m+2+k)$ for $0 \le k \le m$ and $(k, 4m+3-2k, k-m-1)$ for $m+1 \le k \le 2m+1$; they work. From the previous analysis, we conclude that the bound actually occurs, hence it is the desired maximum. $\blacksquare$

We claim $N(n) = \lfloor \frac{2n}{3} \rfloor + 1$. Proof of maximum: Sum over all triplets to get $\sum_{i=1}^k (a_i + b_i + c_i) = kn$. But $\sum_{i=1}^k a_i \ge \frac{k(k-1)}{2}$ since the $a_i$ are distinct, and similarly for the other terms, so we get $\frac{3k(k-1)}{2} \le kn$, which implies $k-1 \le \frac{2n}{3}$ and therefore $k \le \frac{2n}{3} + 1$. Construction: Let $a_i = i-1$, and let the sequence $b_1, b_2, \dots, b_k$ be the sequence of descending even numbers, and then descending odd numbers, from $\{0, 1, 2, 3, \dots, k-1\}$. (For instance, for $k = 7$ we have $b_i = (6, 4, 2, 0, 5, 3, 1)$.) We will prove that the $c_i$ are non-negative and pairwise distinct. Note that $b_i = 0$ when $i = \lfloor \frac{k+1}{2} \rfloor$. First, since the difference between odd numbers or even numbers is at least $2$, $a_i + b_i$ is maximized precisely when $i = 1$ or $i = \lfloor \frac{k+1}{2} \rfloor + 1$ (since in most cases, adding $1$ to $i$ increases $a_i$ by $1$ but decreases $b_i$ by $2$). When $i = \lfloor \frac{k+1}{2} \rfloor + 1$ we have $a_i + b_i = \lfloor \frac{k+1}{2} \rfloor + 2 \lfloor \frac{k-1}{2} \rfloor - 1 = 3 \lfloor \frac{k-1}{2} \rfloor \le \frac{3(k-1)}{2} \le n$. When $i = 1$ we have $a_i + b_i = 0 + 2 \lfloor \frac{k-1}{2} \rfloor < k < n$. Therefore, $a_i + b_i \le n$ for each $i$, so $c_i \ge 0$. In fact, the previous analysis shows that $c_i$ is increasing from $i = 1$ to $\lfloor \frac{k+1}{2} \rfloor$ and increasing from $i = \lfloor \frac{k+1}{2} \rfloor + 1$ to $i = k$. Therefore, it suffices to show that $c_k < c_1$. This is equivalent to $a_k + b_k > a_1 + b_1$, or $$(k-1) + 1 > 2 \lfloor \frac{k-1}{2} \rfloor,$$which is obvious. Therefore, the $c_i$ are distinct, and the proof is complete.

Suppose that $N(n) = k$. Then we can obtain a lower bound on $k$ by summing $a_i+b_i +c_i$ over all $1 \le i \le k$ as $\sum_{i=1}^k a_i \ge \tfrac{k(k-1)}{2}$ so $\tfrac{3k(k-1)}{2} \le nk \implies k \le \tfrac{2n}{3} +1$. Now I claim that $k = \lfloor \tfrac{2n}{3} +1 \rfloor$ is indeed achievable. For equality to be achievable in the case where $n=3m$ for some integer $m$, we must have $\{ a_1,a_2,\dots,a_k\} = \{0,1,\dots,k-1\}$ and analogous for $b_i,c_i$. Therefore each of the $k$ pairs of positive integers $\{ \{a_1,b_1\} ,\{a_2,b_2\} ,\dots,\{a_k,b_k\} \}$ must have a distinct sum ranging every integer from $m$ to $n$ inclusive. Therefore the construction \[\{m-1,1 \},\{m-2,3\},\{m-3,5\},\dots,\{0,2m-1 \} \]union \[ \{2m,0 \},\{2m-1,2\},\{2m-2,4\},\dots,\{m,2m \}\]indeed works. For $n=3m+1$, use the same construction as just shown but add one to every $c_i$. If $n=3m-1$, use the same construction but omit the term $\{0,2m-1\}$ and subtract one from every $a_i$. It is easy to verify that these also work.

We claim that $N(n)=\boxed{\left\lfloor\frac{2n}{3}\right\rfloor+1}$. Claim 1: $N(n)\le\left\lfloor\frac{2n}{3}\right\rfloor+1$. Proof: Note that \[nN=\sum_{i=1}^n(a_i+b_i+c_i)\ge 3\cdot\frac{N(N-1)}{2},\]so $N-1\le\frac{2}{3}n$, as desired. Claim 2: $N(3k))\ge 2k+1$. Proof: All we have to do is provide a construction with $N=2k+1$ triples. Coming up with this is by far the hardest part of the problem. The way I did it was by shifting down, so the problem reduced to showing that there exists $3$ points $A$, $B$, and $C$ in the set of permutations of $(-k,-(k-1),\ldots,k-1,k)$ such that $A+B=C$. Coming up with the construction in this setting is easier, but regardless, here is the final construction for the problem. Note that \begin{align*} &\,\,\,\,\,\,\,\,(0,1,\ldots,2k)\\ &+(k,k+1,\ldots,2k,0,1,\ldots,k-1)\\ &+(2k,2k-2,2k-4,\ldots,0,2k-1,2k-3,\ldots,1)\\ &=(3k,\ldots,3k) \end{align*}so we're done. Claim 3: $N(n-1)\ge N(n)-1$. Proof: Suppose we have a construction $(a_i,b_i,c_i)_{i=1}^{N(n)}$ for $n$. There is at most one $i$ with $c_i=0$, so delete it and consider the triples $(a_i,b_i,c_i-1)$. These clearly work, and we have $N(n)-1$ of them, so we're done. Claims 1 and 2 show that $N(3k)=2k+1$. By Claim 3, we see that $N(3k-1)\ge 2k$, but by claim 1, $N(3k-1)\le 2k$, so $N(3k-1)=2k$. Similarly $N(3k-2)=2k-1$, so the problem is solved.

I claim that the answer is $\left\lfloor\frac{2n}{3}\right\rfloor +1$. As a construction, consider the two sets of triplets $$\left\{\left(\left\lceil\frac{n}{3}\right\rceil+i,i,\left\lfloor\frac{2n}{3}\right\rfloor-2i\right)\bigg|\,0\le i\le \frac{n}{3}\right\}$$and$$\left\{\left(i,\left\lceil\frac{n}{3}\right\rceil +1+i, \left\lfloor\frac{2n}{3}\right\rfloor-1-2i\right)\bigg|0\le i\le \frac{\left\lfloor\frac{2n}{3}\right\rfloor -1}{2} \right\}$$It is not hard to see that this is a valid construction. To see that the bound is strict, consider $S=\sum (a_i+b_i+c_i)$. We have $$Nn=S\ge 3(0+\ldots+N-1)=\frac{3}{2}N(N-1)$$so $N\le \left\lfloor\frac{2n}{3}\right\rfloor+1$, as desired.

Let $N(n)=k$. Think of the triples $(a_i,b_i,c_i)$ as columns in a $3\times k$ grid. We want the sum of the numbers in each column to be $n$, and the rows to have all distinct numbers. The total sum of the numbers in the grid is $kn$, since each of the $k$ columns has sum $n$. But the sum of the numbers in each row is at least $0+1+\cdots + (k-1) = \tfrac{k(k-1)}{2}$, because the elements are all distinct. So \[ 3\cdot \frac{k(k-1)}{2} \le kn \implies k \le \frac{2n}{3}+1. \]We claim we can get $k$ to be the greatest integer possible using the above bound, i.e. $k=\lfloor 2n/3 \rfloor +1$. For each case of $n\mod 3$, we have to make an equality case. Since we want to make our bound (at least close to) sharp, we want to use the numbers $\{ 0,1,\ldots,2m\}$ in each row. But we may have to make small adjustments in each case. If $n=3m$, then the following works for $k=2m+1$: \[ \begin{pmatrix} 0 & 1 & 2 & \cdots & m & m+1 & m+2 & \cdots & 2m \\ m & m+1& m+2 & \cdots & 2m & 0 & 1 &\cdots & m-1 \\ 2m & 2m-2 & 2m-4 & \cdots & 0 & 2m-1 & 2m-3 & \cdots & 1 \end{pmatrix} \]If $n=3m+1$, then the following works for $k=2m+1$: \[ \begin{pmatrix} 0 & 1 & 2 & \cdots & m & m+1 & m+2 & \cdots & 2m \\ m & m+1& m+2 & \cdots & 2m & 0 & 1 &\cdots & m-1 \\ 2m+1 & 2m-1 & 2m-3 & \cdots & 1 & 2m & 2m-2 & \cdots & 2 \end{pmatrix} \]If $n=3m-1$, then the following works for $k=2m$ (this was the trickiest to figure out!): \[ \begin{pmatrix} 0 & 1 & 2 & \cdots & m-1 & m+1 & m+2 & \cdots & 2m \\ m & m+1& m+2 & \cdots & 2m-1 & 0 & 1 & \cdots & m-1 \\ 2m-1 & 2m-3 & 2m-5 & \cdots & 1 & 2m-2 & 2m-4 & \cdots & 0 \end{pmatrix} \]

This is 2012 C2's older, (arguably harder) angry grandpa. Note that for a given integer, it can appear at most $3$ times in the set of triples at indices 1, 2, and 3. Let's say that there are $k$ triples; then, by double counting sums, we get \begin{align*} 3 \cdot (0 + 1 + \cdots + k - 1) \leq k \cdot n, \end{align*}which rearranges to $k \leq \frac{2n}{3} + 1$. Now, we construct based on the cases of $n \pmod 3$. Case 1: $n = 3n'$ or $n = 3n' + 1$. In both cases, we get the bound of $k \leq 2n' + 1$. The construction for $3n'$ is \begin{align*} &(0, n', 2n'), (1, n' + 1, 2n' - 2), \cdots, (n', 2n', 0) \\ &(n' + 1, 0, 2n' - 1), (n' + 2, 1, 2n' - 3), \cdots, (2n', n' - 1, 1). \end{align*} For $3n' + 1$, we can basically just increment everything in the left by $1$. Case 2: $n = 3n' - 1$. Here, we get the bound of $k \leq 2n'$. The construction here is similar to the $3n'$ case; just remove the $(0, n', 2n')$ triplet, and then subtract $1$ from every single leftmost entry.

We claim that $\boxed{N(n)=\left\lfloor \frac{2}{3}n \right\rfloor +1}$ for all $n\ge 2$. First, we prove that $N(n)$ cannot be higher. For a particular $n$, consider a set of $N(n)$ ordered triples satisfying the conditions. It is clear that if we sum all numbers in all triples, we will get $nN(n)$. However, notice that each $a_i$ must be distinct, so the sum of the $a_i$ is at least $0+1+\ldots+(N(n)-1)=\frac{(N(n)-1)N(n)}{2}$. A similar thing can be done for the $b_i$ and $c_i$, so the sum of all numbers in all triples is bounded below by $\frac{3(N(n)-1)N(n)}{2}$. Thus $$\frac{3(N(n)-1)N(n)}{2}\le nN(n) \Rightarrow \frac{3}{2}(N(n)-1)\le n \Rightarrow N(n)\le \frac{2}{3}n +1,$$so the maximum possible value of $N(n)$ for any $n$ is $N(n)=\left\lfloor \frac{2}{3}n \right\rfloor +1$. Now we prove that this is attainable for all $n$. First, we give a working construction for $3|n$. Let $n=3k$, then a set of $2k+1$ triples is $(2i, k-i, 2k-i)$ for $0\le i \le k$ and $(1+2i, 2k-i, k-1-i)$ for $0\le i \le k-1$. It is easy to see that this works. Notice that given a $x$-triple construction for $n=k$, an $x-1$-triple construction for $n=k-1$ can be easily achieved by removing the triple with $a_i=0$ (if it exists), and subtracting one from $a_i$ for all the remaining triples. Therefore, given an optimal set of triples for $n=3k$, we can easily construct an optimal set for $n=3k-1$, and using that, we can construct an optimal set for $n=3k-2$. Since we have shown a construction exists for all $n\ge 2$, we are done.

Solved with awesomehuman!

Let $S$ be the sum of all the $a_i+b_i+c_i$ and let there be $m$ triples then $mn=S\ge 0+3+\dots+3(n-1)=\frac{3}{2}n(n-1).$ Therefore, $N(n)\le \left\lfloor \frac{2n+3}{3}\right\rfloor.$ We claim that $N(n)=\left\lfloor \frac{2n+3}{3}\right\rfloor$ works. $~$ When $n=3x$ take the triples \[(0,x,2x),(1,x+1,2x-2),\dots,(x,2x,0)\text{ and }(x+1,0,2x-1),(x+2,1,2x-3),\dots, (2x,x-1,1)\]When $n=3x+1$ take the same triples, but add one to the first term in every triple. When $n=3x-1$ take the same triples, but subtract one from every first time in every triple, and remove the $(0,x,2x).$

It is clear that, by double counting the sum of all $a_i,b_i,c_i$, $$\frac{N(n)(N(n)-1)}{2}\cdot3\le n\cdot N(n)\rightarrow 3(N(n)-1)\le 2n\rightarrow N(n)\le\boxed{\left\lfloor\frac{2n}{3}+1\right\rfloor}.$$We will prove that this maximum works. Note: All bounds in the constructions are inclusive. If $n=2$, our construction is just $(2,0,0)$ and $(0,1,1)$. Let $x=\left\lfloor\frac{n}{3}\right\rfloor$ and let $y$ be the remainder when $n$ is divided by $3$. If $y\in\{0,1\}$, then our triples will be the following: $a$ moves from $2x$ to $0$ in steps of $2$ $b$ moves from $x$ to $2x$ $c$ moves from $y$ to $x+y$ $a$ moves from $2x-1$ to $1$ in steps of $2$ $b$ moves from $0$ to $x-1$ $c$ moves from $x+y+1$ to $2x+y$ There are a total of $(x+1)+x=2x+1=\left\lfloor\frac{2n}{3}+1\right\rfloor$ of these triples, so this case works. Otherwise, $y=2$, and our triples will be the following: $a$ moves from $2x+1$ to $1$ in steps of $2$ $b$ moves from $x$ to $2x$ $c$ moves from $1$ to $x+1$ $a$ moves from $2x$ to $2$ in steps of $2$ $b$ moves from $0$ to $x-1$ $c$ moves from $x+2$ to $2x+1$ $a=0,b=n,c=0$ There are a total of $(x+1)+x+1=2x+2=\left\lfloor\frac{2n}{3}+1\right\rfloor$ of these triples, so this case also works. Since we have a construction for all possible cases, we are done.

Sketch: Answer is $\boxed{\left\lfloor\frac{2n}{3} \right\rfloor + 1}$; construction is achieved for $n=3k$ and $n=3k+1$ by with $a_i = i-1$, $b_i = k - 1 + i \pmod {2k+1}$; and for any $n=3k+2$, take the construction of $3k$, add one to each $a_i$ and $b_i$, and append $(0, 0, 3k+2)$. For the bound, essentially use the fact that every integer can appear at most $3$ times overall to prove that if there exists more than $\left\lfloor\frac{2n}{3} \right\rfloor + 1$ triples, then globally some sum has to be greater than $n$.

The answer is $N = \lfloor 2n/3 \rfloor + 1$. For a construction, consider $N$ sets of valid triples. Observe that we have $$\frac{N(N+1)}2 \leq \sum_{i=1}^N (a_i+b_i+c_i) = N \cdot n \implies N \leq \frac{2n}3 + 1,$$which proves the bound. For a construction, the details are a bit finicky due to the floor, but are essentially encoded in this diagram: [asy][asy] size(100); pair A = (0, 0), B = (0, 1), C = (0, 2), D = (1, 0), E = (2, 0); draw(C--A--E); draw(B--(1, 2), blue); draw((1, 1)--E, blue); draw(C--D--(2, 2), red); draw(A--(1, 1), green); draw((1, 2)--(2, 1), green); label(A, "$0$", SW); label(B, "$n/3$", W); label(C, "$2n/3$", W); label(D, "$n/3$", S); label(E, "$2n/3$", S); [/asy][/asy]

When the construction is the hardest part of the problem We claim that the answer is $$N(n)=\left \lfloor \frac{2}{3}n+1 \right \rfloor.$$ We will first show the bound. Suppose there are $k$ triples. Arrange the numbers in a 3 by $k$ grid so that the first row contains the first triple, the second row contains the second triple, and so on. Each row sums to $n$. Additionally, each column contains $k$ distinct nonnegative integers, so each column has a sum of at least $k(k-1)/2$. Therefore, $$\frac{3k(k-1)}{2}\leq nk\rightarrow k\leq \frac{2}{3}n+1,$$and since $k$ is an integer, this shows the bound of $$k\leq \lfloor \frac{2}{3}n+1 \rfloor.$$ For the construction: When $n$ is a multiple of 3: say $n=3m$. Then, we construct the grid for $2m+1$ rows by: For the first column, fill out 0 through $2m$. For the second column, start with $m$. Increase by 1 each time until you hit $2m$. Then, go to 0 on the next entry, and increase by 1 each time until you reach $m-1$ by the end. For the third column, start with $2m$, decrease by 2 each time until you get to 0, then go to $2m-1$ on the next row and keep decreasing by 2 until you reach 1 on the last row. This works since each column contains distinct numbers and each row sums to $n$. An example for $n=9$ so $m=3$: \begin{center} \begin{tabular}{ c c c } 0 & 3 & 6\\ 1 & 4 & 4\\ 2 & 5 & 2\\ 3 & 6 & 0\\ 4 & 0 & 5\\ 5 & 1 & 3\\ 6 & 2 & 1\\ \end{tabular}\end{center} If $n$ is 1 mod 3, so $n=3m+1$, we can also obtain $2m+1$ rows by increasing the last column of the $3m$ construction by 1, for example \begin{center} \begin{tabular}{ c c c } 0 & 3 & 7\\ 1 & 4 & 5\\ 2 & 5 & 3\\ 3 & 6 & 1\\ 4 & 0 & 6\\ 5 & 1 & 4\\ 6 & 2 & 2\\ \end{tabular}\end{center} If $n$ is 2 mod 3, so $n=3m+2$, take the $3m+1$ construction and also increase each entry of the second column by 1. Then, insert an additional row with $2m+1,m+1,0$ (which still maintains all required conditions), so for example \begin{center} \begin{tabular}{ c c c } 0 & 4 & 7\\ 1 & 5 & 5\\ 2 & 6 & 3\\ 3 & 7 & 1\\ 4 & 1 & 6\\ 5 & 2 & 4\\ 6 & 3 & 2\\ 7 & 4 & 0 \end{tabular}\end{center} Therefore, $n=3m$ we can get $2m+1$, $n=3m+1$ we can get $2m+1$, and $n=3m+2$ we can get $2m+2$. Therefore, we can always achieve $$\left \lfloor \frac{2}{3}n+1 \right \rfloor,$$so we are done.

If there are $k$ tripples then their sum $kN \geq 3\times(0+1+\dots + k-1) = 3\times\frac{k(k-1)}{2}$. Therefore, $\frac{2N}{3} +1 \geq k$. So, if $N = 3m$ then $k \leq 2m+1$. And we can select $a = (0, 1, 2,\dots, 2m)$, $b = (m, m+1, \dots, 2m, 0,1,\dots, m+1)$ and sequence $c$ accordingly and see that this works. Now, for $N = 3m+1$, we get $k \leq 2m+1$. So we can just copy the construction from $N = 3m$ and add one to each of $a$. Now, for $N = 3m+2$ we get $k \leq 2m+2$. Here we copy the construction from $N = 3m$, then add one to each of $a$ and $b$. Then add tripplet $(0, 0, 3m+2)$ to the list. So, we are done. $\blacksquare$

We claim that $N = \left\lfloor \frac{2}{3}n + 1 \right\rfloor$. Due to size reasons, it must follow that \[ 3 \cdot (0 + 1 + \dots + (N - 1)) \le N \cdot n \]which implies that \[ N \le \frac{2}{3}N + 1 \]We first construct the case $n = 3a$. Then take the triplets as \begin{align*} &(0, a, 2a), (1, a + 1, 2a - 2), \dots (a, 2a, 0), \\ &(2a, a-1, 1), (2a-1, a-2, 3), \dots (a+1, 0, 2a - 1) \end{align*}For $n = 3a - 1$, we can subtract $1$ from the elements of the last tuple and remove the tuple with last element $0$. For $n = 3a + 1$, we can add $1$ to elements of the last tuple.

Let $N(n)$ denote the maximum number of triples $(a_i,b_i,c_i)$ of non negative integers which satisfy the required conditions. Let $N(n)=k$. First we count the sum of the entries of these $k$ triples in two ways. Since we have $k$ triples this sum is clearly, \[S=kn\]Since $a_1,a_2,\dots,a_k$ are distinct, \[S=\sum_{i=0}^k a_i + \sum_{j=0}^k b_j \sum_{l=0}^k c_l \geq 3(0+1+\dots + (k-1)) = \frac{3k(k-1)}{2}\]This means, \[kn \geq \frac{3k(k-1)}{2} \implies k \leq \frac{2n+3}{3}\]Now, we give a construction which achieves, \[N(n) = \lfloor{\frac{2n+3}{3}\rfloor}\]For $n=3a$, \[(0,a+1,2a-1)\]\[(1,a+2,2a-3)\]\[\vdots \]\[(a-1,2a,1)\]\[(a,0,2a)\]\[(a+1,1,2a-2)\]\[\vdots\]\[(2a,a,0)\]For $n=3a+1$ we simply add 1 to the last entry of each tuple in the above construction (since $c_i \neq c_j$ we have that $c_i+1\neq c_j+1$ as well and $c_i+1 \leq 3a+1$). When $n=3a+2$ we tweak this construction a little bit and obtain, \[(0,1,3a+1)\]\[(1,a+2,2a-1)\]\[\vdots \]\[(a,2a+1,1)\]\[(a+1,0,2a+1)\]\[(a+1,2,2a-2)\]\[\vdots\]\[(2a+1,a+1,0)\]Thus, the established bounds are indeed attainable and we are done.

Suppose we have $k$ triples satisfying the condition. Then \[n+\dots+(n-(k-1))\ge (a_1+b_1)+\dots+(a_k+b_k)=(a_1+\dots+a_k)+(b_1+\dots+b_k)\ge (k-1)k\]which reduces to \[\frac{2}{3}n+1\ge k\implies k\le \left\lfloor \frac{2}{3}n \right\rfloor + 1=N(n).\]Now to prove the potential bound we just need to give a construction. We split into cases. First, if $n=3x$, then \[\{a_i\}=\{b_i\}=\{0,\dots,2x\}\]\[\{a_i+b_i\}=\{x,\dots,3x\}.\]Now consider the following sets of $\{a_i\}$ and $\{b_i\}$, where order matters: \[\{a_i\}=\{0,2,\dots,2x\}\cup \{2x-1,2x-3,\dots,1\}\]\[\{b_i\}=\{2x,2x-1,\dots,x\}\cup \{0,1,\dots,x-1\}\]These clearly work. Next, if $n=3x+1$, then \[\{a_i\}=\{0,2,\dots,2x\}\cup \{2x-1,2x-3,\dots,1\}\]\[\{b_i\}=\{2x,2x-1,\dots,x\}\cup \{0,1,\dots,x-1\}\]works (it is the same construction). Finally if $n=3x+2$ then $k=2x+2$. In this case \[\{a_i\}=\{1,3,\dots,2x+1\}\cup \{2x,2x-2,\dots,0\}\]\[\{b_i\}=\{2x+1,2x,\dots,x+1\}\cup \{0,1,\dots,x\}\]will work. We are done. $\blacksquare$

Let there be $a$ triples. Then note that the sum of all triples is $an.$ Note that this also must be $\geq \frac{3a(a-1)}{2}$ as each number is counted at least thrice. This means that $a\leq \frac{2n+3}{3},$ so our answer is $a=\boxed{\lfloor \frac{2n+3}{3}\rfloor}.$ The construction for $n\equiv 0,1 \pmod 3$ is the same because the answer for both is the same. The construction for both of these is simply let the first element of the triple be $0$ through $a-1,$ and the other two are easy. For $n\equiv 2 \pmod 3$ get rid of the triple for which the first number is $0$ and for all other triples subtract one from the first number$.\blacksquare$

I claim the maximum number $N$ of triples is $\lfloor \frac{2n+3}{3} \rfloor$, we get this from taking the minimum sum of the $a_i$, $b_i$ and $c_i$. Clearly we have that the minimum sum is $3\frac{N(N-1)}{2}\leq Nn$ so we get $N\leq \frac{2n+3}{3}$ which is the bound above. For the construction when $n$ is $0$ mod $3$. We take triples of the form $(0, m, 2m), (1, m+1, 2m-2), \dots, (m, 2m, 0)$ and $(m+1, 0, 2m-1), (m+2, 1, 2m-3), \dots (2m, m-1, 1)$. Constructions for $1$ and $2$ mod $3$ are relatively similar.

This problem is bad. Answer is $\left \lfloor \frac{2n+3}{3}\right \rfloor $. The construction is as expected and I dont want to write it out. Suppose it as possible for $k$ triples. Then, their minimum sum is $3(0+1+\dots + k-1)=\frac{3k(k-1)}{2}$ so we need $kn\geq \frac{3k(k-1)}{2}$ or $2n+3\geq 3k$.

took longer than it should have, but doing combi at 2am is also not the best idea...

Suppose that $\sum a_i \leq \sum b_i \leq \sum c_i$. Then \[\frac 13 \cdot Nn \ge \sum a_i \ge 0 + 1 + \ldots + (N-1)\]\[\implies N \leq \boxed{\left\lfloor \frac{2n+3}{3} \right\rfloor},\] which we can construct. $\blacksquare$