For any integer , let be the maximal number of triples , , consisting of nonnegative integers and such that the following two conditions are satisfied:
(1) for all ,
(2) If , then and .
Determine for all .
Solution
Let be an integer and let be any set of triples of nonnegative integers satisfying the conditions (1) and (2). Since the -coordinates are pairwise distinct we have
Analogously,
Summing these three inequalities and applying (1) yields
hence and, consequently,
By constructing examples, we show that this upper bound can be attained, so .
We distinguish the cases and for and present the extremal examples in form of a table.
| 0 | ||
| 1 | ||
| 0 | ||
| 0 | ||
| 1 | ||
| 1 |
| 0 | ||
| 1 | ||
| 0 | ||
| 0 | ||
| 1 | ||
| 1 |
| 0 | ||
| 1 | ||
| 1 | ||
| 0 | ||
| 1 | ||
| 2 |
It can be easily seen that the conditions (1) and (2) are satisfied and that we indeed have triples in each case.
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.