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