There are $n$ cards such that for each $i=1,2, \cdots n$, there are exactly one card labeled $i$. Initially the cards are piled with increasing order from top to bottom. There are two operations: $A$ : One can take the top card of the pile and move it to the bottom; $B$ : One can remove the top card from the pile. The operation $ABBABBABBABB \cdots $ is repeated until only one card gets left. Let $L(n)$ be the labeled number on the final pile. Find all integers $k$ such that $L(3k)=k$.
Problem
Source: 2019 FKMO Problem 1
Tags: combinatorics
lminsl
23.03.2019 15:55
This was quite disappointing; the problem was NOT original(+and also so well-known); and requires dirty case-working.
MNJ2357
23.03.2019 16:40
RIPPPPPPP Did anyone know that there's an explicit form for this?
Pathological
23.03.2019 20:09
There are three families of solutions. Firstly, $k= 1$ is a solution. Now let's define the two sequences $\{a_i\}, \{b_i\}$ by $a_1 = 1, b_1 = 4$ and $a_{i+1} = 729a_i - 104, b_{i+1} = 729b_i - 104.$ Then we claim that all solutions are $k = 1, k = 243 a_i - 35,$ and $k = 243b_i - 35,$ for any $i \in \mathbb{N}.$
To do this, let's define the set $S(P(k), Q(k))$ for two linear functions $P, Q$ in $k$ as the set of positive integers $k$ for which $P(k) \geq Q(k) > 0$ and if we apply the operation on $1, 2, \cdots, P(k)$, the last remaining card is $Q(k).$ Then we are asked to find $S(3k, k).$
Observe that:
If $k$ is in $S(3k, k)$, then either $k = 1$ or $\frac{k-1}{3}$ is in $S(3k+1, k+1).$
If $k$ is in $S(3k+1, k+1)$, then $\frac{k}{3}$ is in $S(3k+1, k+2).$
If $k$ is in $S(3k+1, k+2),$ then $\frac{k+1}{3}$ is in $S(3k, k+2).$
If $k$ is in $S(3k, k+2)$, then $\frac{k-2}{3}$ is in $S(3k+2, k+2).$
If $k$ is in $S(3k+2, k+2)$, then $\frac{k+1}{3}$ is in $S(3k+1, k+3).$
If $k$ is in $S(3k+1, k+3)$, then either $k = 1$ or $\frac{k-1}{3}$ is in $S(3k+2, k+3).$
If $k$ is in $S(3k+2, k+3)$, then either $k = 1$ or $\frac{k+2}{3}$ is in $S(3k, k+3).$
If $k$ is in $S(3k, k+3),$ then $\frac{k-1}{3}$ is in $S(3k+1, k+2).$
But we've already analyzed the case where $k$ is in $S(3k+1, k+2)$ above, so since it is periodic, we can now easily find all solutions with nasty caseworking.
$\square$
Checking would be appreciated
DragonFire1024
26.08.2019 07:18
The explicit forms are $\frac{3^{6x + 2} - 2}7, \frac{2\cdot 3^{6x} - 2}7$. The way you arrive at this is you remove enough cards until you have a power of $3$ left, say $3^x$, which will always happen on your first pass. Then the final card depends on where you are in the ``ABB'' sequence. If you are at A, then the card you're currently on will be the last card. If you're on the 2nd B, then the last card will be the card you're on and going right (wrapping around) until you've encountered $\frac{3^x - 1}2$ more cards, and finally if you're on the last B the last card remaining will be the card after goin $3^x - 1$ cards around. You do casework and you arrive at these solutions.
duongbgbg32
12.10.2020 15:59
Firstly, we will find all $n \ge 3$ such that $L(n)=1$. We call a "screen" is a series of act $$ABBABB \dots ABB$$such that the card of number 1 return on the top of the deck. Because on the first, the card of number 1 lies on the top so if $n$ doesn't divide 3, the anothers is not the card of number 1. Moreover, after a "screen" the number of card becomes $\frac{n}{3} \ge 1$. If $\frac{n}{3} =1,2$, the last card is the card of number 1. And if $\frac{n}{3} \ge 3$, we will have a next "screen". Continue the series, we have $$ L(n)=1 \Leftrightarrow n=3^j,n=2.3^j .$$(*) Return the problem Let $k$ such that $L(3k)=k$, after $k-$ acts the card of number $k$ will the card on the top of the deck. Moreover, the act $k-2,k-1$ must be $B,B$ ( the act $k$ must be $A$). Otherwise, $k$ is the card which is wasted. So 3 is the divisor of $k-1$. After $k-1$ acts, The another number of the card is $$ \frac{k-1}{3} +2k+1=\frac{7k+2}{3}$$( k is the last card ) Let numbered for the deck, and $k$ becomes $1$. Apply the result (*), we have $$ k=\frac{3^{6 j+2}-2}{7} \text { for all } j \geq 0 ; k=\frac{2 \cdot 3^{6 j}-2}{7} \text { for all } j \geq 1 $$