__Combinatorics__

An archive of questions and answers that may be of interest to puzzle enthusiasts.
__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