ThatDonGuy
Joined: Jun 22, 2011
• Posts: 3043
August 2nd, 2017 at 12:01:53 PM permalink
Quote: Dalex64

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

The question on their website is after 109 rounds can the distance be at most 100

My bad - I cut and pasted it, and it came out 109.
ChesterDog
Joined: Jul 26, 2010
• Posts: 581
August 2nd, 2017 at 6:14:26 PM permalink
I find that I cannot keep my distance to the computer less than 100 after 10^9 rounds.

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.)
boymimbo
Joined: Nov 12, 2009
• Posts: 5276
August 2nd, 2017 at 6:24:56 PM permalink

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.
----- You want the truth! You can't handle the truth!
Wizard
Joined: Oct 14, 2009
• Posts: 16474
August 2nd, 2017 at 7:36:35 PM permalink
I understand what is being asked. I just have no idea how to solve it.

Reminds me of another simple yet unsolved problem in mathematics. I'll make a separate thread for it.
It's not whether you win or lose; it's whether or not you had a good bet.
boymimbo
Joined: Nov 12, 2009
• Posts: 5276
August 2nd, 2017 at 8:29:28 PM permalink
Chester, having read your spoiler, I am trying to graph out the computer's ideal pattern given that it is trying to deceive you. For example, if the computer was to plot a course 100% away from you everytime and gave a coordinate that would mislead you the most you would develop a zig zag pattern where each time you are getting slightly further ahead as the computer deviates your path a little more each time, to the point where you are travelling a straight line and deviating your course left and right each time to make you deviate slightly from true. To do this you draw out a circle that is one unit out from your path on each side of your path and put your course at exactly the end point of the path that would result in you making your worse course deviation.

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.

----- You want the truth! You can't handle the truth!
RS
Joined: Feb 11, 2014
• Posts: 5558
August 2nd, 2017 at 8:58:20 PM permalink
I think it makes sense to break the problem down. I think I failed Math Logic in college like 3 times, so maybe I'm not the best at this, buuuut ---

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.
"should of played 'Go Fish' today ya peasant" -typoontrav
98Clubs
Joined: Jun 3, 2010
• Posts: 1716
August 5th, 2017 at 8:03:53 PM permalink
After 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
Recent epitaph: Found dead by a Pokemon Go Player
RS
Joined: Feb 11, 2014
• Posts: 5558
August 6th, 2017 at 3:28:50 AM permalink
Quote: 98Clubs

After 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.
"should of played 'Go Fish' today ya peasant" -typoontrav
Ayecarumba
Joined: Nov 17, 2009
• Posts: 5393
August 6th, 2017 at 7:14:41 AM permalink
Won't you have better information as more coordinates come in from the computer? Each report creates a sphere of possibilities for the computer's actual position. The first report will create a perfect sphere 2 moves in diameter, but when the second report is received, it will eliminate a certain amount of the possibilities available after the first, since some of the original possibilities would not be true if both reports have to be true. By observing where the eliminated positions are located, you should have a better idea of the computer's actual position, and move toward it. Note that this will not always be toward the last reported position.

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.
America is all about speed. Hot, nasty, bad-ass speed. - Eleanor Roosevelt, 1936
charliepatrick
Joined: Jun 17, 2011
• Posts: 1321
August 6th, 2017 at 8:23:13 AM permalink
Quote: ThatDonGuy

....The computer moves to a new location...at the end of the 109th turn, [will] your location will always be distance 100...

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.
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.
Last edited by: charliepatrick on Aug 6, 2017