PUMaC 2023 · 组合（B 组） · 第 7 题
PUMaC 2023 — Combinatorics (Division B) — Problem 7
题目详情
- There are n assassins numbered from 1 to n , and all assassins are initially alive. The assassins play a game in which they take turns in increasing order of number, with assassin 1 getting the first turn, then assassin 2, etc., with the order repeating after assassin n has gone; if an assassin is dead when their turn comes up, then their turn is skipped and it goes to the next assassin in line. On each assassin’s turn, they can choose to either kill the assassin who would otherwise move next or to do nothing. Each assassin will kill on their turn unless the only option for guaranteeing their own survival is to do nothing. If there are 2023 assassins at the start of the game, after an entire round of turns in which no one kills, how many assassins must remain?
解析
- There are n assassins numbered from 1 to n , and all assassins are initially alive. The assassins play a game in which they take turns in increasing order of number, with assassin 1 getting the first turn, then assassin 2, etc., with the order repeating after assassin n has gone; if an assassin is dead when their turn comes up, then their turn is skipped and it goes to the next assassin in line. On each assassin’s turn, they can choose to either kill the assassin who would otherwise move next or to do nothing. Each assassin will kill on their turn unless the only option for guaranteeing their own survival is to do nothing. If there are 2023 assassins at the start of the game, after an entire round of turns in which no one kills, how many assassins must remain? Proposed by Ben Lemkin Answer: 1023 k We show by induction that number of the form n = 2 − 1 are stable, being no one shoots, while all others are not. n = 1 , 2 are trivial; for n = 3, we observe it’s stable for the following reason; if person 1 shoots person 2, then person 3 will kill person 1, so to avoid dying person 1 will not shoot; by symmetry, this means none of them will shoot. Indeed, note by symmetry that we only need to assess the first person’s behavior, as if person 1 shoots then it’s not stable, while k if person 1 does not shoot then it is stable. With the base case proven, suppose n = 2 − 1 is k stable. Consider n = 2 ; the first person will shoot the second person, because then there are k 2 − 1 people remaining, and by assumption no one will shoot in this scenario. Similarly, for 3 k k n = 2 + 1, if the first person shoots the second person, then 2 people will remain standing, k whence the third person will proceed to shoot the fourth person after which 2 − 1 people are left and everyone ceases. Thus, the first person will shoot the second person as long as the k first person is not also the fourth person (meaning 4 ≡ 1 (mod 2 − 1). Continuing like so, k we see that for n = 2 + a for a ≥ 0 that person 1 will shoot, then person 3 will shoot, etc., k all the way up to person 2( a + 1) − 1 shooting person 2( a + 1), after which there are 2 − 1 people left and no one else shoots. This sequence of events will hold up until the point when k 2( a + 1) ≡ 1 (mod 2 + a ), because that would means person 1 gets shot; the smallest a this k k +1 holds for, and thus the next smallest stable position, is a = 2 − 1, implying n = 2 − 1. k Thus, by induction, stable n are of the form 2 − 1, and our answer is 1023.