For $n=5m+1,5m+2$ the answer is $2m$ We construct the pairs $( 4m,1),(4m-1,3) \cdots (3m,2m+1)$ and $(3m-1,4)\cdots (2m+2,2m-2)$ and $(2m,2)$ It is impossible for $2m+1$ pairs by doublecounting: the sum of $2m+1$ pairs $\ge 1+2+\cdots + 4m+2=(2m+1)(4m+3)$ and smaller than $5m+2 + \cdots + 3m+2 = (2m+1)(4m+2)$ , contradiction. For $n=5m+3,5m+4,5m+5$ the answer is $2m+1$ We construct the pairs $( 4m+2,1),(4m+3,3) \cdots (3m+2,2m+1)$ and $(3m+1,2)\cdots (2m+2,2m)$ It is impossible for $2m+2$ pairs by doublecounting: the sum of $2m+2$ pairs $\ge 1+2+\cdots + 4m+4=(2m+2)(4m+5)$ and smaller than $5m+5 + \cdots + 3m+4 = (2m+2)(4m+4.5)$ , contradiction.

The answer is $\left\lfloor \frac{2n-1}{5}\right\rfloor$. This (easy) result goes back to [1] M. S. Klamkin and D. J. Newman, Some combinatorial problems of arithmetic, Mathematics Magazine 42 (1969), pp 53-56 [2] G. J. Woeginger, Disjoint Pairs with Distinct Sums, Mathematics Magazine 79 (2006), p 66

woe wrote: The answer is $\left\lfloor \frac{2n-1}{5}\right\rfloor$. This (easy) result goes back to [1] M. S. Klamkin and D. J. Newman, Some combinatorial problems of arithmetic, Mathematics Magazine 42 (1969), pp 53-56 [2] G. J. Woeginger, Disjoint Pairs with Distinct Sums, Mathematics Magazine 79 (2006), p 66 I assume you are Gerhard Woeginger, author of many IMO Shortlist and other Olympiad problems. I'm curious to see the collection or list of your problems that appeared in IMO Shortlist and other competitions. Thanks!

Solution:

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=133&t=268508

This is easy for a shortlist problem...Once you get that upper bound for the maximum number of pairs,you check small cases and know the process of construction and answer at once....

Quite similar to 2009 C2. IMO ShortList 2012 C2 wrote: Let $n \geq 1$ be an integer. What is the maximum number of disjoint pairs of elements of the set $\{ 1,2,\ldots , n \}$ such that the sums of the different pairs are different integers not exceeding $n$? Answer: $\left \lfloor \frac{2n-1}{5} \right \rfloor$. Let the pairs be $\{a_i, b_i \}$ for $1 \le i \le k$ and let $c_i=a_i+b_i$ for all indices $i$; then, we have $$k(2k+1)=2(1+2+\dots+k) \le \left(\sum^k_{i =1} a_i \right)+\left(\sum^k_{i=1} b_i \right)=\left( \sum^k_{i=1} c_i \right) \le n+(n-1)+\dots+(n-k+1)=nk-\frac{k(k-1)}{2},$$so we get the stated upper bound. To see that equality actually occurs, we just need to provide a construction for all $n \ge 1$. Let $n=5m+r$ for $r \in \{1, 2, 3, 4, 5\}$ and note that $k=2m$ for $r<3$ and $k=2m+1$ otherwise. $r=1$: Consider triples $(1, 5m, 5m+1)$, $(j, 4m+2-2j, 4m+2-j)$ for $2 \le j \le m$ and $(m+j, 4m+1-2j, 5m+1-j)$ for $1 \le j \le m$ and see that these work. $r=2$: Consider the previous triples with $b_i, c_i$ increased by one in each of them and see that these work here. $r=3$: Consider triples $(j, 4m+3-2j, 4m+3-j)$ for $1 \le j \le m$ and $(m+j, 4m+4-2j, 5m+4-j)$ for $1 \le j \le m+1$. $r=4, 5$: Add one and two respectively, to $b_i, c_i$ in the previous case to obtain satisfactory triples in each of these cases. Hence we conclude that $\left \lfloor \frac{2n-1}{5} \right \rfloor$ is indeed the desired maximum. $\blacksquare$

Is it really C2 level ?I think C1's idea is harder than this.As Anant said this is quite similar to 2009 C2.

The answer is $\lfloor \frac{2N-1}{5} \rfloor $. The number of pairs can be seen to be no more than this by considering the sum of all different pairs. Suppose there are $x$ pairs satisfying the problem's condition. On the one hand, the sum of the pairs of numbers is at least $1+2+\cdots +2x$ and on the other hand since the sums of the pairs are distinct the total sum is at most $N+(N-1)+\cdots +(N-x+1)$. So $\frac{(2N-x+1)x}{2} \ge \frac{2x(2x+1)}{2}$ gives us $2n \ge 5x+1$.

Solution from Twitch Solves ISL: The answer is $N = N(n) \le \left\lfloor \frac{2n-1}{5} \right\rfloor$. The proof is nearly identical to that of IMO SL 2009 C2. To prove the bound, suppose the pairs are $(a_1, b_1)$, \dots, $(a_N, b_N)$. Then on the one hand \[ \sum_1^N (a_i + b_i) \le \underbrace{n + \dots + (n-N+1)}_{\text{$N$ largest sums } < n} = \frac{1}{2} N\left( 2n - N + 1 \right). \]On the other hand, \[ \sum_1^N (a_i + b_i) \ge \underbrace{1 + 2 + \dots + 2N}_{\text{$2N$ smallest possible entries}} = N \cdot (2N+1) \]Putting these two bounds together and solving works. For the construction, it suffices to exhibit the construction when $n \equiv 1 \pmod 5$ and $n \equiv 3 \pmod 5$, since for all other $n$ we have $N(n) = N(n-1)$. We just give examples which generalize readily. When $n=18$, we use the following: \[ \begin{array}{cccc|ccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ +&+&+&+&+&+&+ \\ 14 & 12 & 10 & 8 & 13 & 11 & 9 \end{array} \]The general construction for $n=5k+3$ is analogous, using $(k+1)+k=2k+1$ pairs. When $n=21$, we use the following: \[ \begin{array}{ccc|ccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ +&+&+&+&+&+&+&+ \\ 14 & 12 & 10 & 17 & 15 & 13 & 11 & 9 \end{array} \]The general construction for $n=5k+1$ is analogous, using $(k-1)+(k+1) = 2k$ pairs.

@above 2009 C2?

Claim: If $k$ is the maximum number of pairs, then $k \le \lfloor \tfrac{2n-1}{5} \rfloor$. Proof: Put the numbers into a $2\times k$ grid, with the columns being the pairs. Call the pairs $(a_i,b_i)$ for $i=1,\ldots, k$. Consider the total sum of the numbers by rows and by columns; we will use dumb bounds in each count. The sum in column $i$ is at most the $i$'th element of $n,n-1,\ldots,n-k+1$, since the sums are distinct. Hence if the total sum is $S$, then \[ S \le n+(n-1)+\cdots+(n-k+1) = kn - \frac{k(k-1)}{2}. \]If we consider the sum $S$ by rows, we have \[ S=(a_1+\cdots+a_k)+(b_1+\cdots+b_k) \ge 1+2+\cdots+2k = k(2k+1) \]just since the $2k$ elements are at least $1,\ldots,2k$. Putting these together, we get \[ kn - \frac{k(k-1)}{2} \ge k(2k+1) \implies k \le \frac{2n-1}{5}.\]This proves the claim. $\square$ To prove that $\lfloor \tfrac{2n-1}{5} \rfloor$ is the answer, it suffices to show a construction for $n\equiv 1,3 \pmod5$, since these are the points at which the function increases; otherwise just take the construction for $n-1$. Case 1: $n=5a+1$. We want $2a$ pairs. Take $(1,4a-1),(2,4a-3),(3,4a-5),\ldots,(a,2a+1)$ and $(a+1,4a),(a+2,4a-2),\ldots,(2a,2a+2)$. Case 2: $n=5a+3$. We want $2a+1$ pairs. Take $(1,4a),(2,4a-2),(3,4a-4),\ldots,(a,2a+2)$ and $(a+1,4a+1),(a+2,4a-1),(a+3,4a-3),\ldots,(2a,2a+3)$.

I claim that our answer is at most $\boxed{k = \lfloor \tfrac{2n - 1}{5}\rfloor}$ pairs. Let the $k$ pairs be $(a_1, b_1), (a_2, b_2), \ldots , (a_k, b_k)$. Consider the following bounds:\[\sum_{i = 1}^k (a_i + b_i) \leq n + (n-1) + \ldots + (n - k + 1) = \frac12 k(2n - k + 1)\]\[\sum_{i = 1}^k (a_i + b_i) \geq 1 + 2 + \ldots + 2k = k(2k + 1)\]where the upper bound is from the sum of the $k$ greatest possible pair sums and the lower bound is derived from the sum of the $2k$ smallest possible elements for the $k$ pairs. In fact, solving this yields \[2(2k + 1) \leq 2n - k + 1 \implies 5k \leq 2n - 1 \implies k \leq \frac{2n - 1}{5}\]which is our desired upper bound. Now we provide constructions for $k = \lfloor \tfrac{2n - 1}{5}\rfloor$ pairs. We split into the following cases: Case 1: $n \equiv 1, 2 \pmod 5$. Write $n = 5m + 1$ or $5m + 2$. In any case, $k = \lfloor \tfrac{2n - 1}{5}\rfloor = 2m$. Consider the following $2m$ pairs of $4m$ distinct numbers, each of which sums to at most $5m + 1$:\[\{(4m + 1, m), (4m, m - 1), \ldots , (3m + 2, 1)\} \cup \{(3m, 2m), (3m - 1, 2m - 1), \ldots , (2m + 1, m + 1)\}\]which is a valid construction. Case 2: $n \equiv 3, 4, 5\pmod 5$. Write $n = 5m + 3$, $5m + 4$, or $5m + 5$. Then, $k = \lfloor \tfrac{2n - 1}{5}\rfloor = 2m + 1$. Consider the following $2m + 1$ pairs of $4m + 2$ distinct numbers, each of which sums to at most $5m + 3$:\[\{(4m + 2, m + 1), (4m + 1, m), \ldots , (3m + 2, 1)\} \cup \{(3m + 1, 2m + 1), (3m, 2m), \ldots (2m + 2, m + 2)\}\]which is a valid construction. We have provided constructions and proven maximality, so we are done. $\blacksquare$ Remark: This bound was really easy to see. I can't believe that the answer found in the loose bound would actually be the final answer. The construction was also annoying

this construction was PAINPAINPAINPAINPAINPAINAPINAPIANAPPIANAPIANPIANIPNAPNAINAPNAINAPINPAINPANi Assume that we have $k$ pairs so far, then we can lower bound and upper bound the sums of the pairs. The lower bound is just $1 + 2 + \cdots + 2k = k(2k + 1)$, while the upper bound is $n + (n - 1) + \cdots + (n - k + 1) = \frac{k(2n - k + 1)}{2}$, which we can solve to get $k \leq \frac{2n - 1}{5}$. We split the construction up into cases, letting $n = 5m + 1$, $5m + 2$, etc mod $5$. Observe that $5m + 1$ and $5m + 2$ yield the same bound of $2m$, and $5m + 3$, $5m + 4$, $5m + 5$ yield the same bound of $2m + 1$. Construction for $+1$ and $+2$: Take the groups$$\begin{aligned} (2m, 2m + 2), (2m - 1, 2m + 4), \cdots (m + 1, 4m) \\ (1, 4m - 1), (2, 4m - 3), \cdots (m, 2m + 1), \end{aligned}$$and there are evidently $m$ in each group, hence done. Construction for the rest: Take the groups$$\begin{aligned} (m + 1, 4m + 2), (m + 2, 4m), \cdots (2m + 1, 2m + 2) \\ (1, 4m + 1), (2, 4m - 1), \cdots (m, 2m + 3), \end{aligned}$$first group has $m + 1$ and second group has $m$, done.

We claim that the answer is $\lfloor \frac{2n-1}{5} \rfloor$. Firstly, let $(a_1,b_1);(a_2,b_2);...;(a_k,b_k)$ the pairs. If $n= 5m, 5m-1, 5m-2$ for some $m \in \mathbb{N}$, we choose $(a_1,b_1);(a_2,b_2);...;(a_{2m-1},b_{2m-1})=(4m-2,m);(4m-3,m-1);...;(3m,2);(3m-1,1);(3m-2,2m-1);(3m-3,2m-2);...;(2m,m+1)$, which clearly works. Hence, $k \geq 2m-1 = \lfloor \frac{2n-1}{5} \rfloor$ in this case. If $n=5m+1,5m+2 \implies \lfloor \frac{2n-1}{5} \rfloor= 2m$, we can choose $(a_1,b_1);(a_2,b_2);...;(a_{2m},b_{2m})=(4m,m);(4m-1,m-1);...;(3m+1,1);(m+1,m+2);(3m,2m+1);(3m-1,2m);...;(2m+2,m+3)$, which clearly works as well. Thus, $k \geq 2m = \lfloor \frac{2n-1}{5} \rfloor$ in this case. Furthermore, $k \geq 2m-1 = \lfloor \frac{2n-1}{5} \rfloor$ for all $n \in \mathbb{N}$. Now, we will prove the upper bound. Observe that since the pairs are disjunt and $a_i \neq b_i$ for all $i=1,2,...,k$ $$\implies 1+2+...+2k=k(2k+1) \leq \sum_{i=1}^k a_i+b_i \qquad (\star)$$ On the other hand, since $a_i+b_i \leq n$ for all $i= 1,2,...,k$ and the sums $a_i+b_i$ are distinct $$\implies \sum_{i=1}^k a_i+b_i \leq n+(n-1)+...+(n-k+1)=nk+ \frac{k-k^2}{2}$$ $\implies$ from $(\star)$, $nk+ \frac{k-k^2}{2} \geq k(2k+1) \iff n-k+ \frac{k+1}{2} \geq 2k+1 \iff 2n \geq 5k+1 \iff k \leq \frac{2n-1}{5}$, but since $k$ is an integer, we have that $k \leq \lfloor \frac{2n-1}{5} \rfloor$. Therefore, $ \boxed {k= \lfloor \frac{2n-1}{5} \rfloor}$ and we are done. $\blacksquare$

Oops this writeup is really bad and rushed. The answer is $\left \lfloor \frac{2n-1}{5}\right \rfloor$. From now on we will sometimes refer to this quantity as $k$ just to keep things neat. We first give the following construction: If $n=5m+1$ or $5m+2$, then we have $k=2m$. We use the following pairs: $(2m,3m+1),(2m-2,3m+2),\ldots,(2,4m)$ and $(2m-1,2m+1),(2m-3,2m+2),\ldots,(1,3m)$. The first list gives us $m$ pairs, as does the second, for a total of $2m=k$. Further, we can see that the numbers used are distinct: the first list covers even numbers in $[1,2m]$ and all integers in $[3m+1,4m]$. The second list covers odd numbers in $[1,2m]$ and all integers in $[2m+1,3m]$. Finally, the sums are distinct, and all less than $n \geq 5m+1$. The first list gives us $5m+1,5m,5m-1,\ldots 4m+2$ and the second gives us $4m,4m-1,\ldots,3m+1$. If $n=5m+3,5m+4,5m+5$, then we have $k=2m+1$. We use the following pairs: $(2m,3m+3),(2m-2,3m+4),\ldots,(2,4m+2)$ and $(1,3m+2),(3,3m+1),\ldots,(2m+1,2m+2)$. The first list gives us $m$ pairs, and the second $m+1$, for a total of $2m+1=k$. Further, we can see that the numbers used are distinct; the first list covers even numbers in $[1,2m+1]$ and all integers in $[3m+3,4m+2]$, the second list covers odd numbers in $[1,2m+1]$ and all integers in $[2m+2,3m+2]$. Finally, the sums are distinct, and all less than $n \geq 5m+3$. The first list gives us $5m+3,5m+2,\ldots,4m+4$ and the second gives us $4m+3,4m+2,\ldots,3m+3$. Now we show that this is an upper bound. To do this, we will demonstrate that picking $m>k$ pairs is impossible by a double counting argument. On one hand, the least possible sum of these $m$ pairs is equal to $1+2+3+\cdots+(2m-1)+2m=m(2m+1)$, since these are the $2m$ smallest possible entries. On the other hand, the greatest possible sum of these $m$ pairs is equal to $n+(n-1)+\ldots+(n-m+1)=\frac{1}{2}m(2n-m+1)$, since these are the $m$ largest possible sums. Since $m \geq \left \lfloor \frac{2n-1}{5}\right \rfloor$, we can show that $m(2m+1)>\frac{1}{2}m(2n-m+1)$ with simple calculations, implying that $m>k$ is impossible. Thus $\left \lfloor \frac{2n-1}{5}\right \rfloor$ is an upper bound, as desired. $\blacksquare$

The answer is \(\left\lfloor\frac{2n-1}5\right\rfloor\). To establish the bound, let there be \(k\) pairs, and let \(S\) be the sum of the \(k\) distinct sums; then, \(S\) is the sum of \(2n\) distinct addends, but also the sum of \(n\) distinct sums, so \[1+\cdots+2k\le S\le(n-k+1)+\cdots+n.\]This readily rearranges to \(5k\le2n-1\), establishing the bound. What remains is the construction. Here we provide a generalizable construction of \(n=16,17,18,19,20\). The idea is to find the construction for \(n\equiv3\pmod5\) using the equality condition (since \(1+\cdots+2k=(n-k+1)+\cdots+n\), the addends must be \(\{1,\ldots,2k\}\) whereas the sums must be \(\{n-k+1,\ldots,n\}\)), then make small adjustments to hit the surrounding \(n\). \begin{align*} n=16:\quad1+11&=12 & \qquad n=17:\quad1+11&=12\\ 2+12&=14 & 2+12&=14\\ 3+13&=16 & 3+13&=16\\ 5+8&=13 & 5+8&=13\\ 6+9&=15 & 6+9&=15\\ 4+7&=11 & 7+10&=17. \end{align*}\begin{align*} n=18:\quad1+11&=12 & \qquad n=19:\quad1+11&=12 & \qquad n=20:\quad1+11&=12\\ 2+12&=14 & 2+12&=14 & 2+12&=14\\ 3+13&=16 & 3+13&=16 & 3+13&=16\\ 4+14&=18 & 4+15&=19 & 4+16&=20\\ 5+8&=13 & 5+8&=13 & 5+8&=13\\ 6+9&=15 & 6+9&=15 & 6+9&=15\\ 7+10&=17 & 7+10&=17 & 7+10&=17. \end{align*}

Let $k$ denote the answer. We claim $k=\left\lfloor \frac{2n-1}{5}\right\rfloor.$ Claim: $5k\le 2n-1.$ Proof. Let $S$ denote the sum of the $2k$ pairs of elements. Then, note that $$1+ 2 + \cdots + 2k \le S \le n + (n-1) + \cdots + n-k+1 \iff k(2k+1) \le \frac{k(2n-k+1)}{2} \iff 5k\le 2n-1.\blacksquare$$ Claim: There exists a construction for $k=\left\lfloor \frac{2n-1}{5}\right\rfloor.$ Proof. Consider the following $k$ pairs: $$(2k, n-2k), \quad (2k-1, n-2k-1), \quad (2k-2, n-2k-2), \dots, (4k-n+1, 1), \quad (4k-n, k),\quad (4k-n-1, k-1), \quad, (4k-n-2, k-2), \dots, (k+1 , n-2k+1)$$It is not hard to see that this generalization indeed works.

We begin with the following claim Claim There can be a maximum of $[\frac{2n-1}{5}]$ pairs of elements that can be chosen Proof Let $k$ be the maximum number of disjoint pairs that can be created. Let $S$ be the sum of elements present in the pairs chosen. Clearly, \[S\geq 1+2+3+\cdots+2k\] And, considering each pair's sum and noting that they are distinct and atmost n, \[S\leq n+(n-1)+(n-2)+\cdots +(n-k+1)\] Thus, \[1+2+3+\cdots+2k\leq n+(n-1)+(n-2)+\cdots +(n-k+1)\]\[\Rightarrow k(2k+1)\leq \frac{k(2n-k+1)}{2}\] Simplifying gives, \[ k\leq \frac{2k-1}{5}\] We now provide a construction showing that $[\frac{2n-1}{5}]$ pairs of elements can be achieved. Notice that we only need to prove the bound for $n=5t+1$ and $n=5t+3$, the others follow quite trivially since we can use the same constructions we used for one of these 2 For $n=5t+1$, we need to show $2t$ pairs can be chosen. Thus consider the following pairing $(t,4t+1), (t-1,4t), (t-2,4t-1), \cdots , (1,3t+2)$ and $(t+1,2t+1),(t+2,2t+2),\cdots (2t,3t)$ It is easy to see that the above $2t$ pairs satisfy the conditions of the problem Now, for $n=5t+3$, we need to show $2t+1$ pairs can be chosen. Thus consider the following pairing. $(t+1,4t+2), (t,4t+1), (t-1,4t), (t-2,4t-1), \cdots , (1,3t+2)$ and $(t+2,2t+2),(t+3,2t+3)\cdots (2t+1,3t+1)$ It is easy to see that the above $2t+1$ pairs satisfy the conditions of the problem and hence the solution is complete.

ISL marabot solve Case 1: For nonnegative integers $k$, $n=5k+1$ or $5k+2$. We claim the answer here is $\boxed{2k}$. Construction: For $k\ge 3$, take $(4k,1), (4k-1,3), \ldots, (3k,2k+1), (3k-1, 4), (3k-2,6)\ldots, (2k+2, 2k-2), (2k,2)$. For $k=0$, the construction is obvious. For $k=1$, take $(1,3), (2,4)$. For $k=2$, take $(1,8), (3,7), (2,4), (5,6)$. Bound: Suppose we have $2k+1$ such disjoint pairs. There are $4k+2$ total elements contained within these pairs. The sum of these $4k+2$ elements is equal to the sum of all the $2k+1$ distinct numbers formed by the sum of each pair. The minimum sum of $4k+2$ distinct elements is $1+2+\ldots+4k+2=(2k+1)(4k+3)$. The maximum sum of $2k+1$ distinct elements is $(3k+2)+(3k+3)+\ldots+(5k+2)=(2k+1)(4k+2)$. So they can never be equal. Case 2: For nonnegative integers $k$, $n=5k+3$, $5k+4$, or $5k+5$. We claim the answer here is $\boxed{2k+1}$. Construction: $(4k+2, 1), (4k+1,3), \ldots, (3k+2,2k+1), (3k+1, 2), (3k,4),\ldots, (2k+2,2k)$. Bound: Suppose we have $2k+2$ such disjoint pairs. There are $4k+4$ total elements contained within these pairs. The sum of these $4k+4$ elements is equal to the sum of all $2k+2$ distinct numbers formed by the sum of each pair. The minimum sum of $4k+4$ distinct elements is $1+2+\ldots+4k+4=(2k+2)(4k+5)$. The maximum sum of $2k+2$ distinct elements is $(3k+4)+(3k+5)+\ldots+(5k+5)=(k+1)(8k+9)=(2k+2)(4k+4.5)$. So they can never be equal.

Let $P(n)=\left\lfloor\frac{2n-1}5\right\rfloor$, we claim that this is the maximum for all $n$. Fix $n$ and let $m$ be the desired maximum. We will show that $m\le P(n)$. Let the pairs be $(x_i,y_i)\in\{1,2,\ldots,n\}^2$ for $1\le i\le m$. This gives the following key inequalities, as $x_j\ne x_i\ne y_i\ne y_j$ and $x_i+y_i\le n$ for each $1\le i,j\le m$. $$\sum_{i=1}^m(x_i+y_i)\le(n-m+1)+(n-m+2)+\ldots+n=\frac{m(2n-m+1)}2$$$$\sum_{i=1}^m(x_i+y_i)\ge1+2+\ldots+2m=m(2m+1)$$Combined, these imply that $m\le\frac{2n-1}5$, but since $m$ is an integer, $m$ is in fact at most $P(n)$. Finally, some constructions are enough to show that $P(n)$ is a possible value for each $n$. First, we check some trivial cases. After this, we can safely assume that $n\ge6$. If $n=1$ or $n=2$ then $P(n)=0$ and indeed no such pairs can be chosen. If $n=3$ or $n=4$ or $n=5$ then $P(n)=1$ and indeeed we can choose the pair $(1,2)$. If $n=5k+1$ then $P(5k+1)=2k$, which can be achieved with the pairs: $$(i,4k-2i+1)\text{ for }1\le i\le k\text{ and }(j+k,4k-2j+2)\text{ for }1\le j\le k.$$If $n=5k+2$ the same construction as $n=5k+1$ may be used, since $P(5k+2)=2k$ also. If $n=5k+3$ then $P(5k+1)=2k+1$, which can be achieved with the pairs: $$(i,4k-2i)\text{ for }1\le i\le k\text{ and }(j+k,4k-2j+1)\text{ for }1\le j\le k+1.$$If $n=5k+4$ the same construction as $n=5k+3$ may be used, since $P(5k+4)=2k+1$ also. If $n=5k+5$ the same construction as $n=5k+3$ may be used, since $P(5k+5)=2k+1$ also.

Suppose we have $k$ pairs; their sum is at least $k(2k+1)$ and yet the sum is also at most $(n-k+1)+(n-2k+2)+\dots+n=\frac{k(2n-k+1)}{2}$ which clearly implies that $k\le \frac{2n-1}{5}$. Then I claim that the answer is $\left \lfloor \frac{2n-1}{5}\right\rfloor$; note that it's enough to show that we can always get $\frac{2n-1}{5}$ pairs when $n\equiv 3\pmod 5$ and that we can always get $\frac{2n-2}{5}$ pairs when $n\equiv 1\pmod 5$. For the first case, take the pairs \[\left(1, \frac{3n+1}{5}\right),\left(2, \frac{3n+6}{5}\right),\dots, \left(\frac{n+2}{5}, \frac{4n-2}{5}\right)\]and the pairs \[\left(\frac{n+7}{5}, \frac{2n+4}{5}\right), \left(\frac{n+12}{5}, \frac{2n+9}{5}\right), \dots, \left(\frac{2n-1}{5}, \frac{3n-4}{5}\right)\]and for the second case take the pairs \[\left(1, \frac{3n+7}{5}\right), \left(2, \frac{3n+12}{5}\right), \dots, \left(\frac{n-1}{5}, \frac{4n+1}{5}\right)\]and the pairs \[\left(\frac{n+4}{5}, \frac{2n+3}{5}\right), \left(\frac{n+9}{5}, \frac{2n+8}{5}\right), \dots, \left(\frac{2n-2}{5}, \frac{3n-3}{5}\right).\]We are done. $\blacksquare$

Let there be $k$ pairs and $S$ be the sum of all the pairs, then $k(2k+1)\le S\le nk-\frac{k(k-1)}{2}$ which ultimately gives the inequality $5k\le 2n-1$, so \[k\le \left\lfloor\frac{2n-1}{5}\right\rfloor.\]We show that this works. We only need to show that for $n=5x+1,k=2x$ works, and for $n=5x+3,k=2x+1$ works. For $n=5x+2,5x+4,5x+5$, we can use the same pairs as $5x+1$ and/or $5x+3$. For $5x+1$, we first do $(1,4x-2),(2,4x-4),\dots,(x-1,2x+2)$, which have sums $4x-1,4x-2,\dots 3x+1$, and then we do $(x,4x+1),(x+1,4x-1),\dots,(2x,2x+1)$, which have sums $5x+1,5x,\dots,4x+1$ For $5x+3$, we first do $(1,3x+2),(2,3x+3),\dots,(x+1,4x+2)$ which have sums $3x+3,3x+5,\dots, 5x+3$ and then $(x+2,2x+2),(x+3,2x+3),\dots (2x+1,3x+1)$ which have sums $3x+4,3x+6,\dots,5x+2$

We'll prove the bound on $\left \lfloor \frac{2n-1}{5} \right \rfloor$. For $m$ disjoint pairs, satisfying the condition, with total sum $s$ we have $$m(2m+1)=1+2+\dots +2m\leq s\leq n+(n-1)+\dots +(n-m+1)=\frac{m(m+1)}{2}+m(n-m)\implies m\leq \frac{2n-1}{5}\text{ } \Box$$ Example for $n=5k+3$ (and the same for $5k+4,5k$) is a set of pairs $(i;4k+3-2i)$ and $(j;6k+4-2j)$ for all $1\leq i\leq k<j\leq 2k+1$ - pairwise sums are all $2k+1$ integers between $3k+3$ and $5k+3.$ Example on $2k$ pairs for $n=5k+2$ can be obtained from the above by removing of pair $(k+1;4k+2).$ Finally, the example for $n=5k+1$ is a set of pairs $(i;4k+1-2i)$ and $(j;6k+2-2j)$ for all $1\leq i\leq k<j\leq 2k$.

For each pair $(x,y)$, consider a third nonnegative integer $z$ such that $x+y+z=n$. Clearly, $z$ cannot repeat across pairs, but can appear in the $x$ of a different pair, etc. Now, say that the answer is $N(n)$. Then, by double counting the sum of $x,y,z$, $$\frac{N(N-1)}{2}+\frac{2N(2N+1)}{2}\le nN\rightarrow 5N+1\le 2n\rightarrow N\le\boxed{\left\lfloor\frac{2n-1}{5}\right\rfloor}.$$We will now show that this is possible by taking cases on $n$ mod $5$. Let $a=\left\lfloor\frac n5\right\rfloor$.

Since we have provided working constructions for all cases, we are done.

We claim that the maximum number of such pairs is $\left\lfloor{}\frac{2n-1}{5}\right\rfloor{}$. 1. Upper Bound Proof Notice that if we have $k$ pairs of numbers, then we must have that $k$ satisfies the inequality \[n+(n-1)+\dots{}+(n-k+1)\geq{}1+2+\dots{}+2k,\]\[\iff{}\frac{k(2n-k+1)}{2}\geq{}\frac{2k(2k+1)}{2},\]\[\iff{}2n-k+1\geq{}4k+2,\]\[\iff{}2n-1\geq{}5k,\]Proving that $k \leq{} \left\lfloor{}\frac{2n-1}{5}\right\rfloor{}$ 2. Construction, n=5x Then we would take the pairs $(1,3x+2)$, $(2,3x+3)$, $\dots$, $(x-1,4x)$ and $(x+1,2x+1)$, $(x+2,2x+2)$, $\dots$, $(2x,3x)$. 3. Construction, n=5x+1, 5x+2 $(1,3x+2)$, $(2,3x+3)$, $\dots$, $(x,4x+1)$ and $(x+1,2x+1)$, $(x+2,2x+2)$, $\dots$, $(2x,3x)$. 4. Construction, n=5x+3, 5x+4 $(1,3x+2)$, $(2,3x+3)$, $\dots$, $(x+1,4x+2)$ and $(x+2,2x+2)$, $(x+2,2x+2)$, $\dots$, $(2x+1,3x+1)$. Therefore the maximum number of such pairs (since we've both proved and constructed) is $\left\lfloor{}\frac{2n-1}{5}\right\rfloor{}$, finishing the problem.

The answer is $$\lfloor \frac{2n-1}{5} \rfloor.$$ Suppose $p$ is the number of pairs that we form, and let $S$ be the sum of the numbers in the pairs. We have $$S\geq 1+2\cdots +2p=\frac{2p(2p+1)}{2},$$but by the problem condition we also have $$S\leq (n)+(n-1)+(n-2)\cdots +(n-p+1)$$since the largest we can go is the $p$ largest numbers not exceeding $n$. Therefore, we have $$\frac{(2n-p+1)p}{2}\geq \frac{2p(2p+1)}{2}$$$$2np-p^2+p\geq 4p^2+2p$$$$2n\geq 5p+1$$$$p\leq \frac{2n-1}{5},$$as desired. Now, we provide a construction. Since $\lfloor \frac{2n-1}{5}\rfloor$ follows a $x,x,x,x+1,x+1$ pattern, it suffices to provide a construction for $n\equiv 3\pmod{5}$ and $n\equiv 1\pmod{5}$, since the others just follow by adding one or two more to $n$ and doing nothing. We do $n\equiv 3\pmod{5}$ first, since that is the "strongest" case (in the sense that the $\frac{2n-1}{5}$ estimate is exact here). If $n=5s+3$, we can do $$(1,4s+2)$$$$(2,4s)$$$$(3,4s-2)$$$$\dots$$$$(s+2,2s+4)$$$$(s+1,2s+2)$$(transition) $$(s+2,4s+1)$$$$(s+3,4s-1)$$$$\dots$$$$(2s+1,2s+3).$$The pairs before the transition attain sums from $4s+3$ down to $3s+3$, and the pairs after the transition attain sums from $5s+3$ down to $4s+4$, so this works. For $n\equiv 1 \pmod 5$, we can actually borrow our 3 mod 5 construction and add 3 to $n$. We only need one more pair. This can be achieved by looking at each pair in our above construction, adding 1 to the first element and 2 to the second element (increasing the sum by 3, so it if was at most $n$ before then it is still at most $n$ after $n$ increases by 3). However, this frees up $1$ and $2s+3$, which we then use to form our final pair, thus done.

We claim the maximum is $\lfloor{\frac{2n-1}{5}}\rfloor$. We first prove the bound and then show the construction. For the bound, consider the sum of all pairs. We can say that, by double counting, with $k$ pairs: \[S\geq 1+2+\dots+2k=k(2k+1),\]\[S\leq (n-k+1)+\dots+n=\frac{k(2n-k+1)}{2}.\] Thus: \[2n-k+1\geq 4k+2,\]\[5k\leq 2n-1,\]\[k\leq \frac{2n-1}{5},\]as desired $\square$ We now let $n=5m+1,2,3,4,5$ for our construction. For $n=5m+1,2$, our construction is: \[(4m-1,1),(4m-3,2),\dots,(2m+1,m),(4m,m+1),\dots,(2m+2,2m).\]For $n=5m+3,4,5$, our construction is: \[(4m+1,1),(4m-1,2),\dots,(2m+3,m),(4m+2,m+1),\dots,(2m+2,2m+1).\]

The answer is $\left\lfloor \frac{2n-1}{5} \right\rfloor$. Let $k$ be the number of pairs. First, we show that $k > \left\lfloor \frac{2n-1}{5} \right\rfloor$ is impossible. Consider $S$, the sum of all $2k$ integers that are in a pair. The conditions imply that \[ S \leq n + (n-1) + (n-2) + \dots + (n-(k-1)) \]and that \[ S \geq 1 + 2 + \dots + 2k. \]Thus, we have \[ n + (n-1) + (n-2) + \dots + (n-(k-1)) \geq 1 + 2 + \dots + 2k. \]Simplifying this gives $k \leq \frac{2n-1}{5}$, and thus, $k > \left\lfloor \frac{2n-1}{5} \right\rfloor$ is impossible. Next, we provide a construction for when $k = \left\lfloor \frac{2n-1}{5} \right\rfloor$. If $n = 5s + 1$ for an integer $s$, then we have $k=2s$, and the desired $k$ pairs are the union of \[ \{(i, 3s+i+1), (s+i, 2s+i)\} \]for $i = 1,2,\dots,s$. If $n = 5s + 2$ for an integer $s$, then we still have $k=2s$ and hence, we can use the same construction as above. If $n = 5s + 3$ for an integer $s$, then $k = 2s+1$, and the desired $k$ pairs are the union of \[ \{(i, 3s+i+2), (s+j, 2s+j+1)\} \]for $i = 1,2,\dots,s$ and $j = 1,2,\dots,s+1$. Finally, if $n = 5s+4$ or $n = 5s+5$ for an integer $s$, then we still have $k = 2s+1$ and hence, we can use the same construction as above. These constructions can be easily shown to work, concluding the proof.

This is an AIME problem: https://artofproblemsolving.com/wiki/index.php/2009_AIME_II_Problems/Problem_12?