August 2nd, 2017 at 6:18:24 AM
permalink

Besides things like proving Fermat's Last Theorem, that is...

Anyway, at this year's International Mathematical Olympiad, there was one problem that stumped pretty much everybody, including the top three finishers. It goes something like this:

You and a computer are playing a game that goes as follows:

The game is played on an infinite plane, with both of you starting at the point (0, 0).

The game lasts 109 turns.

EDIT: OOPS - that should be 10^{9} (i.e. 1,000,000,000) turns

In each turn, the following happens:

1. The computer moves to a new location that is distance 1 from its current location, but it does not have to be at integer, or even rational, coordinates. For example, the first move can be to (-1, 0), or to (0.6, 0.8), or to (-sqrt(3) / 5, -sqrt(22) / 5). Note that the move's distance has to be exactly 1. Also note that the computer does not tell you where it moved to.

2. The computer will then tell you the coordinates of a point that is within distance 1 of its current point. In other words, if the computer is at point (a, b), then it will tell you the coordinates of any one point on or within the circle (x - a)^{2} + (y - b)^{2} = 1.

3. You then move to a new location that is distance 1 from your current location. Note that the computer does know your location.

The question is, can you guarantee that, at the end of the 109th turn, your location will always be distance 100 or less from the computer's?

Anyway, at this year's International Mathematical Olympiad, there was one problem that stumped pretty much everybody, including the top three finishers. It goes something like this:

You and a computer are playing a game that goes as follows:

The game is played on an infinite plane, with both of you starting at the point (0, 0).

The game lasts 109 turns.

EDIT: OOPS - that should be 10

In each turn, the following happens:

1. The computer moves to a new location that is distance 1 from its current location, but it does not have to be at integer, or even rational, coordinates. For example, the first move can be to (-1, 0), or to (0.6, 0.8), or to (-sqrt(3) / 5, -sqrt(22) / 5). Note that the move's distance has to be exactly 1. Also note that the computer does not tell you where it moved to.

2. The computer will then tell you the coordinates of a point that is within distance 1 of its current point. In other words, if the computer is at point (a, b), then it will tell you the coordinates of any one point on or within the circle (x - a)

3. You then move to a new location that is distance 1 from your current location. Note that the computer does know your location.

The question is, can you guarantee that, at the end of the 109th turn, your location will always be distance 100 or less from the computer's?

Last edited by: ThatDonGuy on Aug 2, 2017

August 2nd, 2017 at 7:15:53 AM
permalink

Is there a such point as 0, 0 on an "infinite" plane? That be like saying, "I have infinite money. If I give you half of it, how much did I give you?"

"And that's the bottom lineeeee, cuz Stone Cold said so!"

August 2nd, 2017 at 7:50:14 AM
permalink

I Beat -

Infinite plane does not mean you need a piece of graph paper of infinite size. 0.0 is the standard starting point for any grid. Traditionally, you go up and right from there, but there's no reason you can't go down and/or left into the negatives. THAT'S an infinite place.

Don -

I don't get why this is so hard. No matter where the computer moves, since it only moves 1, and gives you a position 1 away from there, you can always move 1 in the general direction of the false position.

Seems to me that you'll always be relatively close to the computer's position, so within 100? Sure.

Infinite plane does not mean you need a piece of graph paper of infinite size. 0.0 is the standard starting point for any grid. Traditionally, you go up and right from there, but there's no reason you can't go down and/or left into the negatives. THAT'S an infinite place.

Don -

I don't get why this is so hard. No matter where the computer moves, since it only moves 1, and gives you a position 1 away from there, you can always move 1 in the general direction of the false position.

Seems to me that you'll always be relatively close to the computer's position, so within 100? Sure.

Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood?
Note that the same could be said for Religion. I.E. Religion is nothing more than organized superstition.

August 2nd, 2017 at 9:47:04 AM
permalink

Quote:DJTeddyBearI don't get why this is so hard. No matter where the computer moves, since it only moves 1, and gives you a position 1 away from there, you can always move 1 in the general direction of the false position.

Seems to me that you'll always be relatively close to the computer's position, so within 100? Sure.

Note that the reported position is 1 or less away from the computer's position - not always exactly 1.

Also, regardless of what the computer's first move is, the point (0,0) is always 1 away from its location, so it can report (0,0), and your move might end up being in the opposite direction, so after 1 move, you are now 2 away from it.

August 2nd, 2017 at 10:29:29 AM
permalink

Don -

I get that. But the OP says the end must be less then ONE HUNDRED points away.

No matter how much misdirection the computer uses, I can't see getting anywhere near that far away.

I get that. But the OP says the end must be less then ONE HUNDRED points away.

No matter how much misdirection the computer uses, I can't see getting anywhere near that far away.

Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood?
Note that the same could be said for Religion. I.E. Religion is nothing more than organized superstition.

August 2nd, 2017 at 10:34:55 AM
permalink

What am I missing? No matter where it moves, the computer's actual position will be within a sphere one move from its reported position. If you always move to, or on a tangent toward or across the position reported by the computer each turn, you will certainly be within 100 of the computer's actual position.

Alternately, if you always move toward the point that bisects the last two reported positions, you may end up even closer because the computer will never report it's actual position... or will it.

Alternately, if you always move toward the point that bisects the last two reported positions, you may end up even closer because the computer will never report it's actual position... or will it.

America is all about speed. Hot, nasty, bad-ass speed. - Eleanor Roosevelt, 1936

August 2nd, 2017 at 10:45:01 AM
permalink

I agree with DJT. My reasoning goes something like this...

To get 100 spaces away in 109 turns, the computer would have to increase separation by an average of about 0.9 spaces per turn.

Once the computer gets about 10 spaces away, the estimated position of the computer will give you a pretty good idea of which direction you need to move to approach the computer. I suppose one could calculate a maximum error as a function of separation distance, but it seems intuitive to me that the number can't be much greater than maybe 0.2.

I'd guess that the correct mathematical approach would be to calculate the maximum separation growth rate as a function of separation, then integrate to calculate the maximum separation after n turns. I'm not going to do it.

To get 100 spaces away in 109 turns, the computer would have to increase separation by an average of about 0.9 spaces per turn.

Once the computer gets about 10 spaces away, the estimated position of the computer will give you a pretty good idea of which direction you need to move to approach the computer. I suppose one could calculate a maximum error as a function of separation distance, but it seems intuitive to me that the number can't be much greater than maybe 0.2.

I'd guess that the correct mathematical approach would be to calculate the maximum separation growth rate as a function of separation, then integrate to calculate the maximum separation after n turns. I'm not going to do it.

August 2nd, 2017 at 11:17:54 AM
permalink

The puzzle presented at the 2017 International Mathematical Olympiad is slightly different than what was posted here.

The question on their website is after 10^{9} rounds can the distance be at most 100

The question on their website is after 10

August 2nd, 2017 at 11:31:41 AM
permalink

Dale -

That's different. WAY different.

If the computer moves in a straight line away from you, and constantly misdirecting you, you're zig-zagging to catch up, but losing ground in the process.

Hmmmm.... 10^9? That's a lot of evasive moves and losing ground. Yeah, NOW I see why it's a tough problem.

That's different. WAY different.

If the computer moves in a straight line away from you, and constantly misdirecting you, you're zig-zagging to catch up, but losing ground in the process.

Hmmmm.... 10^9? That's a lot of evasive moves and losing ground. Yeah, NOW I see why it's a tough problem.

Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood?
Note that the same could be said for Religion. I.E. Religion is nothing more than organized superstition.

August 2nd, 2017 at 11:47:58 AM
permalink

OK, that makes more sense! I was about to post some analysis on the original problem. Not sure how useful it is now.Quote:Dalex64The puzzle presented at the 2017 International Mathematical Olympiad is slightly different than what was posted here.

The question on their website is after 10^{9}rounds can the distance be at most 100

Assuming the computer plays perfectly to increase the distance, and the player plays perfectly to decrease the distance, I did a couple of iterations in CAD. (That may be cheating, but I didn't feel like doing the Trig by hand.) Perfect strategy for the computer is to move as far from where it thinks the player is during its move. The player's perfect strategy is to move 1 in the direction of the computer's last reported coordinates.

To analyze the worst case for the player (max distance), let's assume that the computer moves to (1,0), reports the coordinates of (0,0), and that the player moves in the opposite direction to (-1,0). Also, even though the computer doesn't know the player's position, let's say it correctly guesses that the player is at (-1,0). Its best move is to continue to (2,0) and report the coordinates of (2,-1) to create the greatest angle for the player between the reported direction and the true direction.

I computed out through turn 3. Note that the last column indicates how much the computer increased it's 'lead' on the Player:

As you can see, the distance increases with each turn, but the increment will always be decreasing. If the maximum distance between the two after Turn 3 is 2.1469, and each subsequent increment will be no more than 0.0714, then the max distance between the two after 196 more turns would be no more than 9.7513.

Now, if it is the player's strategy to maximize his distance from the computer, that would be a different story. But from the original wording, I don't see this as the case.

To analyze the worst case for the player (max distance), let's assume that the computer moves to (1,0), reports the coordinates of (0,0), and that the player moves in the opposite direction to (-1,0). Also, even though the computer doesn't know the player's position, let's say it correctly guesses that the player is at (-1,0). Its best move is to continue to (2,0) and report the coordinates of (2,-1) to create the greatest angle for the player between the reported direction and the true direction.

I computed out through turn 3. Note that the last column indicates how much the computer increased it's 'lead' on the Player:

Turn | Comp X | Comp Y | Reported X | Reported Y | Player X | Player Y | Distance | Increment |
---|---|---|---|---|---|---|---|---|

0 | 0 | 0 | -- | -- | 0 | 0 | 0 | -- |

1 | 1 | 0 | 0 | 0 | -1 | 0 | 2 | 2 |

2 | 2 | 0 | 2 | -1 | -0.0513 | -0.3162 | 2.0756 | 0.0756 |

3 | 2.9883 | 0.1523 | 3.1407 | -0.8360 | 0.9357 | -0.4769 | 2.1469 | 0.0714 |

As you can see, the distance increases with each turn, but the increment will always be decreasing. If the maximum distance between the two after Turn 3 is 2.1469, and each subsequent increment will be no more than 0.0714, then the max distance between the two after 196 more turns would be no more than 9.7513.

Now, if it is the player's strategy to maximize his distance from the computer, that would be a different story. But from the original wording, I don't see this as the case.

I'm guessing that the trick is to derive a function that describes the trend of the increment? Beyond my pay grade.

"Dealer has 'rock'... Pay 'paper!'"