Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Thanks,

MG

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.