CSE Blog - quant, math, computer science puzzles

Source: Australian Mathematical Society Gazette - Puzzle Corner 28 Problem:  The Mad Hatter is holding a hat party, where every guest must bring his or her own hat. At the party,  whenever two guests greet each other, they have to  swap their hats. In order to save time, each pair of  guests is only allowed to greet each other at most  once. After a plethora of greetings, the Mad Hatter notices that it is no longer possible to return all hats to their respective owners through more greetings. To sensibly  resolve this maddening conundrum, he decides to bring in even more hat wearing  guests, to allow for even more greetings and hat swappings. How many extra guests  are needed to return all hats (including the extra ones) to their rightful owners? Other "Hat" Problems on the blog: Puzzle: What's the number on my Hat? Another Hat Puzzle Fair Hat Game Another Hat Problem Hats in a circle Hats and Rooms Num...

Source:   http://www.ocf.berkeley.edu/~wwu/riddles/medium.shtml Problem: My fancy new digital alarm clock is broken! The time 'jumps' around. When I reset it, it reads 12:00:00. Then it runs as it should, but after 12:04:15 it resets back to 12:00:00. It counts up to 12:04:15 again and then it jumps to ... 12:08:32 ! Weird stuff. Do you know what's wrong with my alarm clock? Update (12/02/2013) Solution posted by Saumya Gupta, Abhimanyu Dhamija (CSE IITB 2011 Alumnus, Citibank Analyst) and Naga Vamsi Krishna in comments!

Source: Counter-intuitive Conundrums Problem: Someone hands you a deck of cards which you thoroughly shuffle. Next, you start to deal them, face-up, counting the cards as you go. “One, Two, Three …” The aim is to predict what the count will be when you encounter the second black Ace in the deck. If you had to select one position before you started to deal, what number would you select that maximizes your chance of guessing the location of the second black Ace?

Source: Introduced to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) Problem: An N by N matrix M has entries in {0,1} such that all the 1's in a row appear consecutively. Show that determinant of M is -1 or 0 or 1. Disclaimer: I could not solve it but I have an awesome solution sent by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012) Update (2/4/2013): Solution posted by Amol Sahasrabudhe (IITB 2004 Alumnus, Ex-Morgan Stanley Quant Associate, Deutsche Bank Quant Associate) and Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student) in comments! Thanks a ton. I have posted the solution provided by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012). All three solutions are essentially the same.

Source: Sent to me by Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student) Problem: Given a arbitrary binary string of length n, find three evenly spaced ones within the string if they exist. Write an algorithm which solves this in O(n * log(n)) time. Update (29th January 2013): Solution posted by JDGM in comments!

Source: Andrej Cherkaev's List of Puzzles Problem: A computer scientist claims that he proved somehow that the Fermat theorem is correct for the following 3 numbers: x=2233445566, y=7788990011, z=9988776655 He announces these 3 numbers and calls for a press conference where he is going to present the value of N (to show that x^N + y^N = z^N and that the guy from Princeton was wrong). As the press conference starts, a 10-years old boy raises his hand and says that the respectable scientist has made a mistake and the Fermat theorem cannot hold for those 3 numbers. The scientist checks his computer calculations and finds a bug. How did the boy figure out that the scientist was wrong? Update (06/01/2012): Solution posted by a lot of people in comments!

Source:  (Romanian Informatics Olympiad ONI'03, extended team selection) ( ^ Representative diagram of Huffman Encoding. No relevance in the problem) Problem: A telegraph machine can transmit only lines and dots; it takes 2 seconds to transmit a line, but only 1 second to transmit a dot. We generally want to transmit texts containing letters of the English alphabet, and digits (so we have  N<=36  symbols in total). Therefore, a prefix-free encoding using lines and dots is needed. Given the frequencies of the  N  symbols in a large text, find the minimum time it takes to transmit the text using a suitable encoding. The solution should run in  O(N^4)  time, and use  O(N^3)  space.