Re: Interesting puzzle
- From: Jules <julianrosen@xxxxxxxxx>
- Date: Sun, 08 Jul 2007 13:48:58 -0700
On Jul 8, 1:59 am, jdo...@xxxxxxxxx (James Dolan) wrote:
in article <1183873956.979085.51...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
jules <julianro...@xxxxxxxxx> wrote:
|While working on something totally different, I stumbled across an
|interesting fact. The proof I have seems more difficult than should
|be necessary, though. The problem is as follows:
|
|Suppose we have some collection of (finite-length) words on two
|symbols (say, 0 and 1). This collection has the property that for
|any infinite binary sequence, some head of that sequence is a member
|of the collection (by a head of a sequence, I mean the string formed
|by taking the first n terms of the sequence, for some positive
|integer n). The collection also has the property that no string in
|the collection is a head of any other string in the collection.
|Prove that the collection is finite.
see "koenig's lemma" (at wikipedia.org, for example). more
specifically, a contrapositive of it. "if a finitely branching tree
has no infinite branches then the whole tree is finite".
--
jdo...@xxxxxxxxxxxx
Thank you for the response. I had not seen Koenig's Lemma before.
The proof I had used the Tychonoff Theorem. It is not hard to show
that the problem is equivalent to showing that the countably-infinite
product of two-point discrete spaces is compact.
.
- References:
- Interesting puzzle
- From: Jules
- Re: Interesting puzzle
- From: James Dolan
- Interesting puzzle
- Prev by Date: Re: A question for Tommy1729
- Next by Date: Re: ** says: Definition: sum{i in N} i = 0
- Previous by thread: Re: Interesting puzzle
- Next by thread: Re: Interesting puzzle
- Index(es):
Relevant Pages
|
