HMMT 二月 2002 · 冲刺赛 · 第 29 题

HMMT February 2002 — Guts Round — Problem 29

[8] A sequence s , s , s , s , . . . is defined by s = s = 1 and, for every positive integer 0 1 2 3 0 1 2 n , s = s , s = s , s = s + s /s . What is the value of s ? 2 n n 4 n +1 2 n +1 4 n − 1 2 n − 1 n − 1 1000 2 n − 1

解析

A sequence s , s , s , s , . . . is defined by s = s = 1 and, for every positive integer 0 1 2 3 0 1 2 n , s = s , s = s , s = s + s /s . What is the value of s ? 2 n n 4 n +1 2 n +1 4 n − 1 2 n − 1 n − 1 1000 2 n − 1 Solution: 720 Some experimentation with small values may suggest that s = k !, where n k is the number of ones in the binary representation of n , and this formula is in fact provable by a straightforward induction. Since 1000 = 1111101000 , with six ones, s = 6! = 720. 10 2 1000