Hi,
Well, I was referred to a very nice article by ali today. It describes human's quest to find the biggest number, in a very interesting way. I actually wished to copy it over here to make sure I do not loose it, in case the original post is removed. But then the it contained some images too. So here is the place where original article can be found :
http://www.scottaaronson.com/writings/bignumbers.html
Thursday, August 30, 2007
Sunday, August 26, 2007
Game of Coins
So, I am back again with an interesting puzzle. Credit goes to my dear friend Sambuddha Roy to introduce me to this puzzle as well as its very simple solution.
Here goes the puzzle :
Even number of coins are laid out in a straight line. Coins may have different denominations. Two players p1 and p2 are playing a game. When a player's turn comes he/she has to pick a coin from either end of the line. When all the coins are exhausted, player with the highest amount wins. A tie occurs whent both the player possess the equal amount.
Prove that if p1 goes first, he/she always have the stretagy such that he/she does not loose the game.
Solution :
Solution to this puzzle is very simple and I really felt really stupid when I came to know about the solution and its simplicity. As always, I tried to use induction to prove that p1 always have a winning stretagy ( or non-loosing stretagy). For the case when number of coins is 2, p1 can pick the larger of the two. But then things get complicated when we need to prove the induction step. In fact, I did not spend enough time to prove that using induction.
A very simple solution is that p1 can index the coins from 1 to n. Then, he can calculate sum total of odd-numbered coins as well as even-numbered coins. p1 can always pick coins in a way such that he/she always gets even-numbered or odd-numbered coins depending on which of those will make up a larger amount.
Here goes the puzzle :
Even number of coins are laid out in a straight line. Coins may have different denominations. Two players p1 and p2 are playing a game. When a player's turn comes he/she has to pick a coin from either end of the line. When all the coins are exhausted, player with the highest amount wins. A tie occurs whent both the player possess the equal amount.
Prove that if p1 goes first, he/she always have the stretagy such that he/she does not loose the game.
Solution :
Solution to this puzzle is very simple and I really felt really stupid when I came to know about the solution and its simplicity. As always, I tried to use induction to prove that p1 always have a winning stretagy ( or non-loosing stretagy). For the case when number of coins is 2, p1 can pick the larger of the two. But then things get complicated when we need to prove the induction step. In fact, I did not spend enough time to prove that using induction.
A very simple solution is that p1 can index the coins from 1 to n. Then, he can calculate sum total of odd-numbered coins as well as even-numbered coins. p1 can always pick coins in a way such that he/she always gets even-numbered or odd-numbered coins depending on which of those will make up a larger amount.
Sunday, August 19, 2007
Space v/s Time
Hi all,
I know there has been a long pause on my blog. Well, it was a transition period for me from IRL to IITK. Yes, I have joined its CSE department as a PhD student. Anyways, I know the title is somewhat misleading as many would think this post has something to do with einstein's theory of relativity and the four dimensional world. You are grossly mistaken if you think so.
Actually, as part of my coursework here I am attending a course by Prof Manindra Aggarwal. Well, it is a big mistake on my side that I have not registered for this course. Even the bigger mistake is that I have registered for a course named "Computational Number Theory and Algebra" by Prof Piyush Kurur. The content itself may be interesting but the way that guy teaches the course, makes it difficult. The worst part is that all the exams of this course are "take home" exams.
Anyways, let's get back to the point. It is indeed an honour to sit in Prof Manindra's class and see him deliver some of the toughest content of the course with a flair. All the people with computer science background are aware of the P not equals NP conjecture. This decade old conjecture has still remain unbeaten. In other words, this conjecture states that the set of problems that can be solved by a deterministic turing machine in polynomial time and the set of problems that can be solved by a non-deterministic turing machine in polynomial time are equal.
There is another notion called Space Complexity in computer science. Space complexity is a measure of the space required to solve any problem by an algorithm. One wonders, whether there is any difference between the set of problems which can be solved by a deterministic turing machine in polynomial space , and the set of problems which can be solved by a non-deterministic turing machine in polynomial space. It actually turns out that non-determinism does not give any more power over deterministic mechanism when space is the criterion. Due to Savitch's theorem it is proven that PSPACE equals NPSPACE.
One may wonder why the similar version in time complexity is yet unbeaten? Non-determinism gives the power to explore exponentially many threads of computation simultaneously. If a deterministic turing machine tries to mimic the behaviour of a non-deterministic one, it has to explore all the paths one by one. It costs time to go through all the paths one by one. One has to add up all the time that has been spend. But does one really have to add up the space as well??? I felt really stupid when I come to know that the reason why power of deterministic and non-deterministic turing machine comes out to be same, is that space can be reused!!!!
As a wild thought, may be if a deterministic turing machine can go back in time to explore the alternate future, thus, reusing the time we may as well have P = NP :D.
I know there has been a long pause on my blog. Well, it was a transition period for me from IRL to IITK. Yes, I have joined its CSE department as a PhD student. Anyways, I know the title is somewhat misleading as many would think this post has something to do with einstein's theory of relativity and the four dimensional world. You are grossly mistaken if you think so.
Actually, as part of my coursework here I am attending a course by Prof Manindra Aggarwal. Well, it is a big mistake on my side that I have not registered for this course. Even the bigger mistake is that I have registered for a course named "Computational Number Theory and Algebra" by Prof Piyush Kurur. The content itself may be interesting but the way that guy teaches the course, makes it difficult. The worst part is that all the exams of this course are "take home" exams.
Anyways, let's get back to the point. It is indeed an honour to sit in Prof Manindra's class and see him deliver some of the toughest content of the course with a flair. All the people with computer science background are aware of the P not equals NP conjecture. This decade old conjecture has still remain unbeaten. In other words, this conjecture states that the set of problems that can be solved by a deterministic turing machine in polynomial time and the set of problems that can be solved by a non-deterministic turing machine in polynomial time are equal.
There is another notion called Space Complexity in computer science. Space complexity is a measure of the space required to solve any problem by an algorithm. One wonders, whether there is any difference between the set of problems which can be solved by a deterministic turing machine in polynomial space , and the set of problems which can be solved by a non-deterministic turing machine in polynomial space. It actually turns out that non-determinism does not give any more power over deterministic mechanism when space is the criterion. Due to Savitch's theorem it is proven that PSPACE equals NPSPACE.
One may wonder why the similar version in time complexity is yet unbeaten? Non-determinism gives the power to explore exponentially many threads of computation simultaneously. If a deterministic turing machine tries to mimic the behaviour of a non-deterministic one, it has to explore all the paths one by one. It costs time to go through all the paths one by one. One has to add up all the time that has been spend. But does one really have to add up the space as well??? I felt really stupid when I come to know that the reason why power of deterministic and non-deterministic turing machine comes out to be same, is that space can be reused!!!!
As a wild thought, may be if a deterministic turing machine can go back in time to explore the alternate future, thus, reusing the time we may as well have P = NP :D.
Subscribe to:
Posts (Atom)