Linear Diophantine Equation 2

 

Review:

Last time, we went over the basic theorems of Linear Diophantine Equation. This time, we will focus on how to solve the problem.

One of the most famous examples is  “Chicken Bunny in the Same Cage“.

Suppose we put some bunnies and chickens in the same cage and there are 100 legs in total, how many bunnies and how many chickens can we have?

2*c + 4*r =100

c: # of chickens
r: # of rabbits

Solution:

# Steps for Slove Linear Diophantine Equation: mx+ ny= w

1. Check the existence of Solution:
gcd (2,4) =2 (2x+4y=100)
2| 100 => the equation has at least one solution.

2. Find the solution of x, y such that 2*x+ 4*y= gcd(m,n)=2
x=-1 , y=1
2*(-1) + 4*1=2 

3. Multiply w/gcd(m,n) to the equation
   100/2=50 
50*2*(-1)+ 50*4*1 = -100 +200= 100

4. Select solutions within the constraints
c=-50, r=200 would be a theoretical solution.
but we are talking about rabbits and chicken, so we need positive numbers.
We can do it by trial or follow the formula, we have a set of solution:
Paired Solution: ( x_initial+ (m/gcd(n,m))*z , y_initial - (n/gcd(n,m)*z)) 

Answer:
(2 chicken, 24 rabbits), (4 chicken,23 rabbits), (6 chicken , 22 rabbits )....

Now we have figured out the set of chicken and rabbits will make 100 legs in total:
(2 🐥, 24 🐰), (4 🐥, 23 🐰) , (6 🐥, 22 🐰) ….

Python Solution:

Now we can try a more technical solution:

#linear diophantine
def isolve(a,b,c):
    q,r=divmod(a,b)
    if r==0:
        return([0,c/b])
    else:
        sol=isolve(b,r,c)
        u=sol[0]
        v=sol[1]
        return([v,u-q*v])

Out[14]: [50.0, 0.0]
#Note: this is one solution, we need to find the rest.

# Alternative Solution
from sympy.solvers.diophantine import diop_linear
diop_linear(2*a + 4*b-100)

Out[13]: {(2*t_0 + 50, -t_0)}

Let t_0= -24, then we have
(2, 24) ....

As we can see, python only generates one particular solution, or the initial solution. If we need to see the set of solutions. we need to do some calculation by ourselves.

 

Summary + Story:

Although Python is very fast with the initial solutions of Linear Diophantine equation, it is always a good idea we understand the Key Concept: GCD behind the solutions.

I still remember how much fun just to play around the numbers.
My favorite Physics teacher Hu Ning said he hated “Bunny and Chicken in a Cage” problem, because who would be so dumb to put the chicken and bunny in the same Cage? More a decade later, Renee told me The Zoo in Highland Park, NJ really put Bunny and chickens in the same Cage. I should take a picture in case i see him again 🙂

 

Puzzle :

Diophantine Equation came from Diophantus, a Hellenistic mathematician from Egypt, He had a lot of great work done in arithmetics. It was said his age was engraved as a puzzle, could you figure out his age?  

‘Here lies Diophantus,’ the wonder behold.
Through art algebraic, the stone tells how old:
‘God gave him his boyhood one-sixth of his life,
One twelfth more as a youth while whiskers grew rife;
And then yet one-seventh ere marriage began;
In five years there came a bouncing new son.
Alas, the dear child of master and sage
After attaining half the measure of his father’s life chill fate took him.
After consoling his fate by the science of numbers for four years,
he ended his life.’

Happy Studying! 🐻

 

Reference:

https://brilliant.org/wiki/linear-diophantine-equations-one-equation/

https://www.math.utah.edu/~carlson/hsp2004/PythonShortCourse.pdf

https://docs.sympy.org/latest/modules/solvers/diophantine.html

https://en.wikipedia.org/wiki/Diophantus

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Social media & sharing icons powered by UltimatelySocial
%d bloggers like this: