41C 30th Birthday Game « Next Oldest | Next Newest »

 ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-04-2009, 05:28 PM 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 ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-04-2009, 05:50 PM 2^30= 1,073,741,824 ▼ Jeff Kearns Member Posts: 222 Threads: 21 Joined: Oct 2006 07-04-2009, 05:58 PM I would say 2^29 = 536,870,912 pieces Walter B Posting Freak Posts: 4,587 Threads: 105 Joined: Jul 2005 07-04-2009, 05:55 PM 2^29 = 536,870,912 Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 07-04-2009, 06:05 PM OK, I see, they are right, 2^29. Mybad. Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-04-2009, 06:35 PM 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. ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-04-2009, 07:59 PM Nope, but close. ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-04-2009, 08:46 PM 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. ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-05-2009, 11:15 AM 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. ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-05-2009, 11:55 AM 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. Mark Edmonds Senior Member Posts: 283 Threads: 33 Joined: Jul 2008 07-04-2009, 08:51 PM 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 ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-05-2009, 11:17 AM 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. ▼ Mark Edmonds Senior Member Posts: 283 Threads: 33 Joined: Jul 2008 07-05-2009, 03:39 PM 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 ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-05-2009, 04:21 PM 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. Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-05-2009, 08:05 PM 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. Valentin Albillo Posting Freak Posts: 1,755 Threads: 112 Joined: Jan 2005 07-05-2009, 10:27 AM ```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. ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-05-2009, 12:37 PM 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. Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 07-06-2009, 02:59 AM 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. ▼ hugh steers Senior Member Posts: 536 Threads: 56 Joined: Jul 2005 07-06-2009, 07:47 PM 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. ? ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-06-2009, 08:20 PM Quote: Didn't you want min? ▼ hugh steers Senior Member Posts: 536 Threads: 56 Joined: Jul 2005 07-07-2009, 04:23 AM sorry, yes min. Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-07-2009, 02:26 AM 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. Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-06-2009, 10:33 PM 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. Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-06-2009, 11:53 PM 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. ▼ Valentin Albillo Posting Freak Posts: 1,755 Threads: 112 Joined: Jan 2005 07-07-2009, 05:39 AM 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. ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 07-07-2009, 09:35 AM 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. :-) ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-07-2009, 11:16 AM 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. Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 07-07-2009, 09:08 AM 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 :-) ▼ Mark Edmonds Senior Member Posts: 283 Threads: 33 Joined: Jul 2008 07-07-2009, 02:26 PM Yes, many thanks for the details everyone and a fun thread too! :) Mark BruceH Senior Member Posts: 275 Threads: 38 Joined: Jul 2007 07-07-2009, 06:25 PM Mmm. Too late to respond to the thread but that cake was yummy. :-) ▼ Dave Shaffer (Arizona) Posting Freak Posts: 776 Threads: 25 Joined: Jun 2007 07-07-2009, 06:46 PM 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.) ▼ Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 07-08-2009, 05:31 AM Egan and all who replied: Thanks for the challenge and the very good explanations. I'm impressed. Jake Schwartz Senior Member Posts: 349 Threads: 66 Joined: Apr 2007 07-08-2009, 02:02 PM 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

 Possibly Related Threads... Thread Author Replies Views Last Post HP Prime: Baker's Game Mark Power 0 706 12-11-2013, 06:25 PM Last Post: Mark Power [HP-Prime] Simple Game (Bugs) CompSystems 1 700 11-01-2013, 10:18 AM Last Post: Han Another PPC DVD Update: 30th Year of Datafile + HP Conference Index Jake Schwartz 0 518 03-31-2013, 01:40 PM Last Post: Jake Schwartz Tunnel game for HP 39gII Mic 0 564 03-25-2013, 02:24 PM Last Post: Mic My birthday, so a little commemorative mini-challenge ! Valentin Albillo 43 4,749 03-07-2013, 03:44 AM Last Post: Walter B HP-28S plays "Happy Birthday" Kevin F 0 524 08-06-2012, 04:53 PM Last Post: Kevin F Happy 40th Birthday, HP35 Jake Schwartz 8 1,384 01-05-2012, 10:42 PM Last Post: db (martinez, ca.) Happy Birthday HP9810A Achim (Germany) 6 1,125 11-03-2011, 03:12 PM Last Post: Achim (Germany) Anyone Updated (re-flashed) a 12C 30th AE? linear 13 1,746 10-14-2011, 02:06 PM Last Post: linear HP12c 30th AE keyboard Paulo MO 4 887 10-01-2011, 03:26 AM Last Post: Paulo MO

Forum Jump: