Mixing
How many of these strings have the property that they are the same as their output string?
$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.
combinatorics discrete-mathematics graph-theory contest-math computer-science
edited Jan 4 at 0:55
Daniel Mathias
61617
asked Jan 4 at 0:11
GimgimGimgim
1869
$endgroup$
add a comment |
$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.
combinatorics discrete-mathematics graph-theory contest-math computer-science
edited Jan 4 at 0:55
Daniel Mathias
61617
asked Jan 4 at 0:11
GimgimGimgim
1869
$endgroup$
add a comment |
$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.
combinatorics discrete-mathematics graph-theory contest-math computer-science
edited Jan 4 at 0:55
Daniel Mathias
61617
asked Jan 4 at 0:11
GimgimGimgim
1869
$endgroup$
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
combinatorics discrete-mathematics graph-theory contest-math computer-science
edited Jan 4 at 0:55
Daniel Mathias
61617
asked Jan 4 at 0:11
GimgimGimgim
1869
edited Jan 4 at 0:55
Daniel Mathias
61617
asked Jan 4 at 0:11
GimgimGimgim
1869
edited Jan 4 at 0:55
Daniel Mathias
61617
edited Jan 4 at 0:55
Daniel Mathias
61617
edited Jan 4 at 0:55
Daniel Mathias
61617
61617
asked Jan 4 at 0:11
GimgimGimgim
1869
asked Jan 4 at 0:11
GimgimGimgim
1869
asked Jan 4 at 0:11
GimgimGimgim
1869
1869
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$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 a0or a1in the new bottom point). However, the triangle corresponding to a0will 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 a0or a1in the new bottom point). However, this time, both new triangles have an even number of ones on the left side.
answered Jan 4 at 1:19
tchtch
739310
$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
add a comment |
$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.
answered Jan 4 at 2:30
Ross MillikanRoss Millikan
293k23197371
$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
add a comment |
$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.
answered Jan 4 at 1:01
Aditya DuaAditya Dua
97918
$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
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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 a0or a1in the new bottom point). However, the triangle corresponding to a0will 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 a0or a1in the new bottom point). However, this time, both new triangles have an even number of ones on the left side.
answered Jan 4 at 1:19
tchtch
739310
$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
add a comment |
$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 a0or a1in the new bottom point). However, the triangle corresponding to a0will 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 a0or a1in the new bottom point). However, this time, both new triangles have an even number of ones on the left side.
answered Jan 4 at 1:19
tchtch
739310
$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
add a comment |
$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 a0or a1in the new bottom point). However, the triangle corresponding to a0will 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 a0or a1in the new bottom point). However, this time, both new triangles have an even number of ones on the left side.
answered Jan 4 at 1:19
tchtch
739310
$endgroup$
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 a0or a1in the new bottom point). However, the triangle corresponding to a0will 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 a0or a1in the new bottom point). However, this time, both new triangles have an even number of ones on the left side.
answered Jan 4 at 1:19
tchtch
739310
edited Jan 7 at 23:56
answered Jan 4 at 1:19
tchtch
739310
answered Jan 4 at 1:19
tchtch
739310
answered Jan 4 at 1:19
tchtch
739310
739310
$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
add a comment |
$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
$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$
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
$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
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
$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
add a comment |
$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.
answered Jan 4 at 2:30
Ross MillikanRoss Millikan
293k23197371
$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
add a comment |
$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.
answered Jan 4 at 2:30
Ross MillikanRoss Millikan
293k23197371
$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
add a comment |
$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.
answered Jan 4 at 2:30
Ross MillikanRoss Millikan
293k23197371
$endgroup$
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.
answered Jan 4 at 2:30
Ross MillikanRoss Millikan
293k23197371
answered Jan 4 at 2:30
Ross MillikanRoss Millikan
293k23197371
answered Jan 4 at 2:30
Ross MillikanRoss Millikan
293k23197371
answered Jan 4 at 2:30
Ross MillikanRoss Millikan
293k23197371
293k23197371
$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
add a comment |
$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
$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$
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
$begingroup$
I agree that it is a better answer.
$endgroup$
– Ross Millikan
Jan 4 at 3:48
add a comment |
$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.
answered Jan 4 at 1:01
Aditya DuaAditya Dua
97918
$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
add a comment |
$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.
answered Jan 4 at 1:01
Aditya DuaAditya Dua
97918
$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
add a comment |
$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.
answered Jan 4 at 1:01
Aditya DuaAditya Dua
97918
$endgroup$
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.
answered Jan 4 at 1:01
Aditya DuaAditya Dua
97918
edited Jan 4 at 3:03
answered Jan 4 at 1:01
Aditya DuaAditya Dua
97918
answered Jan 4 at 1:01
Aditya DuaAditya Dua
97918
answered Jan 4 at 1:01
Aditya DuaAditya Dua
97918
97918
$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
add a comment |
$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
$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$
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
$begingroup$
@RossMillikan Was a typo... fixed it. Thanks.
$endgroup$
– Aditya Dua
Jan 4 at 3:04
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
