# Homework Help: Diophantine equations puzzle problem

1. Feb 15, 2015

### PsychonautQQ

1. The problem statement, all variables and given/known data
One hundred bushels of grain are to be distrubuted amongst 100 people. Each man gets 3 bushels, each woman gets 2 bushels, and each child gets 1/2 bushels. How many men, women and children are there?

2. Relevant equations
GCD, euclidean algorithm, Diophantine equation

3. The attempt at a solution
I'm a bit thrown off, is their an algorithm way to find the answer here? I'm assuming i'm supposed to use the diophantine equation at some point since it's a question from that chapter, but I'm having difficulty finding out how to do it with 3 variables.

I tried solving for men in the persons equation and then substituting that value in to the bushel equation, therefore having only 2 variables so I could use the diophanine equation, but i'm starting to think I'm going to need to do this in a guess and check sort of way? I don't mind doing this, it just seems inefficient. If there is an algorithmic way to find the answer I'd like to know it. Anyone care to shed some light?

2. Feb 15, 2015

### Staff: Mentor

Can't you do it by converting the man and woman into children and solving for children units based on the bushels they receive?

3. Feb 15, 2015

### PsychonautQQ

Since I have more variables than equations, I don't think that would work. Am I missing something obvious here?

4. Feb 15, 2015

### Staff: Mentor

Yes the relationship between men women and children gives you two more equations right?

5. Feb 15, 2015

### PsychonautQQ

Technically yes, but I don't believe the new equations would provide any new information, since they would be linearly dependent on the original's. Right?

6. Feb 15, 2015

### lurflurf

There are multiple solutions
denote a solution as
(men,women,children)
(20,0,80)
trade bunches of men for women and children (while satisfying both conditions) until you run out of men
that is
(20,0,80)|->(20-a,0+b,80-c)
with
a=b-c
3a=2b-c/2
with a,b,c positive integers and a as small as possible

7. Feb 15, 2015

### Ray Vickson

There might not be any relationship between the numbers of men, women and children. Some men/women may be unmarried; some may be single parents; different families may have different numbers of children, etc.

Basically, if the variables are M, W and C (= numbers of men, women and children) the two equations allow one to solve for M and W as functions of C (for example). One can easily get an upper bound on C from the requirements M,W ≥ 0, and the requirements that all variables be integer-valued further reduces the possibilities. A search over the possible values of C is not too hard, although would be tedious if done by hand.

8. Feb 15, 2015

### PsychonautQQ

Okay, that's what I was planning on doing. I just wanted to make sure I wasn't seeing some bigger picture that would allow me to compute it more systematically.

9. Feb 15, 2015

### lurflurf

The system is we easily see that the possible number of women is 0,5,10,15,20,25,30
and if we know the women we know the men and children as well.

10. Feb 15, 2015

### Ray Vickson

Alternatively, we can solve for the numbers of men and women as functions of the number of children, and from the solution formulas can see that the number of children must be an even number between 68 and 80, inclusive.

11. Feb 15, 2015

### lurflurf

three equivalent forms
men between 2 and 20,inclusive by 3's
women between 0 and 30,inclusive by 5's
children between 68 and 80,inclusive by 2's

12. Feb 15, 2015

### Staff: Mentor

I think you misunderstood my post. In post #2, I told the OP basically what you just said above without giving away too much of the answer.