## Solution to Puzzle #154: Can You Divvy Up the Gold?

Apologies for not posting last week, I was traveling on a short break with family.

This was a relatively simple problem for most people, and I received lots of correct answers. Correct answers came from Amit Mittal, Suman Saraf, Abhinav Jain, Pratik Poddar, Praneeth, Sid Mulherkar and Abhishek Masand.

The site from where I borrowed the puzzle, gave the following method:

There are actually infinite answers to the problem, but only one number if the answer is under 1,000. This puzzle is an example of modular arithmetic and the Chinese Remainder Theorem.

The smallest solution under 1,000 for this problem is 341 coins, and the answer is found by working backwards. To find it, we first note that with 11 pirates the coins divided evenly; hence, the number of coins is in the list:

11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132, 143…

What happens if we take these numbers and divide them among 12 pirates? How many coins would be left over? Well, we want 5 coins to be left over after dividing by 12. Hence, we reduce the list above to:

77, 209, 341, 473…

These numbers divide by 11 evenly and have 5 left over when divided by 12. Now we take these remaining numbers and divide them by 13 until we find the number that gives 3 extra coins left over. Hence, 341 coins.

Most of the people who responded to the puzzle gave more elegant answers. I am reproducing the one from Praneeth:

11z = 12y+5 = 13x+3 , so y+5 and 2x+3 should be divisible by 11 but we knew that the max value of y is 72 because 12y+5 < 1000 and also y can take values 6, 17, 28, 39, 50, 61 and 72. Finally checking these numbers gives y = 28 that satisfies all the conditions and the number of coins are 341 = 12*28 + 5.

Hope you all enjoyed the puzzle!

This entry was posted in Solution and tagged , . Bookmark the permalink.