Comparison without relational operators

Source: Quant interview at Religare Technova

Problem: Write a C program to compare two integers without using relational operators (== != < <= > >=)
 

Sum of 2001 powers of digits

Source: Problems on Algorithms (Ian Parberry and William Gasarch)

Problem: 
Let f be a function which takes a number x (number with say n digits, digit i represented by d_i) as input and outputs sum of the 2001 powers of the digits. So, f(327)=3^2001 + 2^2001 + 7^2001. Show that for any x, the set {f(x), f(f(x)), f(f(f(x))),..} is finite.

Update (31 January 2011)
Solution: Posted by Sudeep Kamath (UC Berkeley PhD Student & EE IITB Alumnus) in comments!

Expectation of 2^(Cycle Length)

Source: Mailed to me by Sudeep Kamath (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus), Taken from Anand Sarwate (Postdoc at UC San Diego, PhD from UC Berkeley)

Problem:

Given a permutation p of length n, let c(p) be the number of cycles in p. Suppose p is drawn uniformly from the set of all permutations. Show that

Expectation of 2 raised to the power of number of cycles is n+1, i.e E[2^c(p)]=(n+1)

Hint:
1) There is no high funda group theory/number theory involved. I could solve this in 15 minutes \m/ \m/
2) After you are done, you might want to read this (*Spoiler Alert*)

Solution:
Hint posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) in comments! Solution posted by Kalyan in comments! Kalyan's comment explained in detail by me in comments! A simpler solution posted by Gaurav Sinha (chera) (CSE IITK 1996 Alumnus, Indian Revenue Service) in comments!

CMU Puzzle Toad: Abduction

Source: CMU Puzzle Toad

Problem: Farmer Brown is standing in the middle of his perfectly circular field feeling very content. It is midnight and there is no moon and unknown to the farmer, Martian zoologists are landing randomly at points on the circumference of his field. They land at one minute intervals, starting at midnight. As soon as there are martians at points A,B,C such that triangle ABC contains the center of the field, Farmer Brown will be teleported to the waiting space-ship and transported to spend the rest of his life as an exhibit in a Martian zoo. What is the expected time until he is abducted?

Related Problem: http://pratikpoddarcse.blogspot.com/2009/10/semi-circle-covering-n-points-puzzle.html

Solution: Posted on CMU Puzzle Toad (http://www.cs.cmu.edu/puzzle/solution33.pdf). Check my name in the acknowledgments \m/ \m/

Car Problem

Source: www.quantstudy.com

Problem: Let A and B be two cities, with two different roads connecting them. Suppose that two cars can travel from A to B on different roads, keeping a distance that does not exceed 1 mile between them.  Is it possible for two cars to travel one from A to B, the other from B to A such that the distance between them is always greater than one mile?

Update: (23 January 2011)
Solution: Posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments! A more general solution with clear explanation posted by Ameya Ranade (Microsoft Software Engineer, CSE IITB 2009 Graduate)

Birthday Game

Source: Asked to me by Piyush (Third year Undergraduate Student, CSE, IITD)

Problem: There is a big line of people waiting outside a theater for buying tickets. The theater owner comes out and announces that the first person to have a birthday same as someone standing before him in the line gets a free ticket. Where will you stand to maximize your chance.

Solution: Solution posted by me in comments!

Expected number of draws

Source: http://deltaepsilons.wordpress.com/

Problem: Consider a set of n objects from which m are drawn randomly at a time, with replacement.  What is E(n,m), the expected number of draws I have to make to have drawn all of the objects?

Note that we solved a similar problem and got the value of E(n,1) some time back in this problem.