While I work on gondolin's interesting problem, here's something along the lines of the problems that have been posted.

Definition: A three-legged spider is a the union of three line segments, all meeting at a single point. For example, a T is a three-legged spider.

Question: Can you fit uncountably many three-legged spiders in the plane? If not, can you prove it is impossible?

EDIT:
The plane is infinite
The spiders need not all be congruent
No leg of any given spider may be contained in another leg of that spider
No two distinct spiders can intersect anywhere

qrs

United States3637 Posts

May 12 2009 19:02 GMT

a finite-area plane, you mean?
and do the spiders all have to be congruent?

Muirhead

United States556 Posts

May 12 2009 19:05 GMT

I mean the infinite plane. Uncountable means that you can't number the spiders 1,2,3,4,...

For example, the real numbers are uncountable but the integers are countable because you can number them

1--->0
2--->-1
3--->1
4--->-2
5--->2
6--->-3
etc.

The spiders need not all be congruent.

DeathSpank

United States1029 Posts

May 12 2009 19:32 GMT

yes I would just draw a giant grid that way you wouldn't know which ones were which. Is that a really big spider? or a bunch of tiny ones?

Nytefish

United Kingdom4282 Posts

May 12 2009 19:33 GMT

Is T and a slight extended T that same spider?

Muirhead

United States556 Posts

May 12 2009 19:35 GMT

No two distinct spiders can intersect anywhere

Mogwai

United States13274 Posts

May 12 2009 19:37 GMT

if the spiders can exist in the same space as each other, it seems that you could trivially have uncountably infinite spiders on a plane, but I guess I'm assuming that they cannot have crossing legs

silynxer

Germany439 Posts

May 12 2009 19:42 GMT

Your definition is insufficient, what you probably want to add is that all line segments have to be pairwise disjunct, otherwise every single line segment (that is not a point) would contain uncountably many three legged spiders.

Even if they have to be disjunct you can fit uncountably many three legged spiders in every subset of the plane with non empty interior. But to keep it simple:
Analog to the Cantor Set you can substitute two legs of an initial one legged spider with a smaller* three legged spider in a way that there remains a three legged spider (for example if you substitude only the upper half of the legs). This remaining spider is important because otherwise the limits would be points and no spiders. Repeat this substitution ad infinitum.
To see that you receive an uncountable amount this way you can identify every sequence of {0,1} with exactly one branch of one legged spiders: if the next numer is a 0 you choose the "right" leg for substitution if it is 1 you take the "left". So the number of spiders is the same amount as the number of sequences {0,1} which has the same cardinality as the real numbers in [0,1] which has the same cardinality as the real numbers.

[EDIT]: Ah I was right about them being disjunct, ok.
*To clarify: smaller means for example if you choose T as your starting spider you would create new spiders be halving the length of the two smaller legs and making the other half the bigger leg of an proportional T-shaped spider so they wont intersect.

Muirhead

United States556 Posts

May 12 2009 19:49 GMT

Sorry silynxer... I'm afraid that your solution is wrong. A spider by your definition corresponds to a finite sequence of 0s and 1s. The set of finite sequences of 0s and 1s is countable.

silynxer

Germany439 Posts

May 12 2009 19:59 GMT

#10

Oh it seems you are right, since the limits are still points, let's see if I can make it work ^^.

[EDIT]:There is more to it than it seems on the first look, or I'm just stupid atm but cool riddle anyway.

DeathSpank

United States1029 Posts

May 12 2009 20:11 GMT

#11

On May 13 2009 04:35 Muirhead wrote:
No two distinct spiders can intersect anywhere

so I win!

also what you were probably looking for

A set S is called countable if there exists an injective function

since each spider is represented on a plane and none of them can overlap then no matter what you will be able to count the spiders.

jtan

Sweden5891 Posts

May 12 2009 20:21 GMT

#12

On May 13 2009 05:11 DeathSpank wrote:

Show nested quote +

lol

jtan

Sweden5891 Posts

May 12 2009 20:24 GMT

#13

The problem is interesting, I'm guessing it's impossible, but I'm having a hard time proving it.

silynxer

Germany439 Posts

May 12 2009 20:28 GMT

#14

Hehe, yeah my intuition fooled me as well, I'm now certain it's impossible. For example if you find one point with rational coordinades per spider you would have proven it.

gondolin

France332 Posts

May 12 2009 20:33 GMT

#15

On May 13 2009 05:28 silynxer wrote:
Hehe, yeah my intuition fooled me as well, I'm now certain it's impossible. For example if you find one point with rational coordinades per spider you would have proven it.

Yes, i hoped to prove it's impossible like that, but if you take a T, with the base at non rationnal coordinates (x,y), then the whole T does not meat Q*Q (because either x or y will be irrationnal).

drift0ut

United Kingdom691 Posts

May 12 2009 20:36 GMT

#16

i think this (nearly) does it:

+ Show Spoiler +

no

Project the spiders to the x-axis, they will give you a closed interval as they have 3 lines in them and not all are colinear and the spiders are closed (i'm guessing, i recon you could use the closure of them if not), and any real interval contains a rational so you can count these intervals, (uses choice i think, not totally sure this works) but there may be many spiders with the projection to x.

Now for the n'th interval on the x-axis consider the projections of those spiders onto the y-axis. again countably many. This time no 2 spiders can have the same interval. (to see this we have a closed square with a continuous path from left to right made by spider 1 and spider 2 needs to make a continuous path from top to bottom, this is where i used closed)

edit: dam you can't count the intervals like this but it's so close

Instead of projecting just look at the spiders whose projection _contains_ the n'th interval of the reals, (there ARE countably many rational to rational intervals) [a,b]. Then look at spiders such that "[a,b]xR intersect the spider" projects to an interval that contains the m'th interval on the y-axis.

dammit still not quite... now you no longer know that the path of the second spider goes all the way across the x interval

Muirhead

United States556 Posts

May 12 2009 20:43 GMT

#17

Interesting solution drift0ut... and if it works it is significantly simpler than mine. A closed interval on the x-axis is an unordered pair of distinct real numbers. Certainly there are uncountably many distinct closed intervals. Could you give more detail on why you think there are only countably many that come from projecting distinct spiders onto the x-axis? I'm not totally following. Thanks!

You all have the right idea trying to assign rational points to spiders... but at least my method of doing this requires 1-2 more tricky ideas.

jtan

Sweden5891 Posts

May 12 2009 20:44 GMT

#18

On May 13 2009 05:36 drift0ut wrote:
(...) and any real interval contains a rational so you can count these intervals

I don't see how you necessarily can count them

drift0ut

United Kingdom691 Posts

May 12 2009 20:46 GMT

#19

yeah you can't count them but i've edited it now ... i'm still not convinced it works

ok so last attempt for now:
+ Show Spoiler +

you'll need to draw a picture

alright: the rational intervals (start and end points are in Q) are countable. if a spider projects to cover interval n on the x-axis and (interval n)xR intersect the spider covers interval m on the y-axis. So now we have a line from the top of interval m to the bottom inside interval n.

now do the same in the other order: this spider covers interval m on the y-axis and Rx(interval m) intersect the spider covers interval n on the x-axis, so it gives a line from the left to the right inside interval m of the y-axis.

Now these spiders DO intersect... now it seems pretty likely there's only countably many... i think there are...

silynxer

Germany439 Posts

May 12 2009 21:06 GMT

#20

Damnit had to do the dishes and now it's almost solved, but still:
You can find for every coordinate and every leg a rational number (like the line goes through (PI,5) and (e,7)) or the line is parallel to one axis, but then there is the extra information of parallelity. I'm sure those numbers identify a spider. Now I only have to prove it...
[Edit]: no they don't -.-

1 2 3 4 Next All

Please or register to reply.

Live Events Refresh