Take the 2-minute tour ×

There is an ancient problem, I remember reading once in a book while I was a kid, that says: there was a father who had $N$ sons and $T$ cows. He divided the cows among the sons in the following order: for the first son, $1 + 1/7$ of the remaining; for the second son $2+ 1/7$ of the remaining; ..., for the $i$'th son $i+1/7$ of the remaining... the question asked for the numbers T and N. In fact $N=6$ and $T=36$ is a solution. I found that it can be generalized to any given ratio $1/M$ and $N=M-1$ and $T=N^2$ is a solution. I was wondering if there is any other solution to the general problem in $\mathbb{Z}$. I have formalized the problem as following:

We have a system of equations described by the following $N+1$ equations defined in $\mathbb{Z}$: \begin{align*} n_1 &= 1+ \frac{T-1}{M}\\ n_2 &= 2+ \frac{T-2-n_1}{M}\\ &\vdots\\ n_i &= i+ \frac{T-i-\sum\limits_{j=1}^{i-1} n_j}{M}\\ T&=\sum\limits_{i=1}^{N} n_i. \end{align*}

One set of solutions is given by: \begin{align*} T &= N^2\\ n_i&=N\\ M&=N+1 \end{align*}

For example, when $N=6$, $T=36$, $n_1 = n_2 = \cdots = n_6 = 6$ is a solution.

I'm wondering if there is any other non-trivial integer solutions to the above system of equations.



share|improve this question

1 Answer 1

up vote 7 down vote accepted

Are you interested in solutions in $\mathbb{Z}$ or solutions in $\mathbb{Z}^+$?

Another trivial solution in integers is $$M=1$$ $$n_1=T$$ $$n_i = 0, \forall i \neq 1$$

So setting $M=1$, you can choose $T$ to be any integer and you will get only integer solutions since the condition $T = \displaystyle \sum_{i=1}^N n_i$ is trivially satisfied and $n_i$ are defined recursively as integer combinations of previous $n_i$'s and $T$ with $n_1 = T$.

EDIT: Lets analyze further to see other possible integer solutions. (My analysis is incomplete will try to do this later tonight/tomorrow.)

$$n_N = N + \frac{T-N - \displaystyle \sum_{j=1}^{N-1} n_j}{M}$$

From the constraint, $T = \displaystyle \sum_{j=}^N n_j$, we get $n_N = T - \displaystyle \sum_{j=1}^{N-1} n_j$ and hence

$$n_N = N + \frac{n_N - N}{M}$$ $$\left( n_N-N \right) \left(1-\frac{1}{M} \right) = 0$$ which gives us that $$n_N = N \text{ or } M=1$$

If $M=1$, then we already have the solution $$n_1 = T \text{ and } n_i = 0 \text{ } \forall \text{ }i>1$$

If $M \neq 1$, then $n_N = N$, and we have $$n_{N-1} = N-1 + \frac{T-(N-1) - (n_1+n_2+ \cdots n_{N-2})}{M} = N - 1 + \frac{N + n_{N-1}-(N-1)}{M}$$

$$(n_{N-1} - N + 1)(M-1) = N$$

From which we get that $M \neq 1$ and since we are interested only in integer solutions we have $(M-1)|N$ i.e. $M = 1 + a$ where $a|N$. Then $n_{N-1} = N + \frac{N}{a} - 1$

$$n_{N-2} = N-2 + \frac{n_N + n_{N-1} + n_{N-2} - (N-2)}{1+a}$$

$$n_{N-2} - (N-2) - \frac{n_{N-2} - (N-2)}{1+a} = \frac{N + N + \frac{N}{a}-1}{1+a}$$

$$a(n_{N-2} - (N-2)) = 2N + \frac{N}{a} - 1$$

share|improve this answer

Your Answer


