Sunday, April 20, 2008

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.

Wednesday, April 16, 2008

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

Friday, April 4, 2008

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)

Saturday, March 29, 2008

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)

Tuesday, March 18, 2008

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)

Saturday, March 8, 2008

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)

Sunday, March 2, 2008

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)

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

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)

Saturday, January 26, 2008

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)