PUMaC 2013 · 团队赛 · 第 8 题

PUMaC 2013 — Team Round — Problem 8

Let k be a positive integer with the following property: For every subset A of { 1 , 2 , ..., 25 } with 2 x 3 | A | = k , we can find distinct elements x and y of A such that ≤ ≤ . Find the smallest 3 y 2 possible value of k .

解析

Let k be a positive integer with the following property: For every subset A of { 1 , 2 , ..., 25 } with 2 x 3 | A | = k , we can find distinct elements x and y of A such that ≤ ≤ . Find the smallest 3 y 2 possible value of k . SOLUTION: By considering { 1 , 2 , 4 , 8 , 16 , 25 } , we see that 6 numbers don’t necessarily suf- fice. To prove that k = 7 works, consider the partition { 1 } , { 2 , 3 } , { 4 , 5 , 6 } , { 7 , 8 , 9 , 10 } , { 11 , 12 , ..., 16 } , { 17 , 18 , ..., 25 } . If 7 numbers are picked, two of them, x and y , will be in the 2 x 3 same set. Then ≤ ≤ . 3 y 2 ANSWER: 7