Happy New Year Math Factor fans.

My name is Stephen Morris and like Edmund I’m going to be posting in the Math Factor website.  I have been a listener for some time and have posted comments as ‘stevestyle’.  I’m not a professional mathematician, just a keen amateur and fan of math puzzles.  I live in England.

I thought I would start with an anecdote from the recent holidays, where playing scrabble with the family helped with one of Chaim’s problems.  I hope you enjoy it.

 

I always thought that playing Scrabble at Christmas was just a way to stop people fighting over the TV remote.  Not so!  It can also help in solving Math Factor problems.

 

Chaim gave some sequences recently that are generated by the rules:

–          start with 1;

–          take the average so far and multiply by a constant.

Surprisingly this generates sequences in Pascal’s triangle.

 

Chaim wanted an intuitive explanation in a single sentence.    I’m not sure I can do that but I can tell you an anecdote about playing Scrabble with the family over Christmas.  Funnily enough it helps!

 

At the start of a Scrabble game you have to take seven tiles out of a bag.  The normal way to do this is to take out seven tiles.  The way I often do it is to take eight tiles, realise that I have made a mistake and then put one back in the bag.  My family is incredibly suspicious so I have to make a big show of throwing back a random tile.

Both methods come to the same thing, you end up with seven randomly selected tiles.  However you can work out the number of combinations differently for each method and the second way leads to Chaim’s rule.

 

The number of ways of choosing a certain number of tiles from a bag containing a certain number of tiles is always a number in Pascal’s triangle.

To get one of the sequences Chaim described we need to keep the number of tiles we want constant and vary the number of tiles in the bag.

Let’s say we need r tiles and there are r tiles in the bag.  How many ways are there to select r tiles from the bag?  Obviously there is only one so we write down 1 as the first number in our sequence.

Add an extra tile to the bag to represent the go we have already had.  Now there are r+1 tiles in the bag.  How many ways are there of selecting r tiles?  This time the answer is r+1.  We write down r+1 as the second number in our sequence.

Every time we write down a number in the sequence we add another tile to the bag, so that the bag always contains the number of tiles we need plus the length of the sequence we have already written down. 

 

Suppose that r =0; we don’t want any tiles and we start with an empty bag.  Not a very challenging problem.  There can only be one way to select 0 tiles from a bag, however many tiles it contains, so the sequence is 1,1,1,1,…

Suppose that r=1.   The sequence is the number of ways of choosing 1 tile from a bag containing 1 tile, 2 tiles, 3 tiles, 4 tiles, and so on.  This gives 1, 2, 3, 4, 5, …

Suppose that r =2.  The sequence is the number of ways of choosing 2 tiles from a bag containing 2 tiles, 3 tiles, 4 tiles, and so on.  This gives 1, 3, 6, 10, 15, …

This gives us the sequences we are looking for.

 

We can write this more formally.  For an integer, r >= 0, define a sequence as follows:

Each entry is the number of ways of choosing r tiles from a bag containing (r+n) tiles, where n is the number of previous entries in the sequence.   

 

Clearly the sequence will always start with one.

Now imagine that, like me, you select one-too-many tiles by mistake and so have to throw one back in the bag.

We can work out the number of combinations as:

  (the number of ways of selecting one-too-many tiles)x(the number of ways of selecting the tile to throw back)/(the amount of double-counting)

 

The number of ways of selecting one-too-many tiles is the sum of the sequence so far. 

To see this lets assign each tile a unique rank from 1 to r+n.   The highest ranked tile that you select will be between r+1 and r+n.  If it is r+1 then the other selected tiles are precisely the r tiles of lower rank.  If it is r+2 then the other r selected tiles must come from the r+1 tiles of lower rank.  We consider all cases up to the highest ranked tile being r+n, in which case the other r tiles must come from the r+n-1 tiles of lower rank.  As we work through these cases we are selecting r tiles from r tiles, from r+1 tiles, from r+2 tiles and so on up to r+n-1 tiles.  The number of ways of doing this are given by the previous entries in the sequence.  So the total is the sum of the sequence so far.

 

The amount of double-counting is the length of the sequence so far.

To avoid double counting we must divide by the length of the sequence so far.  We can’t tell at the finish which tile was thrown back, it could have been any of the n rejected tiles left in the bag.   Each possibility represents a different route to get to the same outcome.   To avoid double-counting we must divide by n, which is also the length of the sequence so far.

 

Now we have the sum of the sequence so far divided by the length of the sequence so far, which gives the average of the sequence so far!

 

Finally  we had r+1 choices for the tile to throw back so we must multiply by r+1, a constant for the sequence.

 

Therefore each sequence can be generated by the rules: 

–          start with 1;

–          take the average so far and multiply by a constant.

 

And you thought Scrabble was a word game!

 

Do you think this counts as an intuitive explanation?  I have avoided using the formula for Pascal’s triangle but it still seems a bit complex to me.  I am not sure I could keep it all in my head as a single thought.

Is there a more intuitive explanation out there?