PUMaC 2014 · 组合（A 组） · 第 5 题
PUMaC 2014 — Combinatorics (Division A) — Problem 5
题目详情
- [ 5 ] What is the size of the largest subset S of S = { 2 3 5 : 0 ≤ x, y, z ≤ 4 } such that there ′ are no distinct elements p, q ∈ S with p | q .
解析
- [ 5 ] What is the size of the largest subset S of S = { 2 3 5 : 0 ≤ x, y, z ≤ 4 } such that there ′ are no distinct elements p, q ∈ S with p | q . Solution: Let us find ( x, y, z ) such that x + y + z = 6. We see that when x = 0 , 1 , 2 , 3 , 4, there are 3 , 4 , 5 , 4 , 3 sets respectively, which means there are 19 such ( x, y, z ). Since x + y + z = 6 in these sets, for p | q , we must have p = q . Let us show that 20 is impossible. Firstly, note that ( y, z ) of all elements are distinct. Oth- ′ x y z x y z 0 0 0 0 erwise, we have 2 3 5 and 2 3 5 , and the smaller of the two will divide the larger. We shall show that if ( y, z ) = { (0 , 0) , (0 , 1) , (1 , 0) , (3 , 4) , (4 , 3) , (4 , 4) } then there cannot be 20 dis- tinct ( y, z ), and by pigeonhole principle, any set of 20 distinct ( y, z ) must contain one of the above. 3 x x 4 If 2 is in the subset, we can change 2 to 2 and the subset will still work. In the new subset, we see that the only (4 , y, z ) we can have is y = z = 0. Thus there must be 19 distinct ( y, z ) for x = { 0 , 1 , 2 , 3 } and hence by Pigeonhole Principle, we must have x , x distinct such that 1 2 there are 5 sets of ( x , y, z ). However, it is clear that for a fixed x , the only set of 5 ( y, z ) such i i that ( x , y, z ) are all in the subset is when y + z = 5. Thus it is impossible to find two such i subsets. Contradiction. x x 4 If 2 3 is in the subset, we can change 2 3 to 2 3 and the subset will still work. In the new subset, we see that the only (4 , y, z ) we can have is (4 , 1 , 0) and (4 , 0 , 1). Hence there must be 18 distinct ( y, z ). Just as before, there must be x , x distinct with 5 sets of ( x , y, z ). This 1 2 i leads to a similar contradiction. x 4 4 x 4 3 x 3 4 The same aregument can be made for 2 3 5 , 2 3 5 and 2 3 5 by replacing them with 4 4 4 3 3 4 3 5 , 3 5 and 3 5 respectively. Hence we see that 19 is the maximum possible.