All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
2001 Coin Crossed 1-2-3 Value Conclusion (Posted on 2023-05-07) Difficulty: 3 of 5
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.

See The Solution Submitted by K Sengupta    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution and more Comment 3 of 3 |
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.

  Posted by Brian Smith on 2023-05-07 11:15:32
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (5)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information