Re: Interesting puzzle
- From: jdolan@xxxxxxxxx (James Dolan)
- Date: Sun, 8 Jul 2007 08:59:50 +0000 (UTC)
in article <1183873956.979085.51330@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
jules <julianrosen@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".
--
jdolan@xxxxxxxxxxxx
.
- Follow-Ups:
- Re: Interesting puzzle
- From: Jules
- Re: Interesting puzzle
- References:
- Interesting puzzle
- From: Jules
- Interesting puzzle
- Prev by Date: Re: ** says: Definition: sum{i in N} i = 0
- Next by Date: Re: Interesting puzzle
- Previous by thread: Interesting puzzle
- Next by thread: Re: Interesting puzzle
- Index(es):
Relevant Pages
|
