Why "please"?

Just translating The original problem uses "請問...", which is the polite way of beginning a question in Chinese.

Do they choose $A_1,B_2,...$ in order or can the resulting number be a permutation?

The numbers are chosen in order. (Edited to clarify.)

I thought we have English version in TST?? 我們有英文版的題目吧??

maybe. 可能有喔(?)

I think so? 我想應該有吧？

It might be a bug. 可能是爸個吧。

YaWNeeT wrote: I thought we have English version in TST?? Yeah, these are not the official translations. I happened to be travelling at the time with only access to the Chinese versions, so I just translated the problems myself. USJL wrote: 可能是爸個吧。 T_T

Since this seems a bit silly, can someone check this... Consider the group $(\mathbb{Z}/10^7 \mathbb{Z})^*$. I claim that $x \rightarrow x^7$ for $x \in (\mathbb{Z}/10^7 \mathbb{Z})^*$ is a bijection. If $x^7-y^7 \equiv 0 \pmod{10^7}$, then $\text{ord}_{10^7}(x/y) | 7$. But the order also divides $\phi(10^7)$, which is relatively prime with $7$. So the order in fact equals $1 \implies x \equiv y \pmod{10^7}$. So in fact, if a the 7-digit number is neither a multiple of $2$ or $5$, it's the last 7 digits of some perfect seventh power. So Alice just wants $A_7 = 1, 3, 7, 9$. Since Bob only chooses 3 numbers, Alice can also make the last digits one of those, so she wins.

We claim that if $A_7$ is one of $1,3,7,9$ then there is a integer $n$ such that $n^7 \equiv \overline{A_1B_2A_3B_4A_6B_6A_7}\ (mod \ 10^7)$.Hence Alice will choose one of $1,3,7,9$ as $A_7$ and win. Note that any number of the form $\overline{A_1B_2A_3B_4A_6B_6A_7}$ where $A_7=1,3,7 or\ 9$ is coprime with $10^7$ Call a number of this form $y$. CLAIM:There is an integer $m$ such that $m^7\equiv y (mod\ 5^7)$. Let $r$ be a primitive root mod $5^7$.As $gcd\ (y,5^7)=1$ so there exists integer $b$such that $r^b\equiv y (mod\ 5^7)$ .Now as $r^{\phi(5^7)}\equiv 1 (mod\ 5^7)$ take integer $x$ such that $\phi(5^7)x+b\equiv 0 (mod\ 7)$.[This x indeed exists.if $7|b$ then take $x$ so that $7|x$ otherwise $gcd\ (7,b)=1$ solution of the linear congruence exists].Now $r^{\phi(5^7)x+b}\equiv r^{\phi(5^7)x}.r^b\equiv 1.y=y (mod\ 5^7)$. $\blacksquare$ In the same way there is integer $s$ such that $s^7\equiv y (mod\ 2^7)$.$\blacksquare$ Now there is an integer $z$ such that $z\equiv m (mod\ 5^7)$ and $ z\equiv s (mod\ 2^7)$ by CRT.So we get $z^7\equiv m^7\equiv y (mod\ 5^7)$ $z^7\equiv s^7\equiv y (mod\ 2^7)$. So $z^7\equiv y (mod\ 10^7)$.We are done.$\blacksquare$

You could use $\pmod{x}$ to say $\pmod{x}$

wait what In fact, Alice only needs to pick an odd $A_7$ and she wins. It suffices to show that for any odd integer $k$, we can find some $n$ such that $n^7 \equiv k \pmod{2^7}$ and can also find some $n$ such that $n^7 \equiv k \pmod{5^7}$, and we'll be done by chinese remainder theorem. Take a primitive root $g \pmod{5^7}$, and let $a$ be such that $g^a \equiv k \pmod{5^7}$. Then we can just pick some $t$ such that $a+t \varphi(5^7) \equiv 0 \pmod{7}$ (which is possible because $\varphi(5^7) \not\equiv 0 \pmod{7}$) and then take $n=g^{(a+t \varphi(5^7))/7}$, which will satisfy $n^7 \equiv k \pmod{5^7}$. Now we show that $\{1^7, 3^7, \dots , 127^7 \}$ are equivalent to $\{ 1, 3, \dots , 127 \}$ when taken $\pmod{2^7}$. Assume for contradiction there were odd $a \neq b$ such that $a^7 \equiv b^7 \pmod{2^7}$, and let $m = a \cdot b^{-1} \not\equiv 1 \pmod{2^7}$. Then since $m^7 \equiv 1 \pmod{2^7}$ the order of $m \pmod{p}$ must be $7$, which is a contradiction since $\varphi(2^7) \not\equiv 0 \pmod{7}$ and we're done.

Stormersyle wrote: what the heck is this problem lmao Let $S$ be the set of residues mod $10^7$ that are prime to 10. Since $7\nmid \phi(10^7)$, we see $\{x^7 \pmod{10^7} |x\in S\}=S$, so thus Alice can just choose the last digit as 1 and she wins. It's not hard to fix this issue, but your proof breaks if Bob selects 1 before Alice does.

Note that the units mod $10^7$, a.k.a $U_{10^7}$ gets sent back to itself under the operation $x\rightarrow x^7$ because $\gcd(7,\varphi(10^7)=1$. Thus, as long as the number ends with $S=\{1,3,7,9\}$ then it will be a seventh power residue. Thus, Alice's strategy is to avoid these four, picking in order $\{2,4,5,6,8,10\}$, thus making it so that Bob can only force 3/4 of the elements of $S$ to be chosen , so Alice will always have a digit available to pick so that she can win.

Assuming Alice moves first, she has the winning strategy. The crux of this problem is the following claim: Claim: Any $n$ with $\gcd(n,10)=1$ is congruent to a seventh power modulo $10^7$. Proof: Clearly it suffices to prove that $k^7$ is distinct modulo $10^7$ as $k$ ranges over every mod-$10^7$ residue not divisible by $2$ or $5$, since $\gcd(k,10)=1 \iff \gcd(k^7,10)=1$. By CRT it suffices to prove this for $2^7$ and $5^7$. Suppose that we have $a^7 \equiv b^7 \pmod{2^7}$, but $a \not \equiv b \pmod{2^7}$. The former condition arranges to $(\tfrac{a}{b})^7 \equiv 1 \pmod{2^7}$. Since $a \not \equiv b \pmod{2^7}$, it follows that $\mathrm{ord}_p(\tfrac{a}{b})=7$. But then we require $7 \mid \varphi(2^7)=2^6$, which is absurd. Likewise, for the $5^7$ case we arrive at $7 \mid \varphi(5^7)=5^6$, which is also impossible, yielding the desired result. $\blacksquare$ Now we describe Alice's winning strategy. For her first 3 moves, she picks either an even digit or $5$ (which is always possible). For her final move, she picks a digit in $S=\{1,3,7,9\}$. This is always possible, since Alice will never pick anything in $S$ for her first 3 moves, and therefore at most 3 of the elements of $S$ are chosen. Then, the resuting seven-digit number $N$ has $\gcd(N,10)=1$, so by our claim $N$ is congruent to a seventh power $\pmod{10^7}$, and thus is equal to the last $7$ digits of some seventh power. $\blacksquare$

Alice has the winning strategy. Claim: Any positive integer $n$ relatively prime to $10$ is a perfect seventh power $\pmod{10^7}$. Proof: Suppose not. Then there exist distinct $a,b<10^7$ such that both $a$ and $b$ are relatively prime to $10$ and $10^7 \mid a^7 - b^7$. However, by LTE, we have $\nu_2(a^7 - b^7) = \nu_2(a-b)$ and $\nu_5(a^7 - b^7) = \nu_5(a-b)$. This implies $a\equiv b\pmod{10^7}$, contradiction. $\square$ Clearly Alice can choose $A_7\in \{1,3,7,9\}$, no matter what $B_2, B_4, B_6$ are. Then $\overline{A_1B_2A_3B_4A_5B_6A_7}$ is a perfect seventh power $\pmod{10^7}$ since it is relatively prime to $10$, done.

Alice wins. Claim. Seventh powers are surjective modulo $10^7$. Proof. Suffices to show the conclusion modulo $5^7$ and $2^7$. But the case is obviously true for $p = 2, 5$, so we can just use LTE. Thus Alice wins by just choosing her last digit in $\{1, 3, 7, 9\}$.

never cook again ... I claim that Alice wins. Claim: Any number $n$ with $\gcd(n, 10^7) = 1$ is a $7$th power $\pmod{10^7}$. Proof. By CRT, it suffices to show that $2^7$ and $5^7$ satisfy this property - this is clear for $5^7$ by the existence of primitive roots $\pmod{5^7}$ and the fact that $\gcd(7, \phi(5^7)) = 1$. Hence it suffices to show that $a^7 \equiv b^7 \pmod{2^7}$ is impossible for odd $a$, $b$ - but this is clear by assuming FTSOC that $a$, $b$ exist noting that $m \equiv \frac{a}{b} \pmod{2^7}$ has order $7$, contradiction. Now Alice's strategy is clear - pick only even digits and $5$, so Bob can disallow at most $3$ of the digits $\{1, 3, 7, 9\}$ - Alice just chooses the final digit to be the one Bob missed, done.

How sobad. Solved with encouragement from PikaPika007. Claim: Any residue $r$ relatively prime to $10$ is a seventh power residue modulo $10^7$. Proof. Analyze modulo $2^7$ and $5^7$. Assume that for odd $x \neq y \pmod{2^7}$ yet we find $x^7 \equiv y^7 \pmod{2^7}$. Then we rearrange to find, \begin{align*} \left( \frac{x}{y} \right)^7 \equiv 1 \pmod{2^7} \end{align*}However this implies that $\text{ord}_{2^7}\left(\frac{x}{y} \right) \mid \gcd(7, \phi(2^7)) = 1$. Then $x \equiv y \pmod{2^7}$, contradiction. We may do a similar thing for $5^7$. Then by CRT we may string together numbers to form some seventh power congruent to any residue $r$ relatively prime to $10$, modulo $10^7$. $\square$ Now this implies that any number ending in $1$, $3$, $7$ or $9$ is good. Then Alice can choose even numbers for each of her turns and then finish with one of the above numbers, ensuring her victory. Remarks: The first idea I had right off the bat was we want to characterize all seventh powers modulo $10^7$, in hopes of giving a winning strategy to Alice. However, the main issue is that I had no idea how to prove it. Then we do the dumb thing of ignoring all residues that are not relatively prime with $10$ because those behave nicely. Apparently that is enough :skull:

We are going to prove every seven power residue relative prime to $10$ in $\pmod{10^7}$ goes to every other residue relative prime to $10$ in $\pmod{10^7}$, so if she makes a number $N$ with $\gcd(N,10)=1$ it´s in fact, a seven power $\pmod {10^7}$. To prove this it suffices to show that if $a^7\equiv b^7\pmod {10^7}$ then $a\equiv b\pmod {10^7}$, by Chinese Residue Theorem it suffices to prove the result for $2^7$ and $5^7$ From $a^7\equiv b^7$ we get $\left(\frac{a}{b}\right)^7\equiv 1\pmod {2^7}$ so $\operatorname{Ord}_{2^7}\left(\frac{a}{b}\right)\mid \gcd(7,\phi(2^7))=1$ so $a\equiv b\pmod {2^7}$ anagously we get the result for $5^7$ and we are done So, Alice can win if and only if she can make the seven digit number $N$ to have $\gcd(N,10)=1$ so the strategy is that she choose a number not in$\{1,3,7,9\}$ and in the last turn she choose a number in $\{1,3,7,9\}$

The majority of this proof is the following claim: Claim: If a number $n$ is coprime to $10^7$, there is some integer value of $k$ such that $k^7 \equiv n \pmod{10^7}$. In other words, $n$ can be represented as the last seven digits of some seventh power. Proof: Let $x_1, x_2, \dots, x_n$ be the residues modulo $10^7$ that are relatively prime to $10^7$. Suppose that there is some $x_i$ and $x_j$ with $i \neq j$, such that $x_i^7 \equiv x_j^7 \pmod{10^7}$. In particular, $x_i^7 \equiv x_j^7 \pmod{10}$, which implies $x_i \equiv x_j \pmod{10}$ (since $n^7 \equiv x \pmod{10}$ for odd $n$). Then, note \[\frac{x_i^7-x_j^7}{x_i-x_j} = x_i^6+x_i^5x_j+\dots+x_j^6 \equiv 7x_i^6 \pmod{10}.\] Since $7x_i^6$ doesn't share any factors with $10$, if $x_i^7-x_j^7$ is divisible by $10^7$, so must $x_i-x_j$, which is impossible. Hence, the set of $x_i^7$ are all distinct, but this means it must coincide with the set of $x_i$. $\square$ At this point, Alice wins by selecting three numbers not in the set $\{1,3,7,9\}$. Bob can only select three of those numbers in that set, and once $A_7 \in \{1,3,7,9\}$, the resulting seven-digit number is relatively prime to $10^7$, so we are done. $\square$

We claim the mapping $k \mapsto k^7$ is injective modulo $10^7$, where $\gcd(x,10)=1$. Suppose there exists integers $a$, $b$ both relatively prime to 10 such that $a^7 \equiv b^7 \pmod{10^7}$. Looking at just modulo 10, we find \[a \equiv b \pmod{10} \implies 0 \equiv a^7 - b^7 \equiv (a-b)(7a^7) \pmod{10^7} \implies a \equiv b \pmod{10^7},\] concluding injectivity. A bijection follows, telling us every residue relatively prime to 10 is a septic residue modulo $10^7$. Thus Alice is able to select $A_7 \in \{1,3,5,7\}$ as Bob only has 3 moves, so $\boxed{\text{Alice}}$ is always able to pick a septic residue. $\blacksquare$

Highkey really cool I claim that Alice can always force a win. She can do this by choosing the last digit to be one of the four digits $1$, $3$, $7$, $9$, which she must be able to do. This is because Bob has three turns before her, meaning that he can take at most three of these numbers. Therefore, if Alice chooses digits not from this set of four numbers for all of her previous turns, she will always have at least one left for the last digit. Now I will prove why this strategy always works. Notice that by choosing the last digit to be $1$, $3$, $7$, or $9$, we ensure that the large $7$-digit number is not a multiple of $2$ or $5$. I will now prove that Alice always wins if she forces the number to not be a multiple of $2$ or $5$ by proving the following claim. 1. All $7$-digit numbers not divisible by $2$ or $5$ are valid modulos mod $10^7$ of some number $x^7$. I will prove this claim by splitting this claim into two subclaims - one mod $2^7$ and one mod $5^7$. 1a. For any two odd numbers $a$ and $b$, $a^7\equiv b^7\mod 2^7 \iff a\equiv b \mod 2^7$. Note that proving this claim is equivalent to proving the claim that all odd modulos mod $2^7$ are feasible modulos of powers of seven mod $2^7$ (i.e. $\forall x$ s.t. $x$ is odd, $\exists y$ such that $y^7\equiv x\mod 2^7$). Now, note that we have \[a^7-b^7=(a-b)(a^6+a^5b+a^4b^2+a^3b^3+a^2b^4+ab^5+b^6),\]and since $a$, $b$ are odd, the latter term must be odd. This gives that \[\nu_2(a^7-b^7)=\nu_2(a-b),\]which is $<7$ if $a$ and $b$ are not the same modulo $2^7$. Therefore we have that \[a^7\equiv b^7\mod 2^7 \iff a\equiv b \mod 2^7,\]proving our first subclaim. 1b. For any two numbers $a$ and $b$ not divisible by $5$, $a^7\equiv b^7\mod 5^7 \iff a\equiv b \mod 5^7$. Again similarly, note that proving this claim is equivalent to proving the claim that all modulos not divisible by $5$ mod $5^7$ are feasible modulos of powers of seven mod $5^7$ (i.e. $\forall x$ s.t. $x$ is not a multiple of $5$, $\exists y$ such that $y^7\equiv x\mod 5^7$). FTSOC, assume that there do exist $a$, $b$ not divisible by $5$ such that $5^7|a^7-b^7$, but $a$ and $b$ are not equivalent mod $5^7$. Note that since all mod $5$'s give different mod $5$'s when taken to the power of $7$ (prove this by taking $1^7$, $\dots$, $4^7$ mod $5$, they give $1$, $3$, $2$, and $4$, respectively), this implies that if $5^7|a^7-b^7$, then $5\mid a-b$. Now using LTE (because now that we know $5\mid a-b$, LTE conditions are satisfied), we get that \[\nu_5(a^7-b^7)=\nu_5(a-b)+\nu_5(7)=\nu_5(a-b)<7,\]since $a$ and $b$ are not congruent modulo $5^7$. This is contradiction, since we assumed that $5^7|a^7-b^7$, meaning that $\nu_5(a^7-b^7)\geq 7$. Therefore for any two numbers $a$ and $b$ not divisible by $5$, we have that \[a^7\equiv b^7\mod 5^7 \iff a\equiv b \mod 5^7,\]proving our second subclaim. Finally, by CRT, this means that all modulos mod $10^7$ that are not multiples of $2$ or $5$ are feasible modulos of powers of seven mod $10^7$ (i.e. $\forall x$ s.t. $x$ is not a multiple of $2$ or $5$, $\exists y$ such that $y^7\equiv x\mod 10^7$). Therefore, if Alice chooses the last digit to be one of the four digits $1$, $3$, $7$, $9$, she can ensure that the $7$-digit number is neither a multiple of $2$ or $5$. Combining this with claim (1), we conclude that Alice can always win, finishing the problem.

bit of an overkill but here goes nothing: consider the group $G$ of elements of $\mathbb{F}_{10^7}$, that are coprime to 10, under multiplication Clearly $|G|= \phi(10^7)$ and we have that $gcd(7,\phi(10^7)) =1$ hence we have that the function $$f:G \longrightarrow G \mid f(x)=x^7$$is a bijection and hence Alice just makes $A_7$ one of $\{1,3,7,9\}$ and that number will be a perfect 7th power.

Suppose two numbers $x$ and $y$ such that $x^7 \equiv y^7(mod \ 10^7)$, then $[ {\frac{x}{y}}]^7 \equiv 1(mod \ 10^7)$ implying $x$ and $y$ are coprime and $\frac{x}{y}$ is coprime to $10$. This implies $7$ divides $\phi(10^7)$ or $x \equiv y$ of which the former is untrue so the latter must hold. Hence all $7$th powers not divisible by $2$ or $5$ are attainable, hence the player who goes last wins.

I claim that Alice has a winning strategy. By Gauss, there exists a primitive root $g$ modulo $2^7$ with order $\phi(2^7) = 64$. Since $\gcd(7, 64) = 1$, we find that $\{1, g^7, g^{2 \cdot 7}, \ldots, g^{63 \cdot 7}\}$ is a permutation of $\{1, g, g^2, \ldots, g^{63}\}$ modulo $2^7$. The latter is the set of all odd residues modulo $2^7$, so we find that all odd residues are seventh powers modulo $2^7$. Similarly, since $\gcd(\phi(5^7), 7) = \gcd(5^6 \cdot 4, 7) = 1$, we find that all residues modulo $5^7$ which are not multiples of $5$ are seventh powers. Thus, by CRT, all residues coprime to $10$ modulo $10^7$ are seventh powers; these are precisely those ending in $1, 3, 7$, or $9$. Since at least one of $\{1, 3, 7, 9\}$ must be left for Alice to pick as $A_7$, Alice can guarantee the win.