Gold Coins, Bags, & Thieves

Let $a<b<c$ be some number of bags, gold coins, and thieves, whose orders are still unknown as in the question. We can be sure that there would be no cases of equal numbers because it will result in a remainder of $0$ for some cases, which is not under such constraint. Also, given the remainders of $6$ for all modulos $a,b,c$ , we can conclude that $6<a<b<c$ as well.

It is clear then that the total amount of gold coins is the product of some two numbers, leaving the other as the divisor and $6$ as the remainder for all combinations. In other words, from Holmes' wording, since we can't rule out any combination by trials of divisions, we can deduce that all such divisions lead to the same remainder of 6. Thus, we can set up the modular equivalences, as followed:

$ab \equiv 6 \pmod{c}$ $bc \equiv 6 \pmod{a}$ $ca \equiv 6 \pmod{b}$

Then suppose that $b-a =x$ and $c-b = y$ for some positive integers $x,y$ . That will make $c-a = x+y$ . We can rewrite the above equivalences into these:

$-(x+y)(-y) \equiv y(x+y) \equiv 6 \pmod{c}$ $x(x+y) \equiv 6 \pmod{a}$ $y(-x) \equiv -xy \equiv 6 \pmod{b}$

Rearranging the terms so that there remainders are zeros:

$y(x+y)-6 \equiv 0 \pmod{c}$ $x(x+y)-6 \equiv 0 \pmod{a}$ $xy+6 \equiv 0 \pmod{b}$

Given $x,y$ be positive integers, for the upper equivalences, $y(x+y) - 6 \geq 0$ and $x(x+y) - 6 \geq 0$ because $x,y \geq 1$ , making $y(x+y), x(x+y) \geq 2$ . Then $y(x+y)-6, x(x+y)-6 \geq -4$ . If such product is less than 6, it will leave only remainders of $-1, -2, -3, -4$ , none of which can be divisible by modulo $a,b,c > 6$ .

Now let us transform those equivalences into ordinary Diophantine equations, for some non-negative quotients $q$ :

$y(x+y)-6 = cq_1$ $x(x+y)-6 = aq_2$ $xy+6 = bq_3$

We are then attempting to find the lowest possible quotients, yet, one issue remains: whether $q$ is allowed to be zero for the upper two equations.

Suppose $x(x+y) - 6 = 0$ ; $x(x+y) = 6 = 2\times 3 = 1\times 6$ . Given $x+y > x$ , there are two possible scenarios: $x=2; y=1$ or $x=1; y=5$ . For the former one, it will result in $y(x+y) -6 = -3 <cq_1$ , which is contradicted. For the latter scenario, it will result in $y(x+y)-6 = 24 = cq_1$ , but $xy+6 = 11= bq_3$ . Thus, $b$ must be $11$ , leading to $c = 11+5 =16$ , but $24$ is not a multiple of $16$ , thus contradicted as well.

Similarly, if $y(x+y) = 6 = 2\times 3 = 1\times 6$ , for $y=2; x=1$ , $x(x+y) -6 = -3 <cq_1$ and for $y=1; x=5$ , it will result in $b=11$ and $a=11-5 = 6$ . However, $a>6$ , so it is contradicted as well.

Hence, all quotients must be positive, and the lowest possible values occur when all quotients equal $1$ .

Let us explore whether these Diophantine equations will hold true:

$y(x+y)-6 = c = a+x+y$ _1 $x(x+y)-6 = a$ _2 $xy+6 = b = a+x$ _3

By subtracting equations (1)-(2) and (1)-(3), we will obtain:

$(x+y)(y-x) = x+y$ $y^2 -12 = y$

Hence, it would be obvious that:

$y-x =1$ $y^2 -y -12 = (y-4)(y+3) = 0$

Given $x,y$ as positive integers, we can conclude that $y=4$ and $x=3$ . Therefore, $a = 3(3+4) -6 =15$ . Then $b=15+3 = 18$ , and $c=18+4=22$ . Since all work with this set-up, there is no need to investigate other higher quotients.

Checking the answers, we can see that:

$15\times 18 = 22\times 12 + 6$ $18\times 22 = 15\times 26 + 6$ $22\times 15 = 18\times 18 + 6$

Finally, even though we still don't know which number is for which, we can be certain that there are at least $15$ thieves in this story.

Another possible route (without using number theory) is to write a Prolog program. Of course, you can write it also in some other language, but this puzzle is about logic. Below is a simple SWI-Prolog program for solving this puzzle as well as the output from the console.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

solve(Thieves) :-
    between(7, 100, Thieves),
    between(7, 100, Bags),
    between(7, 100, Coins),

    max_member(Biggest, [Thieves, Bags, Coins]),
    min_member(Lowest, [Thieves, Bags, Coins]),
    Biggest - Lowest < Lowest,

    6 is (Bags * Coins) mod Thieves,
    6 is (Thieves * Coins) mod Bags,
    6 is (Thieves * Bags) mod Coins.

1
2

[7]  ?- solve(Thieves).
Thieves = 15 .