(a) In the new deck, position 1 holds the card from position 1, position 2 holds the card from position 5, position 3 the card from position 2, and so on. Reading this the other way round gives where each card goes:
| p | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|
| f(p) | 1 | 3 | 5 | 7 | 2 | 4 | 6 | 8 |
In formula form, f(p)=2p−1 for 1≤p≤4 and f(p)=2p−8 for 5≤p≤8.
One-one: the eight values 1,3,5,7,2,4,6,8 are all different, so different positions go to different positions.
Onto: every element of A appears among the values, so every position receives a card.
Hence f is a bijection. (For a function from a finite set to itself, one-one already forces onto.)
(b) Apply f to each value of f:
| p | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|
| f(p) | 1 | 3 | 5 | 7 | 2 | 4 | 6 | 8 |
| f2(p) | 1 | 5 | 2 | 6 | 3 | 7 | 4 | 8 |
| f3(p) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
The last row uses f(1)=1, f(5)=2, f(2)=3, f(6)=4, f(3)=5, f(7)=6, f(4)=7, f(8)=8. So f3(p)=p for every p, that is, f3=IA.
Then f∘f2=f2∘f=f3=IA, so f2 is the inverse of f:
f−1=f2:1↦1, 2↦5, 3↦2, 4↦6, 5↦3, 6↦7, 7↦4, 8↦8
Neither f nor f2 is the identity (f(2)=3 and f2(2)=5), so the least number of out-shuffles that restores the deck is 3.
(c) Reflexive: p=f0(p), so pRp for every p.
Symmetric: let q=fk(p) with k∈{0,1,2}. If k=0 then q=p. If k=1 or 2, then 3−k∈{1,2} and
f3−k(q)=f3−k(fk(p))=f3(p)=p
so qRp.
Transitive: let q=fj(p) and r=fk(q) with j,k∈{0,1,2}. Then r=fj+k(p) with 0≤j+k≤4. If j+k≥3, then fj+k=fj+k−3∘f3=fj+k−3 with j+k−3∈{0,1}. Either way r=fm(p) for some m∈{0,1,2}, so pRr.
Hence R is an equivalence relation. Following each card through the shuffles: 1→1; 2→3→5→2; 4→7→6→4; 8→8. The equivalence classes are
{1},{2,3,5},{4,6,7},{8}
Every pair inside a class is related and no other pair is, so
n(R)=12+32+32+12=20
(d) The new deck holds, from the top, the cards from positions 5,1,6,2,7,3,8,4. So the card from 5 goes to 1, the card from 1 goes to 2, the card from 6 goes to 3, and so on:
| p | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|
| g(p) | 2 | 4 | 6 | 8 | 1 | 3 | 5 | 7 |
Then
(g∘f)(2)=g(f(2))=g(3)=6,(f∘g)(2)=f(g(2))=f(4)=7
The two values differ, so g∘f=f∘g. An out-shuffle followed by an in-shuffle does not have the same effect as an in-shuffle followed by an out-shuffle: the order of composition matters.
(e) Follow the cards under g:
1→2→4→8→7→5→1,3→6→3
The six cards in the first chain return to their places only after 6 in-shuffles, and not earlier: card 1 is at positions 2,4,8,7,5 after 1 to 5 in-shuffles. Cards 3 and 6 return after every 2 in-shuffles. So gn=IA needs n to be a multiple of 6, and n=6 works for every card (it is also a multiple of 2). The least value is
n=6
so six in-shuffles are needed, against only three out-shuffles.