734 Combinatorics and Probability
{
σ(
n+ 3
2)
,σ(
n+ 5
2)
,...,σ(n)}
⊂
{
1 , 2 ,...,
n+ 1
2}
.
Letσ(n+ 21 )=k.Ifk≤n+ 21 , then
{
σ( 1 ),...,σ(
n− 1
2)}
=
{
n+ 3
2,
n+ 5
2,...,n}
and {
σ(
n+ 3
2)
,σ(
n+ 5
2)
,...,σ(n)}
=
{
1 , 2 ,...,
n+ 1
2}
−{k}.Ifk≥n+ 21 , then
{
σ( 1 ),...,σ(
n− 1
2)}
=
{
n+ 1
2,
n+ 3
2,...,n}
−{k}and {
σ(
n+ 3
2)
,σ(
n+ 5
2)
,...,σ(n)}
=
{
1 , 2 ,...,
n− 1
2}
.
For any value ofk, there are[(n− 21 )!]^2 choices for the remaining values ofσ, so there are
n[(
n− 1
2)
!
] 2
such permutations.
(T. Andreescu)
837.Letf (n)be the desired number. We count immediatelyf( 1 )=2,f( 2 )=4. For
the general case we argue inductively. Assume that we already have constructedncircles.
When adding the(n+ 1 )st, it intersects the other circles in 2npoints. Each of the 2n
arcs determined by those points splits some region in two. This produces the recurrence
relationf(n+ 1 )=f (n)+ 2 n. Iterating, we obtain
f (n)= 2 + 2 + 4 + 6 +···+ 2 (n− 1 )=n^2 −n+ 2.(25th W.L. Putnam Mathematical Competition, 1965)838.Again we try to derive a recursive formula for the numberF (n)of regions. But
this time counting the number of regions added by a new sphere is not easy at all. The
previous problem comes in handy. The firstnspheres determine on the(n+ 1 )st exactly
n^2 −n+2 regions. This is because the conditions from the statement give rise on the
last sphere to a configuration of circles in which any two, but no three, intersect. And
this is the only condition that we used in the solution to the previous problem. Each of