Looking for Counting Problems for Videos

by rrusczyk, Aug 17, 2008, 3:34 PM

I'm getting to the point where I've finished videos on most of the basic ideas from our Introduction to Counting & Probability book. I'd like to shoot a number of videos on harder problems that use basic concepts (in other words, no generating functions, no advanced inclusion-exclusion, no recursion). So, I'm looking for suggestions. What are some of your favorite counting problems that can be solved with basic counting tools? It's fine to suggest problems that come from contests, like MATHCOUNTS, AMC, or HMMT, but please let me know what contest the problems comes from. I'm looking for problems that are interesting, challenging, and that would be good teaching tools.

AoPS

math

videos

Comment

5 Comments

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

balls and walls!! bijections are good

by not_trig, Aug 17, 2008, 3:48 PM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

I'll have a whole series of videos eventually on those types of problems (I call them distribution problems).

by rrusczyk, Aug 17, 2008, 5:28 PM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Brian Lawrence presented a nice combinatorial solution to the following problem (which was on a MOP test, and is very well known) which is usually killed with a roots of unity filter...find the number of subsets of {1,2,...,2008} such that the sum of the elements is divisible by 5. I don't know if anyone came up with this during the test (I'm pretty sure the answer is no in red, not sure about blue). This is a pretty hard problem to do combinatorially.

So first consider the subsets that for all $0\le i\le400$ , either all of $5i + 1,5i + 2,5i + 3,5i + 4,5i + 5$ are in the subset or all of them are not. Call this set of subsets $A$ (stealing notation from the solution manual). So considering first the terms in the subset less than or equal to 2005, these terms sum to a multiple of 5. Then we have 2006, 2007, 2008, there are 2 ways to take a subset of those 3 to make a multiple of 5 (namely 2007+2008 and none of them). So there are $2\cdot2^{401} = 2^{402}$ subsets here.

Now consider the set of the other $2^{2008} - 2^{404}$ subsets, $B$ . We're going to show that we can partition B into $\dfrac{2^{2008} - 2^{404}}{5}$ 5 element subsets so that the sums of the elements in each of the 5 subsets in the subset form a complete residue class mod 5.

So take an arbitrary set $T$ . in B. Since it's not in A, there exists an integer $0\le i\le 400$ such that of $5i + 1,5i + 2,5i + 3,5i + 4,5i + 5$ , some are in $T$ and some are not in $T$ . Take the smallest possible $i$ . Define a permutation $\phi(T)$ on $T$ as follows (again, notation stealing). If $k\le 5i$ or $k > 5i + 5$ , $k\in\phi(T)$ if and only if $k\in T$ . Then, for $k = 5i + 2,5i + 3,5i + 4,5i + 5$ , $k - 1\in\phi(T)$ if and only if $k\in T$ . Finally, $5i + 5\in\phi(T)$ if and only if $5i\in T$ . Since not all of $5i + 1,5i + 2,5i + 3,5i + 4,5i + 5$ are in T or not in T, $\phi(T)$ and $T$ are distinct.

Then we similarly get $T,\phi(T),\phi^{2}(T),\phi^{3}(T),\phi^{4}(T)$ . Then it's easy to check that the elements of these five sets have distinct sums mod 5, so exactly 1/5 of the sets in B have their elements summing to a multiple of 5.

So now we just compute $2^{402} + \dfrac{2^{2008} - 2^{404}}{5} = \dfrac{2^{2008} + 2^{402}}{5}$ .

This post has been edited 1 time. Last edited by CatalystOfNostalgia, Aug 17, 2008, 8:55 PM

by CatalystOfNostalgia, Aug 17, 2008, 5:54 PM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

You could do probability? cause i suck at it

by Poincare, Aug 17, 2008, 8:43 PM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Here are some that I like.

Star polygon are created as follows: n points are equally distributed around the circumference of a unit circle. An initial point P0 is chosen and each of the remaining points are then consecutively labeled clockwise.
$P_1,P2,P2,...., P_{n-1}$ .
For each m such that $0 < m < n$ , we may or may not construct a star polygon in the following way: We construct the segment $P_0P_m$ . Now a chord of the same length as $P_0P_m$ is constructed starting from Pm and ending at the $m$ th point counting clockwise from $P_m$ . This process is repeated until arriving at $P_0$ . If all the $n$ points are used in this process, then we say that a star polygon has been constructed for this choice of $m$ . How many distinct star polygons are there for $n=24$ ?

The number 632 is a multiple number since the first digit 6 is the product of the other two digits of the number. How many three-digit multiple numbers less than 600 exist?

How many positive two-digit numbers less than 40 have an odd number of factors?

by isabella2296, Aug 17, 2008, 9:12 PM