Review:
Last time, we went over the basic theorems of Linear Diophantine Equation. This time, we will focus on how to solve the problem.
丟番圖方程的用處是可以解 "雞兔同籠".
假設(shè)一些小兔子和小雞 在一個(gè)籠里一共有100只腿，那可以有多少兔子，和多少小雞呢？
c: # of chickens
r: # of rabbits</pre>
Solution:
Steps for Slove Linear Diophantine Equation: mx+ ny= w
1. Check the existence of Solution:
2| 100 => the equation has at least one solution.
2. Find the solution of x, y such that
3. Multiply to the equation
4. Select solutions within the constraints
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:
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 只給我們提供一個(gè)初始解，和公式，我們要自己帶數(shù)字.
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.
我小時(shí)候最喜歡的物理老師胡寧說(shuō)他最討嫌"雞兔同籠" 的題目, 因?yàn)槟睦飼?huì)有人蠢到真的把它們放到一個(gè)籠子里? 十多年過(guò)去了, Renee 告訴我 Highland Park, NJ 的動(dòng)物園里面真的把兔子和小雞放在一個(gè)籠子里，我想我應(yīng)該去照個(gè)照片，希望有機(jī)會(huì)再見(jiàn)到胡老師 ！ ：）
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
