Log In

Determinant of binary matrix

Posted on: January 15th, 2013 by
Comments Disabled

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.

via ST Aditya

De Bruin Card Trick

Posted on: January 15th, 2013 by

A dealer(magician) starts with 16 cards on a deck arranged in some particular order. 4 people are seated in a table around the magician. The magician asks each person in turn to cut the deck at any particular point. Then he distributes the top 4 cards one at a time to each person in the table. Then he concentrates for a while. Since the mental transmission is not clear, he asks the people with red cards to raise their hands. Now, suddenly everything becomes clear and the magician reveals the exact card of each player. How does this trick work?

Hint: Look at comments.

Solution: Here is a video that explains the solution:

Acknowledgement: Thanks to Kartik Venkat and Ritesh Kolte for bringing this to our attention.

Points on a circle

Posted on: January 14th, 2013 by

what is the probability that n points distributed uniformly at random on a circle lie within the same semicircle ?

via ST Aditya

For hint: View comments.

If you have interesting solutions, please post the solution as comments.

Benford's law

Posted on: January 14th, 2013 by
Comments Disabled

Benford's law is an interesting anomaly regarding the distribution of the first digit in a collection of data.

"Now, we have noted elsewhere that by definition the first digit of a decimal number cannot be a zero.  That leaves nine ciphers, though, and one might expect each of them to appear about one out of nine times in that first position.  For each, about 11% would make sense.  Not so.  The cipher 1 is almost three times more likely to take the leftmost position than you would expect by chance -- in 30% of numerical entries.  The cipher 2 is next in order, occupying close to 18% of the first positions, and so forth to the cipher 9 at well under 5% thereby getting less than half its fair share."

via Niquette.com

Fermat Theorem Puzzle

Posted on: January 12th, 2013 by

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?

via CSE Blog - quant, math, cse puzzles.

Simple proofs of the Isoperimetric Inequality

Posted on: January 12th, 2013 by
Comments Disabled

The isoperimetric inequality states that "Among all planar shapes with the same perimeter the circle has the largest area."

Here is the simplest geometric proof that I know of:


There are other proofs too:




Acknowledgement: Thanks to the late prof. Thomas Cover for pointing out a simple proof.

Let me know if any of these proofs  can be extended to dimension 3 or higher dimensions.

Is Axiom of choice correct?

Posted on: January 11th, 2013 by

Puzzle #0: There are n+1 people in a line, and each has a 0/1 number on his hat. Each player can look to the numbers of the players in front of him. So, if x_i is the number of player i, then player i knows x_{i+1},\hdots,x_n. Now, from i = 0 \hdots n the players will say his own number. Is there a protocol such that players 1,\hdots,n will get their own number right? (Notice that they hear what the players before him said).

Puzzle #1: Consider the same puzzle with an infinite number of players. I.e. there arex_i; i \in \mathbb{Z}_+ and player i knows x_j for all j > i. Show a protocol for all players, except the first to get the answer right?

Puzzle #2: Still the same setting, but now players don’t hear what the previous player said. Is there a protocol such that only a finite number of players get it wrong ? (notice that it needs to be finite, not bounded).

via Big Red Bits

Beat your friend at a casino

Posted on: January 10th, 2013 by

Suppose your friend invests $1 in a casino and earns $X, where X is a Random variable with mean 1, i.e. E[X]=1. Suppose you know the cdf F(x) of the random variable X. Find the cdf of a random variable Y with mean 1 (E[Y]=1) so as to maximize \Pr\{Y>=X\}.

For hint: View comments on this article.

Acknowledgement: Thanks to the late prof. Thomas Cover for sharing this puzzle with us.

Yue's "swap" problem

Posted on: January 8th, 2013 by
Comments Disabled

Given a regular 13-gon, a red-blue coloring of the vertices is said to be "symmetric" if there exists an axis of symmetry which passes through the center of the 13-gon. A "swap" is an operation in which we exchange the colors of any two vertices.  I claim that any red-blue coloring of the vertices is at most one swap away from being symmetric. Prove/disprove my claim.

Five Points on a Sphere

Posted on: January 8th, 2013 by
Comments Disabled

Given any five points on a sphere, show that there exists a closed hemisphere containing four of them.

{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}