The Museum of HP Calculators

HP Forum Archive 19

[ Return to Index | Top of Index ]

41C 30th Birthday Game
Message #1 Posted by Egan Ford on 4 July 2009, 5:28 p.m.

The 30th anniversary of the 41C is almost upon us. So dust of your 41 and give this simple challenge a try. What? No 41C? No worries, any calculator will do.

Above is a classic round birthday cake. As I was placing the candles around the cake I imagined that each candle was connected to each other candle with a line. I then wondered, “If I cut the cake following these lines, how many pieces will I have?” To answer this I drew the above four diagrams representing 2, 3, 4, and 5 candles. Remarkably, this divided the cake into 2, 4, 8, and 16 pieces. With all 30 candles around the edge and the cake divided along the imaginary lines what will be the maximum number of pieces?

Edit: Emphasized (italicized) maximum.

Edited: 7 July 2009, 12:46 a.m. after one or more responses were posted

      
Re: 41C 30th Birthday Game
Message #2 Posted by Don Shepherd on 4 July 2009, 5:50 p.m.,
in response to message #1 by Egan Ford

2^30= 1,073,741,824

            
Re: 41C 30th Birthday Game
Message #3 Posted by Jeff Kearns on 4 July 2009, 5:58 p.m.,
in response to message #2 by Don Shepherd

I would say 2^29 = 536,870,912 pieces

      
Re: 41C 30th Birthday Game
Message #4 Posted by Walter B on 4 July 2009, 5:55 p.m.,
in response to message #1 by Egan Ford

2^29 = 536,870,912

      
Re: 41C 30th Birthday Game
Message #5 Posted by Don Shepherd on 4 July 2009, 6:05 p.m.,
in response to message #1 by Egan Ford

OK, I see, they are right, 2^29. Mybad.

      
Re: 41C 30th Birthday Game *** Spoiler ***
Message #6 Posted by Gerson W. Barbosa on 4 July 2009, 6:35 p.m.,
in response to message #1 by Egan Ford

Quote:
Remarkably, this divided the cake into 2, 4, 8, and 16 pieces.

Unfortunately this scheme fails when we have six candles or more. For six candles, there are 9 diagonals and 24 regions comprised among them, so we'll have 30 pieces, 24 + 6, not 32. Not willing to think, I made a table for a few cases and looked up in OEIS:

number of  number of  internal external  number of
candles    diagonals  regions  regions    pieces
    4         2          4        4         8
    5         5         11        5        16
    6         9         24        6        30
Searching for the sequence 4, 11, 24, I found

A007678. From a link there, I found 21480 for n=30. Therefore we'll have 21510 pieces (21480 + 30).

Gerson.

Edited: 4 July 2009, 6:39 p.m.

            
Re: 41C 30th Birthday Game *** Spoiler *** Not Quite
Message #7 Posted by Egan Ford on 4 July 2009, 7:59 p.m.,
in response to message #6 by Gerson W. Barbosa

Nope, but close.

                  
Re: 41C 30th Birthday Game *** Spoiler *** Not Quite
Message #8 Posted by Gerson W. Barbosa on 4 July 2009, 8:46 p.m.,
in response to message #7 by Egan Ford

Well, I've just checked this heptagon:

I've counted all the pieces and have found 50 of them which added to the 7 outer pieces make up 57 pieces, in accordance with this table:

n	d	in	ex	pieces

3 0 1 3 4 4 2 4 4 8 5 5 11 5 16 6 9 24 6 30 7 14 50 7 57 8 20 80 8 88 9 27 154 9 163 10 35 220 10 230 11 44 375 11 386 12 54 444 12 456 13 65 781 13 794 14 77 952 14 966 15 90 1456 15 1471 16 104 1696 16 1712 17 119 2500 17 2517 18 135 2466 18 2484 19 152 4029 19 4048 20 170 4500 20 4520 21 189 6175 21 6196 22 209 6820 22 6842 23 230 9086 23 9109 24 252 9024 24 9048 25 275 12926 25 12951 26 299 13988 26 14014 27 324 17875 27 17902 28 350 19180 28 19208 29 377 24129 29 24158 30 405 21480 30 21510

The third column was taken from OEIS A007678 - Number of regions in regular n-gon with all diagonals drawn. So 21510 appears to be the solution. Of course I may be wrong...

-------

P.S.:

There's another OEIS seguence: A006533:

1, 2, 4, 8, 16, 30, 57, 88, 163, 230, 386, 456, 794, 966, 1471, 1712, 2517, 2484, 4048, 4520, 6196, 6842, 9109, 9048, 12951, 14014, 17902, 19208, 24158, 21510, 31931, 33888...

Edited: 4 July 2009, 9:02 p.m.

                        
Re: 41C 30th Birthday Game *** Spoiler *** Not Quite
Message #9 Posted by Egan Ford on 5 July 2009, 11:15 a.m.,
in response to message #8 by Gerson W. Barbosa

Great looking picture. It looks like a birthday cake too. I edited the original problem to emphasize the requirement for the maximum number of pieces.

BTW, your odd number results are correct.

                              
Re: 41C 30th Birthday Game *** Spoiler *** Not Quite
Message #10 Posted by Gerson W. Barbosa on 5 July 2009, 11:55 a.m.,
in response to message #9 by Egan Ford

Quote:
I edited the original problem to emphasize the requirement for the maximum number of pieces.

You're right! I overlooked the word maximum, something I used to do during examinations... For n=6 for instance it is easy to see the maximum number of pieces will be 31, rather than 30, when the candles are not equally spaced around the cake. It's hard to compute the differences for large n though...

Edited: 5 July 2009, 11:56 a.m.

      
Re: 41C 30th Birthday Game
Message #11 Posted by Mark Edmonds on 4 July 2009, 8:51 p.m.,
in response to message #1 by Egan Ford

Interesting problem!

I haven't read anything added to the thread so I don't know if the solution has been posted. I did accidentally read the first couple of replies. To be honest, I don't think this is a 2^n type problem as the numbers just seem in the wrong ball-park to me.

However, my method is far from certain and short of drawing out the diagram, I don't know how to prove it and I think my solution only works for an even number of candles.

This answer is dependent on equal spacing of each candle round the perimeter. With non-equal spacing, you can't actually answer the question. So...

My result which I am far from confident on is: 5940. (give or take 30 maybe).

Mark

            
Re: 41C 30th Birthday Game
Message #12 Posted by Egan Ford on 5 July 2009, 11:17 a.m.,
in response to message #11 by Mark Edmonds

Quote:
To be honest, I don't think this is a 2^n type problem as the numbers just seem in the wrong ball-park to me.
Your instinct serves your well.
Quote:
With non-equal spacing, you can't actually answer the question.
Actually, you can.
                  
Re: 41C 30th Birthday Game
Message #13 Posted by Mark Edmonds on 5 July 2009, 3:39 p.m.,
in response to message #12 by Egan Ford

Quote:

Actually, you can.


Yes, it was a silly thing to say and I've realised that now but at the time, I was thinking that intersections that didn't meet would form a number of additional sections which would be extremely difficult to calculate.

I would like to see an explanation for how the example 15C programs calculate the correct result please. The method I tried using was based on dividing the circle into a number of triangles where you could easily calculate the number of intersections and then the number of individual portions. However, this only worked up to a point because it then left a polygon in the middle and my attempt to find a way of counting portions in that polygon failed.

So a friendly explanation would be much appreciated!

Mark

                        
Re: 41C 30th Birthday Game
Message #14 Posted by Gerson W. Barbosa on 5 July 2009, 4:21 p.m.,
in response to message #13 by Mark Edmonds

There's an OEIS sequence, A055795, which replicates the table generated by Valentin's program when 1 is added to each term. The sequence is called Binomial(n,4)+binomial(n,2), hence the HP-15C program. Of course this doesn't answer your question. The exact sequence related to this problem is OEIS A000127. You can find some links therein, like this one: Regions of a circle Cut by Chords to n points, which may be of help.

It is interesting to notice Egan's pictures suggested the candles did not have to be equally spaced, which was nice. Cutting along all those diagonal is not an easy task, now imagine placing all thoses candles on the edge of the cake so they make up a regular polygon...

Congratulations for trying to solve the problem by yourself! (unlike me)

Gerson.

Edited: 5 July 2009, 4:34 p.m.

                        
Re: 41C 30th Birthday Game
Message #15 Posted by Egan Ford on 5 July 2009, 8:05 p.m.,
in response to message #13 by Mark Edmonds

Mark,

I'll provide an explanation of both Valentin's and Gerson's solutions shortly. However, if you want to figure it out, then I would suggest that you start with any circle with at least four points and then draw the chords slowly and write down all your observations. You'll see it.

      
Re: 41C 30th Birthday Game
Message #16 Posted by Valentin Albillo on 5 July 2009, 10:27 a.m.,
in response to message #1 by Egan Ford

10 DEF FNF(N)=1+(N^4-6*N^3+23*N^2-18*N)/24

>FOR N=1 TO 30 @ N;FNF(N)@ NEXT N

1 1 2 2 3 4 4 8 5 16 6 31 7 57 8 99 9 163 10 256 11 386 12 562 13 794 14 1093 15 1471 16 1941 17 2517 18 3214 19 4048 20 5036 21 6196 22 7547 23 9109 24 10903 25 12951 26 15276 27 17902 28 20854 29 24158 30 27841

Best regards from V.

            
Re: 41C 30th Birthday Game
Message #17 Posted by Gerson W. Barbosa on 5 July 2009, 12:37 p.m.,
in response to message #16 by Valentin Albillo

Hello Valentin,

On the 15C:

001  LBL A
002  ENTER
003  ENTER
004  4
005  Cy,x
006  x<>y
007  2
008  Cx,y
009  +
010  1
011  +
012  RTN

30 GSB A => 27841

Best regards,

Gerson.

            
Re: 41C 30th Birthday Game
Message #18 Posted by Marcus von Cube, Germany on 6 July 2009, 2:59 a.m.,
in response to message #16 by Valentin Albillo

Hello Valentin,

nice formula! But I'd prefer an explanation over an implementation. I don't even see easily why the polynomial always produces an integer result.

                  
Re: 41C 30th Birthday Game
Message #19 Posted by hugh steers on 6 July 2009, 7:47 p.m.,
in response to message #18 by Marcus von Cube, Germany

This form of the result seems quite elegant, R(n) the number of cake regions:

I've been trying to think of whether it makes the result any easier to understand. for example, it's the sum of combinations of pairs, triangles and quads for all points except one. but why?

Also, in a variation, if you didnt want to cut all the combinations of points but just wanted to make 15 cuts across the cake. can you achieve `n' new pieces for each nth cut, so that the total after n cuts = n(n+1)/2+1

Further, suppose you could place the candles anywhere on the cake (but not co-linear), but wanted to minimise the number of pieces.

so, for 6, instead of:

you have,

You would then have the rectilinear crossing number of intersections. eg for 6 point K6 (above) this is 3. is the RCN related to the number of regions created and if so does this mean the number of pieces is NP-complete to calculate.

?

                        
Re: 41C 30th Birthday Game
Message #20 Posted by Egan Ford on 6 July 2009, 8:20 p.m.,
in response to message #19 by hugh steers

Quote:

Didn't you want min?
                              
Re: 41C 30th Birthday Game
Message #21 Posted by hugh steers on 7 July 2009, 4:23 a.m.,
in response to message #20 by Egan Ford

sorry, yes min.

                        
Re: 41C 30th Birthday Game
Message #22 Posted by Egan Ford on 7 July 2009, 2:26 a.m.,
in response to message #19 by hugh steers

Quote:
This form of the result seems quite elegant, R(n) the number of cake regions:

I've been trying to think of whether it makes the result any easier to understand. for example, it's the sum of combinations of pairs, triangles and quads for all points except one. but why?


I've shown below that R(n) = 1 + C(n,2) + C(n,4). You have shown that:
R(n) = C(n-1,0) +  C(n-1,1) + C(n-1,2)  +  C(n-1,3) + C(n-1,4)
So,
R(n) =     1    + (C(n-1,1) + C(n-1,2)) + (C(n-1,3) + C(n-1,4))

R(n) = 1 + C(n,2) + C(n,4)

It's the only relationship I see.
                  
Re: 41C 30th Birthday Game
Message #23 Posted by Gerson W. Barbosa on 6 July 2009, 10:33 p.m.,
in response to message #18 by Marcus von Cube, Germany

Quote:
I don't even see easily why the polynomial always produces an integer result.

Here Dr. Math explains the formula 1 + C(n,2) + C(n,4), which clearly produces integer results. It is equivalent to

1 + n!/(2!(n - 2)!)) + n!/(4!(n - 4)!)) =

1 + n(n-1)/2 + n(n-1)(n-2)(n-3)/24 =

1 + (n^4 - 6n^3 + 23n^2 - 18n)/24

Regards,

Gerson.

      
Re: 41C 30th Birthday Game -- Solution
Message #24 Posted by Egan Ford on 6 July 2009, 11:53 p.m.,
in response to message #1 by Egan Ford

Quote:
With all 30 candles around the edge and the cake divided the along the imaginary lines what will be the maximum number of pieces?
The answer is 27,841.

The number of pieces for any n number of candles is:

1 + C(n,2) + C(n,4)
This formula can be obtain from the following observations:

With one point there is one region. Each time a chord is added an existing region is split into two and the overall region count is increased by one. For steps 1-6 above this should be straightforward.

When a chord intersects with another chord, the chord still splits a region in two, however it also splits any region that has the intersected chord as an edge. (Follow step 7 to 8).

That’s it, so the number of regions is:

initial regions + number of chords + number of intersections

The initial regions is 1. Since all points connect to all points the number of chords is the number of unique combinations of point pairs or C(n,2). And, since two unique chords make a unique intersection and four unique points make two unique chords, then the number of intersections is the number of unique combinations of four points or C(n,4). Therefore: regions = 1 + C(n,2) + C(n,4). And that is the formula used in Gerson’s 15C solution.

Unfortunately the 41C does not have a combination function, and for large n such as 30, you cannot create your own using n!/k!(n!-k!). The only 41C module I could find that had a combination function was the PPC ROM and its implementation hoses Z making chain calculations challenging. However there is a better COMB function by Werner Huysegoms that can be obtained from here http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/archv013.cgi?read=39655 message #13. With this COMB loaded into my 41C, I can use the following program to compute the number of pieces created by 30 candles:

01 LBL "BDAY"      13 ST- Y           25 LASTX           
02 STO 00          14 X>Y?            26 INT             
03 4               15 X<>Y            27 ST/ Z           
04 XEQ "COMB"      16 +               28 RDN             
05 RCL 00          17 1 E-3           29 DSE X           
06 2               18 ST* L           30 ISG L           
07 XEQ "COMB"      19 X<>Y            31 GTO 02          
08 +               20 ISG L           32 LBL 00          
09 1               21 X=0?            33 RDN             
10 +               22 GTO 00          34 1 E3            
11 RTN             23 LBL 02          35 *               
12 LBL "COMB"      24 ST* Y           36 END          
An alternative would be to expand 1 + C(n,2) + C(n,4) to:
1 + n(n-1)/2 + n(n-1)(n-2)(n-3)/24
and then simplify to (the lazy may just want to cut and paste into Wolfram Alpha):
(n4 - 6n3 + 23n2 - 18n + 24)/24
Look familiar? This was the approach taken by Valentin. Here is my 41C version using the same:
01 LBL "BDAY2"      14 X^2              
02 ENTER^           15 23               
03 ENTER^           16 *                
04 ENTER^           17 +                
05 4                18 X<>Y             
06 Y^X              19 18               
07 X<>Y             20 *                
08 3                21 -                
09 Y^X              22 24               
10 6                23 +                
11 *                24 LASTX            
12 -                25 /                
13 X<>Y             26 END      

Hugh also pointed out an interesting relationship to the sum of the first five values of the nth line of Pascal's Triangle:

n =  1                       1                         R(n) = 1
n =  2                     1   1                       R(n) = 2
n =  3                   1   2   1                     R(n) = 4
n =  4                 1   3   3   1                   R(n) = 8
n =  5               1   4   6   4   1                 R(n) = 16
n =  6             1   5  10  10   5   1               R(n) = 31
n =  7           1   6  15  20  15   6   1             R(n) = 57
n =  8         1   7  21  35  35  21   7   1           R(n) = 99
n =  9       1   8  28  56  70  56  28   8   1         R(n) = 163
n = 10     1   9  36  84 126 126  84  36   9   1       R(n) = 256

For grins, expand Hugh's equation and then simplify. You'll get the same equation Valentin used. Or just use as-is, here is my 50g version:

What I like best about this challenge is that it is so easy to get mislead. 2n-1 is a common answer to this problem. And, if you assume a perfectly even distribution of points, then you get the minimum for even numbers, not the requested maximum. My drawings were intentionally unevenly distributed as a hint.

Thanks to all that participated in this birthday challenge.

Edited: 7 July 2009, 1:58 a.m.

            
Re: 41C 30th Birthday Game -- Solution
Message #25 Posted by Valentin Albillo on 7 July 2009, 5:39 a.m.,
in response to message #24 by Egan Ford

Hi, Egan:

    Egan posted:

      "(n4 - 6n3 + 23n2 - 18n + 24)/24

      Look familiar? This was the approach taken by Valentin. Here is my 41C version using the same:

            01 LBL "BDAY2"      14 X^2              
            02 ENTER^           15 23               
            03 ENTER^           16 *                
            04 ENTER^           17 +                
            05 4                18 X<>Y             
            06 Y^X              19 18               
            07 X<>Y             20 *                
            08 3                21 -                
            09 Y^X              22 24               
            10 6                23 +                
            11 *                24 LASTX            
            12 -                25 /                
            13 X<>Y             26 END      
      
      "

    First of all, thanks for the challenge and your very detailed, thorough solution, and most especially for the considerable time and effort you generously put in it, much welcomed and appreciated.

    Now, that said, and in regard with your quoted 41C RPN solution above ... Egan, please !!!

    It hurts the eyes, man !! ... :-)

    Didn't you ever heard of Horner's Rule as a particularly efficient way to quickly and accurately evaluate polynomials which further is uncannily suited to RPN and which was mentioned, demonstrated, and heartily recommended in each and every HP classic calculator's manual since the very beginning, even for non-programmable models ?

    The obvious plain-vanilla RPN solution for the HP-41C (or any RPN model for that matter) using it is as follows:

        01  LBL "VBDAY"
        02  ENTER
        03  ENTER
        04  ENTER
        05   6
        06   -
        07   *
        08   23
        09   +
        10   *
        11   18
        12   -
        13   *
        14   24
        15   +
        16  LASTX
        17   /
        18  END
    

    which is 8 steps shorter (31 %), simpler, clearer, and much faster as well !

    Taking into account your extreme proficiency when solving my past S&SMC challenges, I'm really surprised indeed ! ... :-)

    Were you one of my students you'd be getting an F- for this and a severe reprimand as well ...

Best regards from V.

Edit: typo

Edited: 7 July 2009, 5:49 a.m.

                  
Re: 41C 30th Birthday Game -- Solution
Message #26 Posted by Egan Ford on 7 July 2009, 9:35 a.m.,
in response to message #25 by Valentin Albillo

Good Morning Valentin,

Quote:
Didn't you ever heard of Horner's Rule as a particularly efficient way to quickly and accurately evaluate polynomials which further is uncannily suited to RPN and which was mentioned, demonstrated, and heartily recommended in each and every HP classic calculator's manual since the very beginning, even for non-programmable models ?
Sheez! What was I thinking?! I wasn't...

To be perfectly honest I lazily typed the expansion into Alpha, scrolled down to the Alternate form: and proceeded to enter the polynomial into my 41 emulator from left to right. It never occurred to me to use Horner's Rule. Most amateurish. Ah, the shame... :-)

Now I assure you that if this polynomial had be longer, then a deeper laziness would have kicked in (you know, that type of laziness where much more time is spent thinking about it so that much less time can be done doing it. Often the total time is greater as is the satisfaction).

Quote:
Taking into account your extreme proficiency when solving my past S&SMC challenges, I'm really surprised indeed ! ... :-)
It'll never happen again as long as my stack (short term memory) gets checked into my registers (long term memory).
Quote:
Were you one of my students you'd be getting an F- for this and a severe reprimand as well ...
Man, Dad will be disappointed. It's going to be a long day, and its starting to rain here in Toronto. Good grief. :-)
                        
Re: 41C 30th Birthday Game -- Solution
Message #27 Posted by Gerson W. Barbosa on 7 July 2009, 11:16 a.m.,
in response to message #26 by Egan Ford

Actually, for the program to fit in 18 steps Horner is not necessary in this case. If we rewrite the polynomial as

(24 + n(n - 1)((n - 2)(n - 3) + 12))/24 = 

(24 + (n2 - n)((n-2)2 - (n-2)) + 12))/24

then one possible HP-41 program will be

    01  LBL "BDAY3"
    02   x^2
    03  LASTX
    04   -
    05  LASTX
    06   2
    07   -
    08   x^2
    09  LASTX
    10   -
    11   12
    12   +
    13   *
    14   24
    15   +
    16  LASTX
    17   /
    18  RTN

Horner is more efficient though as it will require less operations (two multiplications and two subtractions versus three of each kind here).

Gerson.

            
Re: 41C 30th Birthday Game -- Solution
Message #28 Posted by Gerson W. Barbosa on 7 July 2009, 9:08 a.m.,
in response to message #24 by Egan Ford

Thank you for presenting both the problem and the magistral solution.

When the date arrives I would suggest a rectangular cake, like the one below, with two number-shaped candles on it so it doesn't elicit more problems :-)

                  
Re: 41C 30th Birthday Game -- Solution
Message #29 Posted by Mark Edmonds on 7 July 2009, 2:26 p.m.,
in response to message #28 by Gerson W. Barbosa

Yes, many thanks for the details everyone and a fun thread too! :)

Mark

                  
Re: 41C 30th Birthday Game -- Solution
Message #30 Posted by BruceH on 7 July 2009, 6:25 p.m.,
in response to message #28 by Gerson W. Barbosa

Mmm. Too late to respond to the thread but that cake was yummy. :-)

                        
Re: 41C 30th Birthday Game -- Solution
Message #31 Posted by Dave Shaffer (Arizona) on 7 July 2009, 6:46 p.m.,
in response to message #30 by BruceH

Quote:
Mmm. Too late to respond to the thread but that cake was yummy. :-)

All 27,841 pieces of it! (Bite size, to say the least.)

                              
Re: 41C 30th Birthday Game -- Solution
Message #32 Posted by Marcus von Cube, Germany on 8 July 2009, 5:31 a.m.,
in response to message #31 by Dave Shaffer (Arizona)

Egan and all who replied: Thanks for the challenge and the very good explanations. I'm impressed.

                        
Re: 41C 30th Birthday Game -- Solution
Message #33 Posted by Jake Schwartz on 8 July 2009, 2:02 p.m.,
in response to message #30 by BruceH

Quote:
Mmm. Too late to respond to the thread but that cake was yummy. :-)

Yes, and if I recall correctly, Frank Kingswood got the Pi key and I commented that he was now able to have his cake and eat his pi too!

Jake


[ Return to Index | Top of Index ]

Go back to the main exhibit hall