ordered triples choosing

hollandman · Poincare Conjecture Offline Joined: 16 Nov 2008 Posts: 114

Let $n$ be a positive integer, and $A$ be the set of all ordered triples $(a,b,c)$ of nonnegative integers such that $a+b+c=2n$ and $a,b,c\leq n$ .

At most, how many triples can we choose from $A$ such that for any two triples, the numbers in the same position are different.

**Posted:** Sun Apr 05, 2009 4:44 pm

JBL

This seems extremely artificial to me (why $a + b + c = 2n$ instead of the equivalent $a + b + c = n$ ?), and yet I can't help but be drawn to it Smile

. The proof is by intelligent appeal to the OEIS (one of my favorite kinds):

First, we show that $1 + \left\lfloor \frac {2n}{3} \right\rfloor$ is an upper bound. Suppose we have $a$ triples meeting the desired conditions. Then the total sum of all numbers in all triples is $2an$ . It's also clear that this sum is at most $3(n + (n - 1) + (n - 2) + \ldots + (n - a + 1)) = 3an - \frac {3a^2}{2} + \frac {3a}{2}$ , and so $2an \leq a(3n - \frac {3a}{2} + \frac {3}{2})$ . Rearranging this equation gives $a \leq \frac {2n}{3} + 1$ , as claimed.

Doing a few small cases leads one to believe that this is actually the true value. And looking at the OEIS entry (A004396) we see that this really is the case. In particular, this is equivalent to the first comment there by Guy:

**Posted:** Thu May 21, 2009 2:17 pm