Saturday, February 23, 2008

Matrices with big determinant

The Hadamard inequality roughly says that the determinant of an $n \times n$ matrix whose entries are real numbers with absolute value at most $1$ is not greater than $n^{n/2}$. Can you find arbitrarily large matrices with entries of absolute value at most $1$ for which the equality holds (ie the determinant is exactly $n^{n/2}$)? You don't have to find such an $n \times n$ matrix for each $n$ (for some $n$'s this may be impossible, while for others this is a very difficult, unsolved problem), just find a family for arbitrarily large $n$. Can you also give a quick proof of the inequality? Note: the inequality also holds for complex-valued matrices, but you don't have to use complex numbers to solve this problem.

Bonus problem: is it possible to have equality if the matrix is a real $3 \times 3$ matrix?

Update (09/03/2008): Solution posted! (show solution)

Saturday, February 16, 2008

And a triangulated triangle

Now, you have a triangulated triangle, and all the vertices are colores as red, green and blue. The vertices of the big triangle are respectively red, green and blue, and the vertices of the triangulation that are between the red and green one are red or green, those between the green and blue one are green or blue, and those between the red and blue one are red or blue. Prove that at least one triangle in the triangulation has exactly one vertex for each color.

Update (09/03/2008): Solution posted! (show solution)

Monday, February 11, 2008

Rectangulated rectangle

A large rectangle is partitioned into smaller rectangles, with sides parallel to those of the large rectangle. Each smaller rectangle has at least one side whose length is an integer. (For some rectangles this may be the horizontal side; for others, the vertical side.)

Prove that the same holds true of the large rectangle.

Update (09/03/2008): Solution posted! (show solution)

Tuesday, February 5, 2008

The blue-eyed islanders puzzle

Hi, this is a famous puzzle that probably many people already know, and i was also planning to post it here some day for those who still do not. Anyway, looks like that Terence Tao started discussing it before me, so here is the discussion in case that you are interested, contribute while it is hot. :-)

Saturday, February 2, 2008


$500$ pirates have just stolen a treasure of $100$ gold pieces, and they decide to share it in the following way: starting from the $500$th pirate, and going on with the $499$th, $498$th, and so on, each pirate proposes a way to share the gold (for instance, he says: "the pirate $1$ will receive $13$ gold pieces, the $2$nd $17$ gold pieces, ..."). The proposal is voted, and if it passes with at least $50\%$ votes (including the pirate that is making the proposal) it is accepted and the gold is shared. If the proposal is not accepted, the pirate is shot and the next pirate is going to make a new proposal, and so on. How many pirates will survive?
Note that each pirate only trusts himself, and their main purposes are, in order:
$\mathbf{\alpha}$) survive,
$\mathbf{\beta}$) gain as much gold as possible,
$\mathbf{\gamma}$) kill the highest number of other pirates.
Have fun! :-)

Update (17/02/2008): Solution posted! (show solution)