Christmas Tree, O Christmas Tree

[DDRM]

A Christmas tree is made up of triangular-shaped sections, each half the size of the previous one, placed one on top of another. Ignoring the trunk at the bottom, how many such sections can be fitted in before the tree becomes twice as tall as the first section? Bonus points for a graphical demonstration (until the sections become too small to plot, if appropriate).

[Hated Moron]

A Christmas tree is made up of triangular-shaped sections, each half the size of the previous one, placed one on top of another. Ignoring the trunk at the bottom, how many such sections can be fitted in before the tree becomes twice as tall as the first section? Bonus points for a graphical demonstration (until the sections become too small to plot, if appropriate).

Isn't the answer infinity? This seems to be equivalent to asking how many terms of the series 1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ... are required before the sum becomes greater-than-or-equal-to 2.0. But it never does!

The code below shows it graphically, as requested. Since it uses anti-aliased graphics it's hard to know how to interpret "too small to plot", does that mean when the size has underflowed to zero, or when what is plotted is just black? The latter would be a little difficult to determine accurately, but to a first approximation is probably when the height becomes less than about 1/256 graphics units.

Code: Select all

      MODE 20
      ORIGIN 800,0
      OFF
      INSTALL @lib$+"aagfxlib"
      DIM x(2), y(2)
      h = 600
      y = 0
      REPEAT
        x() = -h, 0, h
        y() = y, y+h, y
        PROC_aapolygon(3, x(), y(), &FF00FF00)
        y += h
        h /= 2
        *REFRESH
        WAIT 50
      UNTIL y >= 1200 OR h^2 < 1/64

[DDRM]

Indeed! If you are going down the anti-aliased line, then I'll leave it to you to decide when to stop! What I had in mind was when it fell below half a pixel (since then the "half pixel", or maybe the "threequarter pixel", would fill the last space...

... and thank you for taking up the challenge!



D

[Hated Moron]

What I had in mind was when it fell below half a pixel (since then the "half pixel", or maybe the "threequarter pixel", would fill the last space...

Considering that you are asking for very small triangles to be plotted, I would have thought anything other than anti-aliased graphics would not fully meet the brief. I'd deduct marks, anyway!

Thinking about it, with anti-aliased graphics the stopping point should be roughly when the area of the triangle is less than 1/256 of a (square) pixel, i.e. when h^2 (which is half-base * height in graphics units) is less than 1/64. I've edited the code accordingly.

[DDRM]

The idea of the challenges was that most should be attemptable (is that a word?) by anyone from pretty much a novice programmer upwards. For novices, I'd just expect a simple "integer" solution - and perhaps the realisation that this sequence (1 + 1/2 + 1/4 ...) sums to 2, which might have been an interesting surprise to some!

As you note, for the more advanced, the infinite regression forces some decision-making! Many of the other challenges are the same - a brute-force solution is possible, since the problem size is small, but if you know a bit of maths a solution may be "obvious" (or at least much easier).

Best wishes,

D