World's Hardest (non-calculus) Math Problem?
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 109 (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 109 (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?
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?"
DUHHIIIIIIIII HEARD THAT!
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.
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
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.
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
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.
Simplicity is the ultimate sophistication - Leonardo da Vinci
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 109 rounds can the distance be at most 100
The question on their website is after 109 rounds can the distance be at most 100
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.
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
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 109 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!'"
August 2nd, 2017 at 12:01:53 PM
permalink
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 109 rounds can the distance be at most 100
My bad - I cut and pasted it, and it came out 109.
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.)
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.)
August 2nd, 2017 at 6:24:56 PM
permalink
0,0 are just starting reference numbers. I think about this.
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.
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!
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.
Reminds me of another simple yet unsolved problem in mathematics. I'll make a separate thread for it.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
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.
I'm thinking about the math about this.
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.
-----
You want the truth! You can't handle the truth!
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.
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.
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
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
Some people need to reimagine their thinking.
August 6th, 2017 at 3:28:50 AM
permalink
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.
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.
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.
Simplicity is the ultimate sophistication - Leonardo da Vinci
August 6th, 2017 at 8:23:13 AM
permalink
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.
Last edited by: charliepatrick on Aug 6, 2017
August 6th, 2017 at 1:23:48 PM
permalink
The logical move from the computer would be to move directly move away from you and then report its position such that it maximizes the deviation of your path, which to me, seems to be at the top or bottom of a sphere (as any other would cause you to deviate less), alternating each time.
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.
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.
-----
You want the truth! You can't handle the truth!
August 6th, 2017 at 1:49:06 PM
permalink
Doesn't being on an infinite plane preclude spheres?
August 6th, 2017 at 2:02:39 PM
permalink
Say 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!
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!
August 6th, 2017 at 6:19:09 PM
permalink
Quote: BobDancerDoesn't being on an infinite plane preclude spheres?
Circles. Damnit, I meant circles, or two dimensional spheres!
-----
You want the truth! You can't handle the truth!
August 6th, 2017 at 6:21:10 PM
permalink
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.
-----
You want the truth! You can't handle the truth!
August 7th, 2017 at 7:29:30 AM
permalink
I investigated this idea of just following the computer's last reported position, as it can never be far from his true position...
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.
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.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
August 7th, 2017 at 10:35:57 AM
permalink
^ The case you have is similar to mine - so I've run it through a program and the computer continues to get away. (I've used right angled triangles and sqrt.) Essentially the fractions the computer gains each turn don't decrease enough to stay under 100. Assuming you return to (0,0) thus ensuring you are 2 away and the computer moves to (3,0) reporting (3,1) then it subsequently takes 676798 turns to reach a distance of 100.
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.
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
August 7th, 2017 at 11:31:56 AM
permalink
I've toyed around with some other player strategies but nothing seems better than heading right towards the last stated position. It seems to be logical that if you know somebody is within radius 1 of point x, then you head straight towards x if the object is to minimize the distance between your point and his.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
August 7th, 2017 at 11:46:25 AM
permalink
I think there are two very interesting parts to this problem.
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: an = the computers position (coordinates) after n moves
bn = 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 bn that is as close as possible to bn-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 an and a new reportable location bn such that when the player moves one unit directly towards bn it maximizes the separation distance from an
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.
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: an = the computers position (coordinates) after n moves
bn = 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 bn that is as close as possible to bn-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 an and a new reportable location bn such that when the player moves one unit directly towards bn it maximizes the separation distance from an
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.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
August 7th, 2017 at 2:29:38 PM
permalink
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
August 7th, 2017 at 7:40:05 PM
permalink
As the pursuer, you have more than just the last reported false position to work with. The computer is constrained to move one space each turn, and you know that at every report the actual position is within one space or less: Why doesn't analysis of the previous reports provide triangulation, and therefore a better idea of the computer's actual position compared to just moving toward the last reported position and ignoring the deductions available from all the available info?
Simplicity is the ultimate sophistication - Leonardo da Vinci
August 8th, 2017 at 9:50:31 PM
permalink
I'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.
I am a robot.
August 9th, 2017 at 12:22:02 PM
permalink
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.
August 9th, 2017 at 12:26:51 PM
permalink
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.
August 13th, 2017 at 2:52:19 AM
permalink
Where did you find this devilish problem? I can't find it anywhere.
Never mind, I found it, ya siwwy wabbit.
Never mind, I found it, ya siwwy wabbit.
August 13th, 2017 at 8:19:23 AM
permalink
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.
I am a robot.
August 13th, 2017 at 8:53:17 AM
permalink
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.
If the House lost every hand, they wouldn't deal the game.
August 13th, 2017 at 12:54:19 PM
permalink
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.
