Guess the Permutation

Question

Let $p$ be a prime. I chose a secret permutation $a_0,a_1,...,a_{p-1}$ of $0,1,...,p-1$ unknown to you. Now, you can ask the following types of questions to me:

• Type $1$: Tell me two integers $i,j$ where $0\le i,j\le p-1$. I will then tell you the $k$ such that $a_k\equiv a_i+a_j\pmod p$.
• Type $2$: Tell me two integers $i,j$ where $0\le i,j\le p-1$. I will then tell you the $k$ such that $a_k\equiv a_ia_j\pmod p$.

You may ask at most $p-1$ questions. Show that you have a strategy to determine the correct permutation after asking the questions.

---

Since this is asked in the comments, I now clarify that $i$ can equal $j$.

---

Bonus: Can you achieve a lower number of questions? This means determine the minimal number of questions you need to determine the answer in the worst case with proof. I suspect this is hard, so there will be at least +50 bounty for this (and possibly for people with nontrivial bounds)

---

Problem made by me.

Answer 1

Somewhat surprisingly there is a relatively simple method that does not identify 1 until the very end.

Start by asking a "+" question: $a+b$. Since they cannot both be zero we assume wlog $a \ne 0$. We now successively ask for $a+(ka)$ at $k=1,2,3,...$ until either (1) the outcome $(k+1)a=b$ in which case we skip the next question because we have already asked it and proceed all the way up to $k=p-2$ or (2) we reach $k=p-3$ without ever encountering $b$. At this point only $(p-1)a$ and $0$ are unidentified (because $p$ being prime $a$ cannot be a proper divisor, so the answers we have received must all be distinct). But the first answer tells us which of the two is $b$. In either case we have used a total of $p-2$ questions to obtain a complete list of all the multiples of $a$. (The list contains every number 0,...,p-1 as a result because $p$ is prime.) With the last question we can ask for $aa$, look that value up in our list and read off the corresponding $k$ which must equal $a$. Knowing the value of $a$ and the identities of all its multiples we are done.

Answer 2

A bit of terminology:

Let's say that $(i, j)$ points to $k$ if the answer to a question with input $(i, j)$ is $k$, i.e. $a_i + a_j = a_k$ or $a_i a_j = a_k \bmod p$. The type of the question depends on context. Also, let's say that $(i, j)$ points to itself if $k = i$ or $k = j$. Every equation is assumed to be $\bmod p$.

$p = 2$

Ask Type 1 $(0, 1)$. If it points to $0$, $a_1 = 0$ and $a_0 = 1$. Otherwise, $a_0 = 0$ and $a_1 = 1$.

$p = 3$

Ask Type 1 $(0, 1)$. If it points to $2$, $a_2 = 0$. Otherwise, it points to $0$ or $1$, which implies $a_1 = 0$ or $a_0 = 0$ respectively. Since we know where 0 is, we can now ask Type 2 with other two indices, which will reveal the position of 2.

Partial answer for $p \ge 5$

The following strategy almost works, but uses exactly $p$ questions in the worst case.

Step 1:

The strategy starts by finding the positions of 1 and 0. First ask $\frac{p-1}{2}$ Type 2 questions with the pairs $(0, 1)$, $(2, 3)$, ..., $(p-3, p-2)$, and check which of the pairs point to itself. If $a_i a_j = a_i$, either $a_i = 0$ or $a_j = 1$. Since 0 and 1 can be in two different pairs, in the same pair, or only one of them in a pair and the other at $a_{p-1}$, we can observe two cases.

Step 1, case 1:

Only one pair points to itself. Without loss of generality, let's say $a_0 a_1 = a_0$. Then there are three possibilities:

• $a_0 = 0, a_1 = 1$
• $a_0 = 0, a_{p-1} = 1$
• $a_{p-1} = 0, a_1 = 1$

Now we can differentiate the three cases by seeing if $a_{p-1}$ is 0, 1, or something else. To achieve that, we ask a Type 2 question with $(2, p-1)$. Note that $a_2$ is guaranteed to be neither 0 nor 1. If it points to $2$, $a_{p-1} = 1$; if it points to $p-1$, $a_{p-1} = 0$; otherwise, $a_{p-1} \ge 2$.

In the worst case, we have $\frac{p-1}{2} - 1$ unused equations in the form of $a_i a_j = a_k$.

Step 1, case 2:

Two pairs point to themselves. Without loss of generality, let's say $a_0 a_1 = a_0$ and $a_2 a_3 = a_2$. Since one of the pairs contains 0 and the other contains 1, there are only two possibilities:

• $a_0 = 0, a_3 = 1$
• $a_2 = 0, a_1 = 1$

There are many ways to differentiate between the two with 1 extra question. In the worst case, In the worst case, we have $\frac{p-1}{2} - 2$ unused equations in the form of $a_i a_j = a_k$.

Let's write $a^{-1}_{x} = i$ if $a_i = x$, i.e. $a^{-1}_{x}$ is the index of $x$ in the hidden permutation. At this point, we know $a^{-1}_{0}$ and $a^{-1}_{1}$.

Step 2:

Now that we know $a^{-1}_{1}$, we can ask a series of Type 1 questions: $(a^{-1}_{1}, a^{-1}_{1})$ to find $a^{-1}_{2}$, $(a^{-1}_{1}, a^{-1}_{2})$ to find $a^{-1}_{3}$, and so on. We don't need to ask where $p-1$ is, so this will take $p-3$ questions. But this is way too many questions (in addition to $\frac{p+1}{2}$ questions asked in Step 1), and disregards potential information gained from Step 1 questions.

Note that we have at least $\frac{p-1}{2} - 2$ equations of the form $a_i a_j = a_k$, where $a_i, a_j \ge 2$, $a_k \ge 1$, and $a_i \neq a_j \neq a_k \neq a_i$. When we know two of the values, we can always compute the third, since it is possible to "divide" both sides of $ax = b$ by $a$ to get an integer solution $x = a^{-1} b \bmod p$.

Also note that the equations' left-side variables are pairwise disjoint. I claim that the equations are linearly independent. If we view $(a_{2k}, a_{2k+1})$ as a single node labeled $k$ and the equation $a_{2k} a_{2k+1} = a_{2m}$ (or $a_{2m+1}$) as an edge connecting $k$ and $m$, the graph is an undirected functional graph, whose connected components contain a single cycle and cycle-free branches going out of it. If a dependent set of equations exist, those must precisely consist of the cycle. And it is also clear that a cycle is not dependent, since one of two variables in a node appears only once in the entire cycle.

In addition, there is an implicit equation that (product of all variables) equals $p-1$. I believe this equation is independent to the equations from Step 1 questions, but I'm not entirely sure how to prove this. This is a good news and a bad news. Good news: we can be certain that adding precisely $(p-2) - ((\frac{p-1}{2} - 2) + 1) = \frac{p-1}{2}$ known values to the system will solve all variables. Bad news: we have zero chance that we will save a question by revealing exactly $p-3$ values. So this will cost us $\frac{p+1}{2} + \frac{p-1}{2} = p$ questions in total in the worst case.

How to achieve that bound: As in the naive strategy, use Type 1 questions involving adding 1 to a known value. Whenever a known value is added to the system, see if some equation has two known values, and if so, solve the third variable. When asking the next question, skip $a^{-1}_{k}$ if $a^{-1}_{k+1}$ is already known. This ensures that a "fresh" information is added by each question.

Answer 3

Disclaimer: $p>3$ is very closely inspired by @Albert.Lang's solution. The $p=2,3$ solutions are just rehashes of @Bubbler's. This can be Community Wiki if appropriate.

Imagine a row of $p$ boxes and we're trying to locate the numbers $0,\dots, p-1$. At first, we may put letters (variables) in the boxes. But the goal is to find what these letters stand for.

For brevity, different letters (variables) are in different boxes and are initialised arbitrarily unless otherwise stated. All arithmetic is $\text{mod } p$.

For $p=2$,

ask $a+b$. If the outcome is $a$, then $b=0$, else $a=0$.

For $p=3$,

ask $a+b$. Outcomes: if $c$, then $c=0$; if $a$, then $b=0$, if $b$, then $a=0$. In any case, let $x, y \neq 0$ and ask $xy$, so the outcome is $1\times 2 = 2$.

For $p>3$,

ask the first question $a+a$. If the outcome, $b$, is not $a$, then $a\neq 0$.

If $a\neq 0$, then repeatedly ask for ($a\ +$ the previous outcome) to locate $ka$ for $2\leq k\leq p-1$, using $p-2$ total questions (including the first question). Then the element we haven't encountered is $0 = pa$.

If $a=0$ then choose a different $a$ and locate $ka$ for $2\le k \le p-2$, using $1+(p-3)=p-2$ total questions. Then the element we haven't encountered is $(p-1)a$.

Ask the last question $aa$ and locate the answer in the boxes: if the outcome is $na$, then $aa=na$, which, combined with $a\neq 0$, means $a=n$. Since we know where $kn$ is located for all $k=2,3,\dots,p$, we are done.