MathDB

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 Statement