PUMaC 2023 · 数论（A 组） · 第 5 题
PUMaC 2023 — Number Theory (Division A) — Problem 5
题目详情
- You play a game where you and an adversarial opponent take turns writing down positive integers on a chalkboard; the only condition is that, if m and n are written consecutively on the board, gcd( m, n ) must be squarefree. If your objective is to make sure as many integers as possible that are strictly less than 404 end up on the board (and your opponent is trying to minimize this quantity), how many more such integers can you guarantee will eventually be written on the board if you get to move first as opposed to when your opponent gets to move first?
解析
- You play a game where you and an adversarial opponent take turns writing down positive integers on a chalkboard; the only condition is that, if m and n are written consecutively on the board, gcd( m, n ) must be squarefree. If your objective is to make sure as many integers as possible that are strictly less than 404 end up on the board (and your opponent is trying to minimize this quantity), how many more such integers can you guarantee will eventually be written on the board if you get to move first as opposed to when your opponent gets to move first? Proposed by Austen Mazenko Answer: 94 Note that you can always write squarefree numbers on the board, and thus regardless of whether you move first or second, you can guarantee all squarefree numbers less than 404 get written. Now, if you go second, your opponent can guarantee that you can only write squarefree 2 2 2 2 numbers by simply writing multiples of 2 · 3 · 5 · · · 401 on the board. Thus, it suffices to find the maximum number of non-squarefree numbers you can guarantee get written on the 2 board if you go first. For any prime p , if you ever write a number m such that p ∤ m , then 2 your opponent can continually choose multiples of p that are greater than 404 which prevents 2 you from writing any more multiples of p . Note also that writing any number greater than 404 functionally just stalls the game by a round and cannot give you any advantage. Thus, to 2 2 play optimally, you should thus write all multiples of 2 · 3 = 36 less than 404, after which you should write everything expressible as 4 times a number with no odd divisors that are the squares of a prime, then finally squarefree integers. Tallying, we see there are 11 multiples of