HMMT 二月 2017 · 冲刺赛 · 第 34 题
HMMT February 2017 — Guts Round — Problem 34
题目详情
- [ 20 ] (a) Can 1000 queens be placed on a 2017 × 2017 chessboard such that every square is attacked by some queen? A square is attacked by a queen if it lies in the same row, column, or diagonal as the queen. (b) A 2017 × 2017 grid of squares originally contains a 0 in each square. At any step, Kelvin the Frog chooses two adjacent squares (two squares are adjacent if they share a side) and increments the numbers in both of them by 1. Can Kelvin make every square contain a different power of 2? (c) A tournament consists of single games between every pair of players, where each game has a winner and loser with no ties. A set of people is dominated if there exists a player who beats all of them. Does there exist a tournament in which every set of 2017 people is dominated? (d) Every cell of a 19 × 19 grid is colored either red, yellow, green, or blue. Does there necessarily exist a rectangle whose sides are parallel to the grid, all of whose vertices are the same color? 2
(e) Does there exist a c ∈ R such that max( | A · A | , | A + A | ) ≥ c | A | log | A | for all finite sets A ⊂ Z ? (f) Can the set { 1 , 2 , . . . , 1093 } be partitioned into 7 subsets such that each subset is sum-free (i.e. no subset contains a, b, c with a + b = c )?
解析
- [ 20 ] (a) Can 1000 queens be placed on a 2017 × 2017 chessboard such that every square is attacked by some queen? A square is attacked by a queen if it lies in the same row, column, or diagonal as the queen. (b) A 2017 × 2017 grid of squares originally contains a 0 in each square. At any step, Kelvin the Frog chooses two adjacent squares (two squares are adjacent if they share a side) and increments the numbers in both of them by 1. Can Kelvin make every square contain a different power of 2? (c) A tournament consists of single games between every pair of players, where each game has a winner and loser with no ties. A set of people is dominated if there exists a player who beats all of them. Does there exist a tournament in which every set of 2017 people is dominated? (d) Every cell of a 19 × 19 grid is colored either red, yellow, green, or blue. Does there necessarily exist a rectangle whose sides are parallel to the grid, all of whose vertices are the same color? 2
(e) Does there exist a c ∈ R such that max( | A · A | , | A + A | ) ≥ c | A | log | A | for all finite sets A ⊂ Z ? (f) Can the set { 1 , 2 , . . . , 1093 } be partitioned into 7 subsets such that each subset is sum-free (i.e. no subset contains a, b, c with a + b = c )? Proposed by: Alexander Katz Answer: NNYYYY