It's mid-August and you are stretching on the golden beach
of some cosmopolitan Greek island, faineantly enjoying the warm sun
caressing your MITired body. Before you take another sip at
your double sugar iced coffee, you decide to go for a run of your
favorite pastime. You pick up your 52-card deck, shuffle it, then

(*) you cut the deck at an arbitrary point, and check whether the two 
    adjacent cards at that point are in order\footnote{The
    order of the deck is..}
    --- if not, you swap them into the correct order, join the two
    pieces of the deck back together, and repeat from (*).
    --- if they are in order, you just throw them away, onto the hot
        sand: 
        --- if they are the same color, you throw the smaller one to
            your left and the bigger one to your right;
        --- if they are different color, you throw both cards to the
            same side.  
    You then reshuffle the remaining deck and repeat from (*); unless
    of course there is no more cards in your hands, in which case you
        --- yawn, then 
        --- slowly extend your arm to reach that coffee... 

You wouldn't mind if this went on forever, since this is mid-August
and you are stretching on the golden beach of some cosmopolitan Greek
island. But you know it won't, because you remember having proved this
in the 6.042 Quiz 2 last spring. Now, how exactly did that go?

(A)
* Yeah.. You had modelled your pastime as a state machine. 
--- The states were...
--- the starting states were...
--- and there was a transition between two states ___ and ___ iff...


* And then.. Then, you had defined that derived variable f, mapping each
state of the machine to...


* and you had proved that  f  is strictly decreasing ---here is how:


* which implied the game terminates, because.. 


(B)
Oh, now you remember the entire problem. You were also asked to
prove that, when you are sipping at your coffee again, the
difference 
           (# red cards)  -  (# black cards)
on the sand is the same both on your left and on your right.

*  For this, you had defined the predicate P which was true of a 
   state ___ iff  


* And you had proven two things:
   (i) ...
  (ii) ...


* Which implied that at the end of the game the difference of colors
  is the same on both sides, because.. 



