Cfrgtkky

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.

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.

Let the top row of the triangle be $b_n b_{n-1}ldots b_2 b_1 b_0$. Let us call your output string $a_n a_{n-1}ldots a_2 a_1 a_0$. If we follow your procedure we can see $$a_0=b_0\a_1=b_0+b_1\a_2=b_2+2b_1+b_0=b_2+b_0\
a_3=b_3+3b_2+3b_1+b_0=b_3+b_2+b_1+b_0\
a_4=b_4+4b_3+6b_2+4b_1+b_0=b_4+b_0\a_5=b_5+5b_4+10b_3+10b_2+5b_1+b_0=b_5+b_4+b_1+b_0\a_6=b_6+b_4+b_2+b_0\a_7=b_7+b_6+b_5+b_4+b_3+b_2+b_1+b_0\a_8=b_8+b_0$$
Where the coefficients in the middle are just the numbers of the corresponding rows of Pascal's triangle and the right side comes from reducing the coefficients $bmod 2$. The second line says we need $b_0=0$. The fourth then says $b_2=b_1$. The sixth says $b_4=b_1$ and the seventh $b_4=b_2$. The eighth gives $b_6+b_5+b_4+b_3=0$, so for five bits $frac 14$ of the strings will provide their own output, for six or seven $frac 18$ of the strings will provide their own output, and for eight or nine bits we have $frac 1{16}$ of all strings provide the same output.

Partial attempt:
It may help to try and write out expressions for the output string as a function of the input bits.

In your 5-bit example, let's say we label the bits from left to right as $b_0, b_1, b_2, b_3, b_4, b_5$.

Then the bottom bit in the triangle can be written as $b_0+b_4$, after a little bit of algebra. Now, for this bit to be equal to $b_0$, you must have $b_4=0$.

Similarly, the second output bit is given by $b_1+b_2+b_3+b_4$ and for this to be equal to $b_1$, you must have $b_2+b_3+b_4=0$. Since we already have $b_4=0$, this gives $b_2+b_3=0$.

The third output bit is $b_2+b_4 = b_2$, as desired.

The fourth output bit is $b_3+b_4 = b_3$, as desired.

the final output bit is $b_4 = b_4$ as desired.

So looks like the only constraints to emerge are $b_4=0$ and $b_2+b_3=0$. Thus, there are 8 such strings of length 5.

I am sure this approach can be generalized to arbitrary $n$, but I don't have a ready answer based on intuition.