An even dozen practice combinatorics problems. Have fun!
1) In how many ways can we select two distinct integers from the set {1, 2, ..., 100} so that their sum is even?
2) How many distinct arrangements of the letters INTELLIGENCE have the letters INT next to each other and in order and have the letter G appear somewhere after the INT?
3) On a standard 8x8 chessboard, a rook is permitted to move any number of squares vertically or horizontally. How many different paths can the rook follow from the lower left corner of the board to the upper right corner of the board if all moves must be forward or to the right?
4) A classic puzzle: You own 12 black socks and 12 brown socks, and you keep them all jumbled together in a dresser drawer. You get up in the morning and without turning on the light blindly pick some socks from the drawer. How many must you pick in order to be sure you have 2 that match?
5) Prove by mathematical induction:
for every integer n >1.
6) Six distinct pairs of boots are thrown together in a pile. How many must be picked in order to guarantee that we’ve picked a matching pair?
7) Prove that in any set of 52 distinct integers, there must be two whose sum or difference is a multiple of 100.
8) Prove that for all integers n and r with .
9) At a theater, 7 gentlemen check their hats. Unfortunately, the hat-check person mixed up the claim tags.
In how many ways can the hats be returned so that no gentleman gets his own hat?
In how many ways can the hats be returned so that at least two gentleman gets their own hat?
10) Prove: If m and n are positive integers, then the decimal expansion of the rational number must end with a repeating sequence of digits (possibly all zeroes).
11) A party store sells helium balloons in 20 different colors. We purchase a “bouquet” of 30 balloons. How many color-combinations are possible if we insist on at least one balloon of each color?
12) A store has a promotional sale on 12 different kinds of candy bars. A customer can pick one bar of each of 5 different types, Although different selections may cost different amounts, no selection will cost more than $1.75. Prove that there must be two different selections of 5 bars each that cost the same amount.