Year 12s: what will be the first way you research your future options? >>

D1 binary search problem using 2d and 3d grids

My answers to this question are out so I think I am doing this wrong.

I get the first part correct but next part my answer is out or different to book answer.

Question.

In a game of battleships a player chooses a square on a grid to represent a battleship. A second player tries to find that square by making a sequence of guesses. In response to an incorrect guess, the second player is told either whether the battleship is to the east or west of the guess or whether it is to the north or south.

The game is played on a 15 x 20 grid and a first guess has been made at square K8, as indicated in diagram.

diagram arranged vertical axix numbered 1-15, 15 is northernmost. Horizontal axis is A - T with T eastmost.

The information provided is that the battleship is to the south of the guess.

(a) In a binary search the set of possibilities is, as nearly a possible, halved at each iteration. Given the guess and the information, what would be the next guess?

I guessed K4 - which was correct.

(b) If the information following that next guess is that the battleship is to he north of the guess what would the next guess in a binary search?

I gueesed K6. which was also correct.

(c) What difficulty will be encountered when the information is that the battleship is to the west?

There are 10 cells west of K - A to J. So difficulty is there is no middle value so select eg either E or F. Book agreed halving issue was difficulty.

It is (d) onwards where my answers differ from the book.

(d) Starting a game afresh, what is the minimum no. of guesses that will be needed to be sure of locating the battleship?

Total area = 15 x 20 = 300

So I thought that because binary search halves the possibilities each time 300/2 = 150. 150/2 = 75, etc. ie you could say 2^x = 300 - so take log to the base 2 of 300.

log2(300) = 8.22 so would need 9 guesses.

But book says 7 guesses (8 if answer is counted as a guess).

But surely it is 9? No? Can someone explain why I am 1 out.

Then my other error :-

(iii) Spaceships is similar to battleships but is played in a three-dimensional grid.
Playing a binary search strategy on a 15 x 15 x 15 grid, how many guesses will be needed to guarantee locating the spaceship?

15^3 = 3375

log2(3375) = 11.72 so would need up to 12 guesses.

But book answer says 9 guesses (10 if the answer is counted as a guess).

Why I am I even more out this time?

Is my method of using area for battleships or volume for spaceships idea wrong? What am I doing wrong here?

Reply 1

ghostwalker

Original post by acomber

...

I don't know what is taught in D1, however a couple of comments:

Considering the battleship in 2D.

The dimensions are independent, in that restricting the search in any one direction has no effect on what is known in the other direction.

Searching through 15 items takes

\lfloor\log_215\rfloor=3

. We don't need to round up, as we know the target is in there.

Then through 20 times is

\lfloor\log_220\rfloor=4

.

Hence for a 15x20 grid, it takes 7 goes.

Because of the use of the floor function, you cannot just multiply 15 by 20 and then take logs.

3D is similar.