How Many Ways Can You Build A Staircase?

Riddler Express

This is the fourth and final week of CrossProduct™ puzzles — for now. This time, there are four four-digit numbers — each belongs in a row of the table below, with one digit per cell. The products of the four digits of each number are shown in the rightmost column. Meanwhile, the products of the digits in the thousands, hundreds, tens and ones places, respectively, are shown in the bottom row. Can you find all four four-digit numbers and complete the table?

Computational Solution

from z3 import *

class MysteriousNumbersSolver:
    def __init__(self):
        self.X = [[Int("self.X_%s_%s" % (i, j)) for j in range(4)]
                      for i in range(4)]
        self.s = Solver()
        self.s.add([And(0 <= self.X[i][j], self.X[i][j]<= 9) for i in range(4) for j in range(1,4)])
        self.s.add([And(0 <= self.X[i][0], self.X[i][0]<= 9) for i in range(4)])

    def set_constraints(self):   
        self.s.add(self.X[0][0]*self.X[0][1]*self.X[0][2]*self.X[0][3]==1458)
        self.s.add(self.X[1][0]*self.X[1][1]*self.X[1][2]*self.X[1][3]==128)
        self.s.add(self.X[2][0]*self.X[2][1]*self.X[2][2]*self.X[2][3]==2688)
        self.s.add(self.X[3][0]*self.X[3][1]*self.X[3][2]*self.X[3][3]==125)
        self.s.add(self.X[0][0]*self.X[1][0]*self.X[2][0]*self.X[3][0]==960)
        self.s.add(self.X[0][1]*self.X[1][1]*self.X[2][1]*self.X[3][1]==384)
        self.s.add(self.X[0][2]*self.X[1][2]*self.X[2][2]*self.X[3][2]==630)
        self.s.add(self.X[0][3]*self.X[1][3]*self.X[2][3]*self.X[3][3]==270)

    def output_solution(self):
        m = self.s.model()
        for i in range(4):
            print(" ".join([str(m.evaluate(self.X[i][j])) for j in range(4)]))

    def solve(self):
        self.set_constraints()
        if self.s.check() == sat:
            self.output_solution()
        else:
            print(self.s)
            print("Failed to solve.")

s = MysteriousNumbersSolver()
s.solve()

Here is the solution:

3 6 9 9
8 8 2 1
8 8 7 6
5 1 5 5

Riddler Classic

You have $10$ blocks with which to build four steps against a wall. The first step is one block high, the second is two blocks high, the third is three blocks high and the fourth is four blocks high.

However, the ground ever-so-slightly slopes down toward the wall, and both the floor and the blocks are a little bit slippery. As a result, whenever you place a block at ground level, it slides toward the wall until it hits the wall or another block. And when you place a block atop another block, it will similarly slide toward the wall until it hits the wall or another block.

Suppose the four blocks in the bottom row are labeled A, the three blocks in the second row are labeled B, the two blocks in the next row are labeled C and the topmost block is labeled D. One way to build the steps would be to place the blocks in the following order, one row at a time: A-A-A-A-B-B-B-C-C-D. You could alternatively place the blocks one column at a time: A-B-C-D-A-B-C-A-B-A. But you could not place them in the order A-B-B-A-A-A-B-C-C-D because that would mean at one point you have more blocks in the second row, B, than in the bottom row, A — a physical impossibility!

How many distinct ways are there to build these four steps using the $10$ blocks?

Extra credit: Suppose you have precisely enough blocks to build a staircase with $N$ stairs. How many distinct ways are there to build this staircase?

Computational Solution

Here is a brute force computational solution which gives $\bf{768}$ ways to build the staircase with $4$ steps and $10$ blocks.

from itertools import permutations

def valid_block_seqs(n):
    blocks = [(i,j) for i in range(1,n+2) for j in range(1, n-i+2)]
    sequences = []
    for seq in permutations(blocks[1:]):
        used = set([(1,1)] + [(0,i) for i in range(1, n+1)] + [(i,0) for i in range(1,n+1)])
        for (x,y) in seq:
            if (x-1, y) in used and (x, y-1) in used:
                used.add((x, y))
            else:
                break
        if len(used) == len(blocks) + 2*n:
            sequences.append([(1,1)] + list(seq))
    return sequences

print(len(valid_block_seqs(4)))

All the ways are listed below for those who are interested 😊.