15
$\begingroup$

Alice secretly chooses $2016$ integers $x_1,x_2,\ldots,x_{2016}$. Among these $2016$ integers there are $2015$ that all have the same value, and there is only one number $x_k$ that takes a different value. Bob is allowed to ask questions by announcing $2016$ integers $y_1,y_2,\ldots,y_{2016}$. Alice then computes the value $$x_1y_1+x_2y_2+\cdots+x_{2016}y_{2016}$$ and tells it to Bob. Then Bob asks his next question, and so on.

What is the smallest number of questions that (even in the worst case) allow Bob to determine the values of all $2016$ integers $x_1,x_2,\ldots,x_{2016}$?

$\endgroup$
  • $\begingroup$ can we have $xi<0$ or $yi<0$ ? $\endgroup$ – Fabich May 12 '16 at 9:12
  • $\begingroup$ @Lord of dark: Yes, integer numbers may be negative. $\endgroup$ – Gamow May 12 '16 at 9:15
13
$\begingroup$

It can be done in:

2 Questions

For our questions we use questions similar to those from Ivo Becker's answer:

$[1,-1,1,-1,...]$ and $y_n = z^{n}$ for some prime integer z

Proof:

Let $i$ be the value of the 2015 integers with the same value, and $j$ be the other. Let $a$ be the answer received from the first question. If the answer to our second question is $b$ then:

$$b = i\sum_{n=1}^{2016}z^n \pm a({z}^k)$$

So:

$$i = \frac{b \pm a({z}^k)}{\sum_{n=1}^{2016}z^n}$$

Since $i$ must be an integer, $b \pm a({z}^k)$ must be divisible by $\sum_{n=1}^{2016}z^n$. If we select $z$ to be the smallest prime that is larger than $a^2$ and also larger than 2, then this equation can have only one solution such that $1\le k\le 2016$

$\endgroup$
  • $\begingroup$ Welcome to Puzzling, and great answer! $\endgroup$ – Deusovi May 12 '16 at 15:10
  • 3
    $\begingroup$ The +- sign is unknown, which means that the difference between two candidate numerators can be as big as $2az^{2016}$, which is larger than the denominator. Is there some other reason why there can't be two integer solutions? $\endgroup$ – Gareth McCaughan May 12 '16 at 15:39
  • $\begingroup$ Wait, that's not quite right. To get different signs the candidate numerators must have different values of $k$, so actually the biggest you can make their difference is $a(z^{2016}+z^{2015})$. But that's still bigger than the denominator. $\endgroup$ – Gareth McCaughan May 12 '16 at 15:56
  • $\begingroup$ This is a mistake I believe, when I wrote the proof out the first time I used the powers 0 to 2015, with the implication that the denominator would be odd. I've edited the answer to fix this $\endgroup$ – A Smith May 12 '16 at 16:07
  • $\begingroup$ I'm actually unsure even my edit fixes this now, although I was certain when I wrote this, I'll think on it a little more $\endgroup$ – A Smith May 12 '16 at 16:09
10
$\begingroup$

It can be done in

3

questions.

If we ask as follows:

1. Have $y_1$ to $y_{2016}$ = 1
2. Have $y_1$ to $y_{1013}$ = 1 and have $y_{1014}$ to $y_{2016}$ = -1
3. Have $y_i = (n*10^5)^i$ where n is the smallest power of 10 larger than the modulus of the answers to the first two questions.

Explanation:

The first two questions establish an order of magnitude for the two numbers we are trying to find, and the third question exploits this knowledge to effectively read off each number from a very long concatenation. The third question may need the factors of 10 altering to deal with negative answers. Once I have somewhere to do some working I'll check.

I would be surprised if there isn't a more efficient answer though.

$\endgroup$
5
$\begingroup$

This is just a guess, because I'm not sure and it's just a hunch. I think it can be done in:

2 guesses

With this strategy:

First ask 1,-1,1,-1 ...
Then ask 1,2,4,8,16,32 ...
The first question will give the difference between the numbers. And I have a hunch that in combination with the answer of the second one you get two unique numbers for any of the possible numbers

I'm also not sure how to get the numbers with the results but I think it could be possible.

I could very well be wrong. I would appreciate it if someone could disprove or confirm this strategy.

$\endgroup$
  • 1
    $\begingroup$ Oh, this looks promising! $\endgroup$ – Jonathan Allan May 12 '16 at 13:15
  • 2
    $\begingroup$ If the two numbers are $a$ (once) and $b$ (2015 times), and $a$ is at position $i$, then the two answers are $c=(a-b)(-1)^{i-1}$ and $d=(a-b)2^{i-1}+b(2^n-1)$. Then $d=c(-2)^{i-1}+b(2^n-1)$. Choose $c=2^n-1$ and $d=0$, then $0=(2^n-1)[(-2)^{i-1}+b]$. There are two solutions with this same $c$ and $d$, $a=2^n-2,b=-1,i=1$ and $a=3-2^n,b=2,i=2$. $\endgroup$ – 2012rcampion May 12 '16 at 18:01
  • $\begingroup$ blast, oh well, nice idea anyway $\endgroup$ – Jonathan Allan May 13 '16 at 0:43
4
$\begingroup$

I have a solution in

4 questions

let's call $a$ the number chosen 2015 times, b the unique number and k the position of b

First step : find $a$ and $b$ (3 questions)
Try $y_1 =1$ and $y_{i>1} = 0$ so you know $x_1$
Do the same for $x_2$
If $x_1 = x_2$ then $a=x_1=x_2$ and you can find $b$ by asking $y_i=1$ because $b = \sum{x_i} - 2015*a$
If $x_1 \neq x_2$ you find $x_3$ and you solved the problem.

Second step : find $k$ (1 question)
ask for $y_i = i$, the result is $S = a*\sum{i} - k*a + k*b$ so $k = \frac{S-a*\sum{i}}{b-a}$

However I think the first part may be achieved in 2 steps only

Proof that it can't be done in 1 attempt :

Whatever your query is, you can't differentiate the case {$ a = 0, b = y_2, k = 1 $} from {$a = 0, b = y_1, k= 2$}

$\endgroup$
3
$\begingroup$

The smallest number of questions, even in the worst case is

$3$

Since

Alice really chooses $3$ integers:
$k \in [1,2016]$;
$x_k \in \Bbb I$; and
$x_j \in \Bbb I, x_j \neq x_k$

And Alice provides Bob with

results of the form
$s_n=\sum_{i=1}^{2016} y_i x_i$

From each of which he can

deduce an equation of the form
$s_n=\sum_{i=1}^{2016} y_i x_j + k y_k (x_k-x_j)$

Bob needs

$3$ equations in $3$ unknowns to solve the system and find Alice's $3$ chosen values.

$\endgroup$
  • $\begingroup$ This argument does not quite work. Example: the single equation $k+2017x_j=10000$ would allow you to determine both $k$ and $x_j$. $\endgroup$ – D.A.G. May 12 '16 at 10:40
  • $\begingroup$ @D.A.G. "In the worst case" we cannot control the output (the $10000$ in your equation): imagine Alice knows Bob's method beforehand. Also I don't know how you would construct your given equation via the questioning method! $\endgroup$ – Jonathan Allan May 12 '16 at 10:51
  • $\begingroup$ The value 10000 can be replaced by any other integers and you still can determine both $k$ and $x_j$ from the equation: $k+2017x_j=value$. $\endgroup$ – D.A.G. May 12 '16 at 11:25
  • $\begingroup$ "Also I don't know how you would construct your given equation via the questioning method!" So your argument also uses an extra fact that certain equations cannot be constructed via the questioning method. Could you please explain this extra fact that you are using? Without this fact there is a huge hole gaping in the middle of your argument. $\endgroup$ – D.A.G. May 12 '16 at 11:28
  • $\begingroup$ @D.A.G. I really did not think this was necessary and kind of just clutters the answer since the question says what Alice provides Bob, but I hope that resolves your qualms - if not I need more information as maybe I am overlooking something. $\endgroup$ – Jonathan Allan May 12 '16 at 12:00
2
$\begingroup$

This is roughly the same idea as Scoranio's answer, but with more details filled in. (And some changed; e.g., I don't think making the $y_k$ in the last query increase rapidly is actually the point. And with a proof that the number of queries achieved here is actually optimal.)

[EDITED to add: But the proof is wrong! See below.]

First of all, make Scoranio's first two queries: all-1 and half-1 half-(-1). If one number is $a$ and the other $b$ then these yield $a+2015b$ and $\pm(a-b)$ respectively; each possible choice of $\pm$ yields (by solving a pair of linear equations in $a,b$) one possible pair $(a,b)$.

(We might get lucky and find that only one of them makes $a,b$ integers, but let's not depend on that.)

OK. Now if we pick any sequence of different numbers $y_1,\dots,y_{2016}$ and query with that, we get $s=(\sum y_i)b+y_k(a-b)$ where $k$ is the index that has $a$ rather than $b$, so if we know $(a,b)$ this tells us what $k$ is: it's the one with $y_k=[s-(\sum y_i)b]/(a-b)$.

We don't quite know $(a,b)$ at this point. But if we can arrange that the values $(\sum y_i)b+y_k(a-b)$ for our two possible choices of $(a,b)$ are all different, our third query will finish the job. I don't think just making the $y$ grow rapidly as per Scoranio's answer actually helps with that, but fortunately it will turn out to be easy to accomplish.

So, suppose our first two queries yield answers $u,v$. Then we have either $(a,b)=(\frac{u+2015v}{2016},\frac{u-v}{2016})$ or the same with $v$'s sign changed; that is, $(a,b)=(\frac{u-2015v}{2016},\frac{u+v}{2016})$.

So the possible results of our third query are, in the first case,

$$\left\{\left(\sum y\right)\frac{u-v}{2016}+y_k v\right\}$$

and in the second case

$$\left\{\left(\sum y\right)\frac{u+v}{2016}-y_k v\right\}.$$

Provided the $y$ are distinct, there are no repeats within either of those; we need to arrange that we also never have

$$\left(\sum y\right)\frac{u-v}{2016}+y_i v = \left(\sum y\right)\frac{u+v}{2016}-y_j v.$$

Cancelling the $u$s, dividing out the $v$s, and rearranging a bit, this is equivalent to never having

$$y_i+y_j = \frac{\sum y}{1008}.$$

(In other words, the average of two of the $y$ never equals the average of all of the $y$.) This is actually incredibly easy to arrange: just ensure that $\sum y$ is not a multiple of 1008. For instance, let them be $1,2,3,\dots,2015,\textbf{2017}$.

I think this successfully does it in

three queries;

it remains to show that we can't do it in fewer. So, keeping the same notation as above, suppose we have the answers to queries $y$ (issued first) and $z$ (which may depend on the response to the first query). Then we know $(\sum y)b+y_k(a-b)=u$ and $(\sum z)b+z_k(a-b)=v$ for some $u,v$, and that's all we know.

Suppose Alice responds to the first query with $u=0$, and to the second with $v=(z_1\sum y-y_1\sum z)(z_2\sum y-y_2\sum z)$. Then, if my back-of-envelope algebraic scribblings are correct, we can take either $k=1$ or $k=2$ and set $(b,a-b)=(-y_k,\sum y)v/(z_k\sum y-y_k\sum z)$ which, with the choice of $v$ given above, will both be integers.

Worked example, just to sanity-check the above: suppose the first query is all-1 and the second is $1,2,3,\dots,2016$. Then we have $\sum y=2016$, $\sum z=2033136$, $z_1\sum y-y_1\sum z=-2031120$, $z_2\sum y-y_2\sum z=-2029104$; so Alice's responses are $u=0$ and $v=\Delta_1\Delta_2$ where the $\Delta$s are those two big negative numbers. Taking $k=1$ gives us $(b,a-b)=(-1,2016)\Delta_2$ hence $a=2015\Delta_2,b=-\Delta_2$. Does that work out? The first query gives $a+2015b=(2015-2015)\Delta_2=0$ as required; the second gives $a+(2+3+\cdots+2016)b=(2015-(2+3+\cdots+2016))\Delta_2$ and you may readily check that that factor on the RHS is indeed $\Delta_1$. And likewise if we take $k=2$ and $(b,a-b)=(-1,-2016)\Delta_1$. So indeed Bob can't determine $a,b,k$ from the results of these two queries, and the construction above works no matter what two queries Bob chooses. Therefore

at least three queries are needed in the worst case, and therefore 3 is the required number.

[EDITED to add:]

There is a mistake in the proof above, which you will find if you carefully attempt to use it to refute the Ivo Beckers / A Smith answer that claims to solve the problem with two queries. If the first query, like the one they use, has the property that when it returns zero all the numbers have to be equal, then the fact that we can't determine $k$ in that case is not a problem! If the Beckers/Smith answer is correct (I'm not sure whether it is; there's something that looks like a hole but it seems like a small hole and may be patchable) then obviously my proof must be unfixable.

... OK, I think the hole in the Beckers/Smith solution is patchable and my proof therefore unfixable; see comments to A Smith's answer.

$\endgroup$
0
$\begingroup$

If there was a restriction on what the largest integer could be, then it could be done with:

1 query

In fact, this technique could be used to determine all 2016 integers, regardless of the uniqueness of the integers. They could be all different and this technique would still work.

But this largest integer restriction isn't part of the question, so we would have to first find the largest integer (or something similar) with an additional:

1 query

Bringing the total queries to:

2 queries

They would be these:

The first query would be all ones. The answer we receive would be a ceiling. Call it m. Query two would be 1, m, m^2, m^3, m^4... m^2016. Call this n. Yes, this would become very large. Then x1 is n mod m. x2 is floor(n/m) mod m. x3 is floor(n/m^2) mod m. x4 is floor(n/m^3) mod m. etc.

Or something like that.

Oh shoot. I just realized that the integers could be negative, so this technique wouldn't work, because

you couldn't find the maximum (m). Sorry. I'll post it anyway in case anyone finds it interesting.

$\endgroup$
0
$\begingroup$

The problem has 3 variables namely, the 2015 same integers, the one unique integer, and the position of the unique integer (k).

So by basic math we can say that we would require minimum 3 equations to solve these three values.

Hence the answer to the puzzle is 3. Bob requires to ask 3 questions that (even in the worst case) allow Bob to determine the values of all 2016 integers.

PS. The puzzle does not talk about the approach or the specific questions that Bob needs to ask, this is like a trick puzzle, where you need to answer only what you are asked for, not worry about anything further.

$\endgroup$
-1
$\begingroup$

It can be done in two questions.

First question we give the set $1,1,1,1,1,1,....$. This will give us the sum of the integers, say $z$.

Then we give the set $1,z^2,z^4,z^6,z^8,.....$. The answer, when written in the base-$z$ number system, will directly give us all the integers.

We can also use a power of ten greater than $z^2$ for convenience.

$\endgroup$
  • $\begingroup$ It does not work because $x_i$ can be $<0$ $\endgroup$ – Fabich May 17 '16 at 16:30
  • $\begingroup$ @Lord Is it ok.now? $\endgroup$ – ghosts_in_the_code May 17 '16 at 16:34
  • $\begingroup$ you can have z=0 $\endgroup$ – Fabich May 17 '16 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.