wu :: forums « wu :: forums - Minimum number of shots to kill the rat » Welcome, Guest. Please Login or Register. Feb 27th, 2024, 3:02am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Grimbal, Eigenray, ThudnBlunder, Icarus, SMQ, william wu, towr)    Minimum number of shots to kill the rat « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Minimum number of shots to kill the rat  (Read 9869 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
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
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
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.
@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
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7526
 Re: Minimum number of shots to kill the rat   « Reply #11 on: Sep 7th, 2013, 4:01pm » Quote Modify

Here are some related problems
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_med ium;action=display;num=1132524701
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1131519823
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_med ium;action=display;num=1218583902
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »