Vol. 14: Puzzle This
MAKE's favorite puzzles.
Illustrations by Roy Doty
Digital Edition
SUBSCRIBERS:Read this article now in your digital edition!
Get Make:
Subscribe to MAKE and get the best rate!
+ Downloads & Extras:
Answers
» MAKE: NOISE — Discuss this article
You must be logged in to post a talkback.[ Display main threads only] [ Oldest First]
Showing messages 1 through 3 of 3.

You must be logged in to reply.
Well stated, I couldn't agree more!Posted by sodium11 on May 20, 2008 at 12:32:12 Pacific Time

You must be logged in to reply.
sodium11, I also think the explicitly combinatorial solution is more natural. However, both approaches are two sides of the same coin since the binomial coefficients are defined by the recursion B(n,m) = B(n1,m) + B(n1, m1).
Posted by eharley on May 20, 2008 at 09:19:35 Pacific Time

Cheesecake  brute force or formula?
You must be logged in to reply.
While I would never disparage the brute force method of solving the cheesecakecheckerboard problem, I hardly think it is the "easiest" way to solve the problem, especially if you have a calculator. The way I generated the formula is as follows:
The total number of movements the critter must make is sixteen: eight eastward and eight southward.
Suppose slips of paper numbered 1 through 16 are placed in a hat and we pick out eight of them at random; and at the steps represented by those numbers, he moves east, and at the other steps he moves south. (Thus, if one of the slips is #1, then the first step will be east, if slip #1 is not picked, the first step will be south.)
The total number of possible paths to the cheesecake is equal to the number of combinations of eight slips that can be picked from a set of sixteen. This is equal to 16!/8!8!, which yields the correct answer.
The more general version of this formula is (l+w)!/l!w! where l is the length of the grid and w is the width.
Posted by sodium11 on May 19, 2008 at 17:53:26 Pacific Time
Showing messages 1 through 3 of 3. 
Join the conversation  every MAKE article has an online page that includes a place for discussion. We've made these RSS and Atom feeds to help you watch the discussions: subscribe.