On a table, there are 1001 pennies lined up in a row

On a table, there are 1001 pennies lined up in a row. I then come along and replace every second penny with a nickel (starting with the second). After this I replace every third coin with a dime (starting with the third). Finally I replace every fourth coin with a quarter (starting with the fourth). How much money is on the table? Explain how you know using your knowledge of number theory and divisibility.

The Correct Answer and Explanation is:

We are given 1001 coins initially, all pennies, and then we make the following replacements:

Every 2nd coin is replaced by a nickel (5¢)
Every 3rd coin is replaced by a dime (10¢)
Every 4th coin is replaced by a quarter (25¢)

A coin can be replaced more than once, depending on its position. For example, position 12 is divisible by 2, 3, and 4 — so it is replaced three times.

Step-by-Step Plan:

Let’s denote:

P = Penny = 1¢
N = Nickel = 5¢
D = Dime = 10¢
Q = Quarter = 25¢

Each position from 1 to 1001 starts with a penny. We go through and replace coins as described.

We’ll define a coin’s final value based on the last replacement applied to it:

First pass (every 2nd): replaces P → N
Second pass (every 3rd): replaces current coin → D
Third pass (every 4th): replaces current coin → Q

So the last operation determines the final coin type.

Total Coins:

We need to count how many coins ended as:

Pennies: not replaced at all
Nickels: replaced only on the 2nd pass
Dimes: replaced on the 3rd pass but not the 4th
Quarters: replaced on the 4th pass (regardless of previous changes)

Set Definitions:

Let:

A = multiples of 2 (nickels): ⌊1001/2⌋ = 500
B = multiples of 3 (dimes): ⌊1001/3⌋ = 333
C = multiples of 4 (quarters): ⌊1001/4⌋ = 250

Let’s count how many coins are finally quarters:

Any coin divisible by 4 → replaced last by a quarter
→ So: 250 coins are quarters

Now, remove these from the previous groups:

Dimes:

Dime positions = multiples of 3 but not 4
→ Find numbers divisible by 3 and not 4
→ Multiples of both 3 and 4 = LCM(3,4) = 12
→ ⌊1001/12⌋ = 83
→ Dimes only = 333 – 83 = 250 coins

Nickels:

Nickel positions = multiples of 2 not divisible by 3 or 4
→ Multiples of 6 = LCM(2,3) = ⌊1001/6⌋ = 166
→ Multiples of 4 and 2 = still 250 (already counted in quarters)
→ Multiples of 12 = 83
→ Nickels only = 500 – 166 (shared with 3) – 250 (shared with 4) + 83 (to avoid double subtracting those counted in both 3 and 4)
→ Total = 500 – 166 – 250 + 83 = 167 coins

Pennies:

Never touched → Not divisible by 2, 3, or 4
→ Use inclusion-exclusion:

Count of numbers from 1 to 1001 not divisible by 2, 3, or 4:

Multiples	Count
2	500
3	333
4	250
2 & 3 (6)	166
2 & 4 (4)	250
3 & 4 (12)	83
2,3,4 (LCM=12)	83

Using inclusion-exclusion:

Count = 1001 
        - (Div by 2 + 3 + 4) 
        + (Div by 6 + 8 + 12)
        - (Div by 12 again since LCM of all three is 12)

= 1001 - (500 + 333 + 250) + (166 + 83 + 83) - 83  
= 1001 - 1083 + 332 - 83  
= 1001 - 1083 + 249  
= 167 pennies

Final Tally:

Pennies: 167 coins → 167 × \$0.01 = \$1.67
Nickels: 167 coins → 167 × \$0.05 = \$8.35
Dimes: 250 coins → 250 × \$0.10 = \$25.00
Quarters: 250 coins → 250 × \$0.25 = \$62.50

Total Money:

\$1.67 + \$8.35 + \$25.00 + \$62.50 = \$97.52

✅ Final Answer: \$97.52

Explanation Summary (300+ Words):

This problem involves divisibility and number theory, specifically using inclusion-exclusion principles. Initially, we have 1001 pennies. Replacing every 2nd coin with a nickel means all positions divisible by 2 change to nickels — that’s 500 coins. But the next step replaces every 3rd coin with a dime, meaning positions divisible by 3 (333 total) are changed again, possibly overwriting nickels. Finally, coins in positions divisible by 4 (250 total) are changed again to quarters, which take final priority.

Because a coin can be replaced multiple times, we need to determine which coins are ultimately left as each type. Any coin that’s divisible by 4 ends as a quarter, regardless of earlier replacements. That’s 250 coins. From the dimes (positions divisible by 3), we subtract those also divisible by 4 (83), leaving 250 coins as final dimes. Nickels are positions divisible by 2 but not by 3 or 4 — accounting for overlaps using inclusion-exclusion, we get 167 such positions. Finally, the coins never touched are those not divisible by 2, 3, or 4, which again total 167.

Multiplying the count of each type by its value and summing gives the total money:

167 pennies = \$1.67
167 nickels = \$8.35
250 dimes = \$25.00
250 quarters = \$62.50
Total = \$97.52

This problem highlights how overlapping sets require careful accounting using number theory tools, especially when replacements overwrite earlier changes.