Competition problem — Combinatorics

Library / /130 of 397

Combinatorics Difficulty 5.4 AIME, harder Prove it Taiwan

Let $n$ be an integer greater than or equal to 1. In the set $\{1, 2, \dots, n\}$ , what is the maximum number of pairs of numbers that can be chosen such that each pair consists of two distinct numbers, the sum of each pair is different from the sums of all other pairs, and the sum of each pair does not exceed $n$ ?

Solution

考慮集合 $\{1, 2, 3, \dots, n\}$ 中的 $x$ 對這樣的數字。這些 $2x$ 個數字的總和 $S$ 至少是 $1+2+\cdots+2x$ , 因為這些選出來的數字兩兩互異。另一方面 $S \le n+(n-1)+\cdots+(n-x+1)$ , 因為每對數字的和均不相同, 並且都不超過 $n$ 。於是給出下列的不等式
$\frac{2x(2x+1)}{2} \le nx - \frac{x(x-1)}{2},$
所以推得 $x \le \frac{2n-1}{5}$ 。所以最多可以有 $\lfloor \frac{2n-1}{5} \rfloor$ 對滿足題設的數字。

以下建構 $\lfloor \frac{2n-1}{5} \rfloor$ 對滿足題設的數字。首先考慮 $n = 5k + 3$ ( $k \ge 0$ ) 的情形, 此時 $\lfloor \frac{2n-1}{5} \rfloor = 2k + 1$ 。這些對數字可以用下列的表格表示:

數對	$3k + 1$	$3k$	$\dots$	$2k + 2$	$4k + 2$	$4k + 1$	$\dots$	$3k + 3$	$3k + 2$
和	$2$	$4$	$\dots$	$2k$	$1$	$3$	$\dots$	$2k - 1$	$2k + 1$
和	$3k + 3$	$3k + 4$	$\dots$	$4k + 2$	$4k + 3$	$4k + 4$	$\dots$	$5k + 2$	$5k + 3$

以上的

2k+1

對數字使用了

1

到

4k+2

的所有數字; 各對數字的和包含

3k+3

到

5k+3

的所有數字。當

n = 5k + 4

或

5k + 5

(

k \ge 0

) 時可以用同樣的建構法。在這些情形下要達成的對數

\lfloor \frac{2n-1}{5} \rfloor

仍然是

2k+1

, 而上表中所有的和也都不超過

5k+3

。

在 $n = 5k + 2$ ( $k \ge 0$ ) 的情形下, 只需要 $2k$ 對數字; 此時可以將上表中的最後一行刪除 (於是移除了和是 $5k+3$ 的那一對數)。

最後, 當 $n = 5k + 1$ ( $k \ge 0$ ) 時也需要 $2k$ 對數字。此時只要將上表中的最後一行刪除, 並且將第一列的各個數字減 $1$ 即可。

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.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.