counting « The Math Less Traveled

Archive for the ‘counting’ Category

More cookies

Tuesday, July 27th, 2010

I recently received the following interesting problem from Shadowcat, which is a generalization of the cookie problem I’ve written about previously. We again want to count the ways to distribute identical cookies to non-identical students, with the twist that we impose an upper bound on the number of cookies received by each student (quite reasonable if we want to be mindful of the students’ nutrition):

Imagine that instead of ten cookies and five students, you have fifty cookies and ten students. (It’s easier to quantify this situation using larger numbers.) How many ways can you distribute these cookies among the students so that no student has any more than ten cookies?

Students may be given any number of cookies less than or equal to ten, including zero. The cookies are identical, just as in the original problem, so, as with the original problem, it doesn’t matter which cookie the student gets, just how many. But the students, again, are *not* identical, so which student gets a specific number of cookies is important.

I unfortunately haven’t had much time to think about it yet. Feel free to leave comments, thoughts, partial solutions, and solutions in the comments!

Tags: cookies, counting, students
Posted in arithmetic, challenges, counting | 9 Comments »

Optimal change-carrying

Thursday, June 24th, 2010

Recently Michael left the following challenge in a comment:

I’ve been trying to optimize my change-carrying habits. What is the smallest amount of quarters, dimes, nickels and pennies one can carry while still being able to give perfect change (two decimals)?

It’s not 100% clear what Michael meant by “give perfect change”, but let’s assume the goal is to be able to make any amount between 1 and 99 cents. For non-US readers, US coins are worth 1, 5, 10, and 25 cents.

Some questions for exploration:

What’s the smallest number of coins you can come up with that works? What are they?
Are there multiple solutions, or is the solution unique?
How can you prove that a proposed solution is optimal? Unique?
Can you answer the question for a different system of coins? For example, I am currently spending the summer in Cambridge, England, where coins are worth 1, 2, 5, 10, 20, and 50 pence. What if you also include the 1- and 2-pound (100 and 200 pence) coins, and want to be able to make change for every amount up to 5 pounds (the smallest note)?
The US and UK coin systems both have the property that a greedy strategy works for giving the smallest amount of change. That is, to make a certain amount of change with the smallest possible number of coins, you can just keep picking the biggest coin less than or equal to the remaining amount. What about coin systems without this property? Do they make this problem harder? Easier?
If you got to design your own system of coins with whatever denominations you wanted, how would you design it so that the minimum number of coins needed to make all amounts between 1 and 99 cents is as small as possible? As LARGE as possible?
What are some methodologies for attacking this sort of question in general?

Feel free to come up with your own generalizations as well. Post questions, discussion, and solutions in the comments but don’t peek until you’ve tried solving it! I’ve posted another change-making puzzle before as well; the discussion there might also give you ideas.

Tags: change, minimum
Posted in arithmetic, challenges, counting | 11 Comments »

A gentle introduction to the 5th Polymath project

Wednesday, April 21st, 2010

I highly recommend reading Jason Dyer’s description of the Erdős discrepancy problem, the subject of the most recent Polymath project (the Polymath projects are an experiment in massively collaborative mathematics, where anyone at all can contribute something towards a solution). The Erdős discrepancy problem in particular is fascinating because it is quite easy to understand the statement of the problem with only a knowledge of basic arithmetic—but it has been unsolved for almost 80 years!! Jason’s explanation of the problem is clear and engaging, and has cute pictures—go give it a read!

Tags: discrepancy, Erdős, polymath
Posted in arithmetic, counting, links, number theory, open problems | No Comments »

Challenge #12 solution, part II

Saturday, September 19th, 2009

Recounting the Rationals

Yes, that’s right, that Challenge #12, posted one year, five months, and a day ago. You see, I have this nasty habit of starting things and not finishing them… well, better late than never!

Question two of the aforementioned challenge asked this:

Given a positive integer n, in how many ways can n be written as a sum of powers of two, when each power is allowed to occur at most twice? Say denotes the number of different ways to write n as a sum of powers of two with at most two copies of each power allowed. What can you say about the function h?

These representations using at most two copies of each power of two are sometimes called hyperbinary representations. For example, 11 can be written as 2^3 + 2^1 + 2^0 or as 2^2 + 2^2 + 2^1 + 2^0 . It turns out these are the only hyperbinary representations of 11, so h(11) = 2 .

How to analyze this? We can use a similar approach to that outlined in the solution to part III (which asked a similar question, but allowing any number of copies of each power of two). First let’s think about odd numbers, that is, numbers of the form 2n + 1 . Any representation of an odd number must include an odd number of copies of 2^0 (otherwise the sum won’t be odd!), but since at most two copies are allowed, there must be exactly one copy of 2^0 . If we take away the 2^0 and divide everything else by two, we get a valid representation of . The reverse works as well: if we start with any valid representation of , multiply everything by two, and add a copy of 2^0 , we get a valid representation of 2n + 1 . This means that

h(2n+1) = h(n) .

What about even numbers? A valid representation of 2n + 2 has either two copies of 2^0 , or none. If it has none, we can simply divide by two to get a valid representation of n + 1 (and vice versa); if two, we can take away the copies of 2^0 and then divide by two to get a representation of , and vice versa. Therefore,

h(2n+2) = h(n+1) + h(n) .

These two equations, h(2n+1) = h(n) and h(2n+2) = h(n+1) + h(n) , along with the fact that h(0) = 1 , are enough to completely characterize h(n) . We can easily compute h(n) for the first few values of :

1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,1…

It’s immediately striking, of course, that h(n) isn’t strictly increasing: that is, just because m > n doesn’t mean h(m) > h(n) . In fact, even as the values of h(n) continue to get bigger on average, there are still some values of 1 hiding in there. In fact, h(0) = h(1) = h(3) = h(7) = h(15) = 1 , and the obvious conjecture is that h(2^k - 1) = 1 for every $k \geq 0$ .

The next thing we notice, after staring a bit, is that the h(n) sequence contains a lot of palindromes! Every section sandwiched in between two 1’s seems to read the same forwards and backwards. Let’s make some graphs so we can see these patterns more easily: below I’ve made graphs showing h(n) as goes from 1 to 100, 1000, and 10000, respectively.

The hyperbinary sequence through n=100

The hyperbinary sequence through n=1000

The hyperbinary sequence through n=10000

Pretty! We can clearly see the symmetric structure here, and the way that it occasionally (every 2^k - 1 ) jumps back down to 1.

Here’s another way to think about building the sequence. We start with the first two elements:

$1,\rrr{1}$

Now we copy the red part onto the end of the sequence (the copy will be blue), leaving a blank space in front of each blue number:

$1,\rrr{1},\blnk,\bbb{1}$

Now we fill in each blank (in green) by adding the two numbers on either side of it:

$1,\rrr{1},\gggr{2},\bbb{1}$

Now the blue and green part becomes the new red part:

$1,1,\rrr{2},\rrr{1}$

Now we repeat! Copy the red part to the end, leaving a blank in front of each copied number:

$1,1,\rrr{2},\rrr{1},\blnk,\bbb{2},\blnk,\bbb{1}$

Fill in each blank by adding the two numbers on either side:

$1,1,\rrr{2},\rrr{1},\gggr{3},\bbb{2},\gggr{3},\bbb{1}$

And again: blue and green become the new reds, copy the red numbers to the end with a blank in front of each:

$1,1,2,1,\rrr{3},\rrr{2},\rrr{3},\rrr{1},\blnk,\bbb{3},\blnk,\bbb{2},\blnk,\bbb{3},\blnk,\bbb{1}$

And fill in the blanks by adding:

$1,1,2,1,\rrr{3},\rrr{2},\rrr{3},\rrr{1},\gggr{4},\bbb{3},\gggr{5},\bbb{2},\gggr{5},\bbb{3},\gggr{4},\bbb{1}$

And so on. It takes a little bit of thought, but it can be seen that the method I’ve described here is really just a different way of expressing the equations h(2n+1) = h(n) and h(2n+2) = h(n+1) + h(n) ! But thinking about it this way makes it apparent why a 1 always shows up at h(2^k - 1) , and also why we end up with palindromes.

I’ll stop there for now; in an upcoming post I’ll bring things full circle by showing how these numbers relate to the Calkin-Wilf tree of rationals.

« Previous in series | Next in series »

Tags: binary, hyperbinary
Posted in challenges, counting, induction, pattern, sequences, solutions | 14 Comments »

Idempotent endofunctions

Friday, April 17th, 2009

Via Topological Musings comes another neat little counting problem.

A function is idempotent if applying it twice gives the same result as applying it once: that is, f(f(x)) = f(x) for any input x. Endofunction is just a fancy way of talking about a function whose domain and codomain are the same.

The challenge: consider the set $S = \{1,2,\dots, n\}$ ; how many different idempotent functions are there from to ? For example, when n = 3 one such function is given by f(1) = 2 , f(2) = 2 , and f(3) = 3 . Your answer should be an expression in terms of n.

Feel free to post various approaches and solution methods in the comments, but I won’t be posting a solution later; for that I’ll just direct you to Vishal’s post where I got this problem. He goes on to discuss the relation to exponential generating functions and combinatorial species, which is an amazing topic (although quite a ways above the normal level of TMLT; you have been warned!).

Tags: counting, function, idempotent
Posted in challenges, counting | 8 Comments »

Distributing cookies: solutions

Tuesday, April 14th, 2009

And now for some solutions to the cookie distribution problem. I’m actually going to describe four different methods of solution, and thereby (re)discover some nice combinatorial identities along the way. This is what I love about combinatorics—you discover all this rich structure just by coming up with different ways to count things!

Solution 1: Cookies and Fences

The first solution, as described in a comment by Mike, consists in considering permutations of cookies and fences.

Cookies and fences

If we set up the cookies in a row, we can use four fences to separate them into five sections; the first student will get the first section of cookies, the second student will get the second section, and so on. In the example above, student A gets one cookie, student B gets two, student C doesn’t get any, and students D and E get three and four, respectively. It’s easy to see that every distribution of cookies corresponds to an arrangement of fences, and vice versa. So, how many ways are there to arrange the fences? Think of it this way: we have fourteen “slots”, and into each slot we can put either a cookie or a fence. Choosing a distribution is just choosing in which of the fourteen slots to put the four fences, and there are $\binom{14}{4} = 1001$ ways to choose four out of fourteen slots. (If you don’t know about binomial coefficients, you can read about them here.) Incidentally, this is also the number of ways to distribute four fences to eleven students; just use the cookies to divide the fences into eleven sections (most of which will, of course, be empty). Although I have no idea why students would want fences.

This can be easily generalized: the above argument shows that there are $\binom{c + s - 1}{s - 1}$ ways to distribute c cookies to s students.

So, the problem is solved, right? What more can there be to say about it?

…plenty! This is a nice elegant solution, but it takes some cleverness (and/or luck, and/or experience with this sort of problem) to see it, and in fact it isn’t the first solution I came up with. Looking at some different methods of solution will also illuminate some of the rich structure of binomial coefficients.

Solution 2: Don’t Be So Mean

It seems mean that sometimes some students don’t get any cookies at all. Wouldn’t it be much nicer if every student got at least one cookie (even if they still might be distributed unevenly)? The key insight, as pointed out by Jonathan, is this: the number of ways to distribute ten cookies to five students is the same as the number of ways to distribute fifteen cookies to five students in such a way that each student gets at least one cookie.

Why is this? Well, suppose you have distributed fifteen cookies to five students so that each student has at least one. Now take one cookie away from each student—and you have now distributed ten cookies to five students. Conversely, if you have distributed ten cookies to five students somehow, if you now give each student an extra cookie, you have distributed fifteen cookies and each student has at least one. Each distribution of ten cookies corresponds to precisely one distribution of fifteen cookies where each student gets at least one, and vice versa, so counting one is the same as counting the other. Now, how many ways are there to distribute fifteen cookies like this? We can line the cookies up and imagine choosing points at which to divide them; to divide them into five groups, we have to choose exactly four out of the fourteen possible places to divide the cookies. (There is at least one cookie between any two dividing points, which means that each student has to get at least one cookie.)

Cookies and dividers (each student gets at least one cookie)

The above illustration shows a distribution in which students A, B, C, D, and E get two, three, one, four, and five cookies respectively. Note that this is the distribution of fifteen cookies that corresponds to the distribution of ten cookies illustrated with the fences previously.

So, the number of ways to distribute fifteen cookies to five students so that each gets at least one is $\binom{14}{4}$ ; more generally, the number of ways to distribute c cookies to s students so each gets at least one is $\binom{c-1}{s-1}$ . Also, the total number of ways to distribute c cookies to s students is the same as the number of ways to distribute c+s cookies to s students so that each gets at least one.

Solution 3: One at a time, please!

Another way of approaching the problem comes courtesy of meichenl. To distribute cookies to s students, we first have to give some number of cookies to the first student; we can give her anywhere from zero to ten cookies. If we give her k cookies, there are c – k cookies left to distribute to the other s – 1 students. If we let D(c,s) stand for the number of ways of Distributing c cookies to s students, we can write this observation as

$\displaystyle D(c,s) = \sum_{k=0}^c D(c - k, s - 1).$

That is, we split the distribution up into cases based on how many cookies we give to the first student; in each case we’ve reduced the problem to a simpler distribution problem. Adding everything up, we get the above recurrence—we’ve defined D(c,s) recursively, that is, in terms of itself. This definition actually gets off the ground because we can identify some base cases, that is, simple situations in which we know the answer without breaking things down further. In particular, D(0,s) = 1 for any s (there’s only one way to distribute zero cookies—namely, to give zero cookies to each student), and D(c,1) = 1 for any c (there’s only one way to distribute cookies to a single lucky student!).

So, once we have this recurrence, what do we do with it? We can use it for direct calculation, as Mark James apparently did; he also used the recurrence in a computer program to print all the distributions. As observed by Daniel Klein, this sort of recurrence is also perfectly suited for a programming technique called dynamic programming; it’s easy to turn this recurrence into a computer program to compute D(c,s) for any values of c and s (although in this particular case, as we’ve seen, there are more efficient ways to compute D(c,s) ).

But here’s another interesting thing: we already know what D(c,s) is, from solutions 1 and 2: it’s $\binom{c+s-1}{s-1}.$ So if we substitute this into the above recurrence, we get

$\displaystyle \binom{c+s-1}{s-1} = \sum_{k=0}^c \binom{c - k + s - 2}{s - 2}$

If we substitute d + 1 in place of s – 1 everywhere, we can make this a little nicer without changing anything (d is just a new variable I made up, it doesn’t stand for anything in particular):

$\displaystyle \binom{c+d+1}{d+1} = \sum_{k=0}^c \binom{c + d - k}{d}$

We’ve discovered an identity involving sums of binomial coefficients! Neat! Now, you might think, “OK, let’s prove this by induction.” But we need do no such thing. We have already argued that the expression on the left and the expression on the right count the same things—so they must be equal! This is the epitome of a combinatorial proof: to show that two things are equal, just show that they represent two different ways of counting the same thing.

Solution 4: How mean do you want to be?

The last solution (at least, the last solution I will discuss in this post!) comes courtesy of Dave. Instead of breaking the distribution into cases according to how many cookies we give to the first student (as in the previous solution), we can break it into cases according to how many students get any cookies: we can give all the cookies to one student, or give them all to two students, or three, and so on.

The first case is easy: if we give all the cookies to one student, there are 5 ways to choose which student to give the cookies to, and only one way to give them the cookies. What if we give all the cookies to two students? Well, there are $\binom{5}{2}$ ways to choose which two students get cookies. Now we want to distribute the ten cookies to these two students in such a way that each student gets at least one cookie (otherwise we are back in the first case). As previously noted in solution 2, there are $\binom{9}{1}$ ways to do this. If three students get cookies, there are $\binom{5}{3}$ ways to choose the three students, and $\binom{9}{2}$ ways to distribute the cookies, and so on. Generalizing, we see that

$\displaystyle D(c,s) = \sum_{k=1}^s \binom{s}{k} \binom{c-1}{k-1}.$

Egads! We’ve discovered another combinatorial identity, this one involving a sum of products of binomial coefficients!

$\displaystyle \binom{c+s-1}{s-1} = \sum_{k=1}^s \binom{s}{k} \binom{c-1}{k-1}.$

There’s yet another method of solution I’m aware of—the theory of combinatorial species and generating functions—but that can wait for another post, I think we’ve had quite enough combinatorial goodness for one day!

Tags: binomial coefficients, combinatorial identities, combinatorics, cookies, counting, distribution
Posted in counting, proof, solutions | 4 Comments »

Distributing cookies

Wednesday, April 1st, 2009

Here’s a neat problem I saw in a recent post by Steven Miller on the Williams College math department blog. The problem comes from an old Putnam competition, one of the most prestigious college mathematics competitions. (It’s also one of the most difficult—out of a possible 120 points, the median score is 1!)

Ten cookies and five students

There are ten identical cookies and five students. How many ways can the cookies be distributed among the students?

Note that the cookies are identical, so it doesn’t matter which cookies a student gets, just how many. The students, of course, are not identical, so student A getting four cookies and student B getting two is different than A getting two and B getting four. Assume that the cookies can’t be split into pieces. Note that giving cookies to some students but not others is a valid way of distributing them, as long as all the cookies are distributed. For example, giving six cookies to student A, four to student C, and none to anyone else is a valid distribution.

My wife and I had a fun time solving this problem, which leads to all kinds of interesting combinatorial insights. I’ll describe our
analysis in an upcoming post.

Tags: combinatorics, cookies, Putnam
Posted in challenges, counting | 19 Comments »

Chessboard counting: solutions and further challenges

Monday, March 30th, 2009

And now for some solutions to the chessboard counting challenges.

The first challenge was to count the number of squares of any size on an 8×8 chessboard. The key here (as with many counting problems) is to break the problem down in an appropriate way. In this case, we can think about counting each size square separately. There is only one square with sides of length 8. There are 4 squares of size 7—they can be in one of two positions horizontally, and one of two positions vertically. It’s not hard to see that there are squares of size 6, of size 5, and so on. So the total number of squares is $1^2 + 2^2 + \dots + 8^2 = 204$ .
This pattern continues; on an n by n chessboard, there are $1^2 + 2^2 + \dots + n^2 = \sum_{k=1}^n k^2$ total squares. There’s actually a nice closed formula for this sum for general n: $\frac{n(n+1)(2n+1)}{6}$ . (Showing how to derive this formula is a good subject for another post. We can check it for n = 8: $(8 \cdot 9 \cdot 17)/6 = 4 \cdot 3 \cdot 17 = 204$ , as expected.)
Counting rectangles instead of squares turns out not to be too much harder. There are $8 \cdot 8$ 1 by 1 rectangles, $8 \cdot 7$ 1 by 2 rectangles, $7 \cdot 8$ 2 by 1 rectangles, and so on. In general, there are j by k rectangles. So the total number of rectangles is
$\scriptstyle (8 \cdot 8 + 7 \cdot 8 + \dots + 1 \cdot 8) + (8 \cdot 7 + \dots + 1 \cdot 7) + \dots + (8 \cdot 1 + \dots + 1 \cdot 1)$

That looks annoying to add up, but there’s a clever trick we can pull. Notice that we can factor an 8 out of the first parenthesized expression above, a 7 out of the second, and so on, yielding

$\scriptstyle 8(8 + 7 + \dots + 1) + 7(8 + 7 + \dots + 1) + \dots + 1(8 + 7 + \dots + 1)$

But now we can factor $(8 + 7 + \dots + 1)$ out of this, yielding

$(8 + 7 + \dots + 1)^2 = 36^2 = 1296.$

Ah, that’s much nicer!
For a general m by n chessboard, the same method yields
$(m + (m-1) + \dots + 1)(n + (n-1) + \dots + 1)$

total rectangles. Using the closed formula for the sum of the numbers from 1 through n, we can rewrite this as .

See the comments to the previous post for some further analysis. Also in the comments, Veky posed the following follow-up challenge: how many squares (or rectangles) are there if we also allow squares (rectangles) which are not parallel to the sides of the chess board—the only restriction is that their vertices must occur at “crosshair” points in between the squares of the chess board?

Tags: chess, chess board, counting, rectangles, squares
Posted in challenges, counting, solutions | 2 Comments »

Chessboard counting

Friday, March 13th, 2009

I am currently doing a unit on combinatorics (the mathematical study of counting) with my precalculus students, and I was inspired to post a few counting-themed challenge problems for your enjoyment. (Also, it’s my spring break!)

As you probably know, a chess board consists of 64 squares arranged in eight rows and eight columns.

How many squares—of any size—are on a chess board? Each of the 64 smallest squares count, of course, but there are also larger ones; for example, the four squares in the upper left corner form a 2×2 square.
How many squares of any size would there be on a 9 by 9 chess board? 10 by 10? n by n?
How many rectangles of any size and shape are there on a chess board? Is this easier or harder than counting squares?
How about rectangles on 9 by 9, 10 by 10, n by n, or m by n chess board?

Tags: chess, chess board, counting, rectangles, squares
Posted in challenges, counting | 10 Comments »

Carnival of Math #48, and Monday Math Madness #25

Saturday, January 31st, 2009

The 48th Carnival of Mathematics is posted at Concrete Nonsense. My favorite posts include Foxmath’s post about a strange iterated sequence involving pi and this amazing picture of a fractal cabbage. Also near and dear to my heart is Mark Dominus’s post on monads and closure operators.

Also, check out Monday Math Madness #25 over at Wild About Math!. This week’s problem is a very interesting counting problem.

Tags: carnival, counting, fractal cabbage, monads, pi
Posted in challenges, counting, famous numbers, fractals, links | 1 Comment »

The Math Less Traveled