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.

(In reply to re: Making a sequence (spoilers on the numbers) by ThoughtProvoker)

I haven't been able to prove that the match in the second position implies that all positions match, but the following results match, from an improved version of the program:

  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

The new program being:

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
   done = 1
   FOR i = 1 TO size
     IF card(i, 0) <> i THEN done = 0
   NEXT
  LOOP UNTIL done
  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 21:13:59