返回题库

PUMaC 2014 · 组合（B 组） · 第 7 题

PUMaC 2014 — Combinatorics (Division B) — Problem 7

专题
Discrete Math / 离散数学
难度
L3
来源
PUMaC

题目详情

  1. [ 7 ] Let S = { 1 , 2 , 3 , ...., 2014 } . What is the largest subset of S that contains no two elements with a difference of 4 and 7?
解析
  1. [ 7 ] Let S = { 1 , 2 , 3 , ...., 2014 } . What is the largest subset of S that contains no two elements with a difference of 4 and 7? Solution: 3 We see that 0 , 4 , 8 , 1 , 5 , 9 , 2 , 6 , 10 , 3 , 7 are a series of 11 numbers whoses difference with their neighbours are 4 or 7. Hence in any 11 numbers, there can be at most 5 picked, as other wise two will be adjacent, (7 , 0) included. Since 2014 = 183 × 11 + 1, we see we can have at most 183 × 5 + 1 = 916 elements in the subset. This is possible if we pick all numbers that are 4 , 1 , 9 , 6 , 3 mod 11.