Results 1 to 30 of 79
-
2019-04-06, 08:02 PM (ISO 8601)
- Join Date
- Jan 2014
Finding a point in an infinite space
There is a plane where the X-axis goes from -∞ to ∞ and where the Y-axis goes from -∞ to ∞. You know that somewhere on the plane is a point whose X and Y values are both whole numbers. Your goal is to find this point, but you can only ask yes/no questions about the point; there's no limit on how many such questions you can ask, nor on the complexity of the questions, save that they must be answerable with a binary "yes" or "no" answer. Can you find the point, and if so what is your method?
Last edited by AvatarVecna; 2019-04-06 at 08:08 PM.
Currently Recruiting WW/Mafia: Logic's Deathloop Mafia and Cazero's Graduates Of Hope's Peak - Danganronpa Mafia
Avatar by AsteriskAmp
My Homebrew
-
2019-04-06, 09:00 PM (ISO 8601)
- Join Date
- Nov 2007
- Location
- Indianapolis
- Gender
Re: Finding a point in an infinite space
Pretty easy; "is the y coordinate greater than 0?" Repeat for x. Now you know which quadrant it's in. Repeat basically the same questions, increase the number you ask about by.. Oh a billion or so until you get a broad zone to narrow into. There's probably a more efficient algorithm, but it's not hard to do.
-
2019-04-06, 10:01 PM (ISO 8601)
- Join Date
- Jan 2014
Re: Finding a point in an infinite space
That such a method can theoretically work for a vast number of points is obvious, but it runs into issues because of the nature of the infinite plane. Your own example does a good job of highlighting one of the issues I had in coming up with an answer myself, which is that any individual question cannot be more efficient than eliminating half of all possible points (that is to say, each question is at its most efficient when "yes" and "no" both correspond to half the remaining points, so that no matter what the point is, each question will eliminate half of the remaining possibilities). Your example shows this off well, in that your first two questions each divide the field in two, but your q3, q4, and so on are much tinier slivers of the whole. Q3 "is the Y coordinate greater than 1 billion" for example would eliminate either "1 billion" possibilities (if the answer is yes) or "∞ - 1 billion" possibilities (if the answer is no), and that second part is the problem: if the answer is no, your question has accomplished not quite nothing, but about as close to nothing as a question can accomplish. But then, what are the odds that the answer will be "yes" instead of "no", that we will eliminate everything except a billion possibilities rather than merely eliminating a billion possibilities? It's clearly not a 0% chance that the answer will be yes, but it's trending towards 0, which is the problem.
And that's true whether the large number you increased by is one billion, one septillion, one google, one googleplexion, or any other non-infinite number; it doesn't matter how big the number you're increasing by is, infinite is infinitely bigger. If each of an infinite series of questions can only eliminate an infinitesimally small sliver of the remaining possibilities, can the point always be found? Even if the method is refined in such a way that you exactly eliminate half of all remaining possibilities, does dividing infinite by 2 produce something besides infinite, if done enough times?
Currently Recruiting WW/Mafia: Logic's Deathloop Mafia and Cazero's Graduates Of Hope's Peak - Danganronpa Mafia
Avatar by AsteriskAmp
My Homebrew
-
2019-04-06, 11:17 PM (ISO 8601)
- Join Date
- Dec 2010
Re: Finding a point in an infinite space
Do you have a countably infinite or uncountably infinite number of questions? If countably infinite, then sort the points into a line (for instance, by 2pi * distance first and then by angle) and ask one by one. That will take an infinite number of questions, but it's no less efficient than any other method that requires an infinite number of questions.
-
2019-04-06, 11:18 PM (ISO 8601)
- Join Date
- May 2007
- Location
- Tail of the Bellcurve
- Gender
Re: Finding a point in an infinite space
A constructive method for locating the point is to do the following for each coordinate:
1) ask "is the number zero" If it isn't continue
2) ask "is the number positive?". Store the sign somewhere, and continue
3) set n = 1
4) ask "is the nth in the number's binary representation one?"
5) ask "is there a n+1st term in the number's binary expansion?" If yes, set n = n + 1, return to step 3. If not, you are done.
Repeat steps 3 and 4 until there isn't a next term. When you finish, you will have the binary representation of the number, hence the number. This method is guaranteed to terminate in no more than 2 + 2*d steps, where d is the number of digits in the binary representation.
(Finding the point is, mathematically speaking, trivial. The cardinality of whole number pairs in R2 is countably infinite. Since you get unlimited questions, simply diagonalizing your way through all (x, y) pairs of whole numbers will get you the solution. However that answer's no fun at all.)Blood-red were his spurs i' the golden noon; wine-red was his velvet coat,
When they shot him down on the highway,
Down like a dog on the highway,And he lay in his blood on the highway, with the bunch of lace at his throat.
Alfred Noyes, The Highwayman, 1906.
-
2019-04-06, 11:18 PM (ISO 8601)
- Join Date
- Aug 2018
- Location
- six feet under
- Gender
Re: Finding a point in an infinite space
If you can only ask a finite number of questions, no the point can not be found in general. Otherwise, well...
My method would be to ask about the factors of coordinates. Start with "is the x factor divisible by 2" which eliminates half the points. Then ask if it is divisible by 3, if the answer is no, and 3 * 2 if the answer is yes. Repeat for all primes. Because each number is uniquely factor able into primes I think you would get the answer. I suspect it would take ω steps though.
Edit: I like warty goblins method too.
—CaeruleaLast edited by Caerulea; 2019-04-06 at 11:20 PM.
Non caerulea sum, Caerulea nomen meum est.
Extended Signature.
I'm not not a humanoid. Come not not be one too.
Answer trivial questions in the OOTS trivia thread!
she/her
-
2019-04-06, 11:21 PM (ISO 8601)
- Join Date
- Nov 2007
- Location
- Indianapolis
- Gender
Re: Finding a point in an infinite space
Your search space is infinite, but the value you are looking for is not, which means we can ask useful questions about it regardless of the infinities. How about something like "Assuming Times New Roman in a 12-point print, can the (x or y) coordinate be printed in its entirety on a single line of a standard 8.5 x 11 page of printer paper?" If not, ask again, but use scientific notation. If still no, go to whatever your favorite method of rotating excessively large numbers is. That will eventually get you a (admittedly very, very broad) placement of at least the magnitude of the number you are looking for, and once have that you can refine further...
Or if want to brute force the whole process "Is the (nth) digit (0-9)? Is there an (n+1th) digit? Is the (n+1th) digit (0-9)?" Iterate until you are told there aren't any more digits. Super tedious, sure, but also the sort of thing that's really straightforward to feed into a computer and just come back later to check the progress.
-
2019-04-06, 11:59 PM (ISO 8601)
- Join Date
- Jan 2014
Re: Finding a point in an infinite space
Hmm...the point about countable infinities vs uncountable is I think the stumbling block that was making it difficult for me to wrap my head around, but different degrees of infinite makes it a bit easier. Would an uncountably infinite number of questions be insufficient to determine the point if it was "numbers" instead of "whole numbers", since that opens up fractions and irrationals and makes the problem also an uncountable infinite, or is the uncountable infinite of the problem still not so large that the uncountable infinite of the solution couldn't solve?
Currently Recruiting WW/Mafia: Logic's Deathloop Mafia and Cazero's Graduates Of Hope's Peak - Danganronpa Mafia
Avatar by AsteriskAmp
My Homebrew
-
2019-04-07, 12:22 AM (ISO 8601)
- Join Date
- Dec 2010
Re: Finding a point in an infinite space
A countably infinite number of questions can find the point (and, relatedly, rationals (fractions) are countably infinite).
An uncountably infinite number of questions can determine the point if it's 'numbers', though 'uncountably infinite discrete objects' (e.g. questions) seems a bit of a suspect construction in its own right and probably requires a bit more care than I'm giving it. To be more careful, I think one would want to define a dense manifold of questions and then ask whether there's some aggregation function that collects the answers which identify the point uniquely from the manifold - e.g. the questions are given by Q(x,y) = delta( (x,y) - (point_x, point_y) ) and the location of the point is the integral dx dy (x,y) * Q(x,y).
-
2019-04-07, 03:13 AM (ISO 8601)
- Join Date
- Oct 2014
- Location
- Tulips Cheese & Rock&Roll
- Gender
Re: Finding a point in an infinite space
I think Tyckspoon's method gets a bit better if you start using powers. Don't divide the grid into blocks one billion by one billion, but rather 9 zeroes by 9 zeroes. The number, assuming it was picked by a human, is likely to be relatively small, so it makes sense to have a finer search grid in the low numbers, and expand it from there.
This is still not fast enough to find something like Graham's number (or rather the coordinate Graham's number by -(Grahams number/pi)^146-77854) on a human asking questions timescale, but at that point I think even the most elegant methods will struggle.Last edited by Lvl 2 Expert; 2019-04-07 at 03:16 AM.
-
2019-04-07, 05:20 AM (ISO 8601)
- Join Date
- Jan 2007
Re: Finding a point in an infinite space
Instead, project the infinite plane on a finite one using any bound analytic function like for example ArcTan. For whole numbers this should be as fast as warty goblin's algorithm, since it also uses splitting the plane in halves regarding the specific digits in binary representation.
By using more general questions and slicing the scaled down infinite plane in a natural geometric way, one can approximate any sought number much faster and obtain any desired precision in finite time even if we consider any real number pairs. Cosidering how real numbers are constructed as a limit of rational sequences, we will also obtain exact result in countable infinite questions as well.Last edited by Radar; 2019-04-07 at 05:21 AM.
In a war it doesn't matter who's right, only who's left.
-
2019-04-07, 08:49 AM (ISO 8601)
- Join Date
- Feb 2015
Re: Finding a point in an infinite space
Let's be clear here though, the number of questions required to reach a desired precision (in the original infinite space) depends on the point being sought. You can't say, give me an epsilon, and I will give you an N that will work for all (x,y) points. After N questions there are some points that share all answers with points arbitrarily larger.
-
2019-04-07, 11:50 AM (ISO 8601)
- Join Date
- Jan 2007
-
2019-04-07, 03:54 PM (ISO 8601)
- Join Date
- Sep 2016
Re: Finding a point in an infinite space
[Merging a couple of cases given above and hopefully being a bit more explicit. Radar pretty much said the first 2 paragraphs, while the uncountable case was mentioned by Davidsh ]
For something like the integers. If you have an finite range (x), you are never going to get better than Log2(x) on average, as that differentiates at most x numbers. On the other hand you can get the exact number in Log2(x) via fairly trivial methods (binary chop)
You can trivially get the upper bound for a number (y) in the same time by working upwards, if you use faster growing strategies you save time here, but then your upper bound is crazily high (and the lower bound crazily low), I suspect there are ways to optimize that.
IIUC the binary expansion given by Warty Goblin didn't explicitly terminate, but actually that might be the most efficient way round. Explicitly asking if you finish will get you the number in exactly Log2(x) but if you use a probabilistic approach so you only ask after a suspicious amount of zeros you could probably get much closer to Log2(x).
For a plane you can basically do the 2 co-ordinates separately. You could probably save some steps by finding the (approximate) hypotenuse and then the smallest co-ordinate.
Fractions get a bit more awkward. Treating X/Y as X,Y will of course work, or alternatively (and possibly more elegantly) continuing the binonial chop the other way until it's confirmed as repeating. But it feels (as a non-serious-mathmo) ugly. In the integer case, the bigger number takes a little more time, but it's a much bigger number so you'd expect it too. Anything better than linear seems reasonable too me. In the fractions case between any two fractions, there will be a fraction that will take a (countably) infinite amount of time to resolve but is also infinitesimally close.
Irrational numbers, even a countably-infinite number of separations leaves an uncountably-infinite set of numbers in at least one 'box'. You could get arbitrarily close by continuing binary chop.
Fairly given computational numbers I think I'd do binary chop for a decent while, then see if I can recognize it (doing some unofficial questions of my own). If sqrt[2]+10-1000 is fair game then I don't see a sensible way out unless there are clear limits. [ETA revised credit statements, and also in this case I'd ask them to write it down in words then build up the sentence letter by letter-sorted!!
[10th Edit, Warty Goblin's method does of course include a termination. But not in the bits he repeats :sillyme:Last edited by jayem; 2019-04-07 at 04:08 PM.
-
2019-04-07, 06:59 PM (ISO 8601)
- Join Date
- Jan 2007
Re: Finding a point in an infinite space
Actually even in continuum interval (or plane - doesn't matter) you can get an exact number after countable infinity of binary chops, since this is a consequence of the very definition of real numbers - more specifically the construction from Cauchy sequences. Getting arbitrarily close after countable infinite steps becomes an exact solution.
In a war it doesn't matter who's right, only who's left.
-
2019-04-09, 01:36 PM (ISO 8601)
- Join Date
- Oct 2010
- Location
- Dallas, TX
- Gender
-
2019-04-09, 04:15 PM (ISO 8601)
- Join Date
- Dec 2009
- Location
- Birmingham, AL
- Gender
Re: Finding a point in an infinite space
I set the origin at -X, -Y away from a chosen spot, declare that I have thus found the exact point required, and take the trophy (I assume there's a trophy involved) for finding it in 0 questions.
Cuthalion's art is the prettiest art of all the art. Like my avatar.
Number of times Roland St. Jude has sworn revenge upon me: 2
-
2019-04-09, 04:58 PM (ISO 8601)
- Join Date
- Dec 2007
- Location
- San Antonio, Texas
- Gender
Re: Finding a point in an infinite space
(emphasis added)
We already know which quadrant it's in; they're whole numbers, so they must be a positive integer or 0. No other quadrant is possible, unless the OP is edited to say "the absolute value of their X and Y values are whole numbers."The Cranky Gamer
*It isn't realism, it's verisimilitude; the appearance of truth within the framework of the game.
*Picard management tip: Debate honestly. The goal is to arrive at the truth, not at your preconception.
*Mutant Dawn for Savage Worlds!
*The One Deck Engine: Gaming on a budget
Written by Me on DriveThru RPG
There are almost 400,000 threads on this site. If you need me to address a thread as a moderator, include a link.
-
2019-04-10, 12:09 AM (ISO 8601)
- Join Date
- Oct 2014
- Location
- Tulips Cheese & Rock&Roll
- Gender
Re: Finding a point in an infinite space
The Hindsight Awards, results: See the best movies of 1999!
-
2019-04-10, 11:39 AM (ISO 8601)
- Join Date
- Feb 2016
Re: Finding a point in an infinite space
If the potential number of questions is infinite as well most if not all of those issues should be negated in theory, shouldn't they?
EDIT:
Now that I think of it, maybe not. If the space is continuous then the number of points is uncountably infinite whereas the number of questions must be countably infinite. It should work in an infinite grid of integer coordinates thoughLast edited by Bohandas; 2019-04-10 at 11:41 AM.
"If you want to understand biology don't think about vibrant throbbing gels and oozes, think about information technology" -Richard Dawkins
Omegaupdate Forum
WoTC Forums Archive + Indexing Projext
PostImage, a free and sensible alternative to Photobucket
Temple+ Modding Project for Atari's Temple of Elemental Evil
Morrus' RPG Forum (EN World v2)
-
2019-04-10, 01:13 PM (ISO 8601)
- Join Date
- Jan 2007
Re: Finding a point in an infinite space
With countable infinity of questions one can still pinpoint a... well... point within the continuum. It is the basic concept behind the very construction of real numbers in the version by Cauchy where a real number is defined by a class of convergent sequences, which also are convergent if you essentially mix them up with each other.
With the yes/no questions one finds and refines upper and lower bound for the sought number. Subsequent values of those bound form a sequence. Since we can assure that there is always a finite number of questions we need to make our precision arbitrarily good, then those upper and lower bound sequences converge to a single real number.In a war it doesn't matter who's right, only who's left.
-
2019-04-10, 09:01 PM (ISO 8601)
- Join Date
- Sep 2014
Re: Finding a point in an infinite space
Would that be equivalent to a graphical method where you start by asking if it's a solution to the inequality y>0 and then go on to define smaller and smaller regions using systems of inequalities? It seems like it would be simple to divide each existing half of the graph in half again using that sort of method and various y>mx type equations. This method seems interesting to me because your guessing keeps narrowing the search space while telling you very little about how far away either coordinate is from the origin (since we're only considering integers, we do gradually eliminate coordinates closer to the origin as no integer coordinates are found within that particular narrow slice).
-
2019-04-10, 09:23 PM (ISO 8601)
- Join Date
- May 2007
- Location
- Tail of the Bellcurve
- Gender
Re: Finding a point in an infinite space
I was thinking about methods like that, and how to extract information about the distance from the origin. An algorithm I had considered was something like this:
1: wlog, assume the point is in the first quadrant, since it only takes two questions to determine this.
2: ask if the point is above the line bisecting the quadrant. Regardless of the answer, you now have contained the point between two known rays at unknown distance. Call the lower ray r1 and the upper r2
3: Ask if the point is contained in a triangle determined by r1,, r2, and a line defining an isosceles triangle defined by r1 and r2 with the congruent legs of length, say, k!, where k is the number of questions you have asked.
4: If the answer is yes, exhaustively search the whole number pairs in the triangle.
5: If no, return to step 2, and bisect the angle determined by r1 and r2.
There's probably an additional way to make it clever, by trying to learn something about how far to jump, I just chose k! because it grows quite quickly, but it may be more efficient in some sense to pick a growth value that keeps the number of points in the triangle reasonably constant.Blood-red were his spurs i' the golden noon; wine-red was his velvet coat,
When they shot him down on the highway,
Down like a dog on the highway,And he lay in his blood on the highway, with the bunch of lace at his throat.
Alfred Noyes, The Highwayman, 1906.
-
2019-04-10, 10:16 PM (ISO 8601)
- Join Date
- Sep 2011
- Location
- Calgary, AB
- Gender
-
2019-04-10, 10:43 PM (ISO 8601)
- Join Date
- Aug 2011
Re: Finding a point in an infinite space
Right down the middle.
More seriously: what I think they're proposing is to ask if the point on the plane is above or below the line y=x. Let's assume its below y=x. Knowing this, we can form a triangle using y=x, the x axis (y=0), and the line y = -x + k!, where k is the number of iterations. Eventually the point will be contained by the triangle, and we can search the remaining space.
It's essentially the same as asking about the sum of |x| and |y| to constrain both x and y within some search space at the same time.
—
Since any number can be expressed through a unique prime factorization, another approach would be to ask about the prime factors of X and Y. From what I can tell from some back of the napkin scribbles, the best case could be reasonably fast, but the worst cases crawl to a snails pace.
EDIT: I didn't actually answer the question.
Bisecting an infinite plane is easy: any line on an infinite plane bisects that plane. If that sounds confusing, think of it this way: there is a one to one mapping for every point on one side of the line to a point on the other side (reflection over the line being the simplest mapping I can think of).Last edited by crayzz; 2019-04-10 at 10:55 PM.
Originally Posted by crayzzOriginally Posted by jere7my
-
2019-04-10, 10:55 PM (ISO 8601)
- Join Date
- Jun 2008
- Location
- New Zealand
- Gender
Re: Finding a point in an infinite space
The infinite 2D plane just complicates things. So get rid of that first. Draw a continuous square spiral starting at the origin:
(0, 0)
(1, 0)
(1, 1)
(0, 1)
(-1, 1)
(-1, 0)
(-1, -1)
(0, -1)
(1, -1)
(2, -1)
etc.
This line goes through all points (x, y) on the infinite plane, mapping them to position n an infinite line with n ≥ 0.
From there the trick of asking for each binary digit of n is more obvious, and I don't see any way of making it faster.
Edit: you can do this with a real number plane as well. Space-filling curves are a lot of fun. I think the step of asking for binary digits won't work the same for real numbers, as a finite irrational number will have an infinite number of digits after the decimal point, and no repeating pattern to them.Last edited by Excession; 2019-04-10 at 11:04 PM.
-
2019-04-11, 02:33 AM (ISO 8601)
- Join Date
- Sep 2016
Re: Finding a point in an infinite space
I think so, but I did it the other way round.
This I think has the potential to save some steps. Rather than having to do 2 rangefinder operations you only have to do 1.
So using doubling the descartes method takes log(X)+log(X)+log(Y)+log(Y) steps whereas the polar method takes about log(1.4*X)+log(1.4*X)+log(1.4*2P*X)
If X is about the same as Y you get 4 log(X) against 3 log(X) +C . (If Y is negligible you get 2 log (X) against 3 log(X) so it does lose out on the extreme edges)
However I think you can do rangefinding a bit better than that.
I think my way round (distance first) is slightly better than angle first as when you know the distance you know how many points are in the ring/diamond so you know when to stop (although alternating would be quite possible). I think to get the binary places to use diophantime equations would require as many steps as it saves.
The space filling curve looks like it may be even better to me than that, at first thought. Again you get the single range.
-
2019-04-11, 10:22 AM (ISO 8601)
- Join Date
- Dec 2007
- Location
- San Antonio, Texas
- Gender
Re: Finding a point in an infinite space
You get arbitrary.... sort of like Star Trek, actually.
The Terran System is Sector 001. There's no particular REASON for it to be 001; if they started at the galactic core, our sector would be far higher. But, they picked an arbitrary point (where they were standing) and declared that to be the center of their coordinate grid.
If I say "This point I occupy is 0,0,0 on an xyz coordinate space, pointing to X, Y, and Z, and defining the length of an integer of distance in that space, I can then define other objects in that X,Y,Z space, regardless of any other arbitrary system. My coworker's chair is 2,0,0, since it is 2 meters ahead of me, and neither right nor left nor above or below me. It is a purely relational statement... but if you're looking for a point in space, you've at least cut the infinity you had to search into 8, smaller, infinities.The Cranky Gamer
*It isn't realism, it's verisimilitude; the appearance of truth within the framework of the game.
*Picard management tip: Debate honestly. The goal is to arrive at the truth, not at your preconception.
*Mutant Dawn for Savage Worlds!
*The One Deck Engine: Gaming on a budget
Written by Me on DriveThru RPG
There are almost 400,000 threads on this site. If you need me to address a thread as a moderator, include a link.
-
2019-04-11, 10:30 AM (ISO 8601)
- Join Date
- Sep 2011
- Location
- Calgary, AB
- Gender
Re: Finding a point in an infinite space
But you'very already done that with the origin though, no? After narrowing it down to one of the 4 regular quadrants, you've effectively set boundaries that prevent proper bisecting. There will always be more of the infinite plane on the side opposite your line, so it's not halving anything, so much as dividing an area into 2 arbitrary pieces.
-
2019-04-11, 10:43 AM (ISO 8601)
- Join Date
- Dec 2007
- Location
- San Antonio, Texas
- Gender
Re: Finding a point in an infinite space
The Cranky Gamer
*It isn't realism, it's verisimilitude; the appearance of truth within the framework of the game.
*Picard management tip: Debate honestly. The goal is to arrive at the truth, not at your preconception.
*Mutant Dawn for Savage Worlds!
*The One Deck Engine: Gaming on a budget
Written by Me on DriveThru RPG
There are almost 400,000 threads on this site. If you need me to address a thread as a moderator, include a link.