▼
Posts: 1,619
Threads: 147
Joined: May 2006
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
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
▼
Posts: 222
Threads: 21
Joined: Oct 2006
I would say 2^29 = 536,870,912 pieces
Posts: 4,587
Threads: 105
Joined: Jul 2005
Posts: 1,392
Threads: 142
Joined: Jun 2007
OK, I see, they are right, 2^29. Mybad.
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 1,619
Threads: 147
Joined: May 2006
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 1,619
Threads: 147
Joined: May 2006
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 283
Threads: 33
Joined: Jul 2008
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
▼
Posts: 1,619
Threads: 147
Joined: May 2006
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.
▼
Posts: 283
Threads: 33
Joined: Jul 2008
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
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 1,619
Threads: 147
Joined: May 2006
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.
Posts: 1,755
Threads: 112
Joined: Jan 2005
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 3,283
Threads: 104
Joined: Jul 2005
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.
▼
Posts: 536
Threads: 56
Joined: Jul 2005
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.
?
▼
Posts: 1,619
Threads: 147
Joined: May 2006
Quote:
Didn't you want min?
▼
Posts: 536
Threads: 56
Joined: Jul 2005
Posts: 1,619
Threads: 147
Joined: May 2006
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.
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 1,619
Threads: 147
Joined: May 2006
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.
▼
Posts: 1,755
Threads: 112
Joined: Jan 2005
Hi, Egan:
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.
▼
Posts: 1,619
Threads: 147
Joined: May 2006
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. :-)
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 2,761
Threads: 100
Joined: Jul 2005
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 :-)
▼
Posts: 283
Threads: 33
Joined: Jul 2008
Yes, many thanks for the details everyone and a fun thread too! :)
Mark
Posts: 275
Threads: 38
Joined: Jul 2007
Mmm. Too late to respond to the thread but that cake was yummy. :-)
▼
Posts: 776
Threads: 25
Joined: Jun 2007
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.)
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
Egan and all who replied: Thanks for the challenge and the very good explanations. I'm impressed.
Posts: 349
Threads: 66
Joined: Apr 2007
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
|
