CSE Blog - quant, math, computer science puzzles

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!