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












1














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.










share|cite|improve this question





























    1














    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.










    share|cite|improve this question



























      1












      1








      1


      0





      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.










      share|cite|improve this question















      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.







      combinatorics discrete-mathematics graph-theory contest-math computer-science






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited 3 hours ago









      Daniel Mathias

      1806




      1806










      asked 3 hours ago









      Gimgim

      1146




      1146






















          3 Answers
          3






          active

          oldest

          votes


















          3














          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 eve 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



          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 "subtriangle" (where by subtriangle 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 right 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.






          share|cite|improve this answer























          • You say the far right corner will always agree, but actually the far right corner must be zero.
            – Mike Earnest
            1 hour ago












          • 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.
            – tch
            1 hour ago



















          2














          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.






          share|cite|improve this answer





















          • 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, ....
            – Gimgim
            56 mins ago










          • I agree that it is a better answer.
            – Ross Millikan
            16 mins ago



















          0














          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.






          share|cite|improve this answer























          • I think you should only have eight five bit strings. Each of your equations cuts the number in half from $32$
            – Ross Millikan
            1 hour ago










          • @RossMillikan Was a typo... fixed it. Thanks.
            – Aditya Dua
            1 hour ago











          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "69"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3061176%2fhow-many-of-these-strings-have-the-property-that-they-are-the-same-as-their-outp%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          3 Answers
          3






          active

          oldest

          votes








          3 Answers
          3






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          3














          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 eve 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



          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 "subtriangle" (where by subtriangle 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 right 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.






          share|cite|improve this answer























          • You say the far right corner will always agree, but actually the far right corner must be zero.
            – Mike Earnest
            1 hour ago












          • 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.
            – tch
            1 hour ago
















          3














          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 eve 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



          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 "subtriangle" (where by subtriangle 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 right 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.






          share|cite|improve this answer























          • You say the far right corner will always agree, but actually the far right corner must be zero.
            – Mike Earnest
            1 hour ago












          • 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.
            – tch
            1 hour ago














          3












          3








          3






          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 eve 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



          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 "subtriangle" (where by subtriangle 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 right 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.






          share|cite|improve this 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 eve 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



          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 "subtriangle" (where by subtriangle 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 right 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.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited 56 mins ago

























          answered 2 hours ago









          tch

          559210




          559210












          • You say the far right corner will always agree, but actually the far right corner must be zero.
            – Mike Earnest
            1 hour ago












          • 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.
            – tch
            1 hour ago


















          • You say the far right corner will always agree, but actually the far right corner must be zero.
            – Mike Earnest
            1 hour ago












          • 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.
            – tch
            1 hour ago
















          You say the far right corner will always agree, but actually the far right corner must be zero.
          – Mike Earnest
          1 hour ago






          You say the far right corner will always agree, but actually the far right corner must be zero.
          – Mike Earnest
          1 hour ago














          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.
          – tch
          1 hour ago




          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.
          – tch
          1 hour ago











          2














          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.






          share|cite|improve this answer





















          • 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, ....
            – Gimgim
            56 mins ago










          • I agree that it is a better answer.
            – Ross Millikan
            16 mins ago
















          2














          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.






          share|cite|improve this answer





















          • 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, ....
            – Gimgim
            56 mins ago










          • I agree that it is a better answer.
            – Ross Millikan
            16 mins ago














          2












          2








          2






          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.






          share|cite|improve this answer












          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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 1 hour ago









          Ross Millikan

          292k23197371




          292k23197371












          • 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, ....
            – Gimgim
            56 mins ago










          • I agree that it is a better answer.
            – Ross Millikan
            16 mins ago


















          • 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, ....
            – Gimgim
            56 mins ago










          • I agree that it is a better answer.
            – Ross Millikan
            16 mins ago
















          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, ....
          – Gimgim
          56 mins ago




          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, ....
          – Gimgim
          56 mins ago












          I agree that it is a better answer.
          – Ross Millikan
          16 mins ago




          I agree that it is a better answer.
          – Ross Millikan
          16 mins ago











          0














          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.






          share|cite|improve this answer























          • I think you should only have eight five bit strings. Each of your equations cuts the number in half from $32$
            – Ross Millikan
            1 hour ago










          • @RossMillikan Was a typo... fixed it. Thanks.
            – Aditya Dua
            1 hour ago
















          0














          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.






          share|cite|improve this answer























          • I think you should only have eight five bit strings. Each of your equations cuts the number in half from $32$
            – Ross Millikan
            1 hour ago










          • @RossMillikan Was a typo... fixed it. Thanks.
            – Aditya Dua
            1 hour ago














          0












          0








          0






          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.






          share|cite|improve this answer














          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.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited 1 hour ago

























          answered 3 hours ago









          Aditya Dua

          83918




          83918












          • I think you should only have eight five bit strings. Each of your equations cuts the number in half from $32$
            – Ross Millikan
            1 hour ago










          • @RossMillikan Was a typo... fixed it. Thanks.
            – Aditya Dua
            1 hour ago


















          • I think you should only have eight five bit strings. Each of your equations cuts the number in half from $32$
            – Ross Millikan
            1 hour ago










          • @RossMillikan Was a typo... fixed it. Thanks.
            – Aditya Dua
            1 hour ago
















          I think you should only have eight five bit strings. Each of your equations cuts the number in half from $32$
          – Ross Millikan
          1 hour ago




          I think you should only have eight five bit strings. Each of your equations cuts the number in half from $32$
          – Ross Millikan
          1 hour ago












          @RossMillikan Was a typo... fixed it. Thanks.
          – Aditya Dua
          1 hour ago




          @RossMillikan Was a typo... fixed it. Thanks.
          – Aditya Dua
          1 hour ago


















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Mathematics Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.





          Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


          Please pay close attention to the following guidance:


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3061176%2fhow-many-of-these-strings-have-the-property-that-they-are-the-same-as-their-outp%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          Ellipse (mathématiques)

          Quarter-circle Tiles

          Mont Emei