PUMaC 2020 · 数论（B 组） · 第 2 题

PUMaC 2020 — Number Theory (Division B) — Problem 2

Last year, the U.S. House of Representatives passed a bill which would make Washington, D.C. into the 51st state. Naturally, the mathematicians are upset that Congress won’t prioritize mathematical interest of flag design in choosing how many U.S. states there should be. Suppose the U.S. flag must contain, as it does now, stars arranged in rows alternating between n and n − 1 stars, starting and ending with rows of n stars, where n ≥ 2 is some integer and the flag has more than one row. What is the minimum number of states that the U.S. would need to contain so that there are at least three different ways, excluding rotations, to arrange the stars on the flag? 2 2020 2020 2020 2020

解析

Last year, the U.S. House of Representatives passed a bill which would make Washington, D.C. into the 51st state. Naturally, the mathematicians are upset that Congress won’t prioritize mathematical interest of flag design in choosing how many U.S. states there should be. Suppose the U.S. flag must contain, as it does now, stars arranged in rows alternating between n and n − 1 stars, starting and ending with rows of n stars, where n ≥ 2 is some integer and the flag has more than one row. What is the minimum number of states that the U.S. would need to contain so that there are at least three different ways, excluding rotations, to arrange the stars on the flag? Proposed by: Ollie Thakar Answer: 53 We are looking for the smallest integer m expressible as nk + ( n − 1)( k − 1) for three distinct pairs ( n, k ) , with n, k ≥ 2 , where k is the number of rows of n stars. Thus, we must have the largest value of n ≥ 4 . If we try n = 2 , 3 , 4 , we note that m works if and only if it is 2 mod 3, 3 mod 5, and 4 mod 7, so the Chinese Remainder Theorem gives us that m = 53 is the smallest m that works. Checking n = 5 , 6 makes clear that there is no smaller value of m works. Incidentally, it’s actually impossible if m = 51 , so it’s a good thing that 1) the Senate is rather unproductive and 2) this is not actually a real constraint on flag design. 2 2020 2020 2020 2020