Vika chose a 20-letter word that consists only of letters and . Oleksii wants to know what Vika's word is. He can ask Vika if there are more 's or 's among several (possibly one) consecutive letters of her word. If there are as many 's as there are 's, Vika's answer may be any of the two letters. What is the least number of questions after which Oleksii can guaranteed determine the word Vika chose?
Problem 1860
Official solution
It is clear how Oleksii can determine the word in 20 questions – it suffices to ask about each letter separately.
We want to show that smaller number of questions would not be enough. Suppose Oleksii determined the word in no more than 19 questions. Suppose Vika chose a word that consists of 20 letters . Clearly, for every question Oleksii asked, Vika's answer was that there are more letters . Since there were less than 20 questions, there is a letter that wasn't asked about separately. Let it be the -th letter. Then consider a word that consists of letters everywhere, except for the -th letter, which is . Clearly, for both such words Vika could have had the same answers. Thus, Oleksii couldn't have determined which one of these two words Vika chose.