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.
