ISL 2001 C1

by Wolstenholme, Aug 1, 2014, 9:22 PM

Let $A = (a_1, a_2, \ldots, a_{2001})$ be a sequence of positive integers. Let $m$ be the number of $3$ -element subsequences $(a_i,a_j,a_k)$ with $1 \leq i < j < k \leq 2001$ , such that $a_j = a_i + 1$ and $a_k = a_j + 1$ . Considering all such sequences $A$ , find the greatest value of $m$ .

Solution:

I claim that the answer is $667^3$ which can be obtained by letting $a_i = 1, a_j = 2, a_k = 3$ for all $i \equiv 1 \pmod{3}, j \equiv 2 \pmod{3}, k \equiv 0 \pmod{3}$ .

Now I shall show that $667^3$ is the highest possible number of triples. Let $r, s, t$ be the number of $a_i$ that are congruent to $0, 1, 2 \pmod 3$ respectively. It is clear that since each relevant $3$ -element subset forms a complete residue system modulo $3$ so the maximum number of such subsets is $rst$ .

Now by AM-GM we have that $rst \leq \frac{(r + s + t)^3}{27} = 667^3$ as desired, so we are done.

Comment

0 Comments

Submit

glad to have found a fellow chipotle lover <3
by nukelauncher, Aug 13, 2020, 6:40 AM
the random chinese tst problem is the only thing I read, but I'll assume your blog is nice and give you a shout even though you probably never use aops anymoer
by fukano_2, Jun 14, 2020, 6:24 AM
wolstenholme - op
by AopsUser101, Jan 29, 2020, 8:27 PM
this blog is so hot
by mathleticguyyy, Jun 5, 2019, 8:26 PM
Hi. Nice Blog!
by User360702, Jan 10, 2019, 6:03 PM
helloooooo
by songssari, Jun 12, 2016, 8:21 AM
shouts make blogs happier
by briantix, Mar 18, 2016, 9:57 PM
You were just featured on AoPS's facebook page.
by mishka1980, Sep 12, 2015, 10:33 PM
This is late, but where is the ARML results post?
by donot, Aug 31, 2015, 11:07 PM
"I am Sam"
"Sam I am"
by mathwizard888, Aug 12, 2015, 9:13 PM
HW $\textcolor{white}{}$
by Eugenis, Apr 20, 2015, 10:10 PM
Uh-oh ARML practice is Thursday... I should start the homework.
by nosaj, Apr 20, 2015, 12:34 AM
Yes I am Sam, and Chebyshev polynomials aren't trivial, although they do make some problems trivial
by Wolstenholme, Apr 15, 2015, 10:00 PM
How are Chebyshev Polynomials trivial?
by nosaj, Apr 13, 2015, 4:10 AM
Are you Sam?
by Eugenis, Apr 4, 2015, 2:05 AM
@Brian: yes, yes I did #whoneedsalgskillz?

@gauss1181; hey!
by Wolstenholme, Mar 1, 2015, 11:25 PM
hello!!!
by gauss1181, Nov 27, 2014, 12:19 AM
Hi Wolstenholme did you actually use calc on that tstst problem
by briantix, Aug 2, 2014, 12:25 AM

18 shouts

Wolstenholme's blog

ISL 2001 C1

by Wolstenholme, Aug 1, 2014, 9:22 PM

0 Comments