Author |
Topic: Minimum number of shots to kill the rat (Read 9922 times) |
|
davkrs
Newbie
Posts: 6
|
 |
Minimum number of shots to kill the rat
« on: Aug 27th, 2013, 5:57pm » |
 Quote  Modify
|
I came across this problem, and thought would share here for a good discussion
You have an array of size n. And there is rat in one of the positions in the array.
You have a laser gun which lets you shoot at any index in the array at a given instant. You can move to any index in the array to shoot. However, you can shoot only at one index at any given time
Rat gets to move either left or right (randomly, but if there is only one option available, e.g if rat is in right most index of array, it will move to left) by one position in the array, after you shoot the laser gun. It also moves when you move the laser gun.
How many shots are required to make sure that rat is killed.
|
| « Last Edit: Aug 30th, 2013, 3:57pm by davkrs » |
 IP Logged |
|
|
|
allonhadaya
Newbie
Posts: 3
|
|
Re: Minimum number of shots to kill the rat
« Reply #1 on: Sep 3rd, 2013, 12:48am » |
Quote Modify
|
Nice puzzle! 
I worked out n 1 .. 4 by hand along with alternate solutions for n = 2 and n = 4. They demonstrate some symmetry.
n 1 = 1
0
n 2 = 2
0,0
1,1
n 3 = 2
1,1
n 4 = 5
1,1,2,2,1
2,2,1,1,2
1, 2, 2, 5
I'll sleep on it, but my intuition says something about recursive trees and parity perhaps.
|
| « Last Edit: Sep 3rd, 2013, 12:52am by allonhadaya » |
IP Logged |
|
|
|
jamez
Newbie
Posts: 1
|
|
Re: Minimum number of shots to kill the rat
« Reply #2 on: Sep 3rd, 2013, 12:56am » |
Quote Modify
|
Assuming the rat can change direction at will - there is no solution for n>3.
if n==3 you can just hit the middle index twice to catch if the rat is on the side.
if n==4 you can no longer corner the rat.
Assuming the direction can't change, you can continually hit the second index in from either end, so that catches the rat in that spot and the one on that end in 2 moves.
every other rat after that adds another 2 steps because there could be a rat starting right next to where you are firing, moving in the opposite direction, having to get to the other wall before coming back.
formula for n>3
2(n-2)
formula for n=<3
n
|
|
IP Logged |
|
|
|
allonhadaya
Newbie
Posts: 3
|
|
Re: Minimum number of shots to kill the rat
« Reply #3 on: Sep 3rd, 2013, 1:31am » |
Quote Modify
|
I beg to differ...
for the case of n = 3:
[ r . . ] - 1
[ . r . ] - 1
[ . r . ] - 1
[ . . r ] - 1
[ . r . ] - 1
2 guesses are sufficient: 2 /= 3
and for 4:
[ r . . . ] - 1
[ . r . . ] - 1
[ . r . . ] - 1
[ . . r . ] - 1
[ . r . . ] - 1
[ . . r . ] - 1
[ . . . r ] - 1
[ . . r . ] - 2
[ . . . r ] - 1
[ . . r . ] - 1
[ . . . r ] - 2
[ . . r . ] - 2
[ . . . r ] - 1
[ . . r . ] - 1
[ . r . . ] - 2
[ . . r . ] - 2
[ . . . r ] - 1
[ . . r . ] - 1
[ . r . . ] - 2
[ r . . . ] - 2
[ . r . . ] - 1
5 guesses are needed: 5 /= 2(4 - 2)
It's a tough problem! 
|
| « Last Edit: Sep 3rd, 2013, 1:35am by allonhadaya » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Minimum number of shots to kill the rat
« Reply #4 on: Sep 3rd, 2013, 9:14am » |
Quote Modify
|
4 is enough for 4.
Shoot at 2, then 3 (the rat is now dead if it started at an even position), then 3, and 2
[e]missed the part where aiming elsewhere lets the rat make an extra move[/e]
|
| « Last Edit: Sep 3rd, 2013, 11:09pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
allonhadaya
Newbie
Posts: 3
|
|
Re: Minimum number of shots to kill the rat
« Reply #5 on: Sep 3rd, 2013, 9:30am » |
Quote Modify
|
Nice, you're right. I'll have to think about it some more.
|
|
IP Logged |
|
|
|
Fellius
Newbie
Posts: 1
|
|
Re: Minimum number of shots to kill the rat
« Reply #6 on: Sep 3rd, 2013, 2:11pm » |
Quote Modify
|
How does 2-3-3-2 work?
If we have
O@OOR where the O after the @ is where the cursor is then:
1. After firing at 2 (assuming you start there):
O@ORO
2. After moving to 3:
OR@OO
3. After firing at 3 for the first time:
RO@OO
4. After firing at 3 for the second time:
OR@OO
5. After moving to 2:
O@ORO
6. After firing at two for the second time:
O@OOR
Unless I made a mistake somewhere it seems that strategy wouldn't work for catching a very lucky rat.
If we formalize the system a bit, where O represents somewhere the rat could be, X where the rat cannot be, and @ before the square where the cursor is then it would seem this problem is impossible.
We can start with:
@OOOO
Or:
O@OOO
(The two cases on the other end will be symmetric)
Firing an unlimited amount of times from @OOOO will produce @XOOO. If you move to the second square, then you will have O@OOO (the other starting position), since the rat could've been on square 2 and moved to the left as you moved to the right. From here, you can fire >=2 times to achieve X@XOO.
Clearly, you must move. Moving to the 1st square again produces @XOOO, which we have already seen. Moving to the end will create XOO@O, and firing at the end will simply produce OOO@X (symmetric to @XOOO)
If we attempt to move to the third square from X@XOO, we end up with XO@OO. Firing at the third square produces OO@XO, which is symmetric to O@XOO. Since all reachable states have been enumerated and none of them contain XXXX (which means the rat cannot be anywhere and must have been shot), n=4 is not possible.
Since an array of n=4 is embedded in any n>4, and the rat can simply choose to act as if it must walk on an array of size 4 by sheer random luck, you need an infinite number of shots for n>=4.
n=1 is obviously 1, n=2 is 2, n=3 is 2, and n>=4 is infinite.
|
|
IP Logged |
|
|
|
pmc
Newbie
Posts: 1
|
|
Re: Minimum number of shots to kill the rat
« Reply #7 on: Sep 3rd, 2013, 8:44pm » |
Quote Modify
|
So I might be misunderstanding some part of the problem, but I think many people may be over thinking the solution.
The rat can only move left or right. It cannot stay in the same position. Also, we know the location of the rat in the array.
So let's set up the first n cases (I picked n=5).
n = 1, s (shots) = 1. Obviously. (The rat can't move.)
n = 2, s = 1. Obviously. (The rat can only move to the one open space.)
n = 3, s = 2. [ ][x][ ] is the only case where s > 1. (Edge cases are always = 1, because we know where the rat will move.) It can go left or right, if we miss then we know that the rat will have to move back to the center.
n = 4, s = 2. [ ][x][ ][ ] and the mirror [ ][ ][x][ ] are also s = 2. We know that the rat can move left or right, so we would want to guess on the side of the longer side so that in the chance that we would miss, we can ensure that we make less guesses as we approach the rat one index at a time.
e.g. [ ][x][ ][ ] -> [x][ ][o][ ] -> [ ][xo][ ][ ], x = rat, o = laser
n = 5, s = 3. If the rat is on the ends of the array, s = 1. If the rat is on the second to last index of the array (like the example shown above), we know that s = 2. The next case to consider is if the rat is in the middle of the array. To guarantee that we kill the rat, we have to consider the worst possible case scenario, meaning that all of our intelligent guesses are by chance wrong. It should then be clear to see why s = 3.
i.e. [ ][ ][x][ ][ ] -> [ ][x][ ][o][ ] -> [x][ ][o][ ][ ] -> [ ][xo][ ][ ][ ]
So a quick look at the numbers shows that s = (n+1)/2 with integer division. Let's analyze if the answer makes sense. Obviously it is possible for us to hit the rat on the first guess, but because the problem asks us the 'guaranteed' number of guesses until the rat is killed, we have to assume that the rat the luckiest of all rats. Because we are only guaranteed predictable movement from the rat when it reaches the end (because it can only move in one direction from that point), we have to slowly drive it to the end of the array. That is why we have to make (n+1)/2 guesses, because we start from the middle (considering arrays also with an even number of indices) and slowly move towards the end.
I hope that makes sense, but moreover is right.
|
| « Last Edit: Sep 3rd, 2013, 8:45pm by pmc » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum number of shots to kill the rat
« Reply #8 on: Sep 3rd, 2013, 10:26pm » |
Quote Modify
|
on Sep 3rd, 2013, 2:11pm, Fellius wrote:How does 2-3-3-2 work?
If we have
O@OOR where the O after the @ is where the cursor is then:
1. After firing at 2 (assuming you start there):
O@ORO
2. After moving to 3:
OR@OO
3. After firing at 3 for the first time:
RO@OO |
|
Sorry, it seems I have misread the question and didn't notice that re-aiming the laser also counts as a move. (There's a very similar puzzle floating around without that additional constraint.)
on Sep 3rd, 2013, 8:44pm, pmc wrote:| The rat can only move left or right. It cannot stay in the same position. Also, we know the location of the rat in the array. |
|
I don't think we should assume to know the position of the rat. That makes it rather too easy.
|
| « Last Edit: Sep 3rd, 2013, 10:27pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
davkrs
Newbie
Posts: 6
|
|
Re: Minimum number of shots to kill the rat
« Reply #9 on: Sep 5th, 2013, 2:41pm » |
Quote Modify
|
on Sep 3rd, 2013, 10:26pm, towr wrote:| I don't think we should assume to know the position of the rat. That makes it rather too easy. |
|
Exactly, we should not assume to know the position of the rate.
If we knew the position, we can kill the rat in constant steps
|
|
IP Logged |
|
|
|
davkrs
Newbie
Posts: 6
|
|
Re: Minimum number of shots to kill the rat
« Reply #10 on: Sep 5th, 2013, 2:42pm » |
Quote Modify
|
on Sep 3rd, 2013, 10:26pm, towr wrote:(There's a very similar puzzle floating around without that additional constraint.)
|
|
Can you post the link to that other puzzle.
|
|
IP Logged |
|
|
|
davkrs
Newbie
Posts: 6
|
|
Re: Minimum number of shots to kill the rat
« Reply #12 on: Sep 10th, 2013, 2:34pm » |
Quote Modify
|
Ok, to make things easier, what is the solution when the additional constraint is removed.
Additional constraint being removed: Rat will not move when laser gun is repositioned, it moves only after you shoot the gun.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print