8

Father has left to his children several identical gold coins. According to his will, the oldest child receives one coin and one-seventh of the remaining coins, the next child receives two coins and one-seventh of remaining coins, the third child receives three coins and one-seventh of the remaining coins, and so on through the youngest child. If every child inherits an integer number of coins then find the number of children and gold coins.

I tried to write $x_k$ as some function of $k$ (where $x_k$ is the number of coins taken by the $k_{th}$ child) but failed. All I could write is $x_k= k + \frac{1}{7}(n-k- S_{k-1})$ where $S_k$ denotes the sum of first $k$ terms then $S_k=\frac{n}{7} + \frac{6}{7}(S_{k-1} +k)$ but I cannot proceed further, please help.

Random
  • 83
  • 4
  • 1
    I have a sneaking suspicion that the Chinese Remainder Theorem may play a part, here, but it isn't obvious to me how it might be applied. – Cameron Buie May 19 '19 at 19:07
  • 1
    I have an answer, but I haven't shown it is unique. I started by observing that the last child takes an integer number of coins and assumed that none were left over. If there are $n$ children, this means that the last child takes $n$ coins. I got some control over $n$ and then guessed. – Mark Bennet May 19 '19 at 19:15
  • I don't know if it will help, but you can find a closed form for the sums $S_k$ here. – Cameron Buie May 19 '19 at 19:17

2 Answers2

2

If $n>0$ is the number of children and we denote by $c_k$ the number of coins left after the first $k$ children have taken their share, we have

$$ c_{k+1} = \frac{6}{7} \bigl(c_k - (k+1)\bigr) ~~~\text{ for } k=0,\ldots,n-1 \enspace, $$

with $c_n = 0$. Applying generating functions,

$$ C(x) \biggl(\frac{1}{x} - \frac{6}{7} \biggr) = \frac{c_0}{x} - \frac{6}{7}\biggl(\frac{nx^n}{x-1} - \frac{x^n-1}{(x-1)^2}\biggr) \enspace. $$

Taking $x=\frac{7}{6}$, the left-hand side vanishes and we can solve for $c_0$:

$$ c_0 = 36 + 6 (n-6)\biggl(\frac{7}{6}\biggr)^{\!n} \enspace. $$

The only positive value of $n$ for which $c_0$ is an integer is $6$. Hence $c_0=36$.

Fabio Somenzi
  • 7,676
1

Suppose $D_r$ is the number coins left before distributing to the $r^{th}$ child and that $C_r$ is he number of coins received by the $r^{th}$ child.

Then $$C_r=r+\frac {D_r-r}7$$ and $$D_{r+1}=D_r-C_r=\frac {6(D_r-r)}7$$

In particular, for these numbers to be integers we must have $D_r-r$ divisible by $7$ and $D_{r+1}$ divisible by $6$ - which means $D_r$ is divisible by $6$.

So let $D_r-r=7a$, then $D_{r+1}=6a$, with $D_r=7a+r$.

And working backwards if $D_{r+1}=6a$ then $D_r=7a+r$ with $C_r=a+r$

Now look at the last child, who must receive an integer number of coins, and if there are $n$ children, this must be $D_n=n=6b$.

Then $D_{n-1}=7b+n-1=13b-1=12b+(b-1)$

Now $b-1$ must be a multiple of $6$ - say $6c$, so that $b=6c+1$ and $D_{n-1}=78c+12=6(13c+2)$

Whence $D_{n-2}=7(13c+2)+(n-2)=91c+12+n=91c+12+36c+6=126c+18+c$

And now $c$ must be divisible by $6$, say $c=6d$. Scouting back we have $n=36c+6=216d+6$ and realistically we must have $d=0$ and $n=6$.

You will find that $n=6$ works nicely.

More rigorously, once we are up to the possibility $c\gt 0$ it looks possible to show that every step brings in another multiple of $6$, and this means that the number of children grows without limit - every time we add one step, the number of children multiplies by about $6$.

Mark Bennet
  • 100,194