Posts

Showing posts from January, 2013

Determinant of Binary Matrix

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.

Evenly Spaced Ones in Binary String

Image
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!



Fermat Theorem Puzzle

Image
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!