鸡兔同笼和丢番图

Review:

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

丢番图方程的用处是可以解 "鸡兔同笼".

假设一些小兔子和小鸡在一个笼里一共有100只腿，那可以有多少兔子，和多少小鸡呢？

image

$2*c + 4*r =100$
c: # of chickens
r: # of rabbits</pre>

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 只给我们提供一个初始解，和公式，我们要自己带数字.

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.
我小时候最喜欢的物理老师胡宁说他最讨嫌"鸡兔同笼" 的题目, 因为哪里会有人蠢到真的把它们放到一个笼子里? 十多年过去了, Renee 告诉我 Highland Park, NJ 的动物园里面真的把兔子和小鸡放在一个笼子里，我想我应该去照个照片，希望有机会再见到胡老师！：）

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