764 Combinatorics and Probability
890.Leta<b<c<dbe the members of a connected setS. Becausea−1 does not
belong to the set, it follows thata+ 1 ∈S, henceb=a+1. Similarly, sinced+ 1 ∈/S,
we deduce thatd− 1 ∈S; hencec=d−1. Therefore, a connected set has the form
{a, a+ 1 ,d− 1 ,d}, withd−a>2.
(a) There are 10 connected subsets of the set{ 1 , 2 , 3 , 4 , 5 , 6 , 7 }, namely,
{ 1 , 2 , 3 , 4 }; { 1 , 2 , 4 , 5 }; { 1 , 2 , 5 , 6 }; { 1 , 2 , 6 , 7 },
{ 2 , 3 , 4 , 5 };{ 2 , 3 , 5 , 6 }; { 2 , 3 , 6 , 7 }{ 3 , 4 , 5 , 6 }; { 2 , 4 , 6 , 7 };and{ 4 , 5 , 6 , 7 }.(b) CallD=d−a+1 the diameter of the set{a, a+ 1 ,d− 1 ,d}. Clearly,D> 3
andD≤n− 1 + 1 =n. ForD=4 there aren−3 connected sets, forD=5 there are
n−4 connected sets, and so on. Adding up yields
Cn= 1 + 2 + 3 +···+n− 3 =(n− 3 )(n− 2 )
2,
which is the desired formula.
(Romanian Mathematical Olympiad, 2006)
891.The solution involves a counting argument that shows that the total number of
colorings exceeds those that make some 18-term arithmetic sequence monochromatic.
There are 2^2005 colorings of a set with 2005 elements by two colors. The number
of colorings that make a fixed 18-term sequence monochromatic is 2^2005 −^17 , since the
terms not belonging to the sequence can be colored without restriction, while those in
the sequence can be colored either all black or all white.
How many 18-term arithmetic sequences can be found in the set{ 1 , 2 ,..., 2005 }?
Such a sequencea, a+r, a+ 2 r,...,a+ 17 ris completely determined byaandrsubject
to the conditiona+ 17 r≤2005. For everyathere are^200517 −aarithmetic sequences
that start witha. Altogether, the number of arithmetic sequences does not exceed
(^2005) ∑
a= 1
2005 −a
17
=
2004 · 2005
2 · 17
.
So the total number of colorings that makes an arithmetic sequence monochromatic does
not exceed
22005 −^17 ·2004 · 2005
34
,
which is considerably smaller than 2^2005. The conclusion follows.
(communicated by A. Negu ̧t)
892.Let us consider the collection of all subsets with 2 elements ofA 1 ,A 2 ,...,Am.
We thus have a collection of 6msubsets with two elements ofA. But the number of