HMMT 二月 2003 · COMB 赛 · 第 1 题

HMMT February 2003 — COMB Round — Problem 1

You have 2003 switches, numbered from 1 to 2003, arranged in a circle. Initially, each switch is either ON or OFF, and all configurations of switches are equally likely. You perform the following operation: for each switch S , if the two switches next to S were initially in the same position, then you set S to ON; otherwise, you set S to OFF. What is the probability that all switches will now be ON?

解析

You have 2003 switches, numbered from 1 to 2003, arranged in a circle. Initially, each switch is either ON or OFF, and all configurations of switches are equally likely. You perform the following operation: for each switch S , if the two switches next to S were initially in the same position, then you set S to ON; otherwise, you set S to OFF. What is the probability that all switches will now be ON? 2002 Solution: 1 / 2 2003 There are 2 equally likely starting configurations. All switches end up ON if and only if switches 1 , 3 , 5 , 7 , . . . , 2003, 2 , 4 , . . . , 2002 — i.e. all 2003 of them — were initially in the same position. This initial position can be ON or OFF, so this situation occurs 2003 2002 with probability 2 / 2 = 1 / 2 .