You have a deck of 52 cards - for convenience, number them 1 through 52. You cut the cards into two equal halves and shuffle them perfectly. That is, the cards were in the order
1,2,3,...,52
and now they are
1,27,2,28,...,26,52. Let's call this a perfect in-shuffle.
If you repeat this in-shuffling process, how many in-shuffles will it take for the deck to return to its initial ordering (taking for granted that the cards will eventually do so)?
________________________
How does the solution change if you have a deck of 64 cards, or 10, or in general, n cards? For odd integer values of n, in-shuffling will take 1,2,3,...,n to 1,(n+3)/2,2,(n+5)/2,...,n,(n+1)/2. For example, when n=5, the first in-shuffle yields 1,4,2,5,3.
Now this would be a challenging question:
"What are the next three numbers in this sequence: 5,11,13,19,29,37,53,59,61,67,83,101,107,131,139,149,163,173,179,181 ?
Answer: 197,211,227"
These are prime numbers that correspond to the number of cards in a sequentially numbered deck that requires a number of shuffles one less than its cardinality to be returned to sequential sequence.
(ex) For 11, 10 shuffles are needed:
1 7 2 8 3 9 4 10 5 11 6
1 4 7 10 2 5 8 11 3 6 9
1 8 4 11 7 3 10 6 2 9 5
1 10 8 6 4 2 11 9 7 5 3
1 11 10 9 8 7 6 5 4 3 2
1 6 11 5 10 4 9 3 8 2 7
1 9 6 3 11 8 5 2 10 7 4
1 5 9 2 6 10 3 7 11 4 8
1 3 5 7 9 11 2 4 6 8 10
1 2 3 4 5 6 7 8 9 10 11
Visual Basic program used:
Imports System
Imports System.Runtime.InteropServices
Imports System.Math
Module Module1
Sub Main()
Randomize()
Dim intStart As Integer
intStart = 0
While intStart < 2
Console.WriteLine("Where shall I start ? " & _
"(A number greater than 1)")
intStart = Int(Console.ReadLine())
End While
For IndexZ As Double = intStart To 999999999999
Mainline(IndexZ)
Next
End Sub
Sub Mainline(ByRef IndexZ)
Dim intDeck() As Integer
Dim intFirstHalf() As Integer
Dim intSecondHalf() As Integer
Dim strEndFlag As String
Dim strShowFlag As String
Dim intCards As Integer
Dim intWork1 As Integer
Dim intSize As Integer
Dim intCount As Integer
Dim intSubscr1 As Integer
Dim intSubscr2 As Integer
intCount = 0
intCards = IndexZ
strShowFlag = "?"
While (strShowFlag <> "Y" And _
strShowFlag <> "N")
Console.WriteLine("Do you want to see the " & _
"deck after each shuffle? (Y/N)")
strShowFlag = UCase(Console.ReadLine())
End While
intSize = intCards - 1
If intCards Mod 2 = 0 Then
intWork1 = intCards
Else
intWork1 = intCards + 1
End If
intWork1 /= 2
ReDim intDeck(intSize)
ReDim intFirstHalf(intSize)
ReDim intSecondHalf(intSize)
For Index2 As Integer = 0 To UBound(intDeck)
intDeck(Index2) = Index2 + 1
intFirstHalf(Index2) = 0
intSecondHalf(Index2) = 0
Next
If strShowFlag = "Y" Then
Displaydeck(intDeck, intCount)
End If
strEndFlag = "N"
While strEndFlag <> "Y"
SplitDeck(intDeck, intFirstHalf, intSecondHalf, _
intWork1)
Shuffle(intDeck, intFirstHalf, intSecondHalf, _
strEndFlag, strShowFlag, intWork1, intCount)
End While
Console.WriteLine(" ")
Console.WriteLine(Str(intCards) & _
" cards need " & (intCount) & " shuffles.")
Console.WriteLine(" ")
End Sub
Sub SplitDeck(ByRef intDeck, ByRef intFirstHalf, _
ByRef intSecondHalf, ByVal intWork1)
Dim intSubscr1 As Integer
Dim intSubscr2 As Integer
intSubscr1 = 0
intSubscr2 = intWork1 - 1
For Index1 As Integer = 0 To intSubscr2
intFirstHalf(intSubscr1) = intDeck(Index1)
intDeck(Index1) = 0
intSubscr1 += 1
Next
intSubscr1 = 0
For Index1 As Integer = intWork1 To UBound(intDeck)
intSecondHalf(intSubscr1) = intDeck(Index1)
intDeck(Index1) = 0
intSubscr1 += 1
Next
End Sub
Sub Shuffle(ByRef intDeck, ByRef intFirstHalf, ByRef intSecondHalf, _
ByRef strEndFlag, ByVal strShowFlag, ByVal intWork1, ByRef intCount)
Dim intSubscr1 As Integer
Dim intSubscr2 As Integer
intCount += 1
intSubscr1 = 0
intSubscr2 = intWork1 - 1
For Index1 As Integer = 0 To intSubscr2
intDeck(intSubscr1) = intFirstHalf(Index1)
intFirstHalf(Index1) = 0
intSubscr1 += 1
If intSubscr1 > UBound(intDeck) Then
Exit For
End If
intDeck(intSubscr1) = intSecondHalf(Index1)
intSecondHalf(Index1) = 0
intSubscr1 += 1
If intSubscr1 > UBound(intDeck) Then
Exit For
End If
Next
If strShowFlag = "Y" Then
Displaydeck(intDeck, intCount)
End If
strEndFlag = "Y"
For Index1 As Integer = 1 To UBound(intDeck)
intSubscr1 = Index1 - 1
If intDeck(Index1) = 0 Then
Exit For
End If
If intDeck(intSubscr1) > intDeck(Index1) Then
strEndFlag = "N"
End If
Next
End Sub
Sub Displaydeck(ByVal intDeck, ByVal intCount)
Dim intSubscr2 As Integer
Console.WriteLine("The deck after " & Str(intCount) & " shuffles:")
For Index1 As Integer = 0 To UBound(intDeck)
If intDeck(Index1) = 0 Then
Exit For
End If
Console.WriteLine(Str(intDeck(Index1)))
Next
Console.WriteLine(" ")
End Sub
End Module
Edited on May 20, 2004, 9:01 am
|
Posted by Penny
on 2004-05-20 08:54:38 |