Disclaimer: This has absolutely nothing to do with the television game show of the same name.
"You don't need more than standard 5 maths to solve this puzzle."This Friday, me and Vijay were chatting for a very long time with Mandar. Anyways, so Mandar recently put up a really cool puzzle on his blog, which, during our long conversation he posed to us. Check out the puzzle first.
Ok, so me and Vijay were Harry and Draco and Mandar naturally became the great wizard (don't say anything). So we started. Below are the excerpts of what Harry and Draco said, while the Great Wizard left speechless owing to our abilities ...
"Mandar, I think this is an infinite series"No it isn't ...
"See, the same term can't appear on the board twice, so at some point of time you'll exhaust all possible numbers"Some semblance of hope for Mandar, or was it?
"I got it! I got it! The larger number should progress to the smaller number in steps of the size of the smaller number ... no wait ... but there is a number on the board smaller than the smaller number ... so is that ... smaller?"Yes. How good are we! 5th standard maths is such a piece of cake!
"I am confused"Ya.
So Mandar finally had to step in. Patiently, he took a few examples and solved it out for us. It worked out that you need to find the smallest number that is 'somehow' yes somehow related to both of the original numbers and then divide the larger number by that somehow-number to figure out how many turns can be played in total. Accordingly you can decide whether you should play first or your opponent should be made to. So what is this somehow-number?
"Hey it's called a co-prime! Yes, co-prime ... right?"Wrong.
"Arre moron! Smallest possible number related to both ... its common sense ... it is their LCM"Wrong again, especially since LCM or Least Common Multiple is larger than or equal to the larger of the two numbers.
"If it is not LCM then it has to be that other common thing yaar. Ummm ... ya! GCD!"Yes, the somehow-number is the GCD of the two. The whole process of computing the GCD and then dividing the largest number etc etc is called Euclid's Algorithm, which according to Mandar we have studied in Standard 5.
So, kya ham panchvi paas hain?