11
$\begingroup$

Alice chose a positive integer $n$ and Bob tries to guess it.

In every turn, Bob will guess an integer $x$ $(x>0)$:

  1. If $x$ equals $n$, then Alice tells Bob that he found it, and the game ends.

  2. If not, then Alice tells Bob whether $x+n$ is prime or not.

How to play this game optimally (that is to say, to find the number in the fewest turns)?

You can assume $0< n\le100$ (or any reasonable bound).

PS: This game is invented by me.

$\endgroup$
  • 1
    $\begingroup$ Is it allowed to propose $x > 100$ ? $\endgroup$ – Arnaud May 9 '13 at 16:47
  • $\begingroup$ It's allowed, but if you think it's so hard to solve this question with that condition, you can ignore that. $\endgroup$ – Sayakiss May 9 '13 at 16:50
  • $\begingroup$ Always good to specify what type of number you are talking about upfront. "Number" is a general term that could allow fractions, etc. It's clear from later that you mean non-negative integers, but it is better to state that up front to make reading easier. $\endgroup$ – Thomas Andrews May 9 '13 at 16:50
  • $\begingroup$ A variant which is perhaps closer in spirit to the classic high/low number guessing game would advise whether guess $x = n$, or if not, whether $|x - n|$ is prime or not. I suspect this version would be easier (fewer worst case guesses needed) since slightly higher prime densities can be achieved. Rather than the 26 primes in [2,101] we count 30 primes (both positive and negative) in [-49,+49] (and note that this latter interval could be shrunk). $\endgroup$ – hardmath May 12 '13 at 14:50
9
$\begingroup$

It's not possible to solve the game in all cases with fewer than 7 guesses, because after 6 guesses you have at least 95 unguessed numbers and 6 bits of information and $2^6<94.$

But actually 7 is not achievable, since at most 26 primes can appear in any given block of 101. Thus the first guess, in the worst case, will have at least 74 remaining numbers, and so at least 8 guesses are required since $2^6<68$.

The goal at each step is to find numbers that split the remaining numbers into two sets of roughly equal size. Here are the beginnings of a strategy for 9. Ask about 3. If the number is 3 you're done; if n + 3 is prime it should not be hard to guess the number in 8 more tries.

Otherwise 74 numbers remain: 1, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23, 24, 25, 27, 29, 30, 31, 32, 33, 35, 36, 37, 39, 41, 42, 43, 45, 46, 47, 48, 49, 51, 52, 53, 54, 55, 57, 59, 60, 61, 62, 63, 65, 66, 67, 69, 71, 72, 73, 74, 75, 77, 78, 79, 81, 82, 83, 84, 85, 87, 88, 89, 90, 91, 92, 93, 95, 96, 97, 99. Now ask about 10. If n+10 is prime it should be easy to find the number in 7 more tries.

Otherwise 50 numbers remain: 5, 6, 11, 12, 15, 17, 18, 22, 23, 24, 25, 29, 30, 32, 35, 36, 39, 41, 42, 45, 46, 47, 48, 52, 53, 54, 55, 59, 60, 62, 65, 66, 67, 71, 72, 74, 75, 77, 78, 81, 82, 83, 84, 85, 88, 89, 90, 92, 95, 96. Now ask about 12. If n is 12 you're done; if n+12 is prime you have 6 tries to find 16 numbers.

Now 33 numbers remain: 6, 15, 18, 22, 23, 24, 30, 32, 36, 39, 42, 45, 46, 48, 52, 53, 54, 60, 62, 65, 66, 72, 74, 75, 78, 81, 82, 83, 84, 88, 90, 92, 96. Now ask about 1. If n+1 is prime there are 15 possibilities and you have 5 tries.

Now you have just 18: 15, 23, 24, 32, 39, 45, 48, 53, 54, 62, 65, 74, 75, 81, 83, 84, 90, 92. This is a bit tricky, but guess 1139 (or 1148) to split the remainder into two sets of 9.

Either way you go at least one of the sets has 5 members (4 would be possible only if you picked one of the 18).

$\endgroup$
  • $\begingroup$ I like your solution quite a lot. Hopefully, it will be possible to easily find a set of magic numbers to use here in some sort of binary tree :p $\endgroup$ – Mohamad Ali Baydoun May 9 '13 at 19:05
  • $\begingroup$ @Magtheridon96: It's a bit of a pain, but the general principle of trying to maximize information at each guess works decently well. I think keeping track of all possible best guesses, plus those guesses which are within 1 of the best, would probably suffice to find the best overall. But I haven't coded that. $\endgroup$ – Charles May 9 '13 at 20:40
5
$\begingroup$

I have a pretty cool but probably impractical solution.

Consider this table of primes from $1$ to $110$:

$$ \begin{matrix} 2 & 3 & 5 & 7 & 11 \\ 13 & 17 & 19 & 23 & 29 \\ 31 & 37 & 41 & 43 & 47 \\ 53 & 59 & 61 & 67 & 71 \\ 73 & 79 & 83 & 89 & 97 \\ 101 & 103 & 107 & 109 \\ \end{matrix} $$

Notice the differences between all the primes. That table would look like this:

$$ \begin{matrix} 2 & 1 & 2 & 2 & 4 \\ 2 & 4 & 2 & 4 & 6 \\ 2 & 6 & 4 & 2 & 4 \\ 6 & 6 & 2 & 6 & 4 \\ 2 & 6 & 4 & 6 & 8 \\ 4 & 2 & 4 & 2 \\ \end{matrix} $$

Let's look at the combinations of 6 differences in order. They're ordered from left to right and up to down by value as if the sequences represented digits of a 6-digit number:

$$1,2,2,4,2,4 \ \ \ \ \ \ \ \ \ \ 2,1,2,2,4,2 \ \ \ \ \ \ \ \ \ \ 2,2,4,2,4,2$$ $$2,4,2,4,2,4 \ \ \ \ \ \ \ \ \ \ 2,4,2,4,6,2 \ \ \ \ \ \ \ \ \ \ 2,4,6,2,6,4$$ $$2,4,6,6,2,6 \ \ \ \ \ \ \ \ \ \ 2,6,4,2,4,6 \ \ \ \ \ \ \ \ \ \ 2,6,4,2,6,4$$ $$2,6,4,6,8,4 \ \ \ \ \ \ \ \ \ \ 4,2,4,2,4,6 \ \ \ \ \ \ \ \ \ \ 4,2,4,6,2,6$$ $$4,2,4,6,6,2 \ \ \ \ \ \ \ \ \ \ 4,2,6,4,6,8 \ \ \ \ \ \ \ \ \ \ 4,6,2,6,4,2$$ $$4,6,6,2,6,4 \ \ \ \ \ \ \ \ \ \ 4,6,8,4,2,4 \ \ \ \ \ \ \ \ \ \ 6,2,6,4,2,4$$ $$6,2,6,4,2,6 \ \ \ \ \ \ \ \ \ \ 6,4,2,4,6,6 \ \ \ \ \ \ \ \ \ \ 6,4,2,6,4,6$$ $$6,4,6,8,4,2 \ \ \ \ \ \ \ \ \ \ 6,6,2,6,4,2 \ \ \ \ \ \ \ \ \ \ 6,8,4,2,4,2$$

Notice that no two sequences are equal in the above list

Start out by iterating over values of $x$ in $[0,7]$ incrementally until you hit the first prime number. Let this value of $x$ be denoted as $k$.

The above step requires $8$ guesses in the worst case

You have to use new values for $x$ equal to $k + o$ where $o$ is an offset that starts at $1$ and changes based on what's prime and what's not.

If $k + 1$ is prime, you can stop. $n = 2$.

Else, try $k + 2$ and if that doesn't work, $k + 4$, then $k + 6$.

If for instance, $k + 4$ works, you would then try $k + 4 + 2$. If that's prime too, then continue with these combinations in the same manner:

$$4,2,4,2,4,6$$ $$4,2,4,6,2,6$$ $$4,2,4,6,6,2$$ $$4,2,6,4,6,8$$

Using the above method, you derive the value of the prime $n + k$. $k$ is known, so you can immediately deduce the value of $n$.

In fact, we can optimize that above table of differences to remove the unneeded trials and combine a few of them:

$$ \begin{matrix} 1 & 2,1 & 2,2 \\ 2,4,2,4,2 & 2,4,2,4,6 & 2,4,6,2 \\ 2,4,6,6 & 2,6,4,2,4 & 2,6,4,2,6 \\ 2,6,4,6 & 4,2,4,2 & 4,2,4,6,2 \\ 4,2,4,6,6 & 4,2,6 & 4,6,2 \\ 4,6,6 & 4,6,8 & 6,2,6,4,2,4 \\ 6,2,6,4,2,6 & 6,4,2,4 & 6,4,2,6 \\ 6,4,6 & 6,6 & 6,8 \\ \end{matrix} $$

The magic numbers to add to $k$ when guessing would be:

$$ \begin{matrix} 1 & 2,3 & 2,4 \\ 2,6,8,12,14 & 2,6,8,12,18 & 2,6,12,14 \\ 2,6,12,18 & 2,8,12,14,18 & 2,8,12,14,20 \\ 2,8,12,18 & 4,6,10,12 & 4,6,10,16,18 \\ 4,6,10,16,22 & 4,6,12 & 4,10,12 \\ 4,10,16 & 4,10,18 & 6,8,14,18,20,24 \\ 6,8,14,18,20,26 & 6,10,12,16 & 6,10,12,18 \\ 6,10,16 & 6,12 & 6,14 \\ \end{matrix} $$

It's imperative that the trials are done in order from left to right and top to bottom in this table, else, you will get false information. An example of one optimization is to avoid guessing when the only possible combination to continue with is 1 because we know that $n + k$ is prime.

An example:

  • You tested $k + 4$, $k + 10$, and you're testing for $k + 12$
  • You're now testing for $k + 16$
  • You're now testing for $k + 18$

That last step is redundant. If $k + 16$ is composite, you can skip the $k + 18$ step because you know it will be prime.

I hope this is clear enough.

$\endgroup$
  • $\begingroup$ Can you perhaps explicitly mention in your answer how many guesses will be needed at most with your strategy? $\endgroup$ – Keep these mind May 9 '13 at 18:00
  • $\begingroup$ Pretty nice solution, but it may not be the optimist. $\endgroup$ – Sayakiss May 9 '13 at 18:00
  • $\begingroup$ I confused myself like twice while writing this. I'll work it out and see if I can find the worst case too. It should be about 11-13 guesses in the worst case I think $\endgroup$ – Mohamad Ali Baydoun May 9 '13 at 18:01
  • $\begingroup$ This solution looks a lot nicer than mine (+1), but I'm pretty sure I can get it down to 9 guesses in the worst case. I don't know if 8 is possible but it should be close. 7 is impossible. $\endgroup$ – Charles May 9 '13 at 18:23
  • $\begingroup$ I'm trying to refine it by optimizing the trials. It's pretty hard to do because I'm working with sequences that look alike in plain text :P $\endgroup$ – Mohamad Ali Baydoun May 9 '13 at 18:27
2
$\begingroup$

To get a somewhat efficient algorithm, we can first compute for several choices of $x$ what the answers of Alice would be, for each choice of $n$ between $1$ and $100$.

As noted by Charles, no matter what $x$ is, for at most $26$ of the $100$ possible choices of $n$ will the answer be "Yes, $n + x$ is prime." This maximum information rate is achieved only by choosing $x = 1$, so we will want to ask this question as our first question. There are five choices of $x$ for which there are $25$ numbers where the answer is "Yes", which are $2, 3, 4, 9, 10$. For simplicity, let us assume that we first query the first $4$ numbers with such a high "information rate": $$x \in \{1, 2, 3, 4\}.$$ Now, for each choice of $n$, we can compute what the answers would have been. For the numbers $n = 1, 2, 3, 4$ we would get a match and be done, while for the other $96$ numbers there are only $7$ possible sequences of answers. Along with the choices of $n$ that lead to these answers, these sequences are: $$\begin{align} NNNN &: \{23, 24, 31, 32, 47, 48, 53, 54, 61, 62, 73, 74, 83, 84, 89, 90, 91, 92\} \\ NNNY &: \{7, 13, 19, 25, 33, 37, 43, 49, 55, 63, 67, 75, 79, 85, 93, 97\} \\ NNYN &: \{8, 14, 20, 26, 34, 38, 44, 50, 56, 64, 68, 76, 80, 86, 94, 98\} \\ NYNN &: \{5, 11, 17, 21, 29, 35, 41, 45, 51, 59, 65, 71, 77, 81, 87, 95\} \\ YNNN &: \{6, 12, 18, 22, 30, 36, 42, 46, 52, 60, 66, 72, 78, 82, 88, 96\} \\ NYNY &: \{9, 15, 27, 39, 57, 69, 99\} \\ YNYN &: \{10, 16, 28, 40, 58, 70, 100\} \end{align}$$ So with $4$ questions, we narrow down the search space to at most $18$ numbers. For each group, we may be able to choose the follow-up questions such that in total, we may need only about $10$ questions or so, but this will be very complicated. Of course, we could query each of the at most $18$ numbers in each of the groups, for a total of at most $4 + 18 = 22$ questions, but that would obviously not be optimal.

A somewhat simpler strategy would be to ask more questions in the initial stage, such as first querying $$x \in \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}.$$ In this case, there are $48$ possible strings of answers (and $10$ exact matches), and each group contains $3$ or fewer values of $n$ that lead to these answers. So once we know the answers to these $10$ queries, we are able to narrow down the search space to at most $3$ numbers, and with at most $2$ questions we may then be able to determine the correct value of $n$. So this would lead to a worst-case complexity of $10 + 2 = 12$ questions.

$\endgroup$

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.