OK, it's been long enough that I should probably post the official solution now. See here for an extension (it may not be obvious why this is an extension, but the solution below should make it fairly clear). Bobby Shen wrote: This proof makes use of the ring $\mathbb{Z}[x]$ modulo $x^n-1$ and $c$. A state of the lock $a_1, a_2, \ldots, a_n$ corresponds to the element $\sum_{i=1}^{n} a_i x^{i-1}$. The merit of this particular modulus is that each turn includes adding a desired state to the current state, and rotation of the lock is equivalent to multiplication by powers of $x$. We first prove that if primes $p \neq q$ satisfy $p \mid n$, $q \mid c$, then the lock can't be opened deterministically. (As $n,c>1$, this is equivalent to the "only if" direction of the problem.) Without loss of generality, assume that $c=q$ because if one cannot deterministically set all coefficients to $0$ mod $q$, then one certainly cannot do this modulo $c$. Consider the set $S$ of (symmetric) lock states whose coefficients, when listed in order, are periodic with (minimum) period dividing $n/p$, and let $S'$ be its complement with respect to the set of all states. Notice that an element $a$ is in $S$ if and only if $a(x^{n/p}-1) \equiv 0$, and that $a \in S \Longleftrightarrow {a x^k \in S}$. Initially, the lock may be at some "asymmetric" state $a \in S'$, where $a = \sum_{i=0}^{n-1} a_i x^i$. (For example, $1$ is not symmetric.) We now show that after each turn, this is true (not necessarily for the same $a$). Suppose that the element $b$ is added during the first turn. Possible states for the lock include $b+ax^k$ for all $k$. Multiplying this by $x^{n/p}-1$ gives $b(x^{n/p}-1)+a(x^{n/p}-1)x^k$ where the latter term is nonzero. We claim that $a(x^{n/p}-1) \neq a(x^{n/p}-1)x$. If this were not true, then for some $d\not \equiv 0 \pmod{q}$, $a(x^{n/p}-1) \equiv d(x^{n-1} + \cdots + x + 1)$, so \[a_{n/p}-a_0 \equiv a_{2n/p}-a_{n/p} \equiv \cdots \equiv a_{0}-a_{(p-1)n/p} \equiv d \pmod{q}.\]Adding these $p$ equations yields $0 \equiv pd \pmod{q}$, which is absurd. Therefore, the expression $b(x^{n/p}-1)+a(x^{n/p}-1)x^k$ must take on more than one value. In particular, it takes on a nonzero value, indicating that one of the elements $a'=b+ax^k$ is in $S'$. After rotation, the lock may take on any value of the form $a' x^k$. This shows that after each turn, the lock may still be at an asymmetric state ($0$ is not an asymmetric state). This shows that the lock cannot be opened deterministically. It remains to prove that when $n=p^k, c=p^j$, the lock can always be opened, but first we restrict our attention to $c=p$. It is well known that modulo $p$, $(x-1)^p \equiv x^p-1$. It is easy to see that in fact, $(x-1)^{p^k} \equiv x^{p^k}-1 \equiv 0$ in the ring $\mathbb{Z}[x] / x^n-1, p$. Therefore, for any element $a$, there is some least integer (which is at most $n$) $\text{ord}(a)$ such that $a (x-1)^{\text{ord}(a)} \equiv 0$. The only elements $b$ such that $b(x-1) \equiv 0$ are of the form $d(x^{n-1} + \cdots + x + 1)$. Therefore, for each $a \not \equiv 0$, call the corresponding value $d$ (WLOG, $0 < d < p$) for $a (x-1)^{\text{ord}(a)-1}$ the index $\text{ind}(a)$. The following are necessary facts about $\text{ord}$ (the order) and $\text{ind}$ (the index) to complete the case of $c=p$. Fact 1. If $\text{ord}(b)<\text{ord}(a)$, then $\text{ord}(b+a)=\text{ord}(a)$ and $\text{ind}(b+a)=\text{ind}(a)$. Proof. This is true because $(b+a)(x-1)^{\text{ord}(a)} \equiv 0+0$ and $(b+a)(x-1)^{\text{ord}(a)-1} \equiv 0 + a(x-1)^{\text{ord}(a)-1}$. (The indices are equal because multiplying either $a$ or $b+a$ by $(x-1)^{\text{ord}(a)-1}$ gives the same result.)$\blacksquare$ Fact 2. Suppose that $\text{ord}(a_1)=\text{ord}(a_2) \neq 0$. If $\text{ind}(a_1)+\text{ind}(a_2) \not \equiv 0 \pmod{p}$, then $\text{ord}(a_1+a_2)=\text{ord}(a_1)$ and $\text{ind}(a_1+a_2) \equiv \text{ind}(a_1)+\text{ind}(a_2) \pmod{p}$. Otherwise, $\text{ord}(a_1+a_2)<\text{ord}(a_1)$. Proof. Certainly, $(a_1+a_2)(x-1)^{\text{ord}(a_1)} \equiv 0$. $(a_1+a_2)(x-1)^{\text{ord}(a_1)-1} \equiv (\text{ind}(a_1)+\text{ind}(a_2))(x^{n-1}+ \cdots + x + 1)$, so if the former factor is not $0$ mod $p$, then the order of $a_1+a_2$ is $\text{ord}(a_1)$ and its index is as expected. If the former factor is $0$ mod $p$, then order is indeed less than $\text{ord}(a_1)$.$\blacksquare$ Fact 3. $\text{ord}(a)=\text{ord}(ax^k)$ and $\text{ind}(a)=\text{ind}(ax^k)$. Proof. Simply observe that $ax^k(x-1)^{\text{ord}(a)} \equiv 0$ and $ax^k(x-1)^{\text{ord}(a)-1} \equiv \text{ind}(a)x^k(x^{n-1}+ \cdots + x + 1) \equiv\text{ind}(a)(x^{n-1}+ \cdots + x + 1)$.$\blacksquare$ Partition all possible states of the lock into the set $\{0\}$ and sets $S_{o,i}$ where $0<o \le n$ and $0 < i < n$, where $a \in S_{\text{ord}(a), \text{ind}(a)}$. The process of opening the lock can be represented by keeping track of the remaining possible states. Each turn consists of adding an element to all these possible states, eliminating the $0$ state if it exists, and generating all rotations of remaining states. For our purposes, it suffices to consider the above sets: A set is eliminated if and only if all of its elements are eliminated. In doing this, rotations may be ignored because by 3, they keep elements in the same set. We will prove by induction that one may eliminate all sets of order at most $r$. This is clearly true for $r=0$ by first adding $0$ and also easy to see for $r=1$ because one may repeatedly add the element $x^{n-1}+ \cdots + x + 1$. Notice that in this description, only elements of order less than 2 were added so that by 1, this keeps other elements in the same set. Suppose that for some $0<r<n$, one may eliminate all sets of order at most $r$ such that only elements of order at most $r$ were added. We wish to eliminate all sets of order at most $r+1$, which would finish this case. To do this, first eliminate all sets of order at most $r$. Next, add the element $(x-1)^{n-r-1}$ which has order $r+1$ and index $1$. By repeated application of 2, this takes $S_{r+1,1}$ to $S_{r+1,2}$ etc. and $S_{r+1,p-1}$ to arbitrary sets of smaller order. In particular, the set $S_{r+1,1}$ is eliminated (the elements that would have been shifted to this set are exactly those of order $r$ or less). Eliminate the sets of order at most $r$ according to the earlier assumption. This doesn't affect the sets $s_{r+1,d}$. Again, add the element $(x-1)^{n-r-1}$ which eliminates $S_{r+1,2}$. it is easy to see that this process eventually eliminates all sets of order at most $r+1$ and only uses additions of order at most $r+1$. The partial conclusion follows because one can eliminate every single set which means that the lock must have been opened. For one final induction, we will show that the lock can be opened for $n=p^k$, $c=p^j$ by induction on $j$. The base case has just been shown. Suppose that the lock can be opened for $n=p^k$, $c=p^j$ where $j>0$. Let $a_1, a_2, \ldots, a_s$ be a sequence of additions to the lock that guarantees opening the lock for $n=p^k$, $c=p$ which exists as above. Let $b_1, b_2, \ldots, b_t$ be a sequence of additions to the lock that guarantees opening the lock for $n=p^k$, $c=p^j$ which exists by assumption. I claim that for $n=p^k$, $c=p^{j+1}$, the sequence of additions $a_1, pb_1, pb_2, \ldots, pb_t, a_2, pb_1, pb_2, \ldots, pb_t, a_3, \ldots, a_s, pb_1, pb_2, \ldots, pb_t$ opens the lock, where interrupting the $c=p$ sequence at each turn is the $c=p^j$ sequence, multiplied by $p$. To see why this works, consider the lock mod $p$. The only steps at which it changes are the steps $a_i$. By definition, the lock is indeed $0$ mod $p$ after some step $a_i$. After this, the algorithm applies the sequence $pb_1, pb_2, \ldots pb_t$. This is exactly a $n=p^k,c=p^j$ lock multiplied by p (the state and additions are multiplied), so by the definition of this $c=p^j$ sequence, the lock opens after one of these $t$ steps. This completes the induction and shows that the lock can be opened deterministically if and only if $n$ and $c$ are powers of the same prime. Remark 1. This problem is inspired by the easier special case of $c=2$ and specific $n$, which the reader may have seen elsewhere. Remark 2. There is a seeming clumsiness to the second part of this proof in that it must define two functions which in the end, behave in a very predictable way. This is because they are fancified labels for familiar quantities: the degree and the leading coefficient! In a manner that we have only "explicitly" used for $c=p$, each state of the lock can be represented as a polynomial $P(x)$ such that $P(i) \equiv a_i$ for each $i$. Then order is one more than the degree, and index is equal to the leading coefficient. Properties 1 through 3 are now obvious. Nevertheless, the polynomial idea can be generalized to directly address $c=p^l$ in general -- we invite the reader to try this!

bobby shen is the ultimate troll.

math154 wrote: Bobby Shen wrote: This proof makes use of the ring $\mathbb{Z}[x]$ modulo $x^n-1$ and $c$. A state of the lock $a_1, a_2, \ldots, a_n$ corresponds to the element $\sum_{i=1}^{n} a_i x^{i-1}$. The merit of this particular modulus is that each turn includes adding a desired state to the current state, and rotation of the lock is equivalent to multiplication by powers of $x$. Let me sketch some key points of the solution for people familiar with algebra. When $c$ is a prime and $n$ has a prime factor $p\neq c$, the ideal generated by the cyclotomic polynomial $\Phi_p(x)$ and $x-1$ in $\mathbb{F}_c[x]$ is the whole ring, thus $a\notin(\Phi_p(x))\subset\mathbb{F}_c[x]/(x^n-1)$ $\Rightarrow$ $a(x-1)\notin(\Phi_p(x))$ and hence for any $b$ at least one of $b+a$ or $b+ax$ is out of $(\Phi_p(x)),$ i.e. unlucky rotations could always keep you outside a certain set of states containing $0$ if you are initially out of it. For the constructive part we first note that \begin{align*} n\text{ and }c\text{ are powers of a same prime }p&\Leftrightarrow\text{the (finite) Artin ring }(\mathbb{Z}/c)[x]/(x^n-1)\text{ is local}\\ &\Rightarrow\text{the zero divisor }x-1\text{ is nilpotent} \end{align*}(explicitly we have $(x-1)^n\in(p)$ $\Rightarrow$ $(x-1)^{nr}=0$ if $c=p^r$; for the nilpotence of $x-1$ the condition on $n,c$ is also necessary when $n>1$). Then one can construct for every $m$ a sequence of moves sending any element of $((x-1)^m)$ to $0$ at least once by backward induction. Observe that 1. when $a\in((x-1)^m),$ the residue class $b+ax^k$ mod $(x-1)^{m+1}$ doesn't depend on $k$ and 2. $((x-1)^m)/((x-1)^{m+1})$ is a cyclic group, say of order $l_m=l_{m,n,c}.$ Suppose $S_{m+1}$ is such a sequence of moves for $m+1$, then \[S_m=(S_{m+1},+(x-1)^m,...,S_{m+1},+(x-1)^m,S_{m+1}),\]where $+(x-1)^m$ stands for adding $(x-1)^m$ and repeats $l_m-1$ times, is as desired for $m.$ In particular the length of $S_0$ could be \[\#(\mathbb{Z}/c)[x]/(x^n-1)-1=c^n-1,\]which is as small as possible (consider the case where the lock happens to never shift).

As a kid, ELMO was the scariest olympiad I knew, and this was number one on my list of terrifying problem statements. Being able to solve the problem now brings a strange sense of closure.

We present a more enlightening solution. Solved with Espen Slettnes, Justin Lee, and Max Lu. It is possible whenever \(n\) and \(c\) are powers of the same prime. Say a \((n,c)\)-polynomial is an integer-valued polynomial \(P\) such that whenever \(x\) and \(y\) are integers with \(x\equiv y\pmod n\), then \(P(x)\) and \(P(y)\) are integers with \(P(x)\equiv P(y)\pmod c\). Chapter I: Reduction to polynomials Say a state of the lock is polynomial and degree-\(d\) if there is a \((n,c)\)-polynomial with degree \(d\) so that \(P(i)=d_i\) for all \(1\le i\le n\), and non-polynomial if no such \((n,c)\)-polynomial exists. Claim: If the user can guarantee that the lock is opened in \(d\) moves, then the current position of the lock is degree-\(d\) (i.e.\ polynomial). Proof. The proof is by induction on \(d\), with base case \(d=0\) trivial. It suffices to show that if we can guarantee in one move that the lock is degree-\((d-1)\), then the current position is degree-\(d\). Assume the current position is \((d_1,\ldots,d_n)\), and that the user wishes to add \((x_1,\ldots,x_n)\). Then the sum of \((x_1,\ldots,x_n)\) with all cyclic shifts of \((d_1,\ldots,d_n)\) must be degree-\(d\); that is, for each \(k\) there is a \((n,c)\)-polynomial \(P_k\) of degree \(d\) so that \[P_k(i)\equiv d_{k+i}+x_i\pmod c\quad\forall\; 1\le i\le n.\]It follows that \[d_{j+1}-d_j\equiv P_1(j)-P_0(j)\pmod c\quad\forall\; 1\le j\le n,\]so the differences \(d_2-d_1\), \(\ldots\) are degree-\((d-1)\), implying \(d_1\), \(\ldots\) are degree-\(d\). \(\blacksquare\) Claim: If the position of the lock is degree-\(d\), then at some point, the user can guarantee the position of the lock is degree-\((d-1)\) while ensuring the lock is always degree-\(\le d\). Proof. Consider the degree-\(d\) \((n,c)\)-polynomial \(P_0\) of minimal positive leading coefficient \(\lambda_0\). If the current position may be modeled by the \((n,c)\)-polynomial \(P\) with leading coefficient \(\lambda\), we contend \(\lambda/\lambda_0\in\mathbb Z\). If not, then the leading coefficient of some linear combination of \(P\) and \(P_0\) has magnitude less than \(\lambda_0\). Now, let \(\lambda_0\) have denominator \(D\). From the current position, the user adds \((P_0(1),\ldots,P_0(n))\) a total of \(nD\) times. Then degree always remains at most \(d\), and at some point, the leading term must disappear. \(\blacksquare\) Claim: If the position of the lock is degree-\(d\), then the user can guarantee the position of the lock is \((0,0,\ldots,0)\) while ensuring the lock is always degree-\(\le d\). Proof. We proceed by induction on the degree of the lock. Suppose the position of the lock is degree-\(d\). Then Claim 2 provides a sequence of moves \(A_1\), \(\ldots\), \(A_i\) to ensure that at some point, a degree-\(d\) combination becomes degree-\((d-1)\). The inductive hypothesis provides a sequence of moves \(B_1\), \(\ldots\), \(B_j\) to ensure that a degree-\((d-1)\) combination becomes \((0,0,\ldots,0)\). Then the user applies the moves \[A_1,\;B_1,\;\ldots,\;B_j,\;A_1,\;B_1,\;\ldots,\;B_j,\;A_2,\;\ldots.\]The intermediate operations \(B_1\), \(\ldots\), \(B_j\) do not affect the \(x^d\) term of the polynomial, so after some \(A_i\), the \(x^d\) term vanishes, after which \(B_1\), \(\ldots\), \(B_j\) force \((0,0,\ldots,0)\). \(\blacksquare\) Hence we have established: \begin{quote} The user may guarantee that the lock is opened if and only if the starting configuration is polynomial. \end{quote} Chapter II: Extraction of good pairs It remains to find all \((n,c)\) for which every starting configuration is polynomial. Call such a pair good. We first prove that \((n,c)\) can only be good if \(n\) and \(c\) are powers of the same prime. It suffices to make the following observations: If \((n,c)\) is good and \(d\mid c\), then \((n,d)\) is good, since for each \((d_1,\ldots,d_n)\), we may consider its \((n,c)\)-polynomial \(P\) and restrict its outputs modulo \(d\). If \((n,c)\) is good and \(d\mid n\), then \((d,c)\) is good, since for each \((d_1,\ldots,d_d)\), we may consider the \((n,c)\)-polynomial \(P\) that matches with the \(n\)-tuple \((d_1,\ldots,d_d,\ldots,d_1,\ldots,d_d)\). For primes \(p\ne q\), \((p,q)\) is not good, since for any \((p,q)\)-polynomial \(P\) that is not constant modulo \(q\), by taking repeated finite differences we may find a \((p,q)\)-polynomial \(\tilde P\) that is linear modulo \(q\). However there are no such polynomials. To finish, we show \((n,c)=(p^k,p^\ell)\) is good. In this case, the polynomials \[P_i(x)=\binom{x-i-1}{p^k-1}^\ell\]satisfy \(P_i(i)=1\) and \(P_i(j)=0\) for \(j\not\equiv i\pmod n\). Hence each \((d_1,\ldots,d_n)\) may be modeled by \[P(x)=d_1P_1(x)+\cdots+d_nP_n(x).\]

Mindblowing. Probably the best problem I've ever done. Call a pair winning if the lock can always be opened and losing otherwise. Suppose that $(n,c)$ is losing. Then I claim that $(an,bc)$ is losing as well. Indeed, if the devil stipulates that he will open the lock if $d_a,d_{2a},\ldots,d_{na}$ are all divisible by $c$ and that he will only shift the $d_i$'s by multiples of $a$, this becomes the $(n,c)$ game, which is losing. Thus, to prove that $(n,c)$ is losing if $n,c$ aren't powers of the same prime, it suffices to show that $(p,q)$ is losing where $p \neq q$ are primes. Let the devil truthfully specify that the initial state is a cyclic permutation $(1,0,\ldots,0)$ and also correctly report the state after the player advances the dials but before they're cyclically permuted (so the state before the player advances the dials again is a cyclic permutation of what they were given). Suppose the player can guarantee at any point that they can adjust the dials to all show the same value when they didn't previously. Suppose that the devil reported the dial positions as some cyclic permutation of $d_1,\ldots,d_p$ which are not all the same, and that the player increases dial $i$ by $c_i$. Then we should have $$d_{i+k}+c_i\equiv d_{i+1+k}+c_{i+1} \pmod{q} \implies c_{i+1}-c_i \equiv d_j-d_{j+1} \pmod{q}$$Thus the dial positions should form an arithmetic progression with common difference $c_i-c_{i+1}:=\ell$, but then we should have $d_0 \equiv d_p \equiv d_0+p\ell \pmod{q} \implies \ell \equiv 0 \pmod{q}$, which means that the dial positions were constant: contradiction. I will now prove that $(p^t,p)$ is winning for all primes $p$ and integers $k \geq 1$. We need the following claims. Claim 1: The minimal polynomial $P$ of any $k+1$ consecutive integers can be written in the form $$a_{k}\binom{x}{k}+a_{k-1}\binom{x}{k-1}+\cdots+a_1\binom{x}{1}+a_0\binom{x}{0},$$where $a_k,\ldots,a_0$ are integers. Call this form choosy. Proof: By Lagrange interpolation, the leading coefficient of $P$ times $k!$ is an integer, since for any $0 \leq i \leq k$ we have $$\left|\frac{k!}{\prod_{\substack{0 \leq j \leq k\\j \neq i}}(j-i)}\right|=\frac{k!}{(k-i)!i!}=\binom{k}{i} \in \mathbb{Z}.$$Thus we may subtract an integer multiple of $\tbinom{x}{k}$ from $P$ to make it have degree at most $k-1$ and apply inductive hypothesis on the first $k$ of the $k+1$ consecutive integers. Note that the base case of $k=1$ is trivial. $\blacksquare$ Claim 2: For any $k \leq p^t-1$ we have $$\binom{x+p^t}{k} \equiv \binom{x}{k} \pmod{p}.$$Proof: Lucas' theorem. $\blacksquare$ Thus, every $\mathbb{Z}/p\mathbb{Z}$ sequence $x_0,\ldots,x_{p^t-1}$ can be "modeled" as a choosy polynomial $P$, in the following sense: if we let $\mathbb{Z} \ni y_i \equiv x_i \pmod{p}$ for all $0 \leq i \leq p^t-1$, then let $P$ be the minimal polynomial of $(i,y_i)$ across all $i$ (hence it's choosy by claim 1). Then by claim 2 we find that $P(x+p^t) \equiv P(x) \pmod{p}$ for all $p$, i.e. $P(a) \equiv f(a\%p^t) \pmod{p}$ for all integers $a$, where $\%$ denotes remainder. Call $P$ the representative of $(x_n)$. We are now ready to open the lock for $(p^t,p)$. I claim that, for each $0 \leq d \leq p^t-1$, there exists some procedure $\mathcal{P}_d$ which opens the lock if the representative of the dials has degree at most $d$ and doesn't affect the leading coefficient of $P$ otherwise. Note that the devil's cyclic permuting doesn't change the degree nor leading coefficient of the representative dials. To prove the claim, we use induction on $d$, with the base case of $d=0$ (all dial positions are the same) being simple, simply advance all of the dials by $1$, $p$ times. Now suppose that the dial is degree $d \geq 1$ at some point in time. We advance $d_i$ by $\tbinom{i}{d}$ for each $i$, and then run procedure $P_{d-1}$. Then we repeat this $p$ times in total. Since advancing each $d_i$ by $\tbinom{i}{d}$ increases the $\tbinom{x}{k}$ coefficient of $P$ by $1$ (possibly making it $0$), if $P$ had degree at most $d$ to begin with, it must have at some point had $\tbinom{x}{k}$ coefficient of $0$ after being advanced, hence it was a polynomial of degree at most $d-1$, and performing $\mathcal{P}_{d-1}$ would've opened the lock. If $P$ had degree at least $d+1$, none of these operations will change its leading coefficient, so letting this procedure be $\mathcal{P}_d$ works, as desired. Since $\deg P \leq p^t-1$, we can thus run $\mathcal{P}_{p^t-1}$ and open the lock. We now extend from $(p^t,p)$ to $(p^t,p^\ell)$ by induction on $\ell$, with base case $\ell=1$ already proven. For the inductive step, apply the process that unlocks $(p^t,p^{\ell-1})$. Between each step of this process, perform the process that unlocks $(p^t,p)$, except scaled up by a factor of $p$, so if we were originally increasing a dial by $c$ we now increase it by $cp^{\ell-1}$. Because the scaled process that unlocks $(p^t,p)$ doesn't affect the dials modulo $p^{\ell-1}$, by definition, at some point we end up with all the dials' positions divisible by $p^{\ell-1}$ after a step in the $(p^t,p^{\ell-1})$-unlocking process. At this point, the scaled process that unlocks $(p^t,p)$ by definition will be able to open the lock. This finishes the problem. $\blacksquare$

Probably one of the best problems I've ever done. What downstage does to a person. Don't think anyone has written about motivation so I will yap a bit. The first idea is that you can interleave two procedures $\mathcal{P}, \mathcal{Q}$ applying $\mathcal{Q}$ after each application of $\mathcal{P}$, which is useful if $\mathcal{P}$ guarentees some property and $\mathcal{Q}$ leaves some property unaffected. This is effectively the constructive part of each proof, which inductively shows things are $0$. This allows you to do things like adding $(1, 1, 1, \dots, 1)$ $p$ times every turn to check if you ended up at a dial with all dials equal, or adding $1$ until your dial sum is $0 \pmod{p}$. The case where $c = 2$ can be solved inductively by making sure inductively that the dial at position $x$ and $x + 2^{k-1}$ are all the same, then applying the same combination to the dial at position at $x$ and $x + 2^{k-1}$ to win, and is example of the above interleaving. Then the idea after that is to generalize this to other $c$ that are prime, and higher powers. We then want a property to interleave in the general case, or in other words is preserved under shifts, with some sufficiently nice invariant. This works for divisibility by $(x-1)^t$ in a specific field and also representation as the sum of binomials, which notably both have the case of all dials being equal as the smallest nonsimple equality case!! ($P(x) = 1$ and $P(x) = 1 + x + x^2 + \dots + x^{p^k-1}$ respectively). So it's just interleaving all the way down. We first show the result works for $c = p, n = p^k$. We work in $K = \mathbb{F_p}[x]/ \langle x^{p^k} - 1 \rangle$ which is a field due to being finitely sized. Note that \[ x^{p^k} - 1 \equiv (x - 1)^{p^k} \]by Freshman's dream. Now fix the tuple added to the lock and shift it instead. We then want to show there exists a sequence of polynomials $(P_1, P_2, \dots, P_k)$ in $K$ such that for any choice of $c_1, c_2, \dots, c_k \in \{1, x, x^2, \dots, x^{p-1}\}$ and initial polynomial $Q$, then there exists some $1 \le i \le k$ such that \[ Q + c_1P_1 + c_2P_2 + \dots + c_iP_i = 0. \]or equivalently the LHS is divisible by $(x-1)^{p^k}$. Claim: This is in fact possible. Proof. Define a $r$-procedure $\mathcal{P}_r$ as as series of polynomials $(P_1, P_2, \dots)$ that works if $(x-1)^r \mid Q$ and where $(x-1)^r \mid P_i$. Then we can construct a $r$-procedure as \[ \mathcal{P}_{r+1} = \left((x-1)^r, \mathcal{P}_r, (x-1)^r, \mathcal{P}_r, \dots, (x-1)^r, \mathcal{P}_r\right) \]where there are $p$ repetitions. Note that $\mathcal{P}_r$ doesn't affect the resulting polynomial taken $\pmod{(x-1)^{r+1}}$, and that $c_i (x-1)^r \equiv 1 \pmod{(x-1)^{r+1}}$. As such, if $Q(x) = Q_0(x) \cdot (x-1)^r$, then after $a \equiv -Q_0(1) \pmod{p}$ applications of adding $(x-1)^r$, applying $\mathcal{P}_r$ suffices. We get a base $k-1$-procedure by adding $(x-1)^{p^k-1}$ repeatedly, which then inductively gives us a procedure $\mathcal{P}$. $\blacksquare$ Claim: This remains true when $n$ is a power of $p$. Proof. Induct on the exponent of $n$ with corresponding procedure $\mathcal{Q}_1$ as our base case by the above. If $\mathcal{Q}_1 = (q_1, q_2, \dots, q_n)$ Then we define \[ \mathcal{Q}_{i+1} = \left(q_1, p\mathcal{Q}_i, q_2, p\mathcal{Q}_i, \dots, q_n, p\mathcal{Q}_i\right) \]Then each $p \mathcal{Q_i}$ doesn't affect the resulting tuple taken $\pmod{p}$. As such, after some applications $\left(q_1, p\mathcal{Q_i}, q_2, p\mathcal{Q_i}, \dots, q_k\right)$, the polynomial is $0 \pmod{p}$ in each dial. Then applying $p\mathcal{Q_i}$ suffices. $\blacksquare$ If $c = 1$ then this becomes trivial, so assume not. We now show impossibility when $n \ne p^k, c = p$. Note that, taken over $K = \mathcal{F}_p/ \langle x^n - 1 \rangle$, \[ (x-1)^n \ne x^n - 1. \]This means that there exists some $a$ such that $(x-1)^n = (x-1)^a \cdot P(x)$ for some $P(1) \ne 0$. Claim: If $P \mid (x-1) \cdot Q$ for $P(1) \ne 0$, then $P \mid Q$ over $K$. Proof. Note that this implies $(x-1) P \mid (x-1) \cdot Q$, then cancel out $x-1$. $\blacksquare$ We now show that no procedure $(P_1, P_2, \dots, P_k)$ can ever guarantee that $P(x)$ divides the resulting polynomial. Suppose it does not hold initially for some polynomial $Q$ and we now add $c_i R(x)$. If $P(x) \mid R(x)$, then it does not hold for the resulting $Q(x) + R(x)$ either. If $P(x) \nmid R(x)$, then note that one of $Q(x) + R(x) \not\equiv Q(x) + xR(x)$ can't be divisible by $P(x)$, as \[ P(x) \mid Q(x) + xR(x), Q(x) + R(x) \implies P(x) \mid (x-1) \cdot R(x) \implies P(x) \mid R(x). \]Repeating this for each addition $R(x)$, we get the result.