Finding the magic coins

I’ve been reading through Daniel Velleman and Stan Wagon’s puzzle book Bicycle or Unicycle? and generally enjoying it – the puzzles include simple variations on classics, clever things I haven’t seen before, and some nontrivial uses of real mathematical thinking (as in the title puzzle, which asks whether it is possible for a bicycle to move in such a way that its rear wheel follows exactly along the path of its front wheel). Of course, Tanya’s blog appears several times. The solutions often go beyond the puzzle posed. As is to be expected, they have some coin-weighing puzzles. Here is a generalization of one of them:

You are presented with a set of N coins, among which S are special. You cannot tell which ones are special and which ones are not. Your goal is to choose a subset of coins that contains exactly k special coins. After each choice, an oracle tells you whether or not you have succeeded. What is the value f(N, S, k) of the smallest number of guesses you need to make to succeed?

Velleman–Wagon ask for the value of f(8, 4, 2); their source for the problem is the puzzle column from the MSRI newsletter, which asks to show that f(100, 50, 25) ≤ 50. Here are some some additional facts one might like to show (assuming, as is natural, that 0 ≤ kSN):

  • f(N, N, k) = f(N, S, S) = f(N, S, 0) = 1 for all choices of N, S, k
  • f(N, S, k) = f(N, S, S - k)
  • f(N, 2, 1) \leq \lceil \log_2(N)\rceil
  • f(N, 3, 1) \leq 2 \lceil \log_2(N) \rceil

Can one say anything interesting in general? For example, what is the asymptotic growth of f(N, 2k, k) for fixed k?

This entry was posted in Book reviews, Books, Combinatorics, Math and tagged , , , . Bookmark the permalink.

1 Response to Finding the magic coins

  1. JBL says:

    Or f(N, \alpha N, \beta N) for constants 0 < β < α < 1? (For this version, I think that I can prove that you need at least c \sqrt{N} guesses, for a constant c that depends on α and β, by considering how many S-subsets intersect a given m-set in exactly k elements; the best m is about \frac{\beta}{\alpha} N, and then you do a union bound.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s