Re: infinity
- From: imaginatorium@xxxxxxxxxxxxx
- Date: 2 Sep 2005 10:22:12 -0700
Tony Orlow (aeo6) wrote:
> Virgil said:
> > In article <MPG.1d7f9000c6e111a298a19f@xxxxxxxxxxxxxxxxxxxxxxxxx>,
> > Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> wrote:
> > ...[?]
> > > > > > I mapped paths from the same tree ...
That's enough. I'm generally avoiding both tree and vase arguments,
since they are far too complex. But let's just try a little...
> Let us try inductive proofs regarding the relationship between branches and
> paths.
Uh-oh. OK, I'll try as well. I'll investigate how many ends there are
in an endless tree (that's one in which every node branches into two
child nodes, and this never never never never ends). Intuitively, I'd
expect that an endless tree would not have any ends, since I've defined
it that way, but let's see.
> Proof: In a maximal binary tree, number of paths is half the number of
> branches, plus 1.
>
> 1. For an empty tree consisting of the root node, there is one path in the
> tree, of length zero, and no branches. 1 path = 0 branches/2 + 1.
For an "empty" [not quite the right word, is it] tree, there is one
end.
> 2. If there are n branches, and n/2+1 paths, on level x, and we add level x+1,
> each of the n/2+1 leaf nodes corresponding to a path will be extended by one
> level by adding two branches, and each of the n/2+1 paths will be divided into
> two paths, doubling the number of paths. So, our original n branches are
> increased by 2*(n/2+1), and our original n/2+1 paths is doubled. This gives n+2
> *(n/2+1) = n+n+2 = 2n+2 branches, and 2*(n/2+1) = n+2 paths. 1/2(2n+2)+1 = n+2.
I think you mean that considering the tree that stops at level x, there
are 2^x [plus/minus epsilon*] ends.
* Your notation is so woolly I can't be bothered to work it out
exactly.
> 3. Therefore, each additional level added to the binary tree maintains this
> relationship between branches and paths, and the number of paths is half the
> number of branches, plus 1.
Notice how the word "Therefore" is completely wrong. The statement is
true, but is not a logical deduction from the previous one. Anyway,
turtles all the way down.
> Proof: In a maximal binary tree with paths of length n, or depth of n, there
> are p(n)=2^n paths and b(n) = 2(2^n-1) = 2(p(n)-1) branches.
What do you mean by "Proof"? Isn't this still part of the same
argument? You would get more respect if you took the trouble to
understand elementary notational conventions.
Anyway, never mind: to finish off *my* proof... By induction, the
number of ends of an endless tree is infinity. Da-dah!!
Brian Chandler
http://imaginatorium.org
.
- Follow-Ups:
- Re: infinity
- From: aeo6
- Re: infinity
- References:
- Re: infinity
- From: aeo6
- Re: infinity
- Prev by Date: Re: Physical interpretaion of -2*-3
- Next by Date: Re: infinity
- Previous by thread: Re: infinity
- Next by thread: Re: infinity
- Index(es):
Relevant Pages
|
