Stamps

[Desiato]

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]

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!

[sfwc]

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

Sadly, this isn't quite enough.

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]

Okay, I guess I need to look harder next time. Thanks for the solution though!

[Nitrodon]

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 x²+y² and (x-1)²+y² are algebraic, so their difference 2x-1 is also algebraic. Thus x is algebraic. Furthermore, since x²+y² is algebraic, we also see that y is algebraic.

Now, the distance from X to R is (x-pi)²+y². 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]

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]

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:

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 Rⁿ 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 R²=d(y,y')²+q² 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 Rⁿ, which has already been shown to be sufficient.

[Nitrodon]

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 Rⁿ (any n) with d(x,p)=d(x,q)=2, but d(x,r) =/= sqrt(4 - pi + pi²).

Spoiler:

One can prove by induction that in Rⁿ 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 R²=d(y,y')²+q² 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 Rⁿ, 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]

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 ℝⁿ.

[skeptical scientist]

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.

[mfb]

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]

How about this: for n-dimensions, stamping at point (x₁,x₂,x₃,...) covers all points (y₁,y₂,y₃,...) such that x_i-y_i is algebraic for exactly one value of i. You can generalize this to x_i-y_i is algebraic for exactly n values of i

[mfb]

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]

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:

x² + (other terms) = (algebraic)
(x-1)² + (same other terms) = (algebraic)
(x-pi)² + (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).