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)
The inequality can be quickly proved if you note that the Euclidean norm of a column vector is at most $\sqrt{n}$, and that the determinant is also the volume of the parallelepiped defined by the column vectors. Since its volume in the lucky case that the column vectors are all orthogonal is exactly $\sqrt{n}^n$, we have the estimate (alternatively you can note that applying Gram-Schmidt orthogonalization the norm of the vectors is not increased and the determinant stays the same, so you end up with orthogonal vectors that are smaller or of equal size, and you can estimate here the determinant).

Now, the problem asks if we can show arbitrarily big matrices where the equality holds, and we can do this by finding $n$ orthogonal vectors with coordinates $-1$ o $1$, and this can be done inductively: if we have found such $n$ vectors with $n$ components, we will show $2n$ new vectors with $2n$ components. Suppose that we have $v_i = (a_{i1},..., a_{in})$, our new vectors will be $w_i = (a_{i1},..., a_{in}, a_{i1},..., a_{in})$ for $i = 1,...,n$ and $w_i = (a_{(i-n)1},..., a_{(i-n)n}, -a_{(i-n)1},..., -a_{(i-n)n})$ for $i = n+1,...,2n$. It is straightward to see that the $w_i$ are orthogonal (because the $v_i$ are), and they have the maximum allowed norm, so we have our good matrix because the inductive step is trivial (just take the constant $1$). What we did is passing from the matrix $M$ to the double-sized matrix $N$ containing $M$ in all corners except for the down-right corner that contains $-M$ instead.

Note: we found such matrices for all the powers of $2$. It was proved that the equality cannot hold if $n$ is not $1$, $2$, or $4k$ for some $k$, and it is an open problem (Hadamard conjecture) to prove if it can be done for all $n = 4k$.

Solution of the bonus problem: the vectors that are in such an hypothetical matrix must have norm exactly $\sqrt{n}$, so they must lie on the sphere with radius $\sqrt{n}$. But the condition of having entires at most $1$ forces them to be in the 3-dimensional cube $[-1,1]\times[-1,1]\times[-1,1]$. Thus the only possibilities are the vertices of the cube, and you cannot find $3$ of them that are orthogonal.

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)
For each truangulation you can consider the following invariant (defined modulo $2$): walk along the boundary, and add $1$ modulo $2$ every time that you walk on an edge between two vertices of different color. It is easy to see that the invariant calculated on the union of two regions is the sum of the invariants (in facts the boundary between the two regions would be calculated two times, and it would sum up to $0$, modulo $2$).
Now, for each triangle with at least two vertices with the same color this invariant is $0$, but for the whole triangle it is $1$, so there must be at least one small triangle with all vertices with different colors.

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)
Consider the following integral:
$$\int_{x_0}^{x_1}\int_{y_0}^{y_1}e^{2\pi i(x+y)}dxdy = $$
$$\int_{x_0}^{x_1}e^{2\pi ix}dx \int_{y_0}^{y_1}e^{2\pi iy}dy = $$
$$\frac{(e^{2\pi ix_1} - e^{2\pi ix_0}) (e^{2\pi iy_1} - e^{2\pi iy_0})}{(2\pi i)^2} $$

It is easy to see that this is $0$ if and only if $x_1-x_0$ or $y_1-y_0$ is an integer. The value of the integral for each small rectangle is $0$, so it has to be $0$ also for the big rectangle, that must now have at least one side of integer lenght.

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. :-)

Pirates!

$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)
Suppose that only 2 the pirates remain alive: in this case, the 2nd pirate will simply bring home all gold (votes: 1vs1). What if they are 3? The 3rd pirate has no way to bring the pirate 2 on his side (because he would get all gold anyway), but he can get the vote of the pirate number 1 by just giving him one gold piece, so he proposes to share the gold as 1/0/99 (votes: 2vs1). If they are 4? the pirate number 4 need one vote, and he can get one by giving one gold piece to the 2 pirate, that would otherwise get no gold at all, so he says: 0/1/0/99 (votes: 2vs2).
Case with 5 pirates: 1/0/1/0/98 (votes: 3vs2)
Case with 6 pirates: 0/1/0/1/0/98 (votes: 3vs3)
Case with 7 pirates: 1/0/1/0/1/0/97 (votes: 4vs3)
Case with 8 pirates: 0/1/0/1/0/1/0/97 (votes: 4vs4)
....
Case with 201 pirates: the 201th can save himself giving 1 gold piece to all odd pirates 1,3,5,...,199 (votes: 101vs100)
Case with 202 pirates: the 202th can save himself giving 1 gold piece to all even pirates 2,4,6,...,200 (votes: 101vs101)
Note that the pirates from 1 to 200 are "semplified" since now on, because with 100 gold pieces each pirate will be able to buy 100 votes, while the other 100 will vote against him.
203 pirates: the 203th can only buy 100 other votes, and they are not enough.
204 pirates: the 204th can buy 100 votes, but he will also get a vote from the 203th, so he will survive.
205 pirates: the 205th pirate will die.
206 pirates: the 206th pirate will die.
207 pirates: the 207th pirate will die.
208 pirates: he can buy 100 votes as usual, and the 205th, 206th, 207th pirates will accept any proposal (because they would die if the proposal is rejected). So he survives.
209 pirates: the 209th pirate will die.
210 pirates: the 210th pirate will die.
....
215 pirates: the 215th pirate will die.
216 pirates: he can buy 100 votes as usual, and the 209th, 210th, ..., 215th pirates will accept any proposal (because they would die if the proposal is rejected). So he survives.
...

Now you've probably guessed that the pirates above the 200th that can make a proposal that will be accepted are the (200+x)ths, where x is a power of 2. So, since the biggest power of 2 less then 300 is 256, the answer to the problem is 456, ie the pirates 500, 499, ..., 457 will all die, and the 456 that will make a proposal that will be accepted.