Thursday, December 8, 2011

A Sweet Tooth

As I mentioned in yesterday's post, I've been working through a book of puzzles for programmers.  The title of the first problem is 'A Sweet Tooth', and is very apropos since I had a visit to the dentist this morning (I should probably visit the dentist more and do puzzles less, but that's another matter).

In the problem, there are two children playing a game of cutting cakes and trying to get the largest pieces.  Dennis Shasha, the author, does a pretty good job of explaining the problem, but the hints he gives are a bit wordy and I think those who haven't done a lot of math proofs before might not bother with them.  I think it's easier to state assumptions and separate out the reasoning into cases, working through the math for each methodically.  I like to write mine out on a white board and I wrote out all the algebra, but ended up with the same solution as the one in the book.

I'm too lazy to type it out, but thanks to my handy cell phone you can see how I did it here.  Here's my answer to the first problem:

And here's my answer to the second:

I think it would be fun to code up a generic solution for x number of cakes.  I'll try to post it here when I do.

No comments: