Election time

In Italy, there are just three parties: L (the left), R (the right), and N (north league). Elections are done, L and R get each 49\% of votes, N just 2\%. Since an agreement cannot be found, two tie-break rounds are done, where the two biggest parties are matched, and at the second round the winner is matched against the other party. Prove that there is a strategy for N's electors to make their party win the tie-break rounds, knowing that:

• L's electors, if they cannot vote for L they will vote for R, because they hate N.
• R's electors, if they cannot vote for R they will vote for N, because they hate L.

Minimal values

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a function (any function). Let's call
$$ M := \{ x \in \mathbb{R} : \exists\epsilon_x>0: f(x) \leq f(y)\;whenever\;|y-x| < \epsilon_x\} $$
the set of points where $f$ has a (non-strict) local minimum. Let $V=f(M)$ be the set of the local minimal values. Can $V$ have positive Lebesgue measure? (note that $M$ surely can, just take as $f$ a constant function, and every point is a local minimum).

An elettric circuit

There exists an electric circuit that has an interruption. The -proper- length of the interruption is $L_0$. A tract of electric wire runs along the circuit with speed $v$. The -proper- length of the wire is $L_0$ too. In circuit reference system wire length is $L<L_0$, so the circuit is never closed. In wire reference system interruption length is $L<L_0$, so at some instant the circuit is closed. How can you explain the apparent contradiction?
Update(22/04/2008): Solution posted! (show solution)
In wire reference system, the circuit is just formally closed. Indeed the time in which it remains closed is not sufficient to permit the electric current flows. In this reference system, wire length is $ L_0 / \gamma $, where $\gamma$ is $ {(1-v^2/c^2)}^{-\frac{1}{2} $. So the time during which circuit is closed is $ \Delta t = L_0 \frac{1-1/ \gamma}{v} $ and in that time a signal that has the light speed run distance $ d = \frac{c(\gamma -1)}{v \gamma} L_0 < L_0 $. In conclusion if an electrical instrument is connected to circuit, then in both reference systems it is going to do not work.

Is this linear? Are you sure???

Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be a continuous function such that whenever $a$, $b \in \mathbb{R}$ are such that $a-b \in \mathbb{Q}$, then also $f(a)-f(b)\in \mathbb{Q}$. Prove that $f$ is of the form $f(x) = qx + r$, and that $q$ is rational.

Update (16/04/2008): Solution posted! (show solution)
Consider the function $g_1(x) = f(x+1)-f(x)$, and note that it is continuous, and it only allows rational values. Thus, it has to be a constant $g_1(x) = K_1$ (because of the mean-value theorem, and that you can always find an irrational number between two rationals). We can also consider $g_{1/2} = f(x+{1/2)-f(x)$, this must also be a constant $g_{1/2}(x) = K_{1/2}$, and note that
$$K_1 = f(x+1)-f(x) =$$ $$\;= f(x+1)-f(x+1/2) + f(x+1/2)-f(x) =$$ $$\;= K_{1/2}+K_{1/2} =$$ $$\;= 2K_{1/2}$$ And we can repeat this with $K_{1/4}, K_{1/8}, ..., K_{2^{-n}}$, and get that $K_1 = 2^nK_{2^{-n}}$. So, for every diadic rational number $p2^{-n}$, we have that $f(p2^{-n}) - f(0) = pK_{2^{-n}} = p2^{-n}K_1$, ie. that $f(x)-f(0)$ is linear on diadic rationals, and by continuity it is linear everywhere. Thus $f(x) = qx+r$, and of course $f(1)-f(0) = q\in\mathbb{Q}$.

Boring books

There are strange boring books. In every page of those books there is only one sentence saying: 'the sententence at page $p$ is $X$', where $p$ is a positive integer less or equal of that book lenght -in pages- and $X$ belong to $\{true, false\}$.

• For which books does exist a function from the pages to $\{true, false\}$ that makes true the sentence written in each page?
  

• If such a function exists, how many different functions make the job?

Update (08/04/2008): Solution posted! (show solution)
Let's call chapter a minimal collection of pages such that any page points to a page of the same chapter. We can define the required function independently on all chapters, and every such a good function is also a good function within each chapter. So the question is, when does a chapter admit such a function?

• Note that we can iteratively remove any page that is not referred by any other page. Its truth value will be later defined as the same or the opposite of the value of the page it points to (respectively if this is a assert-true of assert-false page), and this is the only way to keep the function coherent while re-adding the page we removed.
• Let's do so till when there is no more unreferred page, and note that we got a loop (in facts, every page is pointed to by exactly one page, because in the graph there is the same number of arrows as pages, and we are considering a connected graph). Let's call this loop the core loop of the chapter.
  
• A loop admits a truth function precisely when the number of assert-false page is even, and if so there are two different such function (just define one page as true or false, and any other page will have to be defined accordingly in a univocal way).

We can now note that if every chapter is good (ie. admits such a function because the core loop contains an even number of assert-false pages), the total number of functions is $2^c$, $c$ being the number of chapers.

Bijective function

Let $f : \mathbb{Z} \rightarrow \mathbb{Z}$ be a bijective function. Prove that you can find two other bijective functions $u$, $v$ from $\mathbb{Z}$ to $\mathbb{Z}$ such that $f(x) = u(x) + v(x)$, $\forall x \in \mathbb{Z}$.


Update (23/03/2008): Solution posted! (show solution)
A solution was written in the comments (in italian), but i will still post the "official" solution because it is short and instructive. Chose an inductive ordering for $\mathbb{Z}$ (for instance $0<-1<1<-2<2<...$). Suppose now that we have defined $u$ and $v$ on a finite set $A\in\mathbb{Z}$ such that they are injective and $f(x) = u(x) + v(x)$, $\forall x \in A$, and start with $A=\emptyset$. Now we can:

Extend the domain: chose the smallest (w.r.t the ordering) $x \in \mathbb{Z}\backslash A$, and define $u(x)$ and $v(x)$ with $f(x) = u(x) + v(x)$ and so that $u$ and $v$ are still injective .We have infinite possible choices for $u(x)$ that automatically also determine $v(x) = f(x) - u(x)$, and they are all good but a finite number (those that make $u$ or $v$ no longer injective).

Extend the image of $u$: let's chose the smallest $y \in \mathbb{Z}\backslash u(A)$, and look for an $x \in \mathbb{Z}\backslash A$ such that we can define $u(x) = y$, $v(x) = f(x)-u(x)$ keeping $u$ and $v$ injective. Again, we have infinite $x$ that we can try ($f(x)$ are all different!), this choice also determines $v(x)$, and only a finite number of them is bad.

The same as 2, but with $v$ in the place of $u$.

After applying any rule the functions will stay injective. Note that if we apply the rule 1 infinite times, we cannot be sure that $u$ and $v$ are sujective, if we apply 2 infinite times, $u$ will be surjective, but possibly not defined everywhere, and similarly for 3 (w.r.t. $v$). But if we apply all them infinite times as 1,2,3,1,2,3,1... we can be sure that $u$ and $v$ are defined everywhere and that they are surjective, because any missing value would be definitively caught by the right rule.

Looks like SPAM...

One million (1000000) people receive an e-mail with the following message:

• If *exactly* one of you will reply to this e-mail, everyone of you will win 100\$. In any other case, everybody will win nothing.

Suppose that the people receiving this e-mail are all very intelligent, they are willing to win the prize, and they cannot comunicate with each other. The only thing that they can do is just replying, or not. Ah, the e-mail is not SPAM, it is serious :)

What is the best strategy that they can adopt to maximize the probability of succeding? What is (more or less) the probability of success?

Update (20/03/2008): Solution posted! (show solution)
All the receivers of the message cannot communicate with each other, and the only thing that they can do to interact with the problem is replying, or not. So let's say that each of them will reply with probability $p$ (the probability is the same for everyone), and let's calculate how likely it is that exactly one of them will reply. Let $n$ ($=1000000$) be the number of people in the problem, let's chose one of them and let's calculate the probablity the he will be the only one that answers. This probability will be $p(1-p)^{n-1}$, adding this quantity over all the people gives us the probability of success $S(p) = np(1-p)^{n-1}$.
Since we want to maximize it, let's calculate:
$$ \frac{d}{dp}S(p) = n(1-p)^{n-1} + np(n-1)(1-p)^{n-2}(-1) =$$
$$ = n(1-p -(n-1)p )(1-p)^{n-2} =$$
$$ = n(1-np)(1-p)^{n-2} $$
So, $ \frac{d}{dp}S(p) = 0$ is solved by $p=1/n$ or $p=1$, and $p=1$ is surely not a maximum. Thus, the best strategy is replying with probability $1/n$, and the probability of success is:
$$ S(1/n) = n\frac{1}{n}(1-\frac{1}{n})^{n-1} = $$
$$ = n\frac{1}{n}(1-\frac{1}{n})^{n-1} \approx e^{-1} (n\rightarrow\infty).$$

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.

An isometry

Let $K$ be a compact metric space, and $\phi : K \rightarrow K$ an isometry. Prove that $\phi$ is surjective.

Update: Changed formulas to LaTeX. Nobody has solved this yet? come on... i know you can do it!

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


Suppose that $f$ is not surjective, and that $x\in K\f(K)$. The image $f(K)$ of $f$ is a compact, and since a metric space is Hausdorff it is also closed. Then, there is an $\epsilon$ such that $\mathcal{B}(x,\epsilon) \cap f(K) = \emptyset$. Now consider the sequence $(x_n)_{n\in \mathbb{N}}$, where $x_0 = x$, $x_1 = f(x)$, $x_2 = f(f(x))$ and so on. Now, since the distance of $x$ from $f(K)$ is at least $\epsilon$, $d(x_0, x_n) \geq \epsilon$, $n \leq 1$. But since $f$ is an isometry, it is also true that $d(x_m, x_n) \geq \epsilon$, for each $n > m$ (in facts, this is true for the pair $x_o, x_{n-m}$, and applying $f$ ($m$ times) preserves the distances), and so the $(x_n)$ cannot have any convergent subsequence. Hence, $K$ cannot be compact.