A test consists of $30$ true or false questions. After the test (answering all $30$ questions), Victor gets his score: the number of correct answers. Victor is allowed to take the test (the same questions ) several times. Can Victor work out a strategy that insure him to get a perfect score after (a) $30$th attempt? (b) $25$th attempt? (Initially, Victor does not know any answer)
Problem
Source:
Tags: combinatorics unsolved, combinatorics
04.09.2010 16:05
Please post your solutions. They don't agree if in the exam you just write "Yes" !
04.09.2010 16:13
amparvardi wrote: Please post your solutions. They don't agree if in the exam you just write "Yes" ! Yes, I now post solution, but it was to long and my english is not very well, so it takes more time
04.09.2010 16:58
Prove that Victor can get perfect score for $25$ attempt . We call question $yes-q$ if answer yes is write and $no-q$ if answer no is write. Let questions with numbers $(5i+1;5i+2;5i+3;5i+4;5i+5)$ for $i =1,2,3,4,5$ be the $ Group $ 1-st attempt -Victor answer yes for all questions $=>$ he knows summary number of $yes-q$ Show, that victor can knowing true answers on questions of one group by 4 attempt. (Show it's for first group, for other is following. To 2-nd attempt Victor said no to questions 1-5 , for other yes; To 3-rd attempt Victor said no to questions 1,2 , for other yes; To 4-th attempt Victor said no to questions 1,3 , for other yes; To 5-th attempt Victor said no to questions 1,4 , for other yes; From 1 and 2 attempt we know how much $yes-q$ from question 1,2,3,4,5; From 2 and 3 attempt we know, how much $yes-q$ from question 1,2. $(1)$ (1),(2) is $yes-q$ then after 4 attempt we know right answer to (3) question, after 5 attempt he know right answer to (4) question => he knows right answer to (5) question (because he know how much $yes-q$ is from 1-5 and he know right answers to 1-4 question. $(2)$ (1),(2) is $no-q$ then prove similarly first case; $(3)$ one of questions (1);(2) is $yes-q$, one $no-q$ (Victor don't know which is which). From 2;4 and 2;5 attempts we know how much $yes-q$ is from questions (1;3) and (1;4) respectively. If both of the questions from one of this pair is $yes-q$ or $no-q$ (for example (1;3) questions are $yes-q$ then we know that Victor can right answer on all questions of $Group$(similarly $(1)$ case)=> Exist only one case, when in each of the pair (1;2);(1;3);(1;4) is one $yes-q$ and one $no-q$ => if 1 is $yes-q$ then 2,3,4 is $no-q$ => number of $no-q$ from 1,2,3,4,5 qustions grater, than number of $yes-q$ and conversely, but we know number of $yes-q$ => we know number of which type of question grater => we know right answer to 1-st question => we know right answers for 2,3,4 questions => we know right answer to 5-th question. So, Victor can found right answers on question of one $Group$ by 4 attempt, we have 6 $Groups$ and one first attempt (when we answer yes for all questions) But in last $Group$ (26,27,28,29,30) we don't need to use first attempt(when we said on question 26-30 no, for other yes because we know number of $yes-q$ in 1,2,3,4,5 $Group$'s and we know total number of $yes-q$=>we know number of $yes-q$ in question (26,27,28,29,30)=> After 24 attempt we know right answers to all questions => in 25-th attempt we can get a perfect score!