Yet Another Math Puzzle - Page 3

to find a point or points with rational co-ordinates that uniquely denotes a particular spider

Let a spider consist of line segments A, B, and C. Draw three line segments A', B', and C' with the following properties:

• The co-ordinates of the endpoints for A', B', and C' are all rational.
• Orientation: A' and C' are vertical and B' is horizontal OR A' and C' are horizontal and B' is vertical.
• A' intersects A but not B or C; B' intersects B but not A or C; C' intersects C but not A or B.

Any leg of a spider has breadth in at least one dimension (horizontal or vertical), and if two legs have breadth in only one (and the same) dimension then the third leg must have breadth in the other dimension. This allows us to find A' B' and C' with rational endpoints for every spider.

For a given set of horizontal and vertical segments A' B' and C', no more than one spider can be drawn whose legs intersect the given segments. Two such spiders would intersect each other at some point.

Later edit: I drew a picture of the construction with a few different cases of spiders. Some of the cases are a little bit different from what I described here, although the general idea is the same. I'll write some text later; for now I will just add in the picture.+ Show Spoiler +

Lemma 1: you cannot fit an uncountable number of open, pairwise disjoint, sets on the real line.
+ Show Spoiler [proof] +
Assume there are an uncountable number of disjoint spiders in the plane.

Then there exists a line parallel to the x-axis that intersects an uncountable number of spider legs.
+ Show Spoiler [proof] +
+ Show Spoiler [pedagodical picture] +
The spiders that has a leg that intersects that line (these spiders will henceforth be referred to as just "the spiders") has their center (where the three lines meet) above or below the line. There will be an uncountable amount of spiders either above or below the line. By symmetry it doesn't matter which, so lets for simplicity assume that there are an uncountable number of centers above the line.

now look at the endpoints of the two legs that do not intersect. It is possible that 2 or more of the legs intersect the line, but in that case count only the leftmost intersecting leg, and study the two other legs. These two points can be either
both above the center (type 1),
one above and one below (type 2) or
both below the center (type 3).
+ Show Spoiler [pedagodical picture] +
again, an uncountable amount of spiders will fall into at least one of these categories. In case all but a countable number of spiders have their endpoints at exactly the same y as the center, the solution can be transformed by y - q --> (y-q)*e^x, which will maintain the property of intersecting the line (since y = q will not move), but will shift the points that are on the same y as their center, making them type 2.

I will now prove that you end up with contradictions with an uncountable numbers of any of these types.

case 1: an uncountable number of spiders are of type 1.
+ Show Spoiler [case 1] +
case 2: an uncountable number of spiders are of type 2.
+ Show Spoiler [case 2] +
case 3: an uncountable number of spiders are of type 3.
+ Show Spoiler [case 3] +
This concludes the proof.

hmm, I don't understand your construction. What would the endpoints of A', B' and C' be, and how do you know that they are unique for that spider?

Also, if you have a leg that is diagonal, and the other legs approach that first leg with a sin(1/r) behavior from each side, will it not be impossible to draw a horisontal or vertical line that intersects only the first leg? i'm confused...

The endpoints: one co-ordinate would be some rational co-ordinate of either x or y found on some point of the corresponding leg, and the other would be some convenient rational number.

You know they are unique for that spider because: well, again, I'm not putting this in a rigorous form, but the idea is, draw a spider through those lines. Now try to draw another spider through those lines: I believe you will not be able to do so without intersecting the first. The reason is that A' B' and C' shepherd the legs into tracks. It's a little like the squeeze theorem in calculus: let's say A'', B'' and C'' are the legs of the second spider you are drawing. A'' must be either inside or outside A, C'' must be either inside or outside C, and both B and B'' have to be between both A-A'' and C-C''. This forces an intersection.

Here's a picture:

I may have omitted some necessary conditions. For example, we can also specify the shape of the spider (in very general terms: do all legs go down/up (or left/right, whichever way is more convenient) from the origin [/|\], or does one leg go in a different direction from the others [Y]) and orientation of the spider (is the "origin" of the spider above or below the intersecting lines). On second look, I think that you do have to specify the orientation when dealing with a spider with three legs going down/up (/|\), in order to rule out a similar "upside-down spider" penetrating it from the open side. That should be sufficient.

first counterexamples for your picture.

So drawing them randomly according to your criterion will not work in general. I am not even sure if it can be done for any spider to block off every other possible spider, even if you manually choose the straight lines.

So if you want to "block off" so that you cant create another spider that shares the lines, you will have to find an exact algorithm for how to make the extra lines in a unique way from a given spider, and then prove that no two other spider will create the same three lines. That is a lot of work and I wish you good luck with that if you choose to try.

But I am not convinced it is possible at all with this approach, even for straight lines, so don't waste too much times trying.

specifying shape and orientation

specifying the shape of the spider: i.e. two lines point up from the origin and one line points down.

given multiple pairs of lines that converge in the same direction, the inner lines will always meet before the outer lines. Therefore there is no way to assign them to create two "spiders" that do not overlap. Here's an illustration: .

So I don't need to prove that "prove that no two other spider will create the same three lines", as you said. The lines are fairly arbitrary: each spider has (infinitely) many lines that will work, and each set of lines will work for (infinitely) many spiders. All I need to show is that no two spiders in the same plane can go through these lines without the two spiders intersecting. As long as we ensure that we specify the direction towards which the legs converge (using the two general attributes of shape [2 possibilities] and orientation [2 possibilities], I believe that my method works.

Granted, I have not proved it rigorously, and it is possible that I have overlooked something, but I think that this groundwork is enough to build a rigorous proof on if I needed to.

Edit: edit-to-edit: (On second thought, this rambling, partially-thought-through addendum is probably not worth reading; it confuses the point more than it clarifies it. I won't actually delete it, though. The gist is that my HVH/VHV condition is probably not the right one. Instead, the important thing to make sure is that A' B' and C' don't overlap.) + Show Spoiler [not really worth reading, tbh] +

Picture above is updated.

As I said, this is still more of a proof idea than a formal proof, but the more I think about it, the more details I pin down. Maybe at some point I will try to fully formalize it. (Right now, it is just sucking me into wasting more time that I really can't afford to at the moment. When I do have the time, I'll try to take a good look at your proof as well.)

Suppose that you have a counting method that works for everything but cases of T (for instance).
Assume that the T's are uncountable. You can still count everything else.
Now rotate the co-ordinate system (by a non-multiple-of-90-degrees). You haven't changed the relative positions of any spiders, but all vertical/horizontal lines are now diagonal. Count them as before.
(Of course any number of previously diagonal lines may have become vertical or horizontal, but you have already counted those.)

Take the set of all spiders. Let A be the set of all spiders with some point (x,y) where both x and y rational. We can associate these spiders with QxQ, so these are countable.

Let B be the set of all spiders where there does not exist some point (x,y) where both x and y are rational. It is clear that these spiders must be in some rotation of a T shape. Split these spiders up into subsets based on rotation and use the following idea for each subset.

Consider the subset spiders in B oriented as the shape T. Assume towards a contradiction that there are uncountably many of these. Then, there are uncountably many points on the x-axis associated with the vertical bars of the T's. Next, note that the top (horizontal) bar of the T has positive measure. Assume that there exists some ε >0 such that there are uncountably many spiders with top bar length >= ε. (see note) If the three legs of some T spider meet at a point (x,y), then the top bar covers an interval (x-ε,x+ε) at that height y. So, for any specific value y, there can only be countably many spiders, since there are only countably many open intervals (x-ε, x-ε) on that specific 'y-axis'. Therefore, there must be uncountably many y-values associated with the top bars of spiders in order to have the assumed uncountably many spiders. However, by similar logic using the positive measure of the vertical bars, there can only be countably many spiders at any given x-value since there are only countably many intervals open intervals (y-ε, y) on that specific 'x-axis', contradicting the bolded text above.

So, use this logic for each subset of B (ie- rotation of the shape T), and we can show that each subset is countable, so B is countable, and so A union B is countable, and that's all the spiders!

(note: I think this is a safe assumption, since, if it were not true, then for all ε>0, there only exists countably many spiders with top length >=ε. Let ε go to zero, and we have the result we want: only countably many spiders. Now, this makes me a bit uneasy (not very rigorous), but I think it's the right idea... This whole damn problem makes me uneasy, but it's fun to think about :p)

Let ε also be associated with the vertical lengths in the same way (whatever, take a min between horizontal and vertical, call it ε). So, for any specific spider centered at ( x',y' ), the region R_(x',y') = {(x,y) | x \in (x'-ε, x'+ε), y \in (y', y'-ε)} cannot contain any spider centers, since any spider centered there will intersect the spider centered at ( x',y' ).

So, from above, at any specific y-value, there can only exist countably many x-values associated with spider centers at that height. Which implies there are only countably many regions R_(x,y) at that height, all of which cannot contain more than one spider. These regions have positive vertical measure ε, so there are only countable many vertical regions for each horizontal spider center x.

Which brings us back to the same old argument of 'each spider has some positive area which cannot have other spiders in it', but this time for a subset of specifically shaped spiders. So I've done all this complicated stuff to show nothing new. :/




WAIT: No, this works. And it's a lot simpler than I thought. As long as we can wave our hands and accept the note from above (for vertical AND horizontal), then for spiders in the shape T, we can separate the plane into countably many disjoint regions (or at least equivalence classes thereof). We don't have to worry about some clever shape fitting in between things, since each spider in this set is the shape T. Do this for each rotation so that each subset of B is countable, and then A union B is countable and we're done.

Right?

T_T

Suppose, for the sake of contradiction, that there are uncountably many spiders in the plane.
Let the width of a spider be the minimum distance from its center to one of its three endpoints.
For some positive integer N, uncountably many spiders have width at least 1/N. Erase all the spiders with width less than 1/N
Cover the plane with countably many disks of diameter 1/N. At least one such disk has uncountably many centers of spiders. Erase all spiders with centers not in the disk.
Each spider divides the disk into three distinct regions. Associate a triplet of rational points to the spider, one point in each region.