The tale of four wives

Question

This problem is a harder variation of A tale of The Rich Arab Man, which - though phrased very similarly - needs a different method to solve.

A very rich pearl harvester had four wives. His first wife had four kids, the second wife had three kids, third wife had two kids and the last young wife had a single kid.

One day he decided to give away all his pearls to his wives.

He carried all those pearls in a huge bag and entered the house of his first wife. Upon arrival, the four kids quickly picked one pearl for each of them from the bag and ran away. Then he told his intention to his wife. She counted and took for herself a quarter of the pearls in the bag and returned the remainders to him to be shared with the other ladies.

He carried the bag and entered the house of his second wife. Quickly three kids jumped in and get away with a pearl for each of them. After that, knowing the man's intention, his second wife took a quarter of the pearls and returned the balance to be shared with the other ladies.

He then went to the third wife. Two kids grabbed a pearl for each of them and went missing. After that, the lady of the house took a quarter of the pearls and gave the balance to him.

When he walked into the last wife, he gave a pearl to the single kid in that house. The lady took the quarter of what left in that bag.

When he walk out from that house, the pearl harvester found the remaining quantity of the pearls was exactly divisible by four. Then he divided the pearls into four equal numbers and gave away to each wife separately.

What was the initial number of pearls in the bag carried by him.?

Answer 1

I think he had

1000 pearls.

The children of the first wife take 4, leaving him with

996.

The first wife gets one quarter of the rest, so there are

747 left.

Then the children of the second wife take 3, so

744 remain.

The second wife gets the quarter of them, but there are still

558.

The third wife's children take away 2, he still has

556.

After the third wife gets her quarter,

417 pearls stay in the bag.

The last child gets 1,

416 pearls remain.

The last wife gets the quarter of that, leaving him with

312.

Which can be divided into 4 equal parts of

78.

I found this by

solving the following congruence:
$\big(\frac34\big)^4x-\Big(4\big(\frac34\big)^4+3\big(\frac34\big)^3+2\big(\frac34\big)^2+1\big(\frac34\big)\Big)=\frac{81}{256}x-\frac{141}{32}\equiv0\mod4$,
which I got by assuming he has $x$ pearls in the beginning, keeping track how many he has left in each step, and note which amounts have to be divisible by 4. All the equations that came up in the middle were:
$x-4\equiv0\mod4$,
$\frac34x-6\equiv0\mod4$,
$\frac9{16}x-\frac{13}2\equiv0\mod4$,
$\frac{27}{64}x-\frac{47}8\equiv0\mod4$,
but these are automatically satisfied by the solution of the former one.
The congruence can be solved the following way:
First by multiplying both sides (and also the modulus) by 256 and adding 1128 to both sides, we get
$81x\equiv1128\mod1024$.
Then with the extended Euclidean algorithm, we only need to find the multiplicative inverse of 81 mod 1024. Or we have to find an online tool to realize it's 177.

Because of the modular arithmetic, every other number of the form $1000+1024k$ (where $k\in\mathbb{N}$) is a possible other solution, although obviously not minimal.

Answer 2

The man must have had

$1024 q + 1000$ pearls for any postive integer $q$, and so the smallest number he could have had at the start was 1000.

Proof:

At the end, he was able to divide the remaining pearls among the wives. So he must have had $4n$ pearls for some $n$.

Before he visited his fourth wife, he therefore had $\frac{4}{3} (4n) + 1$ pearls; when the child took one of these and the fourth wife took 1/4 of the remainder, he would have had $4n$ left over.

Similarly, before he visited his third wife, he would have had $\frac{4}{3} \left( \frac{4}{3} (4n) + 1 \right) + 2$ pearls.

Similarly, before he visited his second wife, he would have had $\frac{4}{3} \left( \frac{4}{3} \left( \frac{4}{3} (4n) + 1 \right) + 2 \right) + 3$ pearls.

Finally, when he started, he would have had $\frac{4}{3} \left( \frac{4}{3} \left( \frac{4}{3} \left( \frac{4}{3} (4n) + 1 \right) + 2 \right) + 3 \right) + 4$ pearls.

Multiplying this all out, we find that the man must have had $m = (1024 n + 1128)/81$ pearls to begin with. Thus, we must have $1024 n + 1128 = 81 m$ for some other integer $m$, or $1024 n - 81 m = -1128.$ You can use the Extended Euclidean Algorithm to solve this equation; what you find is that $1024 \times (78 + 81 q) - 81 \times (1000 + 1024 q) = -1128$. Thus, the original number of pearls must have been $m = 1024 q + 1000$ for some integer $q$.

Answer 3

The answer is

$1000$

Demonstration:

\begin{align}1000&-4&=~~996\\[1.2ex]~~996&\times\frac34&=~~747\\[1.2ex]~~747&-3&=~~744\\[1.2ex]744&\times\frac34&=~~558\\[1.2ex]~~558&-2&=~~556\\[1.2ex]~~556&\times\frac34&=~~417\\[1.2ex]~~417&-1&=~~416\\[1.2ex]~~416&\times\frac34&=~~312\end{align}
$312\div 4=78$, so, on his second round, the man gives $78$ pearls to each wife.

Unfortunately, I solved this by computer-assisted brute force, so I don't have any proof that this is the minimum.