Solution for October 2012
The Problem: 

We say that a realvalued function $f(x)$ of the real variable $x$ is strictly decreasing if $f(a) > f(b)$ whenever $a < b$.
 Does there exist a strictly decreasing function $f$ for which $f\left(f(x)\right) = x+1$ for all $x\in \mathbf{ R}$?
 Does there exist a strictly decreasing function $g$ for which $g\left(g(x)\right) = 2x+1$ for all $x\in \mathbf{ R}$?

The solution:
Correct solutions were submitted by
Lamis Alsheikh (Syria) 
Diana Andrei (Sweden) 
Daniel Lopez Aguayo (Mexico) 
Luigi Bernardini (Italy) 
Aleksandar Blazhevski (Macedonia) 
Bernard Collignon (France) 
Olivier Cyr (France) 
Hubert Desprez (France) 
MeiHui Fang (Austria) 
Federico Foieri and Nicolás Otero (Argentina) 
Philippe Fondanaiche (France) 
Jan Fricke (Germany) 
Gruian Cornel (Romania) 
Tony Harrison (England) 
Benoît Humbert (France) 
Alex Jeon 
Kipp Johnson (USA) 
Matthew Lim (USA) 
Shpetim Rexhepi (Macedonia) 
Albert Stadler (Switzerland) 
Hakan Summakoğlu (Turkey) 
Arthur Vause (UK) 
Ruben Victor Cohen 
David K.M. Yang (USA) 
Patrick J. LoPresti (USA) 

There was one incorrect submission.
a. No, no function $f$ for which $f\left(f(x)\right) = x+1$ for all $x\in \mathbf{ R}$ can be strictly decreasing. We can use any real number $x$ for a counter example, so we first use $x=f(0)$:
\[f\left(f(f(0))\right) = f(0)+1.\] 
(1) 
But with $x=0$ we have $f\left(f(0)\right) = 0+1 = 1$, so that
\[f\left(f(f(0))\right) = f(1).\] 
(2) 
Comparing equations (1) and (2) we deduce that $f(1) = f(0) + 1$;
that is, $f(1) > f(0)$, whence $f$ cannot be decreasing, let alone strictly decreasing.
An alternative argument was given by a few correspondents who know some basic analysis: Because the function that takes $x$ to $x+1$, namely $f(f(x))$, is bijective, it follows that $f(x)$ must also be bijective. From a course in real analysis we know that a decreasing bijection that maps $\mathbb{R}$ onto $\mathbb{R}$ must have a fixed point (namely the value of $x$ where its graph intersects the line $y=x$), which would also be a fixed point of $f(f(x)) = x + 1$. But this map does not have a fixed point (since $x=x+1$ has no real solution), a contradiction.
b. Yes, there exists a strictly decreasing function $g$ for which $g\left(g(x)\right) = 2x+1$ for all $x\in \mathbf{ R}$. Such a function is
$$g(x) = \sqrt 2 x  (1+\sqrt 2).$$
Note that $g(x)$ is decreasing because it is the equation of a line with negative slope; moreover,
$$g(g(x)) = \sqrt 2(\sqrt 2x 1\sqrt 2)  (1 + \sqrt 2) = 2x +1,$$
as desired.
In fact, we easily see that this is the only linear function that does the job: a decreasing linear function must satisfy $g(x) = ax+b$ for real numbers $a$ and $b$ with $a<0$.
$$g\left(g(x)\right) = g(ax+b) = a(ax+b) + b = a^2x + (ab+b).$$
This quantity equals $2x+1$ only if $a^2=2$, whence $a=\sqrt 2$, and $ab+b = \sqrt 2 b + b = 1$, whence $b = \frac1{\sqrt 2 + 1} = (\sqrt 2 + 1)$, as claimed.
Further comments. The reader should explore for himself why the preceding calculation fails for $f(x) = ax+b$ when $f\left(f(x)\right) = x+1$. As for possible uniqueness in part (b), both Desprez and Humbert observed that (b) has infinitely many solutions. For all real numbers $a \ne \frac12$,
$$g(x) = \left\{\begin{array}{cc} 2^a(x+1)1 & \mbox{ if } \; x \le 1 \\
2^{1a}(x+1)1 & \mbox{ if } \; x \ge 1 \end{array}\right.$$
serves as a nonlinear example. Desprez went further and proved that if $a \le 0$, or if $a=1$ and $b \ne 0$, then there are no strictly decreasing functions that satisfy $f\left(f(x)\right) = ax+b$ for all $x$; otherwise there are infinitely many such functions. He showed, furthermore, how to construct all of them: take an arbitrary continuous strictly decreasing function on an appropriate interval, then use the functional equation $f(ax+b) = af(x)+b$ to extend that function to the real line.
