How many of these strings have the property that they are the same as their output string

combinatoricscomputer sciencecontest-mathdiscrete mathematicsgraph theory

An input is a string of zeros and ones. Write down a row below it using the Pascal triangle rule, where each number is the sum of the two numbers diagonally above it. We are working “modulo $2$” so $1 + 1 = 0$. Repeat until you form a triangle of numbers. Here is an example, where the input is $10111$.

1----------0----------1---------1---------1
-----1----------1----------0---------0-----
----------0----------1----------0----------
---------------1----------1----------------
---------------------0---------------------

The output of this procedure is the string read along the side of the triangle from the bottom to the top right, in that order. In this case the output is $0 1 0 0 1$.
We decide to use a string of length $n$ as input, so there are $2^n$ possible input strings. How many of these strings have the property that they are the same as their output string?

My attempt

Fisrt I was trying to write the strings and wanted to check which pattern gives me the same output and which pattern will not.

First observation: if we start writting the string from the right if we get one number where it gives you wrong output(unequal) then there is no point to stretch it to left any further as the numbers are inductive. e.g: $11$ is wrong so $011$ or $….11$ will be wrong

2nd observation: We can't start with $1$ from the right if $n>1$

3rd observation:From the right we can go on putting (even)zeros and then if you put a single $1$ that is ok but you can't put more than then wrong
e.g: $1100,0100$ wrong.

This doesn't apply if we put odd zeros as $11000$ is right.

4th observation: If we put from right $0$ then $1$ and go on writing (even) 1 then we can alternate $0$ and $1$ after that and we can write same number of (even) zeros after (even) ones but we can't extend it any further e.g $1010110$,$00110$ are right but $000110$,$100110$ are wrong.

5th observation: If we put from right $0$ then $1$ and go on writing (odd) 1 then we are allowed to put only one zero after that and anything we put after that will give us wrong answer e.g $01110$ is right but both $101110$ and $001110$ are wrong.

But I can't see any general pattern please help.

Best Answer

Intuition

I think it helps to work from the far right corner. Now add a diagonal to the left. The patterns are like

0 0  1 0  0 1  1 1
 0    1    1    0

So, if we want to extend a triangle, we need only know the leftmost edge and the bottom entry. Every time the entry above our working entry is a 1, the sign of our next entry switches. This means we need an even number of 1s to have the new top entry match the bottom entry. If we do have an even number of 1s in the left column, it doesn't matter if we start with a 0 or a 1 on the bottom we will get the same thing at the top.

Example: In the below example we pick a 0 for the new bottom entry and observe that the new top entry is also a 0 (and that the number of ones in the new edge is still even).

1 1 0     1 1 0     1 1 0     1 1 0    0 1 1 0
 0 1       0 1       0 1     1 0 1      1 0 1
  1         1       1 1       1 1        1 1
           0         0         0          0

Answer ($ 2^{\lceil n/2 \rceil}$)

We first note that if a triangle's output matches its input, that this is true for every "sub triangle" (whereby sub triangle we mean a triangle you can get by deleting some of the columns from the left).

We will, therefore, induct on the size of the triangles, denoted $n$. Denote the number of "good" by $T_n$.

I claim that $T_n = 2^{\lceil n/2 \rceil}$. More specifically, if $n$ is even the $T_{n+1} = 2T_{n}$ and if $n$ is odd, $T_{n+1} = T_n$. Moreover, if $n$ is even, all of the triangles will have an even number of ones on the left size, and if $n$ is odd, half the triangles will have an even number of ones on the left side.

Proof:

  • $n$ is even: By hypothesis the left side of every triangle has an even number of ones. Therefore, for each triangle we will have two more triangles of size $n+1$ (corresponding to a 0 or a 1 in the new bottom point). However, the triangle corresponding to a 0 will have an odd number of ones.
  • $n$ is odd: By hypothesis, half the triangles have an odd number of ones on the left edge. These are never sub-triangles for larger triangles. Each of the triangles with an even number of ones on the left edge gives two new triangles of size $n+1$ (again corresponding to a 0 or a 1 in the new bottom point). However, this time, both new triangles have an even number of ones on the left side.
Related Question