Each of 2001 coins are assigned the value 1, 2, or 3 and they are arranged in a row.
• Between any two coins assigned the value of 1, there is at least one coin.
• Between any two coins assigned the value of 2, there are at least two coins.
• Between any two coins assigned the value of 3, there are at least three coins.
Determine the maximum number of coins, assigned the value of 3, that could be in the row.
*** Adapted from a problem appearing in a Russian Mathematical Olympiad.
The closest that any pair of 3-coins can be placed is every fourth location - aka to have exactly three other coins between them. So the densest that the row of coins can be is to have the 3-coins every fourth location.
Then starting with a 3-coin we can have 501 3-coins in the row of 2001 coins. Filling in the spaces with a 1-coin, 2-coin, 1-coin will finish the row and have all constraints satisfied. So the maximum number of coins, assigned the value of 3, that could be in the row is 501.
What is more interesting is finding the minimum.
If we were to shift the pattern then we get a situation with 500 3-coins. But I will investigate further. Lets assume there is some row of coins where there is some run of four (or more) coins which have no 3-coins.
For any given denomination of coins they cannot be adjacent to another of the same denomination. Then out of the four coins at most two of those coins can be 1-coins and at most two of those coins can be 2-coins.
This adds up to exactly four coins. So at this point we have if a run of four coins has no 3-coins then it must have exactly two 2-coins and two 1-coins. For two 2-coins to be present they must be the first and fourth coins but this forces the 1-coins to be adjacent, violating the rules. So we must conclude there is no way to have a run of four coins without a 3-coin.
Thus every possible valid row of coins has the 3-coins spaced every fourth coin, as that is the only arrangement of 3-coins that avoids runs of four non-3-coins and has the 3-coins satisfy the rules. So then the minimum number of coins, assigned the value of 3, that could be in the row is 500, from shifting our maximum solution so that a 3-coin does not appear at the ends.