Jim Propp: Let me phrase the puzzle in a more (math-)fun way. A friend of yours has a biased coin, but she won't tell you what the bias p is ("Hey, I'm not THAT good a friend!"). She tosses the coin n times and tells you how many times it came up heads (call it X), and then she gives you a positive integer n'<n. Your job is to use n, n', and X, along with some supplemental randomness, to generate a number X' that is statistically indistinguishable from the (random) number of heads you would get if you tossed your friend's coin n' times. Note that you do not have access to your friend's coin; that is to say, you don't know its bias. Nonetheless, you can effectively simulate n' tosses of your friend's coin if she does you the favor of tossing it n times, where n'<n, and telling you how many heads she observed. Note that X' need not be independent of X. All we require is that X' is governed by the binomial distribution Binomial(p,n') provided that X is governed by the binomial distribution Binomial(p,n). I stress that the point of the puzzle is to find a way to do this that doesn't require knowledge of p. By the way, what's the quickest way to see that you CAN'T accomplish the above if n' is bigger than n?
--re the final sentence, if n=1 it seems clear you cannot simulate n'=1000 tosses just based on knowing whether that 1 toss came up heads. You need continuum information (value of p) to do so well in the limit of large n', but you have only 1 bit of information (heads/tails). --re the simulation problem when n'<n, proceed thus. Regard the n old tosses (of which X are heads) as a string of n bits, X of them 1-bits. Randomly permute the bits. Now, as your output, generate the number of 1-bits among the first n' bits in your permuted bitstring. It seems to me that if X is a genuine sample from the binomial(n,p) distribution, then your output must be a genuine sample from the binomial(n',p) distribution. (By the way, I never looked at Propp's original puzzle since I had no idea what a "Galton board" was. I figured it was something to do with genetics. But googling tells me that guess was totally wrong.)