## Impressing my friends

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Excalibur0998
Posts: 14
Joined: Wed Sep 24, 2008 4:48 am UTC

### Impressing my friends

Someone once showed me a pretty dumb game. You take a deck of cards and guess what the color of the next card is. If you're right you get to keep the card and guess again, but if you're wrong then you have to give the card back and it goes on the bottom of the deck. Usually people get up to about 6-8 cards in a row before they give up. I want to do better.

Here's what I'm thinking. I'll hold the deck and ask them to guess as usual. Whether they get it right or wrong, it doesn't matter because after 52 guesses the cards will be in the exact same order as they were to begin with. Now after they make 52 guesses I want to be able to name the colors of all of the cards.

In coming up with a way to do it, I quickly found that it would be easier if you turned groups of colors into strings. So I assigned blacks to be numbers and reds to be letters. This way, I was remembering "strings" where each string was a set of successive identical colors. (example: red red black black black red black red black would become B3A1A1). I don't have a huge knowledge of stat so I'm wondering, on average how many strings would there be after 52 cards. So, for example, if each card alternated then there would be 52 strings but if there were 26 black cards and then 26 red cards then there would be only two strings. So, how many strings would I be looking at memorizing on average?

Also, if you can come up with better methods of memorization, I'd want to hear about it. Right now I'm thinking that I might assign an alternating string to a shape based on how many cards are in the string. So the example I gave earlier would now become B3Square because a square has four sides and there are four alternating cards.

Thoughts?

qinwamascot
Posts: 688
Joined: Sat Oct 04, 2008 8:50 am UTC
Location: Oklahoma, U.S.A.

### Re: Impressing my friends

the quintessential memorization technique is "roman rooms" where you associate things you wish to memorize with objects in your room, then just take a tour around the room. So In my room, I'd start with the door. The door is red. Then I'd move to my roommate's bed, which might be black. His desk is also black, etc. It's not too hard to just straitout memorize 52 binary digits, but some people have trouble with this. There's plenty of memory association techniques that are available; I met a person who could do 100 random objects through association.

As for memorizing in terms of letters and numbers, I've never heard of that, but if it works for you that's great. I have heard of subdividing the alphabet, and creating weird phonetic sounds that are not hard to memorize. I've also heard of using words to tell a story; the number of letters in each word indicates something. In general, the more abstract you get, the harder it is to memorize. It sort of makes sense...If I memorize the digits of pi, for example, then I have no hint from the last to the next. With words, you can build a chain of associations and eliminate grammatically impossible words, so it's superior.

As for your question, there are C(52,26)=52!/(26!)2 possible ways to arrange the cards if all we care about is red or black. That's a fairly large number. I don't want to prove it but it seems likely that the average string length using this compression algorithm would be 26 due to symmetry.
Quiznos>Subway

t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

### Re: Impressing my friends

The compression technique you describe is known as run-length encoding. Think about it this way:

Every new draw of a card is independent of the draw before, so to generate a list of random card drawings you can do it by flipping a coin every time you want to draw a new card. If it's heads, the new card is the opposite color of the previous card; if it's tails, the new card is the same color as the previous card. The number of distinct strings in the final compression is therefore the average number of heads you flip, which is now obviously 26 as you can prove by a direct bijection. (Actually, it might be 26.5 looking at small cases, but you get the idea.)

Note that because you also have to memorize the length of each string, this doesn't give you very good compression on average. Run-length encoding tends to be most useful when encoding data such as image files that have unusually large runs of identical data, or after performing a Burrows-Wheeler transform (which is clearly unsuited to your purposes here).

Edit: Personally, what I would do is to memorize them in groups of four and associate each "byte" (they're not quite bytes, but you get the idea) with an element of some 16-element set so instead of memorizing a long sequence of a few things you're memorizing a shorter sequence of more things. Letters might get confusing, but how about, say, animals? Whatever sticks in your head.

qinwamascot
Posts: 688
Joined: Sat Oct 04, 2008 8:50 am UTC
Location: Oklahoma, U.S.A.

### Re: Impressing my friends

haha just fyi 4 bits is called a nibble (or nybble).

It's an interesting question as to whether you can even get a reasonably good compression algorithm. It has to do with Kolmogorov complexity. Basically, if you have random data and try to compress it, the complexity of the result plus the complexity of the compression algorithm can't ever be shorter than the original data. You're far better off not worrying about compressing at all and just working on memory to 52 places.
Quiznos>Subway

Christopher
Posts: 31
Joined: Sat Sep 27, 2008 3:57 am UTC

### Re: Impressing my friends

t0rajir0u wrote:The compression technique you describe is known as run-length encoding. Think about it this way:

Every new draw of a card is independent of the draw before, so to generate a list of random card drawings you can do it by flipping a coin every time you want to draw a new card. If it's heads, the new card is the opposite color of the previous card; if it's tails, the new card is the same color as the previous card.

This is not true, he's drawing cards without replacement.

The number of distinct strings in the final compression is therefore the average number of heads you flip, which is now obviously 26 as you can prove by a direct bijection. (Actually, it might be 26.5 looking at small cases, but you get the idea.)

Nor is this, since he draws a new card 51 times, the average number of heads you would get by flipping a coin 51 times is 25.5.

The expected value is in fact 27 because of symmetry.

This is a lot harder to prove than I originally thought, and I need to go to bed, so here's what I was thinking that is not quite there either in terms of clarity or in terms of rigor. Perhaps someone else will feel compelled to clean it up for me. Let n be the number of strings. You could have an even number of strings, in which case there have to be an equal number of red strings and black strings. You could also have an odd number of total strings, in which case you would have one of two possibilities for the number of red strings with the number of black strings being determined by the number of red ones.

Thus for any n, you could count the number of arrangements that would give you n strings by counting the number of ways to group the red cards into the necessary number of pieces, the number of ways of grouping the black cards into the necessary number of pieces and multiplying those two numbers together (for an odd n you have to do this for both possibilities, but they are symmetric since only the colors are switched). These are not too hard to calculate. You are setting a given number of partition within 26 objects so the number of ways to have r red strings is (I think!) C(25, r-1). This is where the symmetry comes from, because C(25, r-1) = C(25, 25-(r-1)). You get the same thing for the partitions of black cards, so there's symmetry in both terms you are multiplying, hence symmetry in the whole thing.

If anyone understood that kudos to you, but I need to get some sleep. Maybe I'll come back and clean this up later.
Last edited by Christopher on Mon Dec 15, 2008 9:02 pm UTC, edited 3 times in total.

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Impressing my friends

qinwamascot wrote:It's an interesting question as to whether you can even get a reasonably good compression algorithm. It has to do with Kolmogorov complexity. Basically, if you have random data and try to compress it, the complexity of the result plus the complexity of the compression algorithm can't ever be shorter than the original data. You're far better off not worrying about compressing at all and just working on memory to 52 places.

The point isn't about compression, though, but rather about memory. Our short-term memory can't easily hold that amount of information. You can train it to do so, but it's better if you have a decent way to transform the info into a more easily-remembered state.

t0rajir0u wrote:Personally, what I would do is to memorize them in groups of four and associate each "byte" (they're not quite bytes, but you get the idea) with an element of some 16-element set so instead of memorizing a long sequence of a few things you're memorizing a shorter sequence of more things. Letters might get confusing, but how about, say, animals? Whatever sticks in your head.

Translated into less generic speak, make a black card be 0 and a red card be 1, then transform every four of them into a hex digit as you go through the deck. This way you go from having to memorize 52 distinct things to only 13 distinct things. This is the whole reason we *have* hex, after all - binary is too big for humans to easily work with. Hex brings it back down to a manageable size.

Plus, you're guaranteed to have 13 things to memorize, which is much better than the original idea which averages 26 and can potentially hit 52 (though at that point it's easy, since the string is just A1A1A1A1... (or 1A1A1A..., of course)).
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))