Sunday, November 7, 2010
Linear Diophantine Equation and a puzzle
November 7, 2010
Linear Diophantine Equation, what is it? Meanwhile read the question posted here and try for solution.
During college days I read one regional language novel. The author created one nice question between two characters of novel, it left a good fragrance on my mathematical interest.
[ The annotation from the novel is something like this,
The male character is in need of money for his parent cremation. He hesitates to beg at female character. On the fly, he phrases one puzzle and poses the same at female character. (The question by male character was also based on single LDE equation of two variables). She immediately cracks it. She evaluates the value of puzzle as one rupee and donates 499 bucks for cremation. Unfortunately, that is the kind of value talent has.
I believe right talent should be at right place ]
Given an equation with two variables, how to solve it? Or what are the conditions to solve it? How many solutions does it have? LDE is the answer. LDE deals with equations having integer solutions. Let us solve the puzzle posted in the following link,
Given that male (M) paid 7/-, female (F) 5/- and children (C) 1/- each. Total number of workers should be limited to 100, considering the capital letters as number of each group, we have
M + F + C = 100 ……… (Equation A)
Total worth of work should be limited to 250/-, i.e.
7M + 5F + C = 250 ……… (Equation B)
We have two equations with 3 unknowns, can we consolidate them to an LDE? Yes, eliminate one variable, we will have
7M + 5F + (100 – M – F) = 250
6M + 4F = 150 ……… (Equation C)
From Equation C, we have common factor, don’t take it out. Now, it is in LDE from. An LDE will have solutions when the GCD of variable’s coefficients is factor of constant on right side.
GCD(4, 6) = 2 which is factor of 150, so we have solutions to Equation C. But, how many?
Rearranging Equation C, will yield the following form
M = (150 – 4F) / 6 = 25 – 4/6F
M = 25 – 4/6F
Replacing F = 6t where t is intermediate variable will yield M value to,
M = 25 – 4t
and C value as,
C = 100 – 25 + 4t – 6t = 75 – 2t,
M = 25 – 4t
F = 6t
C = 75 – 2t
We can have 13 different values of t, satisfying the Equations A and B.
We crack the puzzle.
Now crack it, “if two oranges and three apples cost six rupees, how many integral values can be the prices of orange and apple?”