2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ You say the far right corner will always agree, but actually the far right corner must be zero. $\endgroup$ – Mike Earnest Jan 4 at 2:59
  • $\begingroup$ If $n=1$ the right point can be one, and then when you move to $n=2$ half the triangles are dropped (see odd case in proof). So for $n>1$ the right entry must be 0$ but I think I have accounted for this. $\endgroup$ – tch Jan 4 at 3:03
  • 1
    $\begingroup$ Don't know if you noticed, but since this is XOR, the rule is true no matter which of three orientations you view it in. $\endgroup$ – Haakon Dahl Jan 4 at 5:57
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi, I got the point of your answer. Thanks for such a lucid explanation. I will also ask you if I have any question later. I am accepting tch's answer as he is apparently new and I think that after a 292k point, 23 gold,196 silver and 371 bronze badges you really care for +15 points. +10 respectful upvote to your answer for sure. Regards, .... $\endgroup$ – Gimgim Jan 4 at 3:08
  • $\begingroup$ I agree that it is a better answer. $\endgroup$ – Ross Millikan Jan 4 at 3:48
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you should only have eight five bit strings. Each of your equations cuts the number in half from $32$ $\endgroup$ – Ross Millikan Jan 4 at 2:27
  • $\begingroup$ @RossMillikan Was a typo... fixed it. Thanks. $\endgroup$ – Aditya Dua Jan 4 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.