A few days ago, Abbas posed to me a question in combinatorics. There are 50 coins on a table, of which some are heads-up and some are tails-up. You’re told how many are heads-up, but you don’t know which are heads-up (for example, you’re blindfolded). You need to flip some coins – again, without knowing whether you’re flipping from heads to tails or from tails to heads – and divide the coins into two groups with an equal number of heads.
Most mathematical problems are best translated into numbers. For example, I might call tails 0 and heads 1, and then say the total sum of the values of the coins is m, and given that either leave a coin, labeled a(n) as is or replace it by 1-a(n)…
But with this one, the intuitive solution is better. Suppose m = 1. Take any coin, flip it, and make it one group; don’t flip any other coin. If that coin was originally tails, then now it will be heads, so this group will have one heads-up coin, whereas the other will have the original heads-up coin. If that coin was the one heads-up coin, then now all coins will be tails-up, so both groups will have zero heads-up coins.
Let’s generalize this for every m. Take any group of m coins. This group will have k heads-up coins, where 0 <= k <= m. The other group will have m–k heads-up coins. Flipping all coins in the group of m coins, we get k tails-up coins, hence m–k heads-up coins, and we are done.