branched trees with few leaves

I just thought of the following question, I’ve no idea if it’s a well-known riddle, but it seems a nice story, and it should not prove too difficult to answer:

God is tired before the 6th day of creation so he actually gives you a task, while he goes to take a nap. Namely you have to build the Amazon forest.  (That’s because people in the 21st century are going to need to chop trees in huge quantity in order to make paper, so the plan is that you have to fill the whole South America with trees before midnight). You take an energy drink and prepare to do the job…

Basically the technique to do one of these trees is quite simple: you are given some sticks and you have to glue them at their ends, making a caricature tree, then you plant one of these in the ground, and magically a leaf is going to sprout at the free end of the sticks, while the rest is becoming a realistic wodden tree.

You notice that the sticks become quite nice trunk pieces, while you don’t like so much the way the leaves come out, they seem boring to you (and you immagine that after all 21st century people will look more for wood than for leaves, so you want to concentrate on making that part). So you end up doing trees with many sticks, but as little leaves as possible. The result is not very nice, because you end up gluing all the sticks in a row, and you get a long tree with just one leaf in the end. This makes you wonder what would happen if you start doing a lot of branchings. And here is the question:

If you impose yourself that no gluing is done involving only 2 stick ends (so that your tree has just branch points, possibly with more than 2 branches), what is the least number of leaves that you can get if you use 4 sticks? What about 15 sticks? Is there a formula valid in the case of an arbitrary number of sticks?

Epilogue: Lost in those dreams you fall asleep, leaving an Amazon forest with a total of about 7 trees for the posterity.. but God is forgiving, so he offers you a beer.

Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: