All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Perfect Shuffle (Posted on 2004-05-19) Difficulty: 5 of 5
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.

No Solution Yet Submitted by SilverKnight    
Rating: 4.2500 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution A puzzling sequence (VB program used) | Comment 5 of 20 |
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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information