| Blogs > Muirhead |
|
Muirhead
United States557 Posts
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
and do the spiders all have to be congruent? | ||
|
Muirhead
United States557 Posts
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
| ||
|
Nytefish
United Kingdom4282 Posts
| ||
|
Muirhead
United States557 Posts
| ||
|
Mogwai
United States13274 Posts
| ||
|
silynxer
Germany439 Posts
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 States557 Posts
| ||
|
silynxer
Germany439 Posts
[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
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
On May 13 2009 05:11 DeathSpank wrote: 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. lol | ||
|
jtan
Sweden5891 Posts
| ||
|
silynxer
Germany439 Posts
| ||
|
gondolin
France332 Posts
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
+ 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 States557 Posts
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
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
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
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 -.- | ||
| ||
The PiG Daily
Best Games of SC
ByuN vs Rogue
herO vs SHIN
Serral vs TBD
Clem vs TBD
[ Submit Event ] |
|
|
|
CranKy Ducklings
AI Arena Tournament
BSL: Ladder Tournament
GSL
Yamato Cup
BSL Open Qualifier
BSL Open Qualifier
Replay Cast
Afreeca Starleague
Soma vs Jaedong
WardiTV Weekly
[ Show More ] |
|
|
EPT
