To find fake coin in 3k+1 weighings among 3^2k coins
Source: All-Russian Olympiad 2008 9.8
June 14, 2008
inductioninequalitiesalgorithmlinear algebramatrixcombinatorics proposedcombinatorics
Problem Statement
We are given apparently identical coins,one of which is fake,being lighter than the others. We also dispose of three apparently identical balances without weights, one of which is broken (and yields outcomes unrelated to the actual situations). How can we find the fake coin in 3k\plus{}1 weighings?