2001 coins, each value 1, 2 or 3 are arranged in a row. Between any two coins of value 1 there is at least one coin, between any two of value 2 there are at least two coins, and between any two of value 3 there are at least three coins. What is the largest number of value 3 coins that could be in the row?
Answer
501
Solution
The only way we can have two value 3 coins the minimum distance apart is ...31213... . If we repeat that pattern then the conditions are all satisfied. So the optimal configuration is 312131213... . Since 2001 = 1 mod 4 that will give the last coin as 3 and a total of 1 + 2000/4 = 501 value 3 coins.
Thanks to Bekjan Jumabaev
© John Scholes
jscholes@kalva.demon.co.uk
15 February 2004
Last corrected/updated 15 Feb 04