The other day I saw this tweet which provided this puzzle: Find sequence such that for some fixed
,
and
is max.
In this post I’ll first build some intuition for which numbers are worth putting in , and then turn that into a proof.
Intuition
The next lemma tells us that for numbers greater than , it is better to use 2s:
Lemma 1:
(expand for proof)
Base cases:
:
:
Inductive hypothesis:
Assume the inequality holds true for
Mult both sides by
and since , then add
to both sides to get
i.e. from it follows
and since we cover both odd/even in base, the proof is complete
So if , instead of
which would give prod
, it is better to use
to get prod
But what about numbers equal or less than ?
- Number 1: product is unchanged, try not to use
- Number 4:
, product unchanged
- Number 5:
, but
, so seq
is better than both
and
- Number 2:
vs
and it’s obvious that
is better
- Number 3: interesting case is
vs
. obviously
so 3s win here
Putting it together
For , start with a seq of positive integers that gives max prod.
By Lemma 1, replace each with
2s (and one 1 if
is odd).
There can’t be any 1s or 5s, since and
would increase prod.
Replace each with
. now we only have 2s and 3s, and at most two 2s since
increases prod.
So the number of 2s is determined by :
: no 2s
: two 2s
: one 2
And we fill the rest with 3s. For example, for , use
to get prod
. For
, the only seq is
.
Python code
def best_seq(n): if n == 1: return [1] twos = [0, 2, 1][n % 3] return [3] * ((n - 2 * twos) // 3) + [2] * twos