wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> TopSwops
        
(Message started by: nakli on Oct 28^th, 2010, 8:26am)

Title: TopSwops
Post by nakli on Oct 28^th, 2010, 8:26am

Created by the mathematician John Conway and known as Topswops, the puzzle starts like this: Begin with a randomly ordered deck of cards numbered 1 to n, with n being however high a number you choose. Now count out the number of cards represented by whatever card is the top card, and turn that block of cards over on top of the remaining cards. Then count out the number of cards represented by the new top card and turn this whole block over on top of the remaining cards. Repeat until the card numbered 1 comes to the top (realizing that we know the card numbered 1 will always eventually come to the top).

Now here’s what needs to be done: Calculate the maximum and minimum number of steps required with n number of cards.

http://www.utdallas.edu/news/2010/10/28-6621_Computer-Scientists-Make-Progress-on-Math-Puzzle_article.html

Title: Re: TopSwops
Post by towr on Oct 28^th, 2010, 9:06am

Isn't the minimum simply 0 steps, notably when 1 is randomly on top?

The first terms for the maximum can be found at http://www.research.att.com/~njas/sequences/A000375

[edit]
Ah, the point rather seems to be to find upper and lower bounds to the maximum number of steps n cards might take.
[/edit]