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(4): Making a sequence (spoilers on the numbers) | Comment 6 of 20 |
(In reply to re(3): Making a sequence (spoilers on the numbers) by Richard)

Apparently (based on my understanding of what I read), for odd numbers of cards, the number of shuffles equals the "multiplicative order" of 2 (mod n) where n is the number of cards. For even numbers, use n = one less than the number of cards.

The "multiplicative order" is like a modular logarithm of 1: it is the power to which, in this case, 2 is to be raised, mod n, in order to get 1.  The following program evaluates this:

`DEFINT A-ZCLSFOR size = 3 TO 641 STEP 2  lg = 1: pw = 2  DO   lg = lg + 1: pw = (pw * 2) MOD size  LOOP UNTIL pw MOD size = 1  shCt = lg  n = (size - 3) / 2  col = n \ 40  row = n MOD 40 + 1  LOCATE row, 10 * col + 1  PRINT USING "### ### |"; size; shCt;NEXT`

and it indeed goes faster than actually shuffling the array of "cards".  As only odd sizes are calculated (since the same answer serves for the even size one higher), the list of answers goes twice as high.  The numbers agree with the previous results:

` 3   2 |  83  82 | 163 162 | 243 162 | 323  72 | 403  60 | 483  66 | 563 562 5   4 |  85   8 | 165  20 | 245  84 | 325  60 | 405 108 | 485  48 | 565  28 7   3 |  87  28 | 167  83 | 247  36 | 327  36 | 407 180 | 487 243 | 567  54 9   6 |  89  11 | 169 156 | 249  82 | 329  69 | 409 204 | 489 162 | 569 28411  10 |  91  12 | 171  18 | 251  50 | 331  30 | 411  68 | 491 490 | 571 11413  12 |  93  10 | 173 172 | 253 110 | 333  36 | 413 174 | 493  56 | 573 19015   4 |  95  36 | 175  60 | 255   8 | 335 132 | 415 164 | 495  60 | 575 22017   8 |  97  48 | 177  58 | 257  16 | 337  21 | 417 138 | 497 105 | 577 14419  18 |  99  30 | 179 178 | 259  36 | 339  28 | 419 418 | 499 166 | 579  9621   6 | 101 100 | 181 180 | 261  84 | 341  10 | 421 420 | 501 166 | 581 24623  11 | 103  51 | 183  60 | 263 131 | 343 147 | 423 138 | 503 251 | 583 26025  20 | 105  12 | 185  36 | 265  52 | 345  44 | 425  40 | 505 100 | 585  1227  18 | 107 106 | 187  40 | 267  22 | 347 346 | 427  60 | 507 156 | 587 58629  28 | 109  36 | 189  18 | 269 268 | 349 348 | 429  60 | 509 508 | 589  9031   5 | 111  36 | 191  95 | 271 135 | 351  36 | 431  43 | 511   9 | 591 19633  10 | 113  28 | 193  96 | 273  12 | 353  88 | 433  72 | 513  18 | 593 14835  12 | 115  44 | 195  12 | 275  20 | 355 140 | 435  28 | 515 204 | 595  2437  36 | 117  12 | 197 196 | 277  92 | 357  24 | 437 198 | 517 230 | 597 19839  12 | 119  24 | 199  99 | 279  30 | 359 179 | 439  73 | 519 172 | 599 29941  20 | 121 110 | 201  66 | 281  70 | 361 342 | 441  42 | 521 260 | 601  2543  14 | 123  20 | 203  84 | 283  94 | 363 110 | 443 442 | 523 522 | 603  6645  12 | 125 100 | 205  20 | 285  36 | 365  36 | 445  44 | 525  60 | 605 22047  23 | 127   7 | 207  66 | 287  60 | 367 183 | 447 148 | 527  40 | 607 30349  21 | 129  14 | 209  90 | 289 136 | 369  60 | 449 224 | 529 253 | 609  8451   8 | 131 130 | 211 210 | 291  48 | 371 156 | 451  20 | 531 174 | 611 27653  52 | 133  18 | 213  70 | 293 292 | 373 372 | 453  30 | 533  60 | 613 61255  20 | 135  36 | 215  28 | 295 116 | 375 100 | 455  12 | 535 212 | 615  2057  18 | 137  68 | 217  15 | 297  90 | 377  84 | 457  76 | 537 178 | 617 15459  58 | 139 138 | 219  18 | 299 132 | 379 378 | 459  72 | 539 210 | 619 61861  60 | 141  46 | 221  24 | 301  42 | 381  14 | 461 460 | 541 540 | 621 19863   6 | 143  60 | 223  37 | 303 100 | 383 191 | 463 231 | 543 180 | 623  3365  12 | 145  28 | 225  60 | 305  60 | 385  60 | 465  20 | 545  36 | 625 50067  66 | 147  42 | 227 226 | 307 102 | 387  42 | 467 466 | 547 546 | 627  9069  22 | 149 148 | 229  76 | 309 102 | 389 388 | 469  66 | 549  60 | 629  7271  35 | 151  15 | 231  30 | 311 155 | 391  88 | 471  52 | 551 252 | 631  4573   9 | 153  24 | 233  29 | 313 156 | 393 130 | 473  70 | 553  39 | 633 21075  20 | 155  20 | 235  92 | 315  12 | 395 156 | 475 180 | 555  36 | 635  2877  30 | 157  52 | 237  78 | 317 316 | 397  44 | 477 156 | 557 556 | 637  8479  39 | 159  52 | 239 119 | 319 140 | 399  18 | 479 239 | 559  84 | 639 21081  54 | 161  33 | 241  24 | 321 106 | 401 200 | 481  36 | 561  40 | 641  64`

 Posted by Charlie on 2004-05-20 09:03:20

 Search: Search body:
Forums (1)