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?

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.

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.

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.

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.

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.

The question on their website is after 10

^{9}rounds can the distance be at most 100

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.

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

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.

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

My bad - I cut and pasted it, and it came out 109.

The computer's strategy would be to give a point which with my location makes a line which is at a distance of 1 from the computer. And my strategy would be to move toward that point. I would know the computer's strategy, but I wouldn't know whether the computer is to the left or the right of that point, so I would have to head toward the point given. Then after I move, the computer starts the next round by moving directly away from me.

Let x be the distance from me to the computer after a computer move. Using trig to find the distance after my move, I get: sqrt ( x^2 + 1 - 2 * sqrt ( x^2 -1 ) ). The computer would then move increasing this distance to 1 + sqrt ( x^2 + 1 - 2* sqrt ( x^2 - 1 ) ).

This means that the computer increased its distance from me by the difference between the above distance and x. That's 1 + sqrt ( x^2 + 1 - 2 * sqrt ( x^2 - 1) ) - x . The computer is increasing its lead but at a decreasing rate. The smallest rate of increase would happen at the greatest distance. Consider a distance of 100. The rate at that distance is approximately 1 / 20,000. So, the moves at distances less than 100 would have rates of increase at least as big as 1 / 20,000. You can see 2,000,000 rounds would increase the separation to least 100. And 10^9 rounds at distances less than 100 would increase the separation much more.

(To find the value at x = 100 for this expression: 1 + sqrt ( x^2 + 1 - 2 * sqrt ( x^2 - 1 ) ) - x, I called the expression d and manipulated the equation to get rid of the radicals. d is very small, so d^2 and higher powers are negligible at x = 100. The expression becomes d approximately equals 1 / ( 2x^2 - 2) or about 1 / 20,000.)

The plane or the direction doesn't matter. You adjust the grid to be a directional coordinate. The only thing that matters is the distance to the target, which you know is within 1 unit, and you make your move always to be towards the location that the computer gives you, right or wrong.

So, after one move, the computer can give you a coordinate that is a distance of between 0 and 2 units away from you. However you know that the computer cannot be more than one unit away. So, for example, if the computer gives you the distance as being 2 units away from you, you know exactly where the computer is because it gave you a coordinate with only one possible answer.

So, indeed, it would be in the computers best interest to give a first coordinate of 0,0, because it provides you with no information. Your only move could be to 1,0, at which point you are between 0 and 2 units away from your opponent.

The key is, how does the computer to trick you from getting further away from it. When it moves, it still has to give you a coordinate +/- 1 unit of the actual location, and your only choice is to move towards that location.

So let's say that you make exactly the wrong choice and you are at -1, 0 and the computer is at 1,0. (For all purposes, you are always at 0 and the computer is at 0 +/-1).

At this point, your only choice is to move towards the reported coordinate that the computer gave you, and at that point, you will always be pointing yourself at the computer's reported coordinate. It is the only information that you have.

I think you can finish the game guaranteed and be less than 2 units away.

Reminds me of another simple yet unsolved problem in mathematics. I'll make a separate thread for it.

Even something like straight path for x along the x axis and you putting your course 1 unit to the left and one unit to the right of your path would generate deviations but as the computer you would only do this is you as the follower can't figure out what you're doing. But even if you did figure out what you were doing you would just continue deviating your path.

I'm thinking about the math about this.

It says can you guarantee you'll be within 100 distance from the computer. In other words, we have to try to find a way where, with the worst conditions for us (although we play optimally), we end up more than 100 distance from the computer.

The worst condition for us is when the computer always gives us the worst information. Conversely, the best information would be something like this:

Computer starts: (0,0)

Computer moves: (-1, 0)

Computer says: (-2, 0)

At this point, you know exactly where the computer moved, because his only possible move such that he says (-2, 0) is the initial move to (-1, 0)....any other position he moved to, he would not be able to say (-2, 0) is within 1 distance.

The worst case scenario for this point is when the computer says (0, 0) is within 1 distance from him. Any other point he says, we'd gain some information on where he is. For instance, if he says (-0.5, 0) is within 1 from him, then we know he cannot be further east(?) than (0.5, 0).

For the worst case scenario, we also have to assume the computer will move 1 unit directly away from us (I think? actually probably not), even though we, as the player(s) or at least our strategy, cannot assume this.

Unfortunately, I can't think of exactly how a strategy would work well. I'm assuming it's going to be to try to move as close to where the computer would be (duh?), given you have information on where he was and now is, within 1 distance.

However, there's a bit of a problem, and that's the game goes on for 1,000,000,000 moves. Over that many moves, you have to be at or within 100 distance from the computer. If my math and logic are correct, this means if you average a distance loss between the computer and yourself of 10^-7 per move for the entire 10^9 moves, then you'll be at exactly 100 distance from the computer.

My guess: No, you cannot guarantee you'll be within 100 distance of the computer at the end of the 10^9 moves.

I'll just pass, cuz even presuming an average error in distance of 1/e gets rather dynamic rather quickly. But I'll guess that it has something to do with the inverse Lambert function and squaring the result as an average radius of error.

JMHWAG of 86.4

98

Quote:98ClubsAfter reading the word problem, it appears that the computer moves in a radius of 1, then places the Contestant at or within a radius of 1 from the the computer's new position. The Contestant then moves a radius of 1 from the placement point. How friendly is this computer? How random is this computer? Does the computer learn (AI)?

I'll just pass, cuz even presuming an average error in distance of 1/e gets rather dynamic rather quickly. But I'll guess that it has something to do with the inverse Lambert function and squaring the result as an average radius of error.

JMHWAG of 86.4

98

The question asks if you can GUARANTEE you'll be within 100 distance of the computer's location. So, it doesn't matter how random or not-random it is. You only need to show one case where you cannot be within 100 distance to show you can't guarantee being within 100 distance. It doesn't ask how likely it is to happen.

The third report would narrow it down even more. I think by moving toward the center of the triangular pyramid formed by the last four reported coordinates, you will be able to stay within a sphere 100 moves in diameter of actual.

Thanks for an interesting problem. Is the computer, perhaps using game theory, trying to get away or does it pick randomly. For instance if it moved to (1,0) and you moved to (-1,0) then it would move (possibly with some probability) to (2,0) and report something like (1.7,0.7) to try and send you in the wrong direction. It seems reasonable that your best move is to go towards the reported point by 1 unit, and the puzzle is can the computer get away.Quote:ThatDonGuy....The computer moves to a new location...at the end of the 109th turn, [will] your location will always be distance 100...

Also just to confirm, is the question that after POWER(10,9) turns you can be within 100 of the computer? Thanks.

Edited - lots of people above updated the thread - so added this.

My guess is that the computer will always move 1 away from you (to do anything less is making the distance nearer). It will then report a point at (about) right angles to you - technically it's where the position sends you furthest off course,

With large values of the distance between you were L ("long distance") apart but have now got about 1/(L^2) further away.

While this "about" isn't good enough as it underestimates the difference, it seems that the computer can get away.

However I'm not sure how to prove it without a (logical) spreadsheet except it appears the computer gets one further away roughly every L^2+L+1. So if it's 100 away, then in 10,101 goes it would get 101 away.

If your strategy is to point yourself at the computer's known position then you would be deviating up and down each time getting further and further behind.

Now this is why I asked whether you assumed game theory - because if you know the computer is always going to be consistent, then you could calculate more accurately where it is. For instance your worst case scenario is going to (-1,0) while it has gone to (1,0). On the 2nd move it goes to (2,0) and reports (2,1). Your correct strategy is actually to head back to (0,0) - you then know you're not more than 2 away. Thus the computer shouldn't report (2,1) but something else!

Quote:BobDancerDoesn't being on an infinite plane preclude spheres?

Circles. Damnit, I meant circles, or two dimensional spheres!

Quote:charliepatrickSay you move the grid system so you are at (0,0) and the computer at (say) (50,0). The computer moves to (51,0) then it could report (roughly) (51,1) or (51,-1). However if it reported (50,1) last time and now flips to (51,-1) then you would know where the computer is.

Now this is why I asked whether you assumed game theory - because if you know the computer is always going to be consistent, then you could calculate more accurately where it is. For instance your worst case scenario is going to (-1,0) while it has gone to (1,0). On the 2nd move it goes to (2,0) and reports (2,1). Your correct strategy is actually to head back to (0,0) - you then know you're not more than 2 away. Thus the computer shouldn't report (2,1) but something else!

Well it is always going to go one unit away from you. If you start thinking game theory, then the computer should just randomly pick one unit up or down from you. In that way, you couldn't assume an average and would have to go for the direction because you can't predict which one it will choose.

Let's say the game as been played awhile. Let's define a set of coordinates relative to YOUR position. Let's say the current state is:

You: (0,0)

Computer: (50,0)

The computer tries to both distance himself from you and throw you off to the side by moving to (51,0) and reporting (51,1).

The angle you should pursue the computer is atan(1/51) = 0.019605331 (in radians).

Your move should be to (0.999807822,0.019604075), again in radians.

Given that the computer is actually at (51,0), the distance between you is now 50.00980298.

So, over time, this distance would increase. However, at some point would it reach an equilibrium? Let's see what would happen if the computer were 500 units away and repeated the same strategy. Again, readjust the coordinates so you're at (0,0)

The angle you should pursue the computer is atan(1/501) = 0.001996005 (in radians).

Your move should be to (0.999998008,0.001996004), again in radians.

Given that the computer is actually at (501,0), the distance between you is now 500.000998.

So, the computer is still getting away from you. Remember, the computer knows your position. I don't immediately see how the computer just can't keep adding to his distance minute amounts every time.

Sorry, but but this post adds nothing of value to the discussion.

I'm guessing the player may be able to play better by looking for a pattern, but I can't see a strategy better than going towards the computer's reported place.

(Trial no., Player X, Player Y, Computer's position, New Distance.)

X: 19 PX: 0.9697950116046666 PY: 0.2439213714841422 CX: 3.9758509297645324 ND: 3.0159359772002223

X: 52 PX: 0.9805211694567034 PY: 0.19641343194206107 CX: 4.992128897508099 ND: 4.016413175957989

X: 103 PX: 0.9863847731292482 PY: 0.16445388210304296 CX: 5.997941553676444 ND: 5.014254325818281

X: 175 PX: 0.9899166840088099 PY: 0.14165083381682625 CX: 6.988428217012168 ND: 6.000183794709567

...

X: 637194 PX: 0.9999489887003615 PY: 0.010100494895005084 CX: 98.99999941536115 ND: 98.0000509471707

X: 656797 PX: 0.9999500037417145 PY: 0.009999500834789662 CX: 99.99999202587678 ND: 99.00004252713492

X: 676798 PX: 0.9999509887862765 PY: 0.009900506317758177 CX: 100.99998491922588 ND: 100.00003442053956

First, given that the opponent is a computer and must be guided by a rule-based algorithm, is there an optimum algorithm or set of rules to give the computer such that it maximizes separation, and what is it?

- needs to cover where to move and what (false) position to report

Secondly, how do you counter the algorithm to minimize the growth of separation, what is your chase algorithm.

Chase algorithm: I think that the player cannot do better than to move one unit directly towards the last reported position.

Computer flight algorithm:

Definitions: a

_{n}= the computers position (coordinates) after n moves

b

_{n}= the computer's (false) reported position (coordinates) after n moves

The computer's first move is in a random direction away from (0,0) The computer's first reported position is (0,0) so as to minimize information. Here are two possible algorithms to stimulate the discussion.

Algorithm A

1. On subsequent moves the computer must move 1 unit in a direction that maximally increases the separation from the players latest position.

2. After its nth move, the computer must report a b

_{n}that is as close as possible to b

_{n-1}because this minimizes the information given to the player.

Algorithm B

Based on player's current position, the computer must pick a combination of a new location a

_{n}and a new reportable location b

_{n}such that when the player moves one unit directly towards b

_{n}it maximizes the separation distance from a

_{n}

I think if you develop the algebra for Algorithm B, and then extend its logic for n steps into the future (like a chess computer looking n moves ahead) you will develop a flight algorithm and an expression for maximum distance from the player that converges on some finite number.

Let the computer be L units ahead of the player at C (L,0). It moves to C' at (L+1,0) and reports (L+1,1).

The player proceeds from A (0,0) and after traveling 1 unit gets to position X.

Since the distance AC' = L+1 and the computer says it's 1 away, the Y co-ordinates of the player's position is approx 1/(L+1).

The angle alpha (BAX) is therefore 1/(L+1). Construct two triangles to show that XBY = alpha/2.

Thus XY is about BY * (aplha/2) = 1/(L+1) * 1/2(L+1) = 1/2*(L+1)^2.

Using similar logic shows that beta = 1/L(L+1), so YZ is of order 1/2(L+1)(L+1), i.e of order L^(-3), so can be ignored.

Thus when the computer is L units away the difference increases each turn by about 1/2(L+1)(L+1).

NOTE: The next move has L increasing by the small amount, thus it is not the total of 1/N^2 (which = pi^2/6), but there are multiple turns before L increases by 1.

I am guessing that if the delta is 1/2 L^-2 then the total is the sum of 1/2 N^-1, and this keeps growing.

X: 767 PX: 0.9958907041363316 PY: 0.09056326746999395 CX: 10.996629560282782 ND: 10.001148902713743

X: 5748 PX: 0.9988681228513349 PY: 0.047565461749577584 CX: 20.999861792789293 ND: 20.001050228876725

X: 44310 PX: 0.9997026901599955 PY: 0.02438301225993199 CX: 40.99996667773417 ND: 40.00027141916553

X: 347835 PX: 0.9999238007552851 PY: 0.012344743136443827 CX: 80.99996814055501 ND: 80.00004529225346

X: 2756487 PX: 0.999980711177106 PY: 0.006211060596153274 CX: 160.99999278648622 ND: 160.0000121958631

X: 21948192 PX: 0.9999951475978428 PY: 0.0031152497120672776 CX: 320.99999679776766 ND: 320.00000166533357

X: 175173204 PX: 0.9999987831048686 PY: 0.0015600605058695564 CX: 640.9999992580307 ND: 640.0000004768273

X: 999439751 PX: 0.9999996186192375 PY: 0.0008733621124956036 CX: 1144.9999997844782 ND: 1144.0000001661922

Oh, wow ... that must be the ultimate.Quote:ThatDonGuyBesides things like proving Fermat's Last Theorem, that is...

Anyway, at this year's International Mathematical Olympiad,

I have trouble with addition (with subtraction too, but its rare to need any of that). Getting to 21 with confidence and a measure of speed that does not cause premature baldness amongst the other Blackjack players is extremely difficult for me. I don't 'know' that 8 and 3 are 11 but I can quickly count 8, 9, 10, 11 under my breath. 8 and 5 is a bit more of a challenge though. You can see perhaps why BJ dealers don't particularly care for my action. This character defect is also the reason I was so happy to hear of a variant table game wherein the goal is not 21 but 11. I might be able to get the hang of that without too much difficulty.

Infiniate planes, rational, integers, ... it may be rational but it doesn't make sense to me.

Some artists pour molten aluminum down an anthill to obtain a sculpture of ant tunnels but I believe most foraging behavior is individualized and is the basis of 'swarm behavior' for robots. Kairomonens play an important role as to ant doorkeepers that dab departing ants and sense a failure to return in some which will result in a diminished use of a particular trail.Quote:onenickelmiracleI'm wondering if perhaps these kinds of unsolved math problems have already been solved by mother nature. Thought about this after disturbing an ant hill the other day, the ants seem to have a search pattern down pat.

Never mind, I found it, ya siwwy wabbit.

I've heard people claim plants use complex math in their growth, but have never looked into it.Quote:FleaStiffSome artists pour molten aluminum down an anthill to obtain a sculpture of ant tunnels but I believe most foraging behavior is individualized and is the basis of 'swarm behavior' for robots. Kairomonens play an important role as to ant doorkeepers that dab departing ants and sense a failure to return in some which will result in a diminished use of a particular trail.

Quote:onenickelmiracleI've heard people claim plants use complex math in their growth, but have never looked into it.

Your comment reminded me of a TED talk on this; it was about coral, which isn't exactly plants, but I think is the concept, and expands into all nature. While the whole thing is worth viewing, the lecturer has a very pointed (feminist and climatology) context in the intro that will be a turn-off to several here, so I recommend you skip to the 5 minute mark, where she discusses hyperbolic geometry in very accessible and graphical detail. Trust me; it's worth a viewing.

https://www.ted.com/talks/margaret_wertheim_crochets_the_coral_reef/up-next#t-915933

Yes, it's about crochet, but as a physical manifestation of modeling hyperbolic space which, according to her, was previously considered not possible due to the limitations of 3-dimensional projections and models.

Much of nature does, if not all of it. Mandelbrot sets, etc. Canopy leaves not touching each other, mollusk growth, snake skins, armor cells, parrot fish and coral erosion. Heck, even Face's interest in Pythons reflects their coloration and scale growth in several different wavelengths.Quote:onenickelmiracleI've heard people claim plants use complex math in their growth, but have never looked into it.