Find The Diamond!

Logic Level 3

There is a diamond hidden on an $N\times N$ grid at location $(x_D,y_D)$ , where $x_D$ and $y_D$ are integers .

Every guess, you suggest a pair of coordinates ( $x_G$ , $y_G$ ). And, if you get it wrong you are given a hint as to where to go to continue looking. You are told either NW, N, NE, E, SE, S, SW, or W:

W implies $x_D < x_G$ and $y_D = y_G$
NW implies $x_D < x_G$ and $y_D > y_G$
etc.

If you can get the diamond with 10 guesses or less (i.e. at most 9 wrong guesses and one right one), you get to keep the diamond. What is the largest $N$ for which you can guarantee success?

The answer is 1023.

2 solutions

Geoff Pilling
Jun 19, 2016

Relevant wiki: Information Compression

If you are allowed $2$ guesses, clearly you guess in the middle first, and then you know exactly where it is if $N$ is $3$ . Similarly, if you are allowed $3$ guesses you can guess first in the middle of a $7x7$ grid, and whatever answer you get you'll be left with at most a $3x3$ grid, which you know you can solve with $2$ guesses.

Generalizing this, if you have $n$ guesses, then you can be guaranteed success if $N = 2^n - 1$

For $n=10$ , this is $N = \boxed{1023}$

For 2 guesses (n=2) we can have N=5 starting in the middle, for 3 guesses the maximum N is 7 as you mentioned. But your given formula is unfortunately wrong since N=2*n+1. This means for n=10 we get N= $\boxed{21}$ .

Andreas Wendler - 4 years, 12 months ago

I think you haven't quite got the right formula...

For 2 guesses, you can't guarantee success with a 5x5 grid, since you will only get 8 pieces of information after your first guess, and you will still have 24 spots to choose from.

For 2 guesses, N=3, since you guess in the middle of a 3x3 matrix. For 3 guesses, N=7 as you say, and for 4 guesses, then, you want to divide the grid into four 7x7 grids (which you can solve in 3 moves), two 7x1 segments and two 1x7 segment, (above, below, and to the left and right of your guess. So, you can handle 4 guesses with a 15x15 grid. If you continue this logic, I think you'll find that indeed the formula is N = 2^n + 1. Lemme think about if there is a way I can explain it clearer...

Geoff Pilling - 4 years, 12 months ago

My starting point is always the middle (N=odd) or nearest middle (N=even) of the grid. Then I assume worst case meaning the diamond is located at a corner.

In this sense I can not realize how to reach the diamond for a 15x15 grid within 4 guesses as you said. But for a 9x9 grid this will work on my opinion.

Question: Does a hint always correct the position to one neighbour point of the grid? Or haven't I understood something wrong?

Andreas Wendler - 4 years, 12 months ago

@Andreas Wendler – Yes, the middle is always the best starting point... I agree.

For a 15x15 grid, and 4 guesses, suppose you start in the middle (8,8) and the diamond is in the corner (1,1). i.e. Your guess is (8,8), and the answer is "NW". Then you guess again (in the middle of the remaining 7x7 grid in the upper left corner, or (4,4). Again the answer is "NW". Your third guess is again in the middle of the remaining 3x3 set of options or (2,2). Again the answer is "NW". So, your fourth, and final guess is (1,1) and you have found the diamond!

Make sense?

The hint only tells you where the diamond is relative to your guess. i.e. Its "N, S, E, or W" if you are already on the right column or row, and its "NW", "NE", "SW", or "SE" otherwise.

Geoff Pilling - 4 years, 12 months ago

@Geoff Pilling – Yes it's alright. Unfortunately I had problems in understanding your task. Thanks!

Andreas Wendler - 4 years, 12 months ago

Did it similarily, except I didn't find out the explicit formula and just used the implicit formula 10 times to figure it out: $N_n = 2×N_{n-1} + 1, N_1 = 1$

Kai Ott - 4 years, 12 months ago

I got confused when it said every turn... that means you can only travel along one axis in my mind and you are forced to guess on every turn.

Jerry McKenzie - 4 years, 11 months ago

Good point... Lemme update the verbiage!

Geoff Pilling - 4 years, 11 months ago

Hi Geoff. Here's a variation you might consider ... In your problem any direction between e.g. North and West is called NW, but what if instead any direction between NW and NE is called N, and so on?

Peter Byers - 4 years, 4 months ago

Interesting... lemme think about that one...

Geoff Pilling - 4 years, 4 months ago

It seems like this is a little worse case, since the new definition isn't ideally set up for a NxN grid, but rather a diamond shape... However, if we optimize it for a diamond, and then cut off the stuff that doesn't nicely fit into a square, I get that:

$N = 2^{n-1} + 1$ (where $n$ is the number of guesses you are allowed)

So, $N = 513$ for $n = 10$ .

I'm not sure if we can do better than this, though... Thoughts?

Geoff Pilling - 4 years, 4 months ago

In my opinion, If we start guessing from the center,

Case 1: Total Guesses Allowed = 1 So Single Grig Location Possible (x,y) = (1,1) Hence 3^0 is size of N

Case 1: Total Guesses Allowed = 2 So 9 Grig Locations Possible (x,y) = (3,3) Hence 3^1 is size of N

Case 1: Total Guesses Allowed = 3 27 Grig Locations Possible (x,y) = (9,9) Hence 3^2 is size of N

And so on.

Description of solution is given in the following location.

https://drive.google.com/open?id=1FjABcJSOAssD5ok6xlgwfgy2Q8djS2d4

Please correct me if I am wrong.

Abhra Gupta - 1 year, 3 months ago

Milly Choochoo
Aug 21, 2017

The two directions are independent, so this problem can be reduced to one dimension, i.e. with only a line of $N$ boxes. But this is game is precisely a search through comparisons, so the binary search algorithm will give the best result, $10=\textrm{floor}(\log_2 N)+1\implies \boxed{N=1023}$

Find The Diamond!

The answer is 1023.

2 solutions

0 pending reports