Stamps

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Stamps

You get a magic stamp that hits all points of the area that has transcendental distance from the origin.

How often do you need to stamp to cover the entire plane?

Extending to an n-dimensional stamp, how often do you have to stamp to cover the entire R^n?

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Stamps

For the plane you need two stamps: (0,pi) and (pi,0), this will cover all of the points. This is not a rigorous proof feel free to prove me wrong! I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

sfwc
Posts: 224
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: Stamps

tomtom2357 wrote:For the plane you need two stamps: (0,pi) and (pi,0), this will cover all of the points.

Spoiler:
The circles centered at (0, pi) and (pi, 0) with radius 2 intersect, and so there is a point at distance 2 from both of these points, which is covered by neither stamp
In the plane:
Spoiler:
No 2 stamps will suffice, by an argument like the one above. But 3 stamps is enough. Pick any 2 distinct points P and Q, and any line l. For each pair (p, q) of algebraic numbers, there are at most 2 points at a distance p from P and q from Q. So for each triple (p, q, r) of algebraic numbers there are at most 4 points R on l such that there is a point at a distance p from P, q from Q and r from R. Since there are only countably many such triples, there are only countably many points R on l for which such a triple (p, q, r) can be found. In particular, we can find some R on l for which there is no such triple (as l is uncountable). Now stamp at P, Q and R.
In R^n:
Spoiler:
Pretty much the same argument shows that the minimal number of stamps we can get away with is n + 1

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Stamps

Okay, I guess I need to look harder next time. Thanks for the solution though!
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Stamps

An explicit solution:
Spoiler:
Let P=(0,0), Q=(1,0), and R=(pi,0).

Suppose X=(x,y) is a point with algebraic distance from both P and Q. Then x2+y2 and (x-1)2+y2 are algebraic, so their difference 2x-1 is also algebraic. Thus x is algebraic. Furthermore, since x2+y2 is algebraic, we also see that y is algebraic.

Now, the distance from X to R is (x-pi)2+y2. If this is algebraic, then we can conclude that pi is algebraic, which is not true. Thus, it is impossible for the distance from X to all three points to be algebraic simultaneously.

This argument extends to higher dimensions, where the points chosen are the origin, any n-1 of the standard basis vectors, and a final point with exactly one transcendental component.

Edit:
Spoiler:
For higher dimensions, P=(0,0,...,0), Q=(1,0,...,0), and R=(pi,0,...,0) should work, so you only need 3 points.

mfb
Posts: 948
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Stamps

Nitrodon wrote:Edit:
Spoiler:
For higher dimensions, P=(0,0,...,0), Q=(1,0,...,0), and R=(pi,0,...,0) should work, so you only need 3 points.

That does not work.
Spoiler:
Similar to the argument on the plane: Look at spheres with diameter 4 around the points. In 3+ dimensions, they have common points.
Your argument breaks down, as you cannot restrict more coordinates than just the first one with P and Q.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Stamps

mfb wrote:That does not work.
Spoiler:
Similar to the argument on the plane: Look at spheres with diameter 4 around the points. In 3+ dimensions, they have common points.
Your argument breaks down, as you cannot restrict more coordinates than just the first one with P and Q.

To elaborate on this and sfwc's earlier comment:
sfwc wrote:In R^n:
Spoiler:
Pretty much the same argument shows that the minimal number of stamps we can get away with is n + 1

Spoiler:
One can prove by induction that in Rn after 1≤k≤n stamps, you are missing some (n-k)-sphere. (N.b. a 0-sphere is 2 points.)

After the first stamp, for every algebraic q you are missing all points at distance q from the center of the stamp, so the base case holds.

Assuming the result for k, after k stamps, you are missing some (n-k)-sphere, say centered at x with radius r, and in the (n-k+1)-dimensional hyperplane H through x. If the (k+1)st stamp is centered at y, let y' be the orthogonal projection of y onto H. Choose some number q s.t. d(x,y')-r<q<d(x,y')+r and R2=d(y,y')2+q2 is algebraic. Then the stamp centered at y misses the (n-1)-sphere of radius R about y, which includes the (n-k)-sphere in H centered at y with radius q. By the choice of q, the two (n-k)-spheres in H intersect and are not tangent. Since the intersection of two intersecting, non-tangent m-spheres in an (m+1)-dimensional space is an (m-1)-sphere, we have the result for k+1.

Thus at least n+1 stamps are necessary to cover Rn, which has already been shown to be sufficient.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Stamps

mfb wrote:That does not work.
Spoiler:
Similar to the argument on the plane: Look at spheres with diameter 4 around the points. In 3+ dimensions, they have common points.
Your argument breaks down, as you cannot restrict more coordinates than just the first one with P and Q.

I think it does.
Spoiler:
For my choice of p and q, name one point x in Rn (any n) with d(x,p)=d(x,q)=2, but d(x,r) =/= sqrt(4 - pi + pi2).

skeptical scientist wrote:
Spoiler:
One can prove by induction that in Rn after 1≤k≤n stamps, you are missing some (n-k)-sphere. (N.b. a 0-sphere is 2 points.)

After the first stamp, for every algebraic q you are missing all points at distance q from the center of the stamp, so the base case holds.

Assuming the result for k, after k stamps, you are missing some (n-k)-sphere, say centered at x with radius r, and in the (n-k+1)-dimensional hyperplane H through x. If the (k+1)st stamp is centered at y, let y' be the orthogonal projection of y onto H. Choose some number q s.t. d(x,y')-r<q<d(x,y')+r and R2=d(y,y')2+q2 is algebraic. Then the stamp centered at y misses the (n-1)-sphere of radius R about y, which includes the (n-k)-sphere in H centered at y with radius q. By the choice of q, the two (n-k)-spheres in H intersect and are not tangent. Since the intersection of two intersecting, non-tangent m-spheres in an (m+1)-dimensional space is an (m-1)-sphere, we have the result for k+1.

Thus at least n+1 stamps are necessary to cover Rn, which has already been shown to be sufficient.

Spoiler:
You need an absolute value on the left side of the inequality defining the number q. This leads me to my point: what if y'=x?

Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Stamps

Nitrodon is correct.

Spoiler:
By placing the points P, Q, and R colinearly, all orthogonal directions are equivalent to each other by symmetry. It is therefore sufficient to consider the plane formed by the x-axis and any arbitrary orthogonal direction, such as the y-axis. Since we have already shown that (0, 0), (1, 0), and (π, 0) provide a covering of ℝ², it follows that Nitrodon’s P, Q, and R provide a covering of every 2D slice of ℝⁿ containing the x-axis, which thus means they cover all of ℝⁿ.
wee free kings

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Stamps

Nitrodon wrote:
Spoiler:
You need an absolute value on the left side of the inequality defining the number q. This leads me to my point: what if y'=x?

Damn, missed that.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

mfb
Posts: 948
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Stamps

Oh, good point.

And a stamp which covers all algebraic distances does not work (with countable stamp usage), so there is no obvious follow-up problem .

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Stamps

How about this: for n-dimensions, stamping at point (x1,x2,x3,...) covers all points (y1,y2,y3,...) such that xi-yi is algebraic for exactly one value of i. You can generalize this to xi-yi is algebraic for exactly n values of i
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 948
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Stamps

I would expect that it is not possible to cover the plane (or higher dimensions) with this. Take the plane and assume that a finite number N of stamps covers all points. From these N, let n be stamps where the first coordinate (x) difference is algebraic, and at N-n stamps the second coordinate (y) difference is algebraic. There are coordinates X which have transcendental difference in x to all x-positions of the first group, therefore they are not covered by the first stamp type.
With the same argument, there are coordinates Y which have transcendental difference in y to all y-positions of the second group, therefore they are not covered.
Now, take an x-value out of X and an y-value out one out of Y and you get a point which is not covered.

I hope I did not make a mistake here. If that argument is not flawed, the only way to get a coverage is "the coordinate difference is algebraic for exactly 0 values".

Desiato
Posts: 43
Joined: Fri Nov 25, 2011 11:15 pm UTC

Re: Stamps

Qaanol wrote:Nitrodon is correct.

Spoiler:
By placing the points P, Q, and R colinearly, all orthogonal directions are equivalent to each other by symmetry. It is therefore sufficient to consider the plane formed by the x-axis and any arbitrary orthogonal direction, such as the y-axis. Since we have already shown that (0, 0), (1, 0), and (π, 0) provide a covering of ℝ², it follows that Nitrodon’s P, Q, and R provide a covering of every 2D slice of ℝⁿ containing the x-axis, which thus means they cover all of ℝⁿ.

That's certainly the most elegant argument I've seen for this. Nice!

My own is certainly far less elegant:

Spoiler:
Chosing the points Nitrodon mentions, assume you have a point (x, other coordinates) not covered. Then we have, in lazy convenient notation:

x2 + (other terms) = (algebraic)
(x-1)2 + (same other terms) = (algebraic)
(x-pi)2 + (same other terms) = (algebraic)

We can then establish from the first two equations that x is algebraic, and then by substracting one of the first equations from the last ones get that pi would be algebraic, which is a contradiction.

And I'll skip repeating the arguments for two not being sufficient.

I fell for the same "sloppy" argument that the number of points would increase with dimensions at first as well, which was, I thought, a nice twist to the classical (2-dimensional) problem. Its first occurance known to me was in the usenet group rec.puzzles and in fact can still be found in the FAQ there (e.g. here, then with irrational stamps).