The Enormous TREE(3) - Numberphile
video description
Since the first tree must have one seed, you have to use one of your available seeds and you can only work with the others from then on.
With TREE(1, that's all you've got.
With TREE(2, now you only have one color seed to work with, which finishes you off pretty much immediately.
But with TREE(3, once you use one seed for the first tree, you are free to use the other two seeds in whatever combinations you like, rather than being limited to one state.
Think about it this way: You have 100 coins that must either show heads or tails (no funny edge business. How many ways are there for them all to not show either heads or tails? 0 of course.
How many ways are there for them all to show heads? 1 of course.
How many ways are there for them to each show any side (either heads or tails? A lot of course (1267650600228229401496703205376 to be exact. There are so many more options once you get to alternate between two different options.
Date: 2022-04-08
Related videos
Comments and reviews: 9
Elliot
I'm confused. Why for TREE(2) can't you do two red seeds, two green seeds, a red seed connected to green seed, a lone red seed, and a green seed, in that order?
In that case, TREE(2) = 5, not 3. I know I'm mistaken, but not sure where.
___________________________
In fact, the more I think about it, the more confused I am. TREE(n) means -n- is the number of -colors- I have, not the number of -points- on my tree, as evidenced by TREE(3) where he draws trees with many more than just three points. So by TREE(1, I can make a tree with 17 different points of one color, then another one with 16 different points of the same color. The second tree does not contain the first (because the first tree is bigger. I can then make a third tree with 15 points of that one color, all the way down to a tree with a single point. So I have just demonstrated a game played where TREE(1) = 17. Of course, I can start with a tree of any size (as long as it only has one type of seed, and so TREE(1) = infinity.
reply
I'm confused. Why for TREE(2) can't you do two red seeds, two green seeds, a red seed connected to green seed, a lone red seed, and a green seed, in that order?
In that case, TREE(2) = 5, not 3. I know I'm mistaken, but not sure where.
___________________________
In fact, the more I think about it, the more confused I am. TREE(n) means -n- is the number of -colors- I have, not the number of -points- on my tree, as evidenced by TREE(3) where he draws trees with many more than just three points. So by TREE(1, I can make a tree with 17 different points of one color, then another one with 16 different points of the same color. The second tree does not contain the first (because the first tree is bigger. I can then make a third tree with 15 points of that one color, all the way down to a tree with a single point. So I have just demonstrated a game played where TREE(1) = 17. Of course, I can start with a tree of any size (as long as it only has one type of seed, and so TREE(1) = infinity.
reply
Brandon
If one were to create an algorithm to randomly create trees in a sequence that would be considered a single play of the tree game, what would the average length of that sequence be for a given tree(n? To try to clarify my meaning: If I were to play tree(2) there are 2 potential outcomes to the game. Non-optimal play of tree(2) = 2 states before completion. Optimal play of tree(2) = 3 states. The average length of a random game of tree(2) would be 2. 5 (that may be naive, but I think it is illustrative. So the video as presented gives us the maximum length of tree(3, we can imagine a minimum tree(3) = 3. But would most sequences sort of cluster around a peak of some length?
reply
If one were to create an algorithm to randomly create trees in a sequence that would be considered a single play of the tree game, what would the average length of that sequence be for a given tree(n? To try to clarify my meaning: If I were to play tree(2) there are 2 potential outcomes to the game. Non-optimal play of tree(2) = 2 states before completion. Optimal play of tree(2) = 3 states. The average length of a random game of tree(2) would be 2. 5 (that may be naive, but I think it is illustrative. So the video as presented gives us the maximum length of tree(3, we can imagine a minimum tree(3) = 3. But would most sequences sort of cluster around a peak of some length?
reply
Greg
Calling them -seeds- was far from ideal. To everyone, a tree sprouts out of ONE seed. It may then bear fruit which then hold additional seeds, but that's not part of the setup. The construction of the following trees is independent from the previous tree. Rather unintuitive. Talking about -nodes- would have been perfectly fine. Also, he should have said, -seed types-. I was confused that he said -can only contain two seeds- but then proceeds to construct a tree with four seeds in it. If you say -can only contain two seed types- you'd have made it far more clear.
reply
Calling them -seeds- was far from ideal. To everyone, a tree sprouts out of ONE seed. It may then bear fruit which then hold additional seeds, but that's not part of the setup. The construction of the following trees is independent from the previous tree. Rather unintuitive. Talking about -nodes- would have been perfectly fine. Also, he should have said, -seed types-. I was confused that he said -can only contain two seeds- but then proceeds to construct a tree with four seeds in it. If you say -can only contain two seed types- you'd have made it far more clear.
reply
AshtabulaReviews
I can actually imagine Tree (3) being mind-bogglingly huge.
Because the third and fourth tree that you draw in Tree (3) game only cancels out a fraction of possibility for the fifth tree that you draw.
And this fraction gets smaller with each tree in a logarithmic fraction. As the trees become more complex it becomes easier not to have that same arrangement in the next tree. So already without even being told that tree 3 is very huge, I can somehow imagine it being bigger than a trillion if that makes sense.
reply
I can actually imagine Tree (3) being mind-bogglingly huge.
Because the third and fourth tree that you draw in Tree (3) game only cancels out a fraction of possibility for the fifth tree that you draw.
And this fraction gets smaller with each tree in a logarithmic fraction. As the trees become more complex it becomes easier not to have that same arrangement in the next tree. So already without even being told that tree 3 is very huge, I can somehow imagine it being bigger than a trillion if that makes sense.
reply
Pathway
Seeing the insane growth of TREE(3, I can only begin to wonder what TREE(2. 5) is or TREE(2. 1, or which TREE function would give me 100. I know that it seems like a discreet function (meaning a graph of it would be made up of individual points instead of a line, but factorials are another function that logically should be discreet and are not. Anyone hypothesize what the answers might be?
reply
Seeing the insane growth of TREE(3, I can only begin to wonder what TREE(2. 5) is or TREE(2. 1, or which TREE function would give me 100. I know that it seems like a discreet function (meaning a graph of it would be made up of individual points instead of a line, but factorials are another function that logically should be discreet and are not. Anyone hypothesize what the answers might be?
reply
Rich
So given that the first tree is the one and only tree with a green seed in the TREE(3) possible trees, would it follow that, if the rule was you can't contain a -2-seed or greater- tree mean that TREE(2) with 2-seed matching requirements = TREE(3) with the original rules minus 1? (minus 1 for the single green tree in your TREE(3) game)
reply
So given that the first tree is the one and only tree with a green seed in the TREE(3) possible trees, would it follow that, if the rule was you can't contain a -2-seed or greater- tree mean that TREE(2) with 2-seed matching requirements = TREE(3) with the original rules minus 1? (minus 1 for the single green tree in your TREE(3) game)
reply
Daniel
Would someone mind explaining (if remotely possible in layman's terms) HOW you know that TREE(3) has an upper-bound and is in fact not infinite? I'm not doubting what you say; I'm just not understanding how you can make the claim. Are you going on intuition, or have we a formal proof demonstrating a finite ceiling? Thanks.
reply
Would someone mind explaining (if remotely possible in layman's terms) HOW you know that TREE(3) has an upper-bound and is in fact not infinite? I'm not doubting what you say; I'm just not understanding how you can make the claim. Are you going on intuition, or have we a formal proof demonstrating a finite ceiling? Thanks.
reply
Joseph
I feel like he glossed over the rules so quickly the rest of the video didn't make much sense.
In the spot where they represented some examples of trees they clearly show some trees contained in others. Unless there is some directionality to the connections which matters.
reply
I feel like he glossed over the rules so quickly the rest of the video didn't make much sense.
In the spot where they represented some examples of trees they clearly show some trees contained in others. Unless there is some directionality to the connections which matters.
reply
tony0000
I cannot tell you how much it blows my mind that the tree(3) sequence continues as long as it does, and then stops. How could it be that after that long, with something that conceptually simple, something -new- happens--possibilities for further growth become exhausted.
reply
I cannot tell you how much it blows my mind that the tree(3) sequence continues as long as it does, and then stops. How could it be that after that long, with something that conceptually simple, something -new- happens--possibilities for further growth become exhausted.
reply
Add a review, comment
Other channel videos
