Let $n$ be a positive integer and let $t$ be an integer. $n$ distinct integers are written on a table. Bob, sitting in a room nearby, wants to know whether there exist some of these numbers such that their sum is equal to $t$. Alice is standing in front of the table and she wants to help him. At the beginning, she tells him only the initial sum of all numbers on the table. After that, in every move he says one of the $4$ sentences: $i.$ Is there a number on the table equal to $k$? $ii.$ If a number $k$ exists on the table, erase him. $iii.$ If a number $k$ does not exist on the table, add him. $iv.$ Do the numbers written on the table can be arranged in two sets with equal sum of elements? On these questions Alice answers yes or no, and the operations he says to her she does (if it is possible) and does not tell him did she do it. Prove that in less than $3n$ moves, Bob can find out whether there exist numbers initially written on the board such that their sum is equal to $t$
Problem
Source: Bosnia and Herzegovina TST 2016 day 1 problem 2
Tags: table, combinatorics, Game Theory
mitrov
21.05.2016 20:00
Any solutions?
Garfield
23.05.2016 22:25
Let sum of numbers on table be $L$.We will use simple induction by $n$ to prove Bob can win by less then $3n$ steps:
Induction base: $n=1$ so just Bob asks if $k=f$
induction hypotes : we assume that for $n$ numbers we can "win" in $3n$ steps
induction step: if we have $n+1$ numbers we need to show that we can win in $\leq 3n+3$ steps.In first step we will ask if $L-2t$ is on table.If answer is YES in next step we will remove it from table so now we have $n$ numbers so we can win in next $3n$ so that's $3n+2$ steps.If answer is NO we will add $L-2t$.So in next step we will ask $iv$.If answer is YES then we know that there exist numbers who's sum is $t$ because we have that in every group sum is $L-t$ so other numbers in group with $L-2t$ will have sum $t$,if answer is NO then there don't exist number such their sum is $t$ so just 2 steps.
Garfield
05.07.2016 22:23
Where can I find 6. problem from this competition?
liorz2000
14.05.2017 20:09
Garfield, how you get the sum of the numbers if Bob didn't saw them?
liorz2000
14.05.2017 20:14
Ok, I understood now. I miss that detaile at the biginng when I read the question.