gjk@talcott.UUCP (Greg Kuperberg) (03/06/85)
> > Hey Ron, if he cut the fly in four peices with only two > > swords, shouldn't he have gotten first prize?!?! > > Watch: > > /-----\ > | |_ > | _| <- Fly (sort of) > | | > \----/ > > /-----\ > | |_ > |||====-------- One sword > | | > \----/ > > | > /--|--\ > |__|__| > ___|___ A second sword > | # | > \--#-/ > # > > /-- --\ > |_| |_| > ___ ___ Four parts (count them) > | | | | > \-- -/ > > I hope this clairifies the matter. > > Wayne Ok, folks, and now for a puzzle: If the man had used, say twenty, short-swords instead of two, into how many pieces could he have cut up the fly? (Assume that the fly has a convex shape, and that its components do not scatter after the first few swords, but merely separate a little, as above.) --- Greg Kuperberg harvard!talcott!gjk "2*x^5-10*x+5=0 is not solvable by radicals." -Evariste Galois.
leeper@ahutb.UUCP (m.r.leeper) (03/08/85)
REFERENCES: <233@tekred.UUCP> <222@wuphys.UUCP> <101@ucbcad.UUCP>, <324@talcott.UUCP>
Using finite differences and extrapolating up from lower dimensional
cases, the answer is easy to see, but probably harder to prove.
Dividing up a line with n points you get n+1 pieces. The first set of
difference are all ones and all after that are zeros.
1
1
2 0
1 0
3 0 0
1 0
4 0
1
5
Dividing up a plane with lines you get the first set of differences
are the values from the previous case:
1
1
2 1
2 0
4 1 0
3 0 0
7 1 0
4 0
11 1
5
16
One can see this is correct because the second cut can intersect the
first cut, making four pieces. The next cut can intersect two previous
cuts, adding three pieces. The next cut can interect all three
previous cuts adding four more pieces, etc.
1
1
2 1
2 1
4 2 0
4 1 0
8 3 0 0
7 1 0
15 4 0
11 1
26 5
16
42
The n-th term is (n^3 + 5*n + 6)/6
Twenty cuts will give you 1351 pieces.
Mark Leeper
...ihnp4!ahutb!leeperrobertm@dartvax.UUCP (Robert P. Munafo) (03/10/85)
> 1 > 1 > 2 1 > 2 1 > 4 2 1 > (etc...) No, you told it wrong!! The way I heard it was: 1 > 1 2 > 1 > 2 > 1 4 > 2 > 1 (etc...) Now that's funny! ------ -- If this be error and upon me proved, Then I never writ, nor no man ever loved. Robert P. Munafo - Shakespeare ...!{decvax,cornell,linus}!dartvax!robertm