This has been making the rounds lately; I’m not sure where it first came from.
You’re in a rectangular room. Elsewhere in the room is a man with a gun, who shoots a bullet in a random direction. The bullet careens around the room, bouncing off walls, until it hits either you or one of the various punching bags you’ve placed around the room for purposes of absorbing the bullet. The punching bags must be positioned before you know the random direction of the bullet (though you do know both your own location and the bad guy’s location, neither of which you can change). How many punching bags do you need to guarantee your survival?
This being a math problem, you should treat the room as two dimensional, and yourself, the bullet and the punching bags as points.
I believe I can do it in 16, less if I can choose in advance where I and my assailant stand.
However, if my assailant is shooting at random (in the sense in which that is normally understood), I can contrive a 100% chance of survival with 0 punching bags. Does a 100% chance of success count as a “guarantee”?
One bag must go between you and the shooter – I am intrigued to see how Mike H gets zero. If you and the bullet are points, does that mean you are dimensionless?
Eugene Gutkin has $\ge 1$ paper on the subject. I cannot check the details here and now.
At first thought: eight, you box yourself in, I can get it down to four if when the corners touch the bullet won’t get through. Better yet, I can get it down to three, you’ll stand in the middle of a triangle.
I don’t see how you can get lower, but I am guessing you can get it down to two if you take into account that the angle at which the bullet hits the wall is also the angle at which the bullet ‘leaves’ the wall. Probably down to one if I can assume that the shooter does not hit himself or herself + the bullet leaving the wall at the same angle as the bullet hits the wall.
Should the punching bags really be points? If they have no area, then they could not shield the bullet(?)
If the punching bags are assumed to be circles with a finite area, then wouldn’t it only take one? It would be placed in the corner of the room, with me standing in the gap between the corner and the circle.
You cannot choose your location, although you are aware of it. Presumably the solution must work for any location of yourself and the shooter.
Further, I assume the bullet, bags and yourself are 1 unit of dimension, and the solution must work for any size of room. For an infinite room (no walls), one bag would be needed, directly between you and the shooter.
Yeah, I sense Mike H is referring to the dimensionlessness of a point. I’d calculate the probability of hitting something based on the ratio (number of hits)/(number of tries). The number of hits would be vanishingly small, approaching 0, rendering the probability 0.
Two bags, tangent to one another at the shooter, force the shot follow any line I choose. Pick one of the two lines normal to the wall — the one not passing through the target. Any tangent shot will reflect back to the tangent point, hitting the bags and the shooter. Any non-tangent shot immediately hits a bag.
I’ve taken to thinking about this like a game of snooker. How many balls would you need to place a perfect snooker (i.e. one where the target ball could not be hit without hitting another ball first). This works if we assume the bags are the same size as the people but also that the cue ball can slip through any gap.
Try as I might I can’t see any solution other than boxing the target ball in. But there must be a better solution or the question would never be asked!
Mike H:
However, if my assailant is shooting at random (in the sense in which that is normally understood), I can contrive a 100% chance of survival with 0 punching bags. Does a 100% chance of success count as a “guarantee”?
100% chance isn’t good enough. You need guaranteed survival.
Agreeing with previous commenters … it seems to me that it is impossible to guarantee survival if you and the punching bags are dimensionless. I could be wrong.
If you and the punching bags are circles with equal radius, then six will do (like six pennies surrounding and boxing in one penny). But, as David Johnson says, perhaps there is a better solution.
If I am a dimensionless point (isn’t that what a point is?), then I need one bag, directly between me and the shooter. The room contains an infinite number of points, so the bullet would require infinite time to pass through every point in the room.
@Phil & others: Don’t get hung up on the thickness of the bags. The dimensionless bag and you, also a dimensionless point, define a line. The bag shields you from bullets travelling on that line. What is really being asked is if a finite number of lines defines all the possible paths including ricochets, and ricochets of ricochets of ricochets … [Not quite, as infinitely many could pass through one point].
We can bound the number above by the cardinality of the continuum, just by covering all the walls, and an intermediate point, with bags.
The following assumes idealised laws of reflection. This isn’t stated in the original problem, but I can’t think of what else we’d be expected to assume.
The number of possible trajectories that can hit you are determined by the number of ricochets the bullet can make. If the bullet can’t ricochet at all, there’s only one trajectory; the one pointed straight at you.
If the bullet can make one ricochet, that creates an additional four trajectories that can hit you (one for each wall in the room). A good way of visualising this is to imagine an additional room adjacent to every existing wall, identical to this one (you, gunman, punchbags, etc.) but optically inverted about the wall. This is what you’d see in a room lined with mirrors. If someone fires a laser pointer and it hits your reflection, it also hits you.
This may be getting hard to visualise without some actual visual help, so here’s a diagram:
http://i.imgur.com/i7ien.jpg
X is you, G is the gunman. All squares labelled 1 are squares which represent one ricochet. If the gunman shoots a reflection of you in a 1-square, he shoots you with one ricochet. However, you won’t need one punchbag for each of these five trajectories, because in the 0-square, every trajectory intersects with at least one other trajectory. You only need three; two on each intersection and one for the straight shot.
If the bullet can make two ricochets, that adds an additional eight possible trajectories; one for each square adjacent to a 1-square. If he shoots a reflection of you in a 2-square, he shoots you with two ricochets. However, every one of these trajectories will intersect with at least one of the other trajectories, so you only need one additional punchbag for every two trajectories.
For n reflections, the number of additional trajectories at each stage is 4n, so I make that sum to n^2 + n + 1 punchbags (one punchbag for every two trajectories and one for the straight shot. It’s worth pointing out there’s an equivalent for the same scenario in three dimensions.
There are complications to consider:
– Are any of the trajectories congruent? My intuition for optical problems tells me there aren’t, but I don’t trust this entirely, and don’t have time to investigate this in depth at this point.
– Are there any common intersections between trajectories? Again, optical intuition tells me there aren’t if I’m a point and the trajectory is a line segment.
We’ve not been given any limit on the number of ricochets, so we can assume it’s either infinite or so arbitrarily large as makes no difference. Since there’s no arrangement of finite points that can lie on an infinite number of lines radiating out from a central point, I feel fairly confident in saying there’s no finite number of punchbags that can intercept a potentially infinite number of trajectories for the bullet.
Furthermore, I think any shot will return to the shooter after countably many ricochets, so all you need is to protect against is all the paths which hit you in countably many ricochets. There are only countably many of these, as a countable union of countable sets is countable (assuming choice), so we need only countably many bags.
@Ken B: “The dimensionless bag and you, also a dimensionless point, define a line.”
I disagree. You need infinitely many points to define a line. If you take any two points with a distance lambda on a line, there will always be points inbetween those two points (lambda/2 for instance). So boxing yourself in is impossible.
As to my proposed solution: I would argue that you need infinitely many bags. Suppose that if the shooter looks at you, one wall is to his Left, the other to his Right. One way of ricocheting is Shooter -> L -> You, 2nd: S –> L -> R -> Y; 3rd S -> L -> R -> L -> Y, and etc
If you choose wisely you can cover a multiple of these ricochets with one bag, but since the sequence LRLRLRL… can be infinitely long, you’ll need infinitely many bags.
Daniel Hewitt seems to be onto something. If you stand in the corner of the room it’s possible (if you’re really thin) to get by with one bag. Two bags could probably assure survival.
This would be much more fun if we treated the room as three dimensional. This adds the ability of the shooter to shoot while crouching and thus avoid hitting himself. It also adds the ability of the shooter to shoot at an upward angle and possibly bounced the bullet off the floor, which makes the “surround oneself with bags” solution ineffective.
@Ken B: Right. It seems to me the answer is no. I must be wrong, though, or the question would never have been asked. But here’s my logic.
Suppose, without loss of generality, that the shooter is standing exactly 1 m to the right of me. If he shoots at 12:00, the bullet bounces back and kills him.
But what if he shoots just slightly to the left of 12:00? Then, the bullet hits the top wall, then the bottom wall, then the top wall … all the while moving slightly to the left, until it’s gone 1m to the left and hits me if I’m unprotected.
Now, suppose I’m 1m from both the top and bottom walls. Consider where the bullet is when it’s (say) 1 cm north of me. It depends. If the bullet took 100 ricochets to hit me, then it’s 1/100 of 1/100 of a metre north of me. But if the bullet took 1000 ricochets, then it’s 1/100 of 1/1000 of a metre north of me.
So the bullet could be at an infinite number of points 1 cm north of me. And, actually, you can see that of all the paths the bullet could take to hit me, based on the number of ricochets starting with a shot just slightly off direct North, none of them intersect at any point but me.
So, it seems to me, I’d need an infinite number of dimensionless sandbags.
(Another way to look at it: draw the paths of all the bullets that are initially fired just off straight N. None of them intersect between the shooter and the north wall. By symmetry, at the end of their path before hitting me, none of them intersect between the north wall and me. Therefore, I need an infinite number of sandbags since there’s no one spot that catches an infinite number of bullets.)
Couldn’t you lie down with a bag laying in front and a laying behind you?
OK, I see the flaw in my own reasoning. Because I, too, am a point, not every one of the infinite shots I hypothesize will hit me.
So, never mind. I’ll think some more.
“100% chance [of survival] isn’t good enough. You need guaranteed survival”
*sigh* If only manufacturers of consumer products worked on this same principle.
Ok, I will claim I need at most 16 point-sized punching bags to protect my point-like self from the point-like bullet (or laser beam) of my pointlike assailant.
SPOILER ALERT
My solution : (select from here….
First, I note where I and my assailant will be standing. I install large mirrors on the walls. I note the position of my assailant, and the position of his three reflections in the north wall, the east wall, and the northeast corner. I get a laser range-finder to draw lines to these positions (if necessary, allowing the lines to reflect off the walls), and put a punching bag at the midpoint of each of these lines.
I then note the position of the reflections of these four positions in each of the south wall, the west wall, and the southwest corner, giving me another 12 positions and lines. I put punching bags at the midpoints of these lines too.
Then I stand in my allotted position, grin confidently, invite my assailant in, and
close my eyes and pray my maths is rightbop him a good one while he’s not looking and run out the door.… to here to see it)
Phil: “I must be wrong, though, or the question would never have been asked.”
You are invoking my favourite, the Good Puzzle Theorem. Here the GPT suggests the answer is no, and that you can fire a shot that creates a space filling curve, because then you have one neat solution for all cases (as the GPT requires) but I have no argument for this guess yet.
Hmm, I tried to make my solution invisible, but apparently HTML ‘font’ tags are stripped from comments.
Sorry for the spoiler!
@Ken B What is really being asked is if a finite number of lines defines all the possible paths including ricochets
As you noted, this is
Not quite [correct] as infinitely many could pass through one point
In fact, it’s quite clear that there will be infinitely many lines, once you put mirrors on the walls and imagine the room unfolded into its infinitely many tesselating reflections
I am wondering what other room shapes allow a solution with finitely many punching bags. I think it’s clear that an equilateral triangle would.
The solution differs a great deal if you assume points versus if you assume unit-1 objects.
The “one” solution fails because the experiment takes place in a room with ricochets and in fact infinite ricochets. Since there are (potentially) infinite ricochets then you must assume the line (of the bullet) can approach you from any angle.
The degenerate case, then, is that you’d need a circle to block every possible line that intersects the point (you).
Since you know the location of the two points ahead of time, you also know the distances and angles from those points to the walls of the room. Also assume you know the (unstated) rules about how bullets bounce – presuming some regular rule like angle of incidence = angle of reflection. If bullets bounce randomly then you’re back to any initial shot can go anywhere in the room and you need a full circle.
Under your assumed rules of bouncing you can compute which initial angles of shot will cause the bullet eventually to travel to you and you only need to block those. So, tell me what rule(s) govern bullet bouncing please?
If I simplify the problem to an infinitely long hallway instead of a room and imagine a gunman who is actually trying to hit me, I think I can use three punching bags to stop him. One punching bag halfway between us, and two more on the walls where he would shoot to try to hit me with one ricochet. I can’t do the math, but my intuition (and doodles) make me think that shots with odd numbers of ricochets will hit the two punching bags on the walls and shots with an even number of ricochets will hit the punching bag midway between me and the gunman.
Adding back the two walls, and continuing with this line of reasoning, I think I’d need another nine bags for a total of twelve.
Assuming “usual” bouncing, and that the bullet can bounce infinite times, I think we need an infinite number of bags.
The reflection walls can be thought of a copy of the room. If multiple bounces are allowed, we can think of infinite copies of the room, in the whole plane. We have infinite “me” in the plane, and the shooter can aim to any “me” he wants.
Just need one little jump to conclude the points are infinite… ;)
(at least it’s countable!)
Does the answer “y” count, where y is the shorter axis of the room? You could always place y bags in a line (parallel to short axis) between you and the shooter and the bullet could never hit you.
Now I’m thinking my reasoning leads to seventeen points. Counting is hard.
Could we re-phrase the questions to ask,
Imagine that you’re a point in a rectangular room with mirrors on all the walls. There is a point of light somewhere in the room. How many poles would you need to install into to room to block all view of the light?
(Just doing my bit to reduce violence in hypothetical worlds….)
Alan Wexelblat:
So, tell me what rule(s) govern bullet bouncing please
They act like light rays; angle of incidence equals angle of reflection.
Mike H, seems to me like lots of room shapes will do, in particular anything you can get by gluing right-angled isosceles triangles, equilateral triangles or rectangles together at matching sides.
Mike H, seems to me like lots of room shapes will do, in particular anything you can get by gluing right-angled isosceles triangles, equilateral triangles or rectangles together at matching sides.
Conjecture: The number of bags you’d need is proportionate to the number of prime numbers. Because there are infinite number of prime numbers, you’d need infinite numbers of bags.
There are, of course, an infinite number of paths the bullet could travel to hit you. If you have any hope of surviving with a finite number of bean bags, then at least one of the bean bags needs to stop and infinite number of possible bullet paths. I feel like that’s impossible but I’m not sure.
Consider an elliptical room with a player at each focus. Now you cannot survive.
In the case of the rectangular room I think the properties of the rectangle let us replace
the rectangle with a rectangular tesselation of the plane.
This is because the line after the second ricochet is parallel to the original line.
So imagine tesselating the plane with copies of the rectangle which you do by reflecting the rectangle along an edge.
I assert without proof you can do this.
When you do straight lines in the tesselation correspond to ricochet paths.
Put a red dot at the shooter’s spot in the original rectangle
and a blue dot at the victim’s spot in each rectangle.
Now every line connecting the red to a blue dot is a possible trajectory.
If there is some rational number realtionship betweene lengths here you might get a finite number
but allowing for irrational ratios it looks like an infinite number.
So for a given room there should always be a pair of points where you fail.
I think it is 5.
You definitely need at least one point on the straight line between yourself and your enemy.
I am not sure if my reasoning works after this…
Since the position of your enemy is fixed somewhere in the square, can’t he only change the point along the wall the bullet ricochets off of, and not the angle of incidence that the bullet will hit the wall? If this is the case, then the enemy can only hit each wall in one spot for the bullet to hit you. Any other spot would either ricochet in an endless loop around the square, or would hit the enemy. Therefore, you only need to place one bag on each of these lines for a total of 4 more bags.
You could never move again, because a bullet will be ricocheting in infinite loops, but you are definitely safe.
Two circular bags tangent at shooter constrain the path to a line of my choosing, enough to guarantee survival in a rectangle. Three crcular bags tangent at shooter constrain the path to half of a line, enough for survival inside an ellipse.
42
Enough to surround the shooter say four times? (24?)
Depending upon the caliber of the firearm, the type of firearm, and a multitude of other very relevant variables, I’d the ability to slow the bullet most immediately, and possibly rendering it inert is the only feasible way to guarantee survival (assuming that gravity exists, and if the bullet ricochets, it will lose momentum, and ultimately stop).
This would be especially efficacious if he were sequestered into a corner.
I’m not a math whiz, so forgive my less than sophisticated solution. I’m just not sure if the question need be that complex. =/
Joseph Zacardi: ” the enemy can only hit each wall in one spot for the bullet to hit you”
Nope. Imagine a long series of caroms off the walls. For example the rectangular wall is 1 mile long and 10 feet wide, and the bullet bounces back and forth, back and forth as it zig zags along the mile length.
Good point Ken B.
Still thinking this through. Using a more generic logic to what I said above, not every bullet fired at random will ever hit me, even in the absence of bags. Therefore, there has to be a finite number of bullets that will hit me. I just haven’t figured out how to count them…
Joseph… “Therefore, there has to be a finite number of bullets that will hit me.”
Nope again — at least from the logic you offered. There may be an infinite number of misses, but there are still an infinite number of shots that can hit you.
My answer: I would need one punching bag to stop one bullet. I would place the punching bag in the barrel of the shooter’s gun.
Next!
Similar to Scott H. answer. Two bags forming a wall on each side of the shooter forcing the shot to either be directly into a bag, or into a wall that will ricochet the round back into the shooter. Four bags total for a guarantee of survival.
If the shooter, victim, and bags are dimensionless points, then there are an infinite number of paths the bullet can take at random, and an infinite number of paths that would strike the victim. So is the question whether these infinities have the same cardinality?
I would need 1 bag between me and the shooter; 4 bags to cover all of the single reflection paths; 12 bags to cover all of the double reflection paths; 28 (I think) to cover all of the triple reflection paths; and I didn’t count past there. The point is I would need infinite bags to cover infinite trajectories.
I may be misunderstanding the problem, but I think I need 0 bags. There are uncountably infinite directions that the shoot can fire in, leading to uncountably infinite trajectories that the bullet can take. The number of trajectories that might strike the victim are countably infinite. Therefore, there is no possibility that the shooter will fire in a direction that would strike the victim.
An analogy: I am going to select a random real number between 0 and 1. What is the probability that the number selected is rational? Zero.
Al V.: If your argument is that probability zero events can never happen, then of course there is *no* direction in which the gun can be fired. But the gun gets fired, which suggests that there’s a flaw in your argument.
The answer appears to be Aleph Null, i.e. a countable infinity of bags. Most bullet trajectories cannot hit me, even though they ricochet infinitely. All fatal trajectories can be described by two integers: Ny = number of caroms off the top/bottom walls (sign indicating which is hit first) and Nx = number of caroms off the side walls. Thus a countable number of bags will block all fatal shots. Intuition suggests that there is no finite set of attractors (at least for prime numbers Nx and Ny) where all the fatal trajectories intersect.
@Lucas Reis (and others)
While it’s true that the reflective walls mean there are infinitely many copies of the assailant shooting at infinitely many copies of you, giving an infinite number of directions the bullet may travel, you forget that each single punching bag you place becomes infinitely many punching bags and can block (potentially) infinitely many of these trajectories.
Ok, here’s how I thought about it.
If you put mirrors on the north and east walls, the room gets multiplied by four. There are now four assailants shooting at you.
So, make that the puzzle. There are four assailants in a room. Each time a bullet hits a wall, it instantly teleports (via a wormhole in space) to the corresponding point on the opposite wall.
How can you stop all these bullets?
Lets dress the assailants in different-coloured tee shirts for easy identification in the police line-up, and figure out how to stop the blue one.
If you take a photo, then (because of the wormholes) you don’t see a single blue assailant, but an infinite number of them on a regularly spaced grid. You place a punching bag, and you see an infinite number of them on an infinitely spaced grid.
If you carefully place the first punching bag, you’ll find that it and its copies block a full quarter of the infinite number of paths between the copies of Mr Blue and you.
So with four punching bags you can block Mr Blue’s wicked plans. And you already have a photo of him carrying his laser gun, which you can quickly email to Steve in case he’s needed as a witness in Mr Blue’s trial.
Then, you block Mr Yellow, Mr Green and Mr Red in the same way.
I’d fail to be unsurprised if this solution turned out not to be suboptimal.
Erratum :
* for “an infinitely spaced grid” read “an infinite, regularly spaced grid”
* for “Erratum” read “Errata”
My intuition is that you can’t do it with a finite number of sandbags, despite this violating Ken B’s “Good Puzzle Theorem”.
My logic: imagine an arbitrarily long hallway, shooter and victim 100 feet apart. Imagine shooting the victim with one ricochet. Then three. Then five. Then seven, and so on. Each time, the horizontal distance between the first ricochet point and the last ricochet point increases. It’s 100 feet, minus (the sine of the angle of incidence times the distance from the shooter to the wall) minus (the sine of the angle of incidence times the distance from the victim to the wall). So each horizontal ricochet distance is that, divided by the number of ricochets.
This does not seem to have any obvious pattern, where we could see that certain numbers of ricochets have points in common. This makes it seem like there can’t be any finite number of points that every path touches.
My intuition is like Al V’s of 7:32 pm, where the number of bags required increases as the number of ricochets does, and there’s never a point where adding ricochets just reuses all the existing bags.
But that’s just gut. I’m probably wrong.
Mike H./8:44:
Could you give an example, including where the four bags would go to stop the blue shooter? I don’t see it, but maybe a real example would help.
In my post of 7:41, I was agreeing with A Marchant. The shooter chooses a random direction to shoot in, and the probability that that bullet’s trajectory passes through the victim’s point is (I am probably getting the math wrong here) aleph-null / beth-one, which is close enough to zero for me.
Of course, we’re kind of in a Zeno’s paradox situation here, because another way to look at this is that the bullet will eventually pass through every point in the plane, given infinite time.
***Spoiler Warning***
16 bags is enough.
WLOG, let the corners of the room be (0,0), (1,0), (0,a), (1,a). Let your position be A = (x_0, y_0) and the shooter’s be G = (x_1, y_1). Using rikkhill’s setup, we draw an infinite array of 1 by a rooms, reflecting A each time. The x-coordinates of the reflections of A are x_0 + 2n and (1 – x_0) + 1 + 2n for any integer n.
Let A’ be one of these reflections, and let M’ = (x_2, y_2) be the midpoint of A’G. Now x_2 is one of (x_1 + x_0)/2 + n or (x_1 + 1 – x_0)/2 + n for some integer n. Let M = (x_3, y_3) be the point inside the original room corresponding to M’. Define frac(x) := x – floor(x). Depending on the parity of floor(x_2), x_3 is either frac(x_2) or (1 – frac(x_2)).
Our two possible expressions for x_2 give us four different possible expressions for x_3. I could write them out, but that would distract from the point; all that matters about them is that the n’s cancel out in each of the four expressions, simply because frac(x) = frac(x+n) for all real x and integers n. Therefore, there are only four possible values for x_3. Similarly, there are only four possible values for y_3. Thus, there are at most 16 possible positions for M. We place a punching bag at each one, thus saving ourselves from the bullet with certainty.
I don’t know how to prove that 16 bags is the minimum, or even if it is.
Second paragraph, second sentence should read:
Now x_2 is one of (x_1 + x_0)/2 + n or (x_1 + 2 – x_0)/2 + n for some integer n.
The error doesn’t propagate.
My wife’s cousin was a military sniper. I think he told me that they trained him at 1,000m with an M4 rifle.
“I’d fail to be unsurprised if this solution turned out not to be suboptimal.”
Is that a quadruple negative? :-)
As they say in economics: “When risk of death is involved, cost is not a consideration”. I’ll take infinity bags.
“As they say in economics: “When risk of death is involved, cost is not a consideration”.”
Who says that? ‘Cause it’s false.
@Jeffrey Yes
@Phil/8:57 : imagine the original room is 5 x 5, so the room with the wormholes is 10×10
I am at (1,2), Mr Blue and his images are at (3,4)… and at (3+10m,4+10n)
I place a bag at (2,3), which has the effect of also placing images of the bag at (2+10p,3+10q)
The bag image at (2+10p,3+10q) saves me from the Mr Blue at (3+20p,4+20q). I’m now 25% safer from Mr Blue’s bullets.
By placing bags at (7,3), (2,8) and (7,8), I save myself from the Blues at (13+20p,4+20q), (3+20p,14+20q) and (13+20p,14+20q) also. And now Mr Blue is feeling blue.
I’ve shown how to protect myself from Mr Blue in the 10×10 room with the wormholes. In the original 5×5 room with the mirrors, my bags go at (2,3), (7,3)->(3,3), (2,8)->(2,2) and (7,8)->(2,2).
I also must protect myself from Mr Green at (7,4), Mr Yellow at (3,6) and Mr Red at (7,6). This requires bags at
* For Mr Green, (4,3), (9,3)->(1,3), (4,8)->(4,2) and (9,8)->(1,2)
Ooops! We have a problem here…. !!
I’m also at 16 bags, by the same sort of logic as Jeffrey/Mike H.
Bonus: Using the similar logic, (and the standard quotient maps on the unit square…) playing this game on the torus should require 4 bags, and the klein bottle/projective plane should each require 8 bags…
Is there some cute algebraic structure hiding inside this problem, or am I reading too far into this?
What if the room is a regular hexagon? And how do I defend myself against Mr Green, above?
@HH each of these bags is a single point. They can’t be expensive to manufacture. He could just buy a line segment and attack it with a cheese grater.
The problem is easy for an infinite corridor (a rectangular with one size infinite). Walls are A and B.
1) no ricochet: any point between you and the shooter is good
2) odd number of ricochets (on wall A odd number, on wall B even number): all shots will, sooner or later, ricochet on wall A on the same point as if there was a single ricochet on wall A. That is if for example there are 5 ricochet on wall A and 4 on wall B, the 3rd on wall A will be on the exact same point as if there were 1 ricochet on wall A and no ricochet on wall B. THIS IS A POINT WHERE TO PUT A BAG. If the odd number is on wall B the bag has to be put there, for a total of 2 bags
3) even number of ricochets
3a) even number on A and B separately: every shot passes on the median between you and the shooter (if u draw a line between you two, the point at equal distance on the line). This is a good point also for case 1) so A BAG SHOULD GO HERE.
3b) odd number of ricochets on A and B: every shot passes on the symmetric projection (with respect to the axis of the corridor) of the point we just took (the median between you and the shooter). Another point WHERE TO PUT A BAG.
So, for the corridor, we just need 4 bags: one on wall A, one on wall B, one in the median and one on the “symmetric median”.
Our problem can’t be solved just putting 7 points though (above procedure for horizontal direction and vertical direction, the median point is the same for both), because ricochets from walls orthogonal one to each other screw everything up.
I am pretty sure that adding a point for every wall (4 more) and the symmetric points of the median with respect to the diagonals of the rectangle (2 more points) should solve the problem. So even if I cannot yet prove or disprove this I vote for 13 TOTAL BAGS
Mike H: ” for “Erratum” read “Errata””
Enough with the paradoxes!
Errata: the bag in 2) is not necessarily on the wall but there is still a point where all the similar trajectories pass
Jeffery, Mike H., Jacopo and anyone else with their type of logic…
It doesn’t matter how many weird math notations you use in your post.
The situation is at least this bad…
Every single ricochet shot that uses a (Prime Number -1) number of ricochets will hit all the walls in a completely unique location from all other (Prime Number -1) ricochet shots. There are an infinite number of prime numbers, ergo there are an infinite number of unique ricochet shots.
Scott H: There are clearly an infinite number of unique ricochet shots. That doesn’t prove you need infinitely many obstructions to stop them all.
There are, for example, infinitely many trajectories through the origin in the plane — but you can block all of them with a single obstruction at the origin.
One bag suffices…provided it’s stuffed with enough $1,000 bills that you can trade it for the gun (I mean how crazy could the assailant be?)
That’s all I got. Mike H’s explanation with the mirrors and colored tees feels right. Each bag becomes infinitely many bags, cool.
@ Steve Landsburg…
I hate being wrong.
I see that my infinite number of ricochets ends up getting stopped with bags at the involved walls half way between each point (when orthogonally projected onto the walls).
It would be very helpful to have a diagram showing the 16 bags, and showing how the various different ricochets all converge to one of them.
I suppose I could do it myself, if I had a few hours to kill and I got the equations right!
Phil: I second that!
Assumptions. 1)By “absorb” you mean the bullet cannot kill him once it hits punching bag—so it cannot deflect (and you mean a big cylindrical body punching bag).
2)Neither participant can choose position.
3)The bullet does not stop or decelerate until it hits bag or you
4)He gets one truly random shot
5)By guarantee you mean absolute 100% certainty.
6)That each punching bag protects the side its on—-i.e., 4 is like a box and 3 is like a triangle with a space in bewteen for the person but no space between the bags
7)You choose to place the punching bags wherever you want
The above assumptions lead me to 3 or 4 (depending how I fit in between bags(thinking 3D). But 3 works. But…………
…………if I am thinking in terms of everything as points and 2D then infinite bags seem the answer, as there will always be a space between you and points outside the bags, i.e., it is a limit. Spaces between points can be infinitely small but never zero. Given the infinite number of rebounds possible (i.e., it is also a limit)you never get to 100% certainty–unless the bullet is somehow bigger than the space bewteen the points. But it is a point too. It is unsolvable.
Zero is an intriguing answer but wrong. There is 100% certainty you will be hit with zero bags. It is like a limit when measuring a shore line at ever smaller increments—-it never reaches a final answer. In the same way, a random bullet can bounce infinitely until it hits a target. This is the same logic I am using with “points” above.
If my “point analysis” is a non-sequitur, then I have to figure out why 3 is not the right answer, since it is the “obvious” one. For it not to be 3, there has to be many angles (to cover the entire space not covered by the missing bag if we used 2, (for example) that a bullet cannot take. It seems impossible for a space that large (if it were 2 bags, to have zero probability of being transversed—or conversely if the shooter had 2 bags instead of 3 around him)
Unless there is some kind of conditional probability of placement with 2 bags where certain angles are impossible, I will go with 3 bags in 3D real life land. And infinity or unsolvable in 2D land.
I’ve been thinking along these lines as well. And I think this statement only holds if you and the shooter are equidistant from the walls. But imagine that the shooter is closer to wall A than you are:
Let Wall A be x=0; Wall B be x=3. Shooter is at (1,0). You’re at (3,16).
To hit you on one ricochet off Wall A, shooter would hit point (0,4). So let’s put a bag there.
To hit you on three ricochets off Wall A, shooter would hit points (0,1), (3,4), (0,7), (3,10), (0,13). The bag at (0,4) offers no protection.
__
To address the problem algebraically, can we devise a generalized formula to calculate these bank shots, using simply the coordinates of me (A,B), the shooter (C,D) and the dimensions of the room (X,Y)? I end up with a formula that relies on minimize functions and absolute values, and it’s not any fun to work with.
Here is another try
For 3D real life land, one needs 4 bags not 3. You need one to lay across the top of the triangle.
for 2D land it is 6—-somehow I think the question must assume some dimensionality or it is pointless (pun). One has to block any direct straight line to the one being shot at. It would appear that a group of points can be created such as there is a way to block a direct line. Assume you are in the middle of a triangle of points which are infinitely close but never touch. Create 3 more points, each equidistant between the 3 pairs of the inside points of the triangle. These will be infinitely close to each inside pair and will block a direct straight line to the inside point, which is the shootee.
Therefore, it is 6. Since you cannot know where the shooter is beforehand, if you leave an open shot for him there is no guarantee that 5 will work surrounding him.
Sadly, I was going to complain about other people failing to read each others’ answers, when I noticed that I hadn’t even read the original problem statement. OK, dimensionless bags. Is it cheating to place one on the shooter and be done with it? Or one on the target?
@Liudvikas “Is it cheating to place one on the shooter and be done with it?”
It may well be enough to drop a heavy punching bag – or even just a heavy punch – on the shooter. Steve will have to adjudicate on this point… and reflections on it…
“This being a math problem, you should treat the room as two dimensional, and yourself, the bullet and the punching bags as points”
Based on this then you just need to put a point representing a punching bag on the point that represents the bullet and you should be safe.
So the answer is 1.
I’ll cast my vote with the 16 group. Sorry my explanation is so long-winded and probably hard to follow, but it’s hard to describe a graphical approach without a drawing… so obviously, feel free to ignore it. :)
My first thoughts on this were that while there are an infinite number of trajectories, they are constrained by the starting point and ending point which made me think of perhaps some rough analogue to nodes and standing waves and multiples of frequencies, etc. where some point or set of points is in all solutions even as the number of reflections increased. The first attempt at thinking of this was the simple hallway with shooter and target in the middle at either end (i.e. only reflections off the side walls). In that case it seemed clear that all trajectories pass through one of 3 points (the mid point of either wall or the center of the room– i.e. the straight shot and the 2-reflection Z trajectory go through the center, the 1 and 3 reflection “V” and “W” trajectories hit a mid point along the wall, etc.). Higher numbers of reflections just keep alternating through these 3 points. The obvious thing that struck me was the common points were always the half-distance point for all the trajectories that passed through them. So from that I generalized and guessed that if there were common points they would always be half-distance points for all trajectories passing through them (and by half-distance point I mean half the distance of the total trajectory length — not necessarily halfway between target and shooter).
I thought I would try to get an intuitive sense of it graphically but of course once you add the other two walls it gets messy trying to figure out many general-case reflections and where the center points would fall. However, it’s actually pretty easy if you simply create a grid of reflected rooms. With the original room in the center you simply reflect it over and over again in various directions. In each reflected room there is a reflection of the target (the shooter stays in the original room). For example, say the target is somewhere near the lower-left corner. Then in the first reflection to the left or right it will be in the lower right corner, in the second, back to the lower left, etc. The same goes for reflecting up and down but now it’s either the top or bottom left corner alternating. For all others you can get the reflections by doing a combination of left-right and up-down reflections to create a grid of reflected rooms. (After this you’re left with a grid where each room can be identified by it’s row and column number where the original room which is in row,column 0,0.)
Now you can simply draw straight lines from the shooter in the original room to each target in all reflected rooms. Each line represents one independent trajectory (of course in reality this method would result in an infinite plane of reflected rooms for the infinite trajectories but you don’t need many to spot the pattern). Note that the each room represents a distinct number of reflections for that trajectory. The path to the target in the adjacent four rooms are the 4 one-reflection trajectories, the room 2 to the left is a 2-reflection trajectory and the room over 3 and up 2 is a 5-reflection trajectory, etc.
Now you can very easily find the mid point of any trajectory as it’s simply a straight line. Right away you’ll see that the targets in any row of rooms form a horizontal line and in any column of rooms the targets form a vertical line. This is obvious but important.
Returning to the rows, start with the main row running right or left of your original room for several trajectories in each direction. You can quickly calculate x-coordinates of various midpoints and reflect that midpoint back to the original room. You’ll soon see the repeating patten of reflections in either direction cause the x-coordinate to cycle through 4 points in the original room once you reflect them back correctly (4 or less actually; symmetries in the placement of shooter and target can cause some of those 4 points to fall on top of each other reducing the number, but 4 is the most you’ll get for a generic, non-symmetric shooter-target location). By looking at the plots and thinking about what that means for the midpoints you’ll probably see why the pattern repeats in 4s.
Now you know the 4 possible x-coordinates of the midpoint of all the simple left-right trajectories (main row). But, as noted above, all reflected targets for a column of rooms lie in a vertical line and the only thing determining the x-coordinate is the horizontal distance which is thus constant for any given column. So you now know the 4 possible x-coordinates for the midpoint of EVERY possible trajectory as the same horizontal distance between shooter and target repeats in every row above and below the main first row.
Further, since we’re using a general rectangular room and there is nothing special about the labels horizontal or vertical, we can generalize that the same pattern of repeating y-coordinates for a given column of rooms will hold (and if you try it, it does). Therefore the same argument as above results in EVERY possible trajectory having a midpoint with one of 4 possible y-coordinates.
Given that every trajectory’s midpoint must have one of four x-coordinates and one of 4 y-coordinates, the maximum number of unique midpoints for all successful trajectories is 16 and blocking those 16 points guarantees no shots get through.
I assert : if you are allowed to choose where you and your assailant will stand, you can solve the puzzle with 1 punching bag.
Puzzle : where should place you, your enemy, and the punching bag?
Mike H: that is true only if you (and the shooter) can stand on the border of the rectangle while the bullet cannot travel in it; solution: put you and the shooter on corners of the same wall, bag on the middle of the opposite one.
Back to OUR problem :)
nobody.really: yes, you are right, and I already corrected myself. Still for the “corridor” problem there are 4 points that cover ALL the possible trajectories. Since many prefer formulas I’ll write my explanation in a more mathematical way.
We have a corridor of width 2b infinite in the x direction. Its borders are defined by y=b and y=-b. Chose the origin somewhere.
Shooter: (x1,y1)
You: (x2,y2)
What anyone can easily prove is that EVERY trajectory passes through either
((x1+x2)/2,(y1+y2)/2) the “median” point
((x1+x2)/2,-(y1+y2)/2) the “symmetric median”
((x1+x2)/2,b-(y1-y2)/2) if it bounces more on y=-b
((x1+x2)/2,-b+(y1-y2)/2) if it bounces more on y=b
Rotating the corridor [width 2a,infinite in the y]
((x1+x2)/2,(y1+y2)/2) same as above
(-(x1+x2)/2,(y1+y2)/2)
(a-(x1+x2)/2,(y1+y2)/2)
(-a+(x1+x2)/2,(y1+y2)/2)
These are the 7 points I was talking about in my first post. I don’t believe any symmetry can be added to remove either, but I might be wrong, so please correct me before I move further on to the rectangle (which looks like a mess)
Thx
Forgot to add:
My calculation is on par to the reflecting rule explained by Brian two posts above. The fact is I am confident that 16 bags will put us safe (as he explained), but I am still NOT sure that this is the minimum number.
Jacopo: “What anyone can easily prove is that EVERY trajectory passes through either…”
Anyone?
I have found all the different descriptions very useful in gaining insight into the solution. Brians step by step description was particularly helpful to me. Whilst I would not say I understood for certain, there are a couple of insights reported that convince me the solution is correct.
First, the corridor – I can understand here that in order to hit me the bullet must pass through one of very few points. This makes it reasonable that the solution is not infinity for the room.
Second, that the bullet bouncing off the wall is the same as it passing through the wall into a reflection. This gives the tesselating array of rooms allows visualisation of the trajectory, and to see that the different lines go through common points.
I’d say you and the shooter are in catticorner corners (Northeast vs. southwest, say), and the bag in the center of the room.
How does the shooter avoid being hit?
The puzzle states that the bullet continues until it hits you or a bag.
The size/shape of the the room is also irrelevant as the bag(s) should be placed to either not get to you or to never leave the shooter.
BTW, my answer remains one. You have the bag and the shooter occupy the same space.
Andrew, if the bag and the shooter are just points, and the two coincide, then the bullet will leave the punching bug just as well as it will leave the shooter.
SPOILER ALERT!
Waiting for Steve to weigh in with the correct answer, see this article: http://www.researchgate.net/publication/2134978_Growth_of_the_number_of_geodesics_between_points_and_insecurity_for_riemannian_manifolds/fulltexts/4e5f9b58f0c41c4932db5288.pdf/preview.
It states, “the geodesics between any pair of points cannot be blocked by a finite number of point obstacles.”
If the bags and shooter are infinitely small points, then the bags can be infinitely close to the shooter. That makes the answer six bags as a hexagon surrounding the shooter. The layout is that of seven circles with the shooter in the center. We’ve all done this with coins, plates and other round objects.
@Al V. “the geodesics between any pair of points cannot be blocked by a finite number of point obstacles.”
There must be some conditions attached to that statement. If the manifold is the real line, the geodesic between any two points can be blocked with a single point.
BTW – When I click the link, I get a blank page.
my answer is, infinity… the most tricky situation is, when the shooter shoots “almost” squarely against one wall… the ricochetted bullet then returns”almost” over its path, only slightly shifted. And bounces between the facing walls, until it hits you Therefore it will approach you from an angle that is equal to the original angle (bullet track vs the “first impact wall”).
As the shooter can choose infinite number of angles between say 89 and 90 degrees, I see no way how a finite number of point punchbags might stop the bullet. True, you are point like too, so not all these shots will hit you. But my intuition is, there is still infinite number of tracks that go through you… you can construct such tracks with n bounces on the way, n going from zero to infinity. And I have even willingly omitted the bullets going back from the “far wall”.
maznak: you have recreated the “corridor” version of the problem. The answer proposed is that any trajectory that hits you must pass through one of four points – see post from Jacopo for example.
Mike H – is nobody.realy’s answer to your one bag problem correct? It looks about right, and perhaps will be a special case that is easy to visualise.
I think a snooker player would answer: 5, no doubt ’bout that!
The stuff Al V brought up…
A better link: http://www.math.northwestern.edu/~burns/papers/bg/
The result (quoth the Abstract): “We derive from this that a compact Riemannian manifold with no conjugate points whose geodesic flow has positive topological entropy is totally insecure: the geodesics between any pair of points cannot be blocked by a finite number of point obstacles”
Harold: I see your point. My fault that I have not read carefully all the posts…
I don’t have the math for this problem, so my apologies if my thoughts are boneheaded, but I had fun doodling on a piece of paper for twenty minutes because of this post and wanted to share.
I think it’s 5 punching bags. I imagine a line from Shooter to Target. One bag equidistant on that line between the two. If you carry that line from Shooter to the wall behind him, one bag equidistant between shooter and wall. Similarly, one bag equidistant between Target and wall. Then, I made two triangles using these two points and third points out from the shooter and target. In an 11 by 6 rectangle, with Shooter at (8,5) and Target at (8,2) for instance, I have bags at (8,1) (8,3.5) (8,5.5) and the others are at about (9,3) and (5,3). The height of both triangles varies depending on the size of the room and the distance between Shooter and Target.
I believe you need 4 bags, if the points have a radius of r, touching you at 90 degrees, the gap between the bags would be 1.41r, this is less than 2r for the bullet the pass through. Assuming the bullet and you are also points with radius r. 4 bags around the shooter would work too.
Random: points are points, i.e. no radius at all…
Has this question been solved yet? If not, here’s just a preliminary thought from me. If we’re assuming infinite ricochets and no loss of energy, and reflections just like light waves, couldn’t we rephrase the problem as such?
So we have a 2d rectangular room with two points. Generate infinite reflections of the room along each of its sides. Then break down all barriers between the reflected rooms and the original room. The shooter can shoot at any of the victims in the reflected rooms, and it can be shown that such an aim would reflect on the walls of the original room to hit the victim in that room. This is because we’re replicating the room along the same reflecting principles that the shot would reflect with.
So the question becomes how many different unique victims can the shooter choose to aim at such that no two victims intersect on the same line to the shooter (that shot would be blocked by the same dummy) and does not have a reflection of the shooter before the victim (the shooter would serve as a free dummy in that case).
A bit of elaboration to show the thought process.
Let’s take the simple case of one where the shooter and assailant are on the very edges of a rectangle such that a line between them would run perpendicular to the side they’re against. The distance of a straight line between then we shall call d.
So we need to block the straight shot. 1 dummy. If we put it at the midpoint of the straight line, we can block all shots that ricochet off at an odd interval along the side walls (ie all shots initially aimed at a d/{odd number > 1} interval between the shooter and victim on the side walls, since those lines will always pass through the midway point. Next taking into account the ricochets of d/{even number > 0} intervals. 2 dummies will account for these if placed at d/2 points on the side walls.
Now we need to account for the nontrivial case where the shooters are in the middle of the room and the bullet can ricochet from behind. After that there are probably issues to consider where the straight line between the two is not parallel to a side wall.
My answer 3 bags…assuming that I can stand in an unoccupied corner.
Stand in the corner…with a one bag touching each wall…and a third touching each bag and blocking the gap between them.
I have diameter = ‘d’. Assume bags have diameter ‘d’ same as me!
Therefore, to fully close off corner in front of me I need in a wall of bags in front of me, a triangle of sorts. Bags touch wall…no penetration of bullet, third bag touches each other bags, no penetration of bullet….2D world – ignores ricochet off ceiling.
Side of triangle = 2*d (me plus bag along wall)
Angles are 90/45/45
Cos(theta) = adjacent side / hypotenuse
Hypotenuse = 2d / Cos(angle)
The ratio of the side to the hyp will remain constant as d goes to zero (i.e., point)
Length of hypotenuse = 2 * cos(45) = 2.83 * d
Minimum number of bags = 3 (cannot subdivide bags)
If I cannot choose my location, than I’d need 7 to surround myself…same assumptions as above – but circumference = 2*PI*radius…minimum radius = 2 r, assuming bag and me are same.
only problem is when the gunman is w/in the distance of one bag…then I can’t block all random shots….
Come to think of it, for infinite ricochets I need a nondenumerably infinite set of punching bags otherwise there’s a diagonal argument I risk biting the bullet. Personally, I think this stand your ground business has gone too far. I blame Zorn’s lemma. That boy aint right.