MathDB

n

-stick is a connected figure consisting of

n

matches of length

1

which are placed horizontally or vertically and no two touch each other at points other than their ends. Two shapes that can be transformed into each other by moving, rotating or flipping are considered the same. An

n

-mino is a shape which is built by connecting

n

squares of side length 1 on their sides such that there's a path on the squares between each two squares of the

n

-mino. Let

S_n

be the number of

n

-sticks and

M_n

the number of

n

-minos, e.g.

S_3=5

And

M_3=2

. (a) Prove that for any natural

n

S_n \geq M_{n+1}

. (b) Prove that for large enough

n

we have

(2.4)^n \leq S_n \leq (16)^n

. A grid segment is a segment on the plane of length 1 which it's both ends are integer points. A polystick is called wise if using it and it's rotations or flips we can cover all grid segments without overlapping, otherwise it's called unwise. (c) Prove that there are at least

2^{n-6}

different unwise

n

-sticks. (d) Prove that any polystick which is in form of a path only going up and right is wise. (e) Extra points: Prove that for large enough

n

we have

3^n \leq S_n \leq 12^n

Time allowed for this exam was 2 hours.

Problem Statement