Wednesday, January 16, 2008

Logic and Games

Hi All,
Well, it has been some time since I have posted anything technical on this blog. Lately I have been very lazy about writing down interesting things over here. The biggest pain that I face is that there is no support for latex in blogspot.

Anyways, coming down to the point. I am attending a few lectures by Rohit Parikh at Logic School. He is a very good orator, I must say. As a part of his talk on "Finite and Infinite Dialogues", he mentioned a very famous product-sum puzzle. I am writing it down here just for the sake of completeness.


Mr P and Mr S are told product and sum of two number a and b respectively, where 2<= a,b <= 99.
P : I don't know the numbers.
S : I knew you did not know them.
P : Now, I know the numbers
S : Now, I know them too.

the solution can be found from dijkstra's paper.

With this example, Prof. Rohit went on to describe interesting world of finite and infinite dialogs between two parties in order to determine certain information. Yet another interesting example that he gave was as follows :

A randomly chosen positive integer n is chosen. One of them is written on Ann's forehead and n+1 is written on Bob's forehead. Now, each of them are asked to determine the numbers written on their forehead.

If 1 is written on Ann ( called as A now on ) and 2 is written on Bob ( called as B from now on ). Bob can immediately deduce that his number is 2. If A has got 3 and Bob has got 2 then A have two possibilities 1 or 3. When Bob says I don't know, A can determine that number she has got is 3. It is easy to prove by induction how they can determine their numbers in linear time with respect to number n.

One can devise a game where it would take infinite amount of time to determine one's number. Here is the interesting lecture notes which covered these beautiful examples.

PS : Please note that lecture notes/papers may be copyrighted. Contact the authors in case one wish to use it for non-academic purpose.

Thursday, January 03, 2008

Funny greeting cards

Hi all,
I got this one from iitb.humour.

1. I always wanted to have someone to hold, someone to love. And now
that you've come into my life...
(Inside card) - I've changed my mind.

2. I must admit, you brought religion into my life...
(Inside card) - I never believed in Hell until I met you.

3. As the days go by, I think how lucky I am....
(Inside card) - That you're not here to ruin it for me ..

4. Congratulations on your promotion. Before you go....
(Inside card) - Will you take the knife from my back? You'll probably
need it again.

5. Happy Birthday! You look great for your age....
(Inside card) - Almost lifelike!

6. When we were together, you said you'd die for me...
(Inside card) - Now we've broken up, I think it's time to keep your

7. Congratulations on your new bundle of joy....
(Inside card) - Did you ever find out who the father was?

8. You are such a good friend. If we were on a sinking ship and there
was only one life jacket...
(Inside card) - I'd miss you terribly and think of you often .

9. Your friends and I wanted to do something special for your
(Inside card) - So we're having you put to sleep.

10. Looking back over the years that we have been together, I can't help
but wonder.....
(Inside card) - What the hell was I thinking

11. I'm so miserable without you...
(Inside card) - It's almost like you're still here.

12. Thank you for being part of my life.....
(Inside card) - I never knew what evil was until I met you!

13. Congratulations on your wedding day!
(Inside card) - Too bad no one likes your husband.

14. How can I say this....
(Inside card) - Your cooking kills me

15. Hooray.....
(Inside card) - You're divorced.

16. I just want you to know that I'm sorry for what happened...
(Inside card) - Especially since you survived.

17. Congrats on getting married...
(Inside card) - It's not everyday you decide to ruin your life.

18. Someday I hope to marry...
(inside card) - Someone other than you.

19. We have been friends for a very long time...
(Inside card) - What do you say we stop?

Wednesday, January 02, 2008

Water Jug Puzzle

Hi All,
So I am back with a classic water jug puzzle - Courtesy Vaibhav Gupta.
--- Problem ---
I have 3 jars of capacity 19 L, 13 L and 7 L.
13 L and 7 L are completely filled with water.

Give me two jars of 10 L of water.

You are given only 20L water so no spilling is allowed.

--- Solution 1 by vaibhav ---
19L, 13L, 7L (In same order)
Initial conf ==> 0 , 13, 7

0, 13, 7
13, 0, 7
19, 0 , 1
19, 1, 0
12, 1, 7
12, 8, 0
5, 8, 7
5, 13, 2
18, 0, 2
18, 2, 0
11, 2, 7
11, 9, 0
4, 9, 7
4, 13, 3
17, 0, 3
17, 3, 0
10, 3, 7
10, 10, 0
Done. :D

-- Solution 2 by achyut ---

Tilt 13L jar and pour water into 19L upto the point where water surface coincides with the diagonal of the jar, thus exactly pouring half of the water ( 6.5L ) into 19L jar.

Do the same with 7L jar thus we will have 10L ( 6.5L + 3.5L ) in 19L jar.

Pour the remaining 3.5L from 7L jar into 13L jar again making 10L ( 6.5L + 3.5L ).

Now that is called out of the box thinking !!!