# Shuffling Cards (with a flip)

*Achyut Bharadwaj*

##### April 2023

## Introduction–The Shuffling Problem #

Card shuffling is an important part of playing any card game. When a card deck isn’t shuffled properly, it leads to uneven and unfair distribution of cards. It would certainly help if you knew what cards other players had!

Suppose we have a specified shuffling algorithm. Is it possible for us to guess the outcome of the card shuffling? Is it possible that the card deck will at some point return to its original configuration? In a previous article we explored ways of trying to guess the outcome of a specific type of card shuffling, known as the riffle shuffle. In this article, we modify the shuffling algorithm to introduce a flip that introduces some interesting complexities.

### The Standard Problem #

We may define a riffle shuffle, for a deck of an even number of cards, as a shuffle carried out by performing the following steps.

Split the card deck into two equal halves

Put the top half of the deck to the left and the bottom half of it to the right.

Take a card from the top of the deck on the left and put it down on the table

Take a card from the top of the deck on the right and put this card

**below**the card that is already on the tableRepeat.

A well-known problem is: How many riffle shuffles will it take for the deck of $m$ cards to return to its original position? It turns out that the answer is the order of $2$ modulo $m$. Another problem that must in fact be answered in order to answer the previous question is: Given the current position of a card, what will be its position after a single riffle shuffle is performed? It turns out, that if we label the positions of the cards from $0$ to $m-1$, then the position of a card with current position $k$ after a single shuffle will be $2k \mod{m-1}$.

### A Modification of the Problem #

A modification of the problem is as follows: While you are performing the riffle shuffle, suppose instead of putting down the cards as they are, you flip the cards from the right deck. Now, how many shuffles will it take for all cards in the deck to return to their original positions? What about the number of shuffles after which all cards will return to their original flip configuration? What is the relation between these two?

## Visualizing the Process #

We shall start with visualizing the process of shuffling cards as described in the previous section. Let us start with an example of a deck of $8$ cards. Each card in the deck is unique. Initially, let the cards in the deck be labelled from $A$ to $H$ and be in alphabetical order. If a card $X$ is flipped, we shall denote it by the corresponding lower case letter $x$. So, the deck initially looks like as follows: $$\begin{matrix} A \\ B \\ C \\ D \\ E \\ F \\ G \\ H \end{matrix}$$ Let us now shuffle the deck. By our definition of a shuffle, we split the deck into two equal halves, and place the top half of the deck to the left and the bottom half deck to the right: $$\begin{matrix} A & E \\ B & F \\ C & G \\ D & H \end{matrix}$$

Now, as described before, we first put the card at the top of the left
deck, $A$. Next, we take the card on top of the right deck, flip it
over, and put it below card $A$. So we will have $e$ below $A$. We
continue to repeat this process. Doing so, we finally get the following
deck: $$\begin{matrix}
A \\
e \\
B \\
f \\
C \\
g \\
D \\
h
\end{matrix}$$ Notice that, as before the position of each card (when
the positions are numbered from $0$ to $7$) is doubled modulo $7$ after
performing a shuffle. The position of the last card in the deck remains
$7$.

Our primary concern in this section is to find after how many shuffles
the cards will all be unflipped. Based on our notation, this is the same
as finding the number of shuffles after which every card in the deck is
represented by an upper-case letter. We shall try to derive a relation
between the number of shuffles it takes for the cards to all be flipped
face-down, and the number of shuffles it takes to get the cards all back
to their original position. We shall refer to the number of shuffles
that it takes to get all cards back to flipping up the flip period and
the number of shuffles it takes for all cards to get back to their
original position the shuffle order.

In order to see a full picture of what is going on, let us continue
shuffle our deck of $8$ cards. $$\begin{matrix}
A & A & A & A & A & A & A \\
B & e & c & b & E & C & B \\
C & B & e & c & b & E & C \\
D & f & G & D & f & G & D \\
E & C & B & e & c & b & E \\
F & g & d & F & g & d & F \\
G & D & f & G & D & f & G \\
H & h & H & h & H & h & H
\end{matrix}$$

When does a particular card, say card C for instance, get flipped? We
see that card $C$ takes on the following positions:
$2, 4, (1), (2), (4), 1, 2$. Here, $(a)$ denotes that the card is at
position $a$ and is flipped, whereas $a$ denotes that the card is at
position $a$ and is NOT flipped. This motivates an observation: *A card
gets flipped in the next shuffle, if its current position is greater
than half of $7$ (where $7$ is the maximum position that a card may
take, i.e. $m-1$ where $m$ is the number of cards in the deck).* In
other words, a card gets flipped in the next shuffle if it currently
lies in the second half of the deck. Indeed, card $C$ gets flipped only
when its position is $4$.

While this observation is significant, it does not require much effort to prove. It follows directly from how we are shuffling the cards. We flip only the second half of the deck, which proves this observation.

So now, how do we determine whether a particular card is flipped or not, given the number of cards in the deck and the number of times that the deck has been shuffled? Let us again take an example. Consider a deck of $8$ cards as earlier. Suppose the deck is shuffled $5$ times. What is the orientation of card $C$? Is it flipped face-down or face-up? We see that the position of card $C$ after $5$ shuffles is $1$ and it is not flipped (or face-up). When the deck is shuffled $4$ times, card $C$ is flipped and is at position $(4)$. Card $C$ is flipped after $2, 3$ and $4$ shuffles, whereas it is not flipped after $0, 1, 5$ and $6$ shuffles.

Is there a general pattern? Note that a card will be flipped face-down if the number of times it gets flipped during the process of shuffling is even, and will be face-up if the number of times it gets flipped during the process is odd. This indeed does hold for card $C$. Now, since a card is flipped when it lies in the second half of the deck, this implies that a card is face-up when the number of times it lies in the second half of the deck

*before*the $k$the shuffle is odd, where $k$ is the number of shuffles.

For example, let $k=5$. Card $C$ lies in position $4$ twice before the fifth shuffle takes place. Therefore, $C$ is face-down after $5$ shuffles.

Let $k=4$. Card $C$ lies in position $4$ only once

*before*the fourth shuffle. Thus, the card is flipped face-up.

In general, we may conclude that, for a deck of $m$ cards, a given card is flipped after $k$ shuffles if and only if the number of times its position is greater than $(m-1)/2$ before the $k$th shuffle takes place is odd. In other words, consider a deck of $m$ cards. Consider some card in the deck, $X$. Let the position of card $X$ after $i$ shuffles be $a_i$. Card $X$ is flipped after $k$ shuffles if and only if the number of values of $a_i$ that are greater than $(m-1)/2$ as $i$ goes from $0$ to $k-1$ is odd.

Now, let us explore the relation between the flip period and the shuffle order. Notice that the shuffle order for $8$ cards is $3$, whereas the flip period is $6$. Notice how the shuffle order divides the flip period. Does this always hold? Indeed, using a computer program, one may observe that the flip period is always a multiple of the shuffle order. We shall in the rest of the article, try to prove this.

## Mathization #

In this section we shall focus on making the process more mathematical in order to make it easier to prove our observations. Before doing so, we shall introduce a modified division algorithm in order to motivate future steps.

**Theorem 1**. *For positive $a$ and $p$ that are integers, there exist
integers $q, r$ and $\epsilon$ such that $a = pq + \epsilon r$ where
$0 \leq r \leq \frac{p}{2}$ and $\epsilon = \pm1$.*

We shall prove this result later. We will explain what the result states
in more detail and move directly to its application to our card
shuffling problem.

The ordinary division algorithm states that for every $a, p$ that are
positive integers, there exist integers $q$ and $r$ such that
$a = pq + r$ and $0 \leq r < p$. However, our new division algorithm
takes this a step further. Our new division algorithm further restricts
the possible values of the remainder to just $0 \leq r \leq p/2$.
However, in order to ensure that this division algorithm holds for all
integer, it is necessary to introduce a variable $\epsilon$ that is
either $+1$ or $-1$. Another way to think of the difference between the
two division algorithms is as follows: The quotient obtained by the
ordinary division algorithm yields the greatest integer that is less
than or equal to $a/p$. On the other hand, our modified division
algorithm not only floors the result of $a/p$, but rounds it off to the
nearest integer.

Let us also introduce new notation equivalent to mod for our new
division algorithm. Let
$a\mkern{3mu}{\mathrm{mmod}}\mkern{3mu}p$ denote
the remainder, $\epsilon r$ obtained when $a$ is divided by $p$ using
our modified division algorithm. So, we have
$13\mkern{3mu}{\mathrm{mmod}}\mkern{3mu}5 = -2$
whereas $13 \mod 5 = 3$.

How does all of this relate to our problem? We earlier concluded that a
given card is flipped after $k$ shuffles if and only if the number of
times it was in the second half of the deck before the $k$th shuffle is
odd. Notice how our new division algorithm gives us a neat way to tell
when a card is in the second half of the deck. If the position of a card
mmod $p$ where $p = m-1$ is positive, then the card is in the first half
of the deck. If it is negative, it is in the second half of the deck.
For example, consider a deck of $8$ cards. We want to check if the
position $4$ corresponds to the first half of the deck or the second
half of the deck. Since
$4 \mkern{3mu}{\mathrm{mmod}}\mkern{3mu}7 = -3$, it
is in the second half of the deck.

We may thus reframe our condition for a card to be flipped as follows:
*In a deck of $p+1$ cards, a card is flipped after $k$ shuffles, iff the
number of times its position in the deck mmod $p$ is negative before $k$
shuffles have taken place, is odd.* We may also state it as: consider a
deck of $m$ cards. Consider some card in the deck, $X$. Let the position
of card $X$ after $i$ shuffles be $a_i$. Card $X$ is flipped after $k$
shuffles if and only if the number of values of $a_i$ that are negative
mmod $p$ as $i$ goes from $0$ to $k-1$ is odd. For example, let us
reconsider the deck of $8$ cards and the card $C$. The position of card
$C$ mmod $7$ is given as: $2, -3, 1, 2, -3, 1, 2$. There are two
negative values before $5$ shuffles have taken place. Hence $C$ is not
flipped after $5$ shuffles. There is only one negative value before $4$
shuffles. Thus, $C$ is flipped after four shuffles.

However, none of what we have done till now makes the problem
significantly easier to solve. Instead of saying the number of times the
position of the card is greater than $p/2$, we simply said the number of
times its position mmod $p$ is negative. This does not make any
difference but convenience. It does not make it any clearer as to how
one could proceed to prove that the flip period is a multiple of the
shuffle order. In order to make full use of our new division algorithm
and notation, we need another important result. We need something that
will help us identify when a card will have a negative position.

**Theorem 2**. *Let $a, p, q, r$ and $\epsilon$ be integers (with $a$
and $p$ positive) such that $a = pq + \epsilon r$. Then
$\epsilon = (-1)^{\left\lfloor 2a/p \right\rfloor}$.*

Again, we shall for now focus more on the application of the above
theorem and leave the proof to the end. How do we use this theorem? Let
the position of a card in the deck be $a$. By the above theorem, we have
that the card is in the second half of the deck if and only if
$\left\lfloor 2a/p \right\rfloor$ is odd. For example, if the position
of card $X$ is $a=4$ in a deck of $8$ cards, then it lies in the second
half of the deck since $\left\lfloor 2a/p \right\rfloor = 1$. On the
other hand, $\left\lfloor 2\cdot 3/7 \right\rfloor = 0$ and therefore
the card at position $3$ lies in the first half of the deck.

We may thus state our result regarding the flip of a card finally as
follows: *Consider a deck of $p+1$ cards. Consider a card $X$ in the
deck. Let the position of $X$ after $i$ shuffles be given by $a_i$.
Then, the card $X$ is flipped after $k$ shuffles if and only if the
number of times $\left\lfloor 2a_i/p \right\rfloor$ is odd as $i$ goes
from $0$ to $k-1$ is odd.*

Till now, all we did was state the same result that we observed in the
very first section in different ways, some in fact more complicated. How
does this help in any way? Let us try to use what we know from the
already solved problem of shuffle order. We know that if the position of
card $X$ is initially $a$, then its position after $i$ shuffles is given
by $2^ia \mod p/2$. So, in a deck of $p+1$ cards, if $a$ is the initial
position of a card $X$, then its position will proceed as follows, till
$k$ shuffles: $$a, 2a, 2^2a, \dots, 2^ka \pmod{p/2}$$ We also know that
the card $X$ will be flipped after $k$ shuffles if the number of times
the position is greater than $p/2$ is odd. We may equivalently say that:
the card $X$ will be flipped if the number of times
$\left\lfloor 2a_i/p \right\rfloor$ is odd, is odd. We saw this in the
previous section.

But the former way of stating it sounded much simpler. Why did we
introduce the latter way of putting it in the first place? It seems to
only make it more complicated. However, when one tries to solve the
problem of finding the number of times $2^ia\mod p$ is greater than
$p/2$, it is not so easy. So, let us see how lucky we get with the
latter, more complicated form.

Since $a_i = 2^ia$,
$\left\lfloor 2a_i/p \right\rfloor = \left\lfloor 2^{i+1}a/p \right\rfloor$
where $a$ is the initial position of $X$. Thus, $X$ is flipped if and
only if the number of times $\left\lfloor 2^{i+1}a/p \right\rfloor$ is
odd, is odd. In case this sounds confusing, let us go back to our
example of a deck of $8$ cards. The initial position of card $C$ is $2$.
The values of $\left\lfloor 2^{i+1}a/p \right\rfloor$ are therefore:
$$\left\lfloor 2\cdot 2/7 \right\rfloor, \left\lfloor 4\cdot 2/7 \right\rfloor, \left\lfloor 8\cdot 2/7 \right\rfloor, \left\lfloor 16\cdot 2/7 \right\rfloor, \left\lfloor 32\cdot 2/7 \right\rfloor, \left\lfloor 64\cdot 2/7 \right\rfloor, \left\lfloor 128\cdot 2/7 \right\rfloor$$
which is equal to $$0, 1, 2, 4, 9, 18, 36$$ Suppose $5$ shuffles are
performed. The number of values that are odd before 5 shuffles are
performed is $2$. Thus, the card is not flipped after five shuffles,
whereas it is flipped after four.

Now, for the sake of convenience, let us introduce a new notation.
Consider a positive real number $n$ and the list
$S_n [\left\lfloor n \right\rfloor, \left\lfloor n/2 \right\rfloor, \left\lfloor n/4 \right\rfloor, \dots, 0]$.
We shall say $\xi(n) = 0$ if the number of odd elements of the list is
even, and $\xi(n) = 1$ if the number of odd elements of the list is odd.
How does this relate to our problem? Suppose we let $n=2^ka/p$. Then,
the corresponding list will be
$[\left\lfloor 2^ka/p \right\rfloor, \left\lfloor 2^{k-1}a/p \right\rfloor, \dots, 0]$.
This list is equivalent to the list of
$\left\lfloor 2a_i/p \right\rfloor$ as $i$ ranges from $0$ to $k-1$.
Hence, if the number of odd elements in this list is odd, then the card
$X$ will be flipped. In other words, card $X$ will be flipped if
$\xi(2^ka/p) = \xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 1$.
Similarly, it will not be flipped it
$\xi(\left\lfloor 2^ka/p \right\rfloor = 0)$.

Therefore, we may now conveniently say that in a deck of $p+1$ cards, a
card $X$ with initial position $a$ is flipped after $k$ shuffles if and
only if $\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 1$.

## Flip Period and Shuffle Order #

Until now, the only thing we did was to give a nice mathematical way of
saying when a card is flipped, purely using notations. We shall now use
it in order to prove our observed relation between shuffle order and
flip period. Let us represent the shuffle order of a deck of $p+1$ cards
as $\mathop{\mathrm{ord}}(p)$ and the flip period of a deck of $p+1$
cards as $\mathop{\mathrm{ford}}(p+1)$. We know that
$\mathop{\mathrm{ord}}(p)$ equals the order of $2$ modulo $p$. We shall
now use these facts to prove the relationship we observed.

Firstly, let us get an idea of what the flip period is, as we have not
discussed it in detail till now. The shuffle flip period is the number
of shuffles that it takes for all cards in the deck to revert to their
original configuration in terms of flips. In other words, the smallest
number of shuffles it takes for all cards to be facing down again. We
know that for a card $X$ with initial position $a$ to be facing down
after $k$ shuffles, we must have
$$\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 0$$ Now, we are
dealing with the case when ALL cards in the deck face down. Therefore,
for every card in the deck, the above must hold, where $a$ is the card’s
respective starting position. In other words, for all $a$ from $0$ to
$p-1$, we must have the above being true. The smallest positive $k$ for
which this is satisfied will yield the flip period. In order to show
that $\mathop{\mathrm{ord}}(p) \vert \mathop{\mathrm{ford}}(p)$, it will
suffice to show that when
$\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 0$ for all $a$ from
$0$ to $p-1$, then $2^k \equiv 1 \pmod{p}$. This will imply that
$\mathop{\mathrm{ord}}(p)$ divides $k$ and hence that
$\mathop{\mathrm{ord}}(p) \vert \mathop{\mathrm{ford}}(p)$ since
$\mathop{\mathrm{ford}}(p)$ just represents the smallest such $k$. ^{1}

Let us first formulate a strategy. We want to prove that if
$\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 0$ for *all* $a$
from $0$ to $p-1$, then $2^k$ is $1$ mod $p$. Note the emphasis on
*all*. Let us start with the assumption that $2^k$ is not 1 mod $p$.
Then, even if we could prove that there exists just one value of $a$
from $0$ to $p-1$ that does not satisfy
$\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 0$, we would be
done with our proof. Since it holds for all $a$, it must also hold for
$a = 1$. Hence, $\xi\left(\left\lfloor 2^k/p \right\rfloor\right) = 0$.
Given this, is it possible to find some value of $a$ such that
$\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 1$? What is
$\xi\left(\left\lfloor 2^ka/p \right\rfloor\right)$ in terms of
$\xi\left(\left\lfloor 2^k/p \right\rfloor\right)$?

Before moving on, let us first explore a simple property of the $\xi$
function and another result.

**Proposition 1**. *If $\xi(n) = 0$ then $\xi(2^in) = 0$ for any
nonnegative integer $i$.*

This is easy to prove. We are given that the number of odd elements in
the list $S_n$ is even. The list $S_{2^in}$ is merely the list $S_n$
plus the elements $2^in, 2^{i-1}n, \dots, 2n$. All of these are even.
Thus there are no more odd elements being added to $S_n$. Hence the
result is proven.

Now, if $n$ is even and $\xi(n) = 0$, then what can we say about
$\xi(n+1)$? Clearly, all elements of $S_{n+1}$ are the same as that of
$S_n$, except for the last element, i.e. $n+1$. Since $n$ is even, $n+1$
is odd. Therefore, $\xi(n+1) = 1$.

Now how may we use this in our proof? We start with the fact that
$\xi\left(\left\lfloor 2^k/p \right\rfloor\right) = 0$. Then, we know
that if $a = 2^x$ for some nonnegative integer $x$, we have
$\xi\left(a\left\lfloor 2^k/p \right\rfloor\right) = 0$. It follows that
$\xi\left(a\left\lfloor 2^k/p \right\rfloor + 1\right) = 1$.

How does this help? So we did find *something* that yields $1$ when it
is operated on by the $\xi$ function. But we need to find something of
the form $\left\lfloor 2^ka/p \right\rfloor$. So, what if
$$\left\lfloor 2^ka/p \right\rfloor = a\left\lfloor 2^k/p \right\rfloor + 1$$
Then, clearly $\xi\left(\left\lfloor 2^ka/p \right\rfloor\right) = 1$
and we have found our desired value of $a$. But does there always exist
such a value of $a$ which both satisfies the above and the fact that
$a = 2^x$? It turns out that such an $a$ does not always exist. So our
attempt at proving our observation failed. Can we however salvage this?
Indeed, the following result gives us some hope:

**Proposition 2**. *Let $p, q$ be integers, with $p>q>1$. There exists
some even integer $a$ such that
$$\left\lfloor \frac{aq}{p} \right\rfloor = a\left\lfloor \frac{q}{p} \right\rfloor + 1$$
and $a < p$.*

We shall prove the above proposition at the end along with other results
that we have left out. We will be more concerned regarding how we may
apply this to our problem.

The propoosition implies that for every $p$, if $2^k$ is not $1$ mod
$p$, then there exists some even integer $a$ that is between $0$ and
$p-1$ such that
$$\left\lfloor \frac{2^ka}{p} \right\rfloor = \left\lfloor \frac{2^k}{p} \right\rfloor a + 1$$
Let us try to use this fact. Since $a$ is even, let $a = 2^xb$ where $b$
is odd. Given the above and that $x \neq 0$, what can we say about
$\left\lfloor 2^kb/p \right\rfloor$? Observe that
$$\left\lfloor \frac{2^kb}{p} \right\rfloor = \left\lfloor \frac{2^k}{p} \right\rfloor b$$
Again, we will prove this later, and will be concerned regarding its
application. We may write
$$\left\lfloor \frac{2^ka}{p} \right\rfloor = \left\lfloor \frac{2^k}{p} \right\rfloor a + 1 = 2^x\left\lfloor \frac{2^k}{p} \right\rfloor b + 1$$
Since
$\left\lfloor 2^kb/p \right\rfloor = b\left\lfloor 2^k/p \right\rfloor$
we may therefore write the above as
$$2^x\left\lfloor \frac{2^kb}{p} \right\rfloor + 1$$ Now, since $b<a$ it
clearly lies between $0$ and $p$. It follows that
$\xi\left(\left\lfloor 2^kb/p \right\rfloor\right) = 0$. Hence, as we
have seen earlier
$$\xi\left(\left\lfloor \frac{2^kb}{p} \right\rfloor + 1\right) = \xi\left(\left\lfloor \frac{2^ka}{p} \right\rfloor\right) = 1$$
But $a$ lies between $0$ and $p-1$. This means that the card deck is not
shuffled! This contradicts our assumption that $2^k$ is not $1$ mod $p$.
Therefore, we *must* have $2^k \equiv 1 \pmod{p}$. This completes our
proof!

## Completing Proofs #

**Proposition 3**. *Let $p, q$ be integers, with $p>q>1$. There exists
some even integer $a$ such that
$$\left\lfloor \frac{aq}{p} \right\rfloor = a\left\lfloor \frac{q}{p} \right\rfloor + 1$$
and $a<p$.*

*Proof.* Let $q = pq’ + r$. So,
$q’ = \left\lfloor \frac{q}{p} \right\rfloor$ and $0 \leq r < p$. We
shall consider two cases as follows:

When $r > p/2$

When $r \leq p/2$.

When $r>p/2$, we may multiply both sides of $q = pq’ + r$ by $2$ to get
$$2q = p(2q’) + 2r$$ Since $p/2 \leq r < p$, it follows that
$p < 2r < 2p$. Hence,
$$\left\lfloor \frac{2q}{p} \right\rfloor = 2q’ + 1 = 2\left\lfloor \frac{q}{p} \right\rfloor + 1$$
Thus, there always exists a value of $a$ satisfying the required
conditions, i.e. $a=2$, when $r>p/2$.

Now, we come to the case when $r \leq p/2$. Let $a_0$ be the smallest
possible value of $a$ that is even such that $a_0r \geq p$. We want to
prove that $a_0r < 2p$. In order to do so, assume for the sake of
contradiction that $a_0r \geq 2p$. Now, consider $a = a_0 - 2$. We have
$$(a_0-2)q = p(a_0-2)q’ + (a_0-2)r$$ Since $0 \leq r \leq p/2$ and
$a_0r \geq 2p$, it follows that $p \leq(a_0-2)r$. This contradicts our
assumption that $a_0$ is the smallest even value of $a$ for which
$a_0r \geq p$ since we have found a smaller value, i.e. $a-2$. Thus, we
must have $p \leq a_0r < 2p$.

Now, $$a_0q = p(a_0q’) + a_0r$$ Since $p \leq a_0r < 2p$,
$$\left\lfloor \frac{a_0q}{p} \right\rfloor = a_0\left\lfloor \frac{q}{p} \right\rfloor + 1$$
This shows that there exists some even $a$ such that
$\left\lfloor aq/p \right\rfloor = a\left\lfloor q/p \right\rfloor + 1$
when $r \leq p/2$. Since we also showed the same for $r > p/2$, it holds
valid regardless of the value of $r$. This completes our proof. ◻

**Proposition 4**. *Let $a$ be even such that
$\left\lfloor 2^ka/p \right\rfloor = \left\lfloor 2^k/p \right\rfloor a + 1$.
Let $a = 2^xb$. Then,
$\left\lfloor 2^kb/p \right\rfloor = \left\lfloor 2^k/p \right\rfloor b$.*

*Proof.* Let $2^k = pq + r$ where $0 \leq r < p$. In other words,
$\left\lfloor 2^k/p \right\rfloor = q$. Now, if we multiply both sides
by $a$, we get $2^ka = p(aq) + ar$. It follows that
$$\left\lfloor \frac{2^ka}{p} \right\rfloor = aq + \left\lfloor \frac{ar}{p} \right\rfloor = \left\lfloor 2^k/p \right\rfloor a + \left\lfloor \frac{ar}{p} \right\rfloor$$
since $q = \left\lfloor 2^k/p \right\rfloor$. We are also given that
$\left\lfloor 2^ka/p \right\rfloor = \left\lfloor 2^k/p \right\rfloor a + 1$.
Thus, $$\left\lfloor \frac{ar}{p} \right\rfloor = 1$$ This implies that
$$p \leq ar < 2p$$ Now, let $a = 2^xb$. Since $a$ is even, $x\neq 0$.
Dividing the above inequality by $2$ we therefore get
$$\frac{p}{2} \leq 2^{x-1}br < p$$ It follows that $br < p$. Thus,
$$\left\lfloor \frac{2^kb}{p} \right\rfloor = \left\lfloor \frac{2^k}{p} \right\rfloor b$$
which proves the desired result. ◻

Notice that we only took $a$ from $0$ to $p-1$ without including $p$. The last card in the deck clearly remains at the last position and merely oscillates in its flip. It is not possible for the rest of the cards to be face-down and the last card to be face up. We may thus ignore this card. ↩︎