|
This one I think is pretty nifty, I hope you guys enjoy it. I feel like some of the parts might be confusing to understand, so please ask for clarification if needed.
Wile E. Coyote just got a shipment of an infinite number of bombs, and he's ready to blow up the Road Runner once and for all. However, the rules of the game this time around are a bit different from the usual.
You see, this world is one dimensional, so the Road Runner only runs in a straight line. Also, the world is discrete, and everything has integer values. The Road Runner starts at an integer location and moves at a constant integer velocity. Since time is also discrete, the Road Runner warps from his current location to his next location every second, instead of running continuously on the line.
The problem for Wile E. Coyote is that he doesn't know the Road Runner's velocity or starting location, but he can fire one bomb at any location, every second.
Devise a strategy for Wile E. Coyote that, given an infinite amount of time, assures that he will finally be able to blow up the Road Runner.
|
wah wah wah
wile e coyote should just detonate the same location every time because a 1 dimensional random walk returns to its original location with 100% probability.
dink success
|
It's not a random walk, the Road Runner moves in a straight line at some velocity. Actually, the Road Runner never ends up at the same location twice.
|
+ Show Spoiler [Sketch solution] +This is basically the same as what you posted last time with the mapping of 2D integers to the natural numbers. I'm sure you did that on purpose, very nice.  Assuming he knew Roadrunner's starting position and velocity, Wile E. Coyote could easily calculate where to bomb based on how much time had elapsed. So he just has to cover all the possibilities by doing that spiral walk on the 2D integer space of (starting position, velocity).
|
I couldn't simplify the problem enough for the math that I know to solve it, so I'm just going to say you cheated and walk away. 
+ Show Spoiler +I know essentially, in 2 dimensions, you have to find a curve that intersects with every possible non-horizontal, non-vertical line starting on t=0, this doesn't work with the discreteness and the one bomb a second rule, but I am assuming it is a small adjustment from that to the answer, idk, somebody please tell me if I am on the right track.
|
Are you guys professors or something? Maybe Polemarch isn't, based on his sig. Slithe?
+ Show Spoiler +See "Hotel Infinity" entry to this blog. Slithe shows a diagram of mapping a 1-d line to 2 dimensions.
Infinity is indeed very awesome.
|
|
|
Nice post, not too hard but I liked it!
Tadzio00; Z is a discrete infinite set.
|
Nice solution polemarch... I'm sorry I saw this too late. I think I might also start posting problems soon.
|
Haha I'm not professor, far from it. I'm just an undergraduate computer science major. I get most of these problems from other students who also like doing this stuff. I don't know there they get these though.
Polemarch is correct in noticing that the mapping I showed from my hotel infinity blog is the exact same thing. I think he answered my blog with the answer within like 10 minutes or something absurd like that. I may have to require that polemarch give everyone else at least a day before ravaging my problems so quickly haha.
Muirhead, you should totally post problems up. That would be awesome, cause then I can try and solve some too.
|
I just posted my first problem . See if you can solve it... either Slithe or polemarch. Also tell me what you think of the difficulty and subject. I can vary both of those quite a bit.
|
Sorry, that was pretty inconsiderate to not even use spoilers. Now fixed. I know that reading a solution is nowhere near as satisfying as working it out yourself, and that it takes a LOT of self control not to. So... I'll be good.
|
+ Show Spoiler +Roadrunner travels at x_0+vt. Consider a coordinate grid with an x_0-axis and a v-axis, where each point represents the roadrunner's travel function. At time zero, start from the origin and progressively work your way outward in squares, evaluating the point's function at whatever time you got there at.
|
Yes Emerald that is the correct answer. Good Job.
|
Does Wile know the direction the Road Runner is running?
|
I like this thread. Not because I like to solve these questions, but I'm always amazed at
A ) The difficulty of these questions.
B ) The vast amounts of math that I have no clue of.
C ) Seeing someone get it right (like Emerald) I find impressive.
|
To pat777: Velocity is both speed and direction, so Wile does not know Road Runner's direction.
|
+ Show Spoiler +Ok, Draw a graph of plane xy. I define x as the starting point and y as the velocity. Each integer point on the graph will generate a set with elements for each second. y=0 will generate {x,x,x...}. Point (1,1) will generate (1, 2, 3, 4...). Start from point (0, 0) and pick the first element from the set to bomb. Then move one integer right on the plane and pick the 2nd element from the set. Then move one integer up on the plane and pick the 3rd element from the set. Then move one integer left and pick the 4th element from the set. Move another integer left and pick the 5th element from the set. Move an integer down and pick the 6th element from the set. Continue spiraling out and you will eventually hit the roadrunner.
|
|
|
|
|
|
EPT
