Let $a_1,a_2,\dots, a_{17}$ be a permutation of $1,2,\dots, 17$ such that $(a_1-a_2)(a_2-a_3)\dots(a_{17}-a_1)=2^n$ . Find the maximum possible value of positive integer $n$ .
Problem
Source: 2019 CSMO Grade 11 Problem 1
Tags: maximum value, combinatorics
jeff10
26.11.2020 03:12
Reversing the order of the permutation multiplies the expression on the left by $-1$, so we do not need to worry about positive or negative when treating the resulting value. It is also clear that all differences of the form $a_i - a_j$ for $i, j \le 17$ must be powers of $2$.
There are two distinct classes modulo $2$. In order to reach both of them, we must have at least $2$ differences equal to $1$ in order to reach them both. If there were none, then we would be stuck on the odd integers or stuck on the even integers, and if there was only one, then a permutation that starts with an odd integer can never cycle back.
Using a similar "distinct modulo classes" argument, we can deduce that at least $4$ differences must be at most $2$, at least $8$ differences must be at most $4$, and at most $16$ differences must be at most $8$. Hence, the largest possible value that the expression on the left can attain is $2(2^0)\times 2(2^1)\times 4(2^2)\times 8(2^3)\times 1(2^4) = 2^{17}$. We see that this is attainable via the sequence $17, 1, 9, 13, 5, 3, 11, 7, 15, 14, 6, 10, 2, 4, 12, 8, 16$ (or its reverse). Hence, the maximum possible value of $n$ is $\boxed{17}$.
EmersonSoriano
02.06.2022 02:22
There is an example for $n=38$: $$(1-17)(17-9)(9-13)(13-5)(5-3)(3-11)(11-15)(15-7)(7-8)(8-16)(16-12)(12-4)(4-6)(6-14)(14-10)(10-2)(2-1)=2^{38}.$$