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

 Perfect Shuffle (Posted on 2004-05-19)
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.)
 Making a sequence (spoilers on the numbers) | Comment 1 of 20

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 13610   6 |  50  21 |  90  11 | 130  14 | 170 156 | 210  90 | 250  82 | 290 13611  10 |  51   8 |  91  12 | 131 130 | 171  18 | 211 210 | 251  50 | 291  4812  10 |  52   8 |  92  12 | 132 130 | 172  18 | 212 210 | 252  50 | 292  4813  12 |  53  52 |  93  10 | 133  18 | 173 172 | 213  70 | 253 110 | 293 29214  12 |  54  52 |  94  10 | 134  18 | 174 172 | 214  70 | 254 110 | 294 29215   4 |  55  20 |  95  36 | 135  36 | 175  60 | 215  28 | 255   8 | 295 11616   4 |  56  20 |  96  36 | 136  36 | 176  60 | 216  28 | 256   8 | 296 11617   8 |  57  18 |  97  48 | 137  68 | 177  58 | 217  15 | 257  16 | 297  9018   8 |  58  18 |  98  48 | 138  68 | 178  58 | 218  15 | 258  16 | 298  9019  18 |  59  58 |  99  30 | 139 138 | 179 178 | 219  18 | 259  36 | 299 13220  18 |  60  58 | 100  30 | 140 138 | 180 178 | 220  18 | 260  36 | 300 13221   6 |  61  60 | 101 100 | 141  46 | 181 180 | 221  24 | 261  84 | 301  4222   6 |  62  60 | 102 100 | 142  46 | 182 180 | 222  24 | 262  84 | 302  4223  11 |  63   6 | 103  51 | 143  60 | 183  60 | 223  37 | 263 131 | 303 10024  11 |  64   6 | 104  51 | 144  60 | 184  60 | 224  37 | 264 131 | 304 10025  20 |  65  12 | 105  12 | 145  28 | 185  36 | 225  60 | 265  52 | 305  6026  20 |  66  12 | 106  12 | 146  28 | 186  36 | 226  60 | 266  52 | 306  6027  18 |  67  66 | 107 106 | 147  42 | 187  40 | 227 226 | 267  22 | 307 10228  18 |  68  66 | 108 106 | 148  42 | 188  40 | 228 226 | 268  22 | 308 10229  28 |  69  22 | 109  36 | 149 148 | 189  18 | 229  76 | 269 268 | 309 10230  28 |  70  22 | 110  36 | 150 148 | 190  18 | 230  76 | 270 268 | 310 10231   5 |  71  35 | 111  36 | 151  15 | 191  95 | 231  30 | 271 135 | 311 15532   5 |  72  35 | 112  36 | 152  15 | 192  95 | 232  30 | 272 135 | 312 15533  10 |  73   9 | 113  28 | 153  24 | 193  96 | 233  29 | 273  12 | 313 15634  10 |  74   9 | 114  28 | 154  24 | 194  96 | 234  29 | 274  12 | 314 15635  12 |  75  20 | 115  44 | 155  20 | 195  12 | 235  92 | 275  20 | 315  1236  12 |  76  20 | 116  44 | 156  20 | 196  12 | 236  92 | 276  20 | 316  1237  36 |  77  30 | 117  12 | 157  52 | 197 196 | 237  78 | 277  92 | 317 31638  36 |  78  30 | 118  12 | 158  52 | 198 196 | 238  78 | 278  92 | 318 31639  12 |  79  39 | 119  24 | 159  52 | 199  99 | 239 119 | 279  30 | 319 14040  12 |  80  39 | 120  24 | 160  52 | 200  99 | 240 119 | 280  30 | 320 14041  20 |  81  54 | 121 110 | 161  33 | 201  66 | 241  24 | 281  70 | 321 10642  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:

`CLSFOR 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

 Search: Search body:
Forums (0)