Maths Olympiad Prep

Library / /365 of 520

Number theory Difficulty 7.1 National olympiad, round 2 Find the answer

2・13 Let S={1,2,,n},AS=\{1,2, \cdots, n\}, A be an arithmetic sequence with at least two terms, a positive common difference, all of whose terms are in SS, and adding any other element of SS to AA does not form an arithmetic sequence with the same common difference as AA. Find the number of such AA (here, a sequence with only two terms is also considered an arithmetic sequence). \quad

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

[Solution] Let the common difference of AA be dd, then 1dn11 \leqslant d \leqslant n-1.
We discuss in two cases:
(1) Suppose nn is even, then
when 1dn21 \leqslant d \leqslant \frac{n}{2}, there are dd AAs with common difference dd;
when n2+1dn1\frac{n}{2}+1 \leqslant d \leqslant n-1, there are ndn-d AAs with common difference dd. Therefore, when nn is even, the total number of such AAs is
(1+2+n12)+{1+2++[n(n2+1)]}=n42 (cases) \left(1+2+\cdots \frac{n-1}{2}\right)+\left\{1+2+\cdots+\left[n-\left(\frac{n}{2}+1\right)\right]\right\}=\frac{n}{4}^{2} \text { (cases) }
(2) Suppose nn is odd, then
when 1dn121 \leqslant d \leqslant \frac{n-1}{2}, there are dd AAs with common difference dd;
when n+12dn1\frac{n+1}{2} \leqslant d \leqslant n-1, there are ndn-d AAs with common difference dd. Therefore, when nn is odd, the total number of such AAs is
(1+2++n12)+(1+2++n12)=n214( cases )\left(1+2+\cdots+\frac{n-1}{2}\right)+\left(1+2+\cdots+\frac{n-1}{2}\right)=\frac{n^{2}-1}{4}(\text { cases })

Both cases can be unified as: the number of such AAs is [n˙24]\left[\frac{\dot{n}^{2}}{4}\right].

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.