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.)
 re(2): Making a sequence (spoilers on the numbers) | Comment 3 of 20 |
(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:

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

 Search: Search body:
Forums (0)