HMMT 二月 2005 · 冲刺赛 · 第 45 题
HMMT February 2005 — Guts Round — Problem 45
题目详情
英文原题
- A binary word is a finite sequence of 0’s and 1’s. A square subword is a subsequenceconsisting of two identical chunks next to each other. For example, the word 100101011
contains the square subwords 00, 0101 (twice), 1010, and 11.
Find a long binary word containing a small number of square subwords. Specifically,
write down a binary word of any length n ≤ 50. Your score will be max { 0 , n − s } ,
where s is the number of occurrences of square subwords. (That is, each differentsquare subword will be counted according to the number of times it appears.) 7
解析
英文解析
- A binary word is a finite sequence of 0’s and 1’s. A square subword is a subsequenceconsisting of two identical chunks next to each other. For example, the word 100101011
contains the square subwords 00, 0101 (twice), 1010, and 11.
Find a long binary word containing a small number of square subwords. Specifically,
write down a binary word of any length n ≤ 50. Your score will be max { 0 , n − s } ,
where s is the number of occurrences of square subwords. (That is, each differentsquare subword will be counted according to the number of times it appears.)
Remark: See http://www.combinatorics.org/Volume 10/PDF/v 10 i 1 r 12.pdf foranalysis of this problem. The maximum possible score is on the order of 25. In general,
the minimum number of square subwords of a word of length n tends to roughly 0 . 551 nas n → ∞ .
18