## Combinatorics

An archive of questions and answers that may be of interest to puzzle enthusiasts.
Back to main page

Question 1 - alphabet.blocks:
What is the minimum number of dice painted with one letter on all six sides such that all permutations without repetitions of n letters can be formed by placing n dice together in a line? Show Answer

Question 2 - coinage/combinations
Assuming you have enough coins of 1, 5, 10, 25 and 50 cents, how many ways are there to make change for a dollar? Show Answer

Question 3 - coinage/dimes:
"Dad wants one-cent, two-cent, three-cent, five-cent, and ten-cent stamps. He said to get four each of two sorts and three each of the others, but I've forgotten which. He gave me exactly enough to buy them; just these dimes." How many stamps of each type does Dad want?
A dime is worth ten cents. -- J.A.H. Hunter Show Answer

Question 4 - coinage/impossible:
What is the smallest number of coins that you can't make a dollar with? I.e., for what N does there not exist a set of N coins adding up to a dollar? It is possible to make a dollar with 1 current U.S. coin (a Susan B. Anthony), 2 coins (2 fifty cent pieces), 3 coins (2 quarters and a fifty cent piece), etc. It is not possible to make exactly a dollar with 101 coins. Show Answer

Question 5 - color
An urn contains n balls of different colors. Randomly select a pair, repaint the first to match the second, and replace the pair in the urn. What is the expected time until the balls are all the same color? Show Answer

Question 6 - full
Consider a string that contains all substrings of length n. For example, for binary strings with n=2, a shortest string is 00110 -- it contains 00, 01, 10 and 11 as substrings. Find the shortest such strings for all n. Show Answer

Question 7 - gossip:
n people each know a different piece of gossip. They can telephone each other and exchange all the information they know (so that after the call they both know anything that either of them knew before the call). What is the smallest number of calls needed so that everyone knows everything? 01, 10 and 11 as substrings. Find the shortest such strings for all n. Show Answer

Question 8 - grid.dissection:
How many (possibly overlapping) squares are in an mxn grid? Assume that all the squares have their edges parallel to the edges of the grid. 01, 10 and 11 as substrings. Find the shortest such strings for all n. Show Answer

Question 9 - permutation
Compute the nth permutation of k numbers (or objects). Show Answer

Question 10 - subsets:
Out of the set of integers 1,...,100 you are given ten different integers. From this set, A, of ten integers you can always find two disjoint non-empty subsets, S & T, such that the sum of elements in S equals the sum of elements in T. Note: S union T need not be all ten elements of A. Prove this. Show Answer

Question 11 - transitions:
How many n-bit binary strings (0/1) have exactly k transitions (an adjacent pair of dissimilar bits, i.e., a 01 or a 10)? Show Answer