Getting Lost V2.0
4 friends, Aaron, Bobby, Cathy, and Danny, decide to go on an adventure in the famous 'dark forest'. They pack their bags, and take off. A few days later, they are completely lost in the forest. To make matters worse, they are each in a different part of the forest. They know they are each in a different section of the forest, and the forest has 36 sections. The forest has 6 rows and columns of sections, each numbered with a unique number from 1-36. Aaron, Bobby, and Cathy all has sensing and communication devices, but Danny does not. Aaron, Bobby, and Cathy decide to try and save Danny. Each activate their sensing device, and they find that no person is in the same row or column in the forest. Then, all the sensing devices shut off, and there is no way to turn them on again.
Question: How many squares do Aaron, Bobby and Cathy need to check in order for them to guarantee they know which section of the forest Danny is in (without using the sensing device again)?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
First, draw a 6x6 grid made out of 36 unit squares.
Choose any 3 points (To represent Aaron, Bobby, and Cathy) that are not on the same row or column. Cross out all the squares in the row or column they
are in.
Then count the remaining number of squares. Danny has to be in one of those sections, and the worst case scenario is that Aaron, Bobby and Cathy check
the squares Danny is not in.
Since there are 9 squares left after step 2, they need to check 8 squares in order to guarantee that they find Danny. (Since the last square has to be the one Danny is in)
Why is it true for the general case?
Suppose we first give Aaron a random section. If we set him in any of the 36 squares, then there will be a total of 11 squares in the same row or column as
Aaron. Thus, we only have 36-11=25 ways to put the next person.
We then put Bobby on another available square. After we set him on a square, there will only be 25-9=16 squares left.
We then put Cathy on another available square. After we set him on a square, there will only be 16-7=9 squares left.
So Danny has to be in one of the last 9 squares.
Since there are 9 squares left, they need to check 8 squares in order to guarantee that they find Danny.