Puzzler -- Toy Blocks

Re: Puzzler -- Toy Blocks

Larry Barrett

I started with 1 block, 1 step, 1 way - B

Then 3 blocks, 2 steps, 2 ways, - BBG and BGB

Then 6 blocks, 3 steps, 7 ways - BBBGGO, BBBGOG, BBGGOB, BBGOGB, BBGOBG, BGOBGB, BGOBBG. If I did this correctly I observe that after the first BBB, I can use the 2 step solution and abbreviate these two ways as BBB(2 step solutions), or BBB(2); also after the last two ways, which can be BGO(2). So the # ways for 3 steps can be shown as 2+1+1+1+2 = 7

Next is the 10 block, 4 step solution. Some of the ways make use of the abbreviation technique for the 3 steps solution and the 2 step solutions:

BBBB(7), BBB(7)B, BB(2)BGBG, BB(2)BBGG, BGOR(7), BGB(2)GORO, BGB(2)GOOR. Total # ways = 7+7+2+2+7+2+2 = 29.

Pretty complicated. Probably some way to use factorials.

Re: Puzzler -- Toy Blocks

Larry Barrett

I am reasonably sure I got the correct count for the one block, one step - 1 way, and the three block, two step - 2 ways solutions. But there are more ways for the six block, three step solutions and then lots more ways for the 10 block, 4 step solutions.

For the six block 3 step solution I came up with these solutions:

BBBGGO, BBBGOG, BBGGOB, BBGOGB, BBGOBG, BGOBGB, BGOBBG

After thinking about this some more I can add BBGGBO, BBGBGO, BBGBOG and I am not sure this is all. About the only rule I can come up with is that in each sequence the number of blocks of the lower level color must always be >= the number of blocks of the next higher level color. So you can't have a sequence that starts out BGG... or BOG... for example.

Re: Puzzler -- Toy Blocks

Alex Y

I think there are way more possibilities than you have listed, but I haven't figured out how to determine the number. Here is how I am working it.

The blocks are attracted to both the wall and the floor, and the strength of that attraction doesn't matter, so I find it helpful to recast my mental image of the problem to avoid "favoring" gravity toward the floor. Here is my mental image, preserving the colors to tie back to the original.

One way to build the staircase is to build first a single stair, then to add two blocks to create a second stair, add three more to create a third stair, then the remaining 4.

Looking at my image, that is 1!=1 way to create the first step, the block with slanted blue strips.

There are 2!=2 ways of adding the blue horizontal and green horizontal to add the second step

There are 3!=6 ways of adding the vertically striped blocks to add the third step, and

4!=24 ways to add the 4th step.

So building the staircase following this process gives 1!x2!x3!x4!=288 alternatives.

But I haven't figured out how to enumerate the possibilities that do not follow this "rule", basically where a block or blocks are added before the previous layer (in my image) has been completed.

Hint

Alex Y

I couldn't figure this one out, but saw the solution. Below is a hint, followed by a start.

Hint: look at all the possible states the blocks could be in as the stairs are built, and the ways to reach those states.

Beginning

On the first row of a sheet of paper, draw all (one) ways the first block can be placed.

On the second row, draw both possible ways two blocks can be placed, and draw lines between the first row image and these.

On the third row, draw all three possible states for the blocks, and connect them with the states from the previous row from which they might have come. At this point you need to start writing in the counts-1 for the cases of three on the floor and three stacked, and 2 for the case of stairs.

On each subsequent row, the number of routes to a state is the sum of the numbers for each prior row state that could have led to it.

Be careful! I missed two of the seven possible states for six blocks and came up with an answer that was less than 1/2 of the correct answer.

Answer -- Toy Blocks

Alex Y

There are 768 orders in which you can put down those blocks to form the staircase.

Here is a diagram of all possible states of the staircase as it is being built, and the 768 routes from the first block being placed until the tenth is placed.

Re: Answer -- Toy Blocks

Larry Barrett

Pretty complicated.

It is interesting that there is left-to-right symmetry in the number of ways to add one more block as you go up, i.e. 1, 1 1, 1 2 1, 1 3 2 3 1, etc, sort of like Pascal's triangle.

Except in the 8th row where it is 70 56 90 42 56 70.

Re: Answer -- Toy Blocks

Alex Y

Yes, and the eighth row from the bottom is the first one that has two arrangements with "wall-to-floor" symmetry.

Actually, there is a formula for the number of ways to build this staircase, but first you need a definition i had never heard of.

The hook length of a block in the staircase is 1 + the number of blocks directly above it + the number of blocks directly to the right. E.g., the hook length of the second from bottom block against the wall is 1+2+2=5.

The formula for the number of ways to build the staircase is

(number of blocks)! / Product of all the hook lengths

=10! / (7 * 5^2 * 3^3 * 1^4)

This formula shows how quickly the number grows as the stairway gets taller: 16 for 3 steps, 768 for 4, and 292,864 for 5

Confirming that last one with a diagram is left as an exercise for the reader ;-)