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.

The numbers involved can be found via computer program.  Arranged by n:

 3   2 |  43  14 |  83  82 | 123  20 | 163 162 | 203  84 | 243 162 | 283  94
 4   2 |  44  14 |  84  82 | 124  20 | 164 162 | 204  84 | 244 162 | 284  94
 5   4 |  45  12 |  85   8 | 125 100 | 165  20 | 205  20 | 245  84 | 285  36
 6   4 |  46  12 |  86   8 | 126 100 | 166  20 | 206  20 | 246  84 | 286  36
 7   3 |  47  23 |  87  28 | 127   7 | 167  83 | 207  66 | 247  36 | 287  60
 8   3 |  48  23 |  88  28 | 128   7 | 168  83 | 208  66 | 248  36 | 288  60
 9   6 |  49  21 |  89  11 | 129  14 | 169 156 | 209  90 | 249  82 | 289 136
10   6 |  50  21 |  90  11 | 130  14 | 170 156 | 210  90 | 250  82 | 290 136
11  10 |  51   8 |  91  12 | 131 130 | 171  18 | 211 210 | 251  50 | 291  48
12  10 |  52   8 |  92  12 | 132 130 | 172  18 | 212 210 | 252  50 | 292  48
13  12 |  53  52 |  93  10 | 133  18 | 173 172 | 213  70 | 253 110 | 293 292
14  12 |  54  52 |  94  10 | 134  18 | 174 172 | 214  70 | 254 110 | 294 292
15   4 |  55  20 |  95  36 | 135  36 | 175  60 | 215  28 | 255   8 | 295 116
16   4 |  56  20 |  96  36 | 136  36 | 176  60 | 216  28 | 256   8 | 296 116
17   8 |  57  18 |  97  48 | 137  68 | 177  58 | 217  15 | 257  16 | 297  90
18   8 |  58  18 |  98  48 | 138  68 | 178  58 | 218  15 | 258  16 | 298  90
19  18 |  59  58 |  99  30 | 139 138 | 179 178 | 219  18 | 259  36 | 299 132
20  18 |  60  58 | 100  30 | 140 138 | 180 178 | 220  18 | 260  36 | 300 132
21   6 |  61  60 | 101 100 | 141  46 | 181 180 | 221  24 | 261  84 | 301  42
22   6 |  62  60 | 102 100 | 142  46 | 182 180 | 222  24 | 262  84 | 302  42
23  11 |  63   6 | 103  51 | 143  60 | 183  60 | 223  37 | 263 131 | 303 100
24  11 |  64   6 | 104  51 | 144  60 | 184  60 | 224  37 | 264 131 | 304 100
25  20 |  65  12 | 105  12 | 145  28 | 185  36 | 225  60 | 265  52 | 305  60
26  20 |  66  12 | 106  12 | 146  28 | 186  36 | 226  60 | 266  52 | 306  60
27  18 |  67  66 | 107 106 | 147  42 | 187  40 | 227 226 | 267  22 | 307 102
28  18 |  68  66 | 108 106 | 148  42 | 188  40 | 228 226 | 268  22 | 308 102
29  28 |  69  22 | 109  36 | 149 148 | 189  18 | 229  76 | 269 268 | 309 102
30  28 |  70  22 | 110  36 | 150 148 | 190  18 | 230  76 | 270 268 | 310 102
31   5 |  71  35 | 111  36 | 151  15 | 191  95 | 231  30 | 271 135 | 311 155
32   5 |  72  35 | 112  36 | 152  15 | 192  95 | 232  30 | 272 135 | 312 155
33  10 |  73   9 | 113  28 | 153  24 | 193  96 | 233  29 | 273  12 | 313 156
34  10 |  74   9 | 114  28 | 154  24 | 194  96 | 234  29 | 274  12 | 314 156
35  12 |  75  20 | 115  44 | 155  20 | 195  12 | 235  92 | 275  20 | 315  12
36  12 |  76  20 | 116  44 | 156  20 | 196  12 | 236  92 | 276  20 | 316  12
37  36 |  77  30 | 117  12 | 157  52 | 197 196 | 237  78 | 277  92 | 317 316
38  36 |  78  30 | 118  12 | 158  52 | 198 196 | 238  78 | 278  92 | 318 316
39  12 |  79  39 | 119  24 | 159  52 | 199  99 | 239 119 | 279  30 | 319 140
40  12 |  80  39 | 120  24 | 160  52 | 200  99 | 240 119 | 280  30 | 320 140
41  20 |  81  54 | 121 110 | 161  33 | 201  66 | 241  24 | 281  70 | 321 106
42  20 |  82  54 | 122 110 | 162  33 | 202  66 | 242  24 | 282  70 | 322 106

In the specific deck sizes asked for: 52 cards require 8 shuffles; 64 require 6; 10 cards require 6 also.

For a number of cards equal to a power of 2, the number of shuffles is the base-2 log of n.  That is, multiplying the number of cards by 2 adds one to the number of required shuffles.  This is not true for numbers that are not powers of 2. For example, while 52 cards takes 8 shuffles, 104 cards require 51 shuffles.

Here's the program:

CLS
FOR size = 3 TO 322
  REDIM card(size, 1)
  FOR i = 1 TO size
   card(i, 0) = i
  NEXT
  shCt = 0
  DO
   a = 1: b = (size + 2) / 2: IF b <> INT(b) THEN b = b + .5
   bInit = b
   i = 1
   DO
    card(i, 1) = card(a, 0)
    IF i < size THEN card(i + 1, 1) = card(b, 0)
    a = a + 1: b = b + 1
    IF a = bInit THEN EXIT DO
    i = i + 2
   LOOP
   FOR i = 1 TO size
    card(i, 0) = card(i, 1)
   NEXT
   shCt = shCt + 1
  LOOP UNTIL card(2, 0) = 2
  n = size - 3
  col = n \ 40
  row = n MOD 40 + 1
  LOCATE row, 10 * col + 1
  PRINT USING "### ### |"; size; shCt;
NEXT

 

Posted by Charlie on 2004-05-19 15:00:18