Talks using just two words, such that the same thing is never said three times in a row
$begingroup$
A bit more than 20 years ago, the following exercise was assigned to a class as the Christmas holiday exercise. I did search for a while whether it was posted here earlier, and could not find it. I guess I might as well ask it as a New Year's Eve riddle here. It was in German; I hope I can translate it in such a way that its spirit is preserved.
Two politicians are arguing who of the two of them is able to give the longest talk, without saying the same thing three times in a row. There is a problem, however, they both do only know 2 words, namely 'but' (B) and 'if' (I).
The first one begins 'B', the second one replies 'BI' which is countered by 'BIIB'. The second politician is quite bright, he simply repeats literally the last talk given by the other one, then takes that talk again but interchanges B and I and appends the result of this operation to the first talk. His opponent realizes this strategy and proceeds in the same way. So we get talks
$$ B, B, I, BI, IB, BIIB, IBBI, BIIB IBBI, IBBIBIIB, ...$$
That is, the $k$-th talk $T_k$ has length $2^{k-1}$ and coincides with the first half of $T_{k+1}$.
A mathematician comes along, who has not much to contribute, either. But he solves the controversy in a mathematician's manner. He gives a talk $T$ of infinite length, such that the first $2^{k-1}$ words of $T$ agree with $T_k$. Afterwards (!) he leaves and leaves it to the politicians to prove that in his talk he had never said the same thing three times in a row, to be more precise, nowhere in his talk $T$ exists a segment $S$ of finite length which occurs three times as a sequence $SSS$ in $T$.
How do you prove this? :-)
puzzle
edited Jan 1 at 15:47
Blue
48.6k870156
$endgroup$
|
show 2 more comments
$begingroup$
A bit more than 20 years ago, the following exercise was assigned to a class as the Christmas holiday exercise. I did search for a while whether it was posted here earlier, and could not find it. I guess I might as well ask it as a New Year's Eve riddle here. It was in German; I hope I can translate it in such a way that its spirit is preserved.
Two politicians are arguing who of the two of them is able to give the longest talk, without saying the same thing three times in a row. There is a problem, however, they both do only know 2 words, namely 'but' (B) and 'if' (I).
The first one begins 'B', the second one replies 'BI' which is countered by 'BIIB'. The second politician is quite bright, he simply repeats literally the last talk given by the other one, then takes that talk again but interchanges B and I and appends the result of this operation to the first talk. His opponent realizes this strategy and proceeds in the same way. So we get talks
$$ B, B, I, BI, IB, BIIB, IBBI, BIIB IBBI, IBBIBIIB, ...$$
That is, the $k$-th talk $T_k$ has length $2^{k-1}$ and coincides with the first half of $T_{k+1}$.
A mathematician comes along, who has not much to contribute, either. But he solves the controversy in a mathematician's manner. He gives a talk $T$ of infinite length, such that the first $2^{k-1}$ words of $T$ agree with $T_k$. Afterwards (!) he leaves and leaves it to the politicians to prove that in his talk he had never said the same thing three times in a row, to be more precise, nowhere in his talk $T$ exists a segment $S$ of finite length which occurs three times as a sequence $SSS$ in $T$.
How do you prove this? :-)
puzzle
edited Jan 1 at 15:47
Blue
48.6k870156
$endgroup$
10
$begingroup$
This is the Thue-Morse sequence, q.v.
$endgroup$
– Gerry Myerson
Dec 31 '11 at 19:09
5
$begingroup$
This falls under the umbrella concept of combinatorics on words. This sequence if known as the Thue-Morse sequence. The latter Wikipedia page lists the 'cubefree' property, but without proof :-). Happy Sylvester/New Year to you all depending on your time zone (and time of reading)!
$endgroup$
– Jyrki Lahtonen
Dec 31 '11 at 19:13
3
$begingroup$
as one of my teachers once said: now it has a name and we need no longer be afraid of it ;-) I still don't know how to solve it..
$endgroup$
– user20266
Dec 31 '11 at 19:17
4
$begingroup$
cs.umb.edu/~offner/files/thue.pdf :) (Warning: Might contain spoilers ^^)
$endgroup$
– Listing
Dec 31 '11 at 19:18
1
$begingroup$
@Listing yes, it does. Contain spoilers, that is.
$endgroup$
– user20266
Dec 31 '11 at 19:54
|
show 2 more comments
$begingroup$
A bit more than 20 years ago, the following exercise was assigned to a class as the Christmas holiday exercise. I did search for a while whether it was posted here earlier, and could not find it. I guess I might as well ask it as a New Year's Eve riddle here. It was in German; I hope I can translate it in such a way that its spirit is preserved.
Two politicians are arguing who of the two of them is able to give the longest talk, without saying the same thing three times in a row. There is a problem, however, they both do only know 2 words, namely 'but' (B) and 'if' (I).
The first one begins 'B', the second one replies 'BI' which is countered by 'BIIB'. The second politician is quite bright, he simply repeats literally the last talk given by the other one, then takes that talk again but interchanges B and I and appends the result of this operation to the first talk. His opponent realizes this strategy and proceeds in the same way. So we get talks
$$ B, B, I, BI, IB, BIIB, IBBI, BIIB IBBI, IBBIBIIB, ...$$
That is, the $k$-th talk $T_k$ has length $2^{k-1}$ and coincides with the first half of $T_{k+1}$.
A mathematician comes along, who has not much to contribute, either. But he solves the controversy in a mathematician's manner. He gives a talk $T$ of infinite length, such that the first $2^{k-1}$ words of $T$ agree with $T_k$. Afterwards (!) he leaves and leaves it to the politicians to prove that in his talk he had never said the same thing three times in a row, to be more precise, nowhere in his talk $T$ exists a segment $S$ of finite length which occurs three times as a sequence $SSS$ in $T$.
How do you prove this? :-)
puzzle
edited Jan 1 at 15:47
Blue
48.6k870156
$endgroup$
A bit more than 20 years ago, the following exercise was assigned to a class as the Christmas holiday exercise. I did search for a while whether it was posted here earlier, and could not find it. I guess I might as well ask it as a New Year's Eve riddle here. It was in German; I hope I can translate it in such a way that its spirit is preserved.
Two politicians are arguing who of the two of them is able to give the longest talk, without saying the same thing three times in a row. There is a problem, however, they both do only know 2 words, namely 'but' (B) and 'if' (I).
The first one begins 'B', the second one replies 'BI' which is countered by 'BIIB'. The second politician is quite bright, he simply repeats literally the last talk given by the other one, then takes that talk again but interchanges B and I and appends the result of this operation to the first talk. His opponent realizes this strategy and proceeds in the same way. So we get talks
$$ B, B, I, BI, IB, BIIB, IBBI, BIIB IBBI, IBBIBIIB, ...$$
That is, the $k$-th talk $T_k$ has length $2^{k-1}$ and coincides with the first half of $T_{k+1}$.
A mathematician comes along, who has not much to contribute, either. But he solves the controversy in a mathematician's manner. He gives a talk $T$ of infinite length, such that the first $2^{k-1}$ words of $T$ agree with $T_k$. Afterwards (!) he leaves and leaves it to the politicians to prove that in his talk he had never said the same thing three times in a row, to be more precise, nowhere in his talk $T$ exists a segment $S$ of finite length which occurs three times as a sequence $SSS$ in $T$.
How do you prove this? :-)
puzzle
puzzle
edited Jan 1 at 15:47
Blue
48.6k870156
edited Jan 1 at 15:47
Blue
48.6k870156
edited Jan 1 at 15:47
Blue
48.6k870156
edited Jan 1 at 15:47
Blue
48.6k870156
edited Jan 1 at 15:47
Blue
48.6k870156
48.6k870156
asked Dec 31 '11 at 18:48
user20266
10
$begingroup$
This is the Thue-Morse sequence, q.v.
$endgroup$
– Gerry Myerson
Dec 31 '11 at 19:09
5
$begingroup$
This falls under the umbrella concept of combinatorics on words. This sequence if known as the Thue-Morse sequence. The latter Wikipedia page lists the 'cubefree' property, but without proof :-). Happy Sylvester/New Year to you all depending on your time zone (and time of reading)!
$endgroup$
– Jyrki Lahtonen
Dec 31 '11 at 19:13
3
$begingroup$
as one of my teachers once said: now it has a name and we need no longer be afraid of it ;-) I still don't know how to solve it..
$endgroup$
– user20266
Dec 31 '11 at 19:17
4
$begingroup$
cs.umb.edu/~offner/files/thue.pdf :) (Warning: Might contain spoilers ^^)
$endgroup$
– Listing
Dec 31 '11 at 19:18
1
$begingroup$
@Listing yes, it does. Contain spoilers, that is.
$endgroup$
– user20266
Dec 31 '11 at 19:54
|
show 2 more comments
10
$begingroup$
This is the Thue-Morse sequence, q.v.
$endgroup$
– Gerry Myerson
Dec 31 '11 at 19:09
5
$begingroup$
This falls under the umbrella concept of combinatorics on words. This sequence if known as the Thue-Morse sequence. The latter Wikipedia page lists the 'cubefree' property, but without proof :-). Happy Sylvester/New Year to you all depending on your time zone (and time of reading)!
$endgroup$
– Jyrki Lahtonen
Dec 31 '11 at 19:13
3
$begingroup$
as one of my teachers once said: now it has a name and we need no longer be afraid of it ;-) I still don't know how to solve it..
$endgroup$
– user20266
Dec 31 '11 at 19:17
4
$begingroup$
cs.umb.edu/~offner/files/thue.pdf :) (Warning: Might contain spoilers ^^)
$endgroup$
– Listing
Dec 31 '11 at 19:18
1
$begingroup$
@Listing yes, it does. Contain spoilers, that is.
$endgroup$
– user20266
Dec 31 '11 at 19:54
10
10
$begingroup$
This is the Thue-Morse sequence, q.v.
$endgroup$
– Gerry Myerson
Dec 31 '11 at 19:09
$begingroup$
This is the Thue-Morse sequence, q.v.
$endgroup$
– Gerry Myerson
Dec 31 '11 at 19:09
5
5
$begingroup$
This falls under the umbrella concept of combinatorics on words. This sequence if known as the Thue-Morse sequence. The latter Wikipedia page lists the 'cubefree' property, but without proof :-). Happy Sylvester/New Year to you all depending on your time zone (and time of reading)!
$endgroup$
– Jyrki Lahtonen
Dec 31 '11 at 19:13
$begingroup$
This falls under the umbrella concept of combinatorics on words. This sequence if known as the Thue-Morse sequence. The latter Wikipedia page lists the 'cubefree' property, but without proof :-). Happy Sylvester/New Year to you all depending on your time zone (and time of reading)!
$endgroup$
– Jyrki Lahtonen
Dec 31 '11 at 19:13
3
3
$begingroup$
as one of my teachers once said: now it has a name and we need no longer be afraid of it ;-) I still don't know how to solve it..
$endgroup$
– user20266
Dec 31 '11 at 19:17
$begingroup$
as one of my teachers once said: now it has a name and we need no longer be afraid of it ;-) I still don't know how to solve it..
$endgroup$
– user20266
Dec 31 '11 at 19:17
4
4
$begingroup$
cs.umb.edu/~offner/files/thue.pdf :) (Warning: Might contain spoilers ^^)
$endgroup$
– Listing
Dec 31 '11 at 19:18
$begingroup$
cs.umb.edu/~offner/files/thue.pdf :) (Warning: Might contain spoilers ^^)
$endgroup$
– Listing
Dec 31 '11 at 19:18
1
1
$begingroup$
@Listing yes, it does. Contain spoilers, that is.
$endgroup$
– user20266
Dec 31 '11 at 19:54
$begingroup$
@Listing yes, it does. Contain spoilers, that is.
$endgroup$
– user20266
Dec 31 '11 at 19:54
|
show 2 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Ah, a beautiful riddle.
The answer is the Thue-Morse sequence.
Defined as follows:
Starting with $a(0)$, $a(n)$ is equal to $B$ if $n$ has an odd number of $1$s in his binary representation, and $I$ otherwise.
The theorem (never saying the same thing thrice in a row) is a special case of "no overlaps", where overlap means $xAxAx$ where $x$ is a letter and $A$ is a (possibly empty) string of letters.
The proof of "no overlaps in the Thue-Morse sequence" is in this paper:
http://arxiv.org/abs/0706.0907.
If there is some nonempty string of letters $A$ that's said thrice in a row, $AAA$, then $A=xB$ where $x$ is the first letter of $A$ and $B$ is the rest of the string ($B$ might be empty), then there is $AAA=xBxBxB$, but even $xBxBx$ doesn't appear in the sequence, thus $xBxBxB=AAA$ doesn't appear.
edited Jan 1 at 15:34
Brahadeesh
6,42442363
answered Apr 20 '12 at 12:40
EkuurhEkuurh
17210
$endgroup$
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%2f95480%2ftalks-using-just-two-words-such-that-the-same-thing-is-never-said-three-times-i%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Ah, a beautiful riddle.
The answer is the Thue-Morse sequence.
Defined as follows:
Starting with $a(0)$, $a(n)$ is equal to $B$ if $n$ has an odd number of $1$s in his binary representation, and $I$ otherwise.
The theorem (never saying the same thing thrice in a row) is a special case of "no overlaps", where overlap means $xAxAx$ where $x$ is a letter and $A$ is a (possibly empty) string of letters.
The proof of "no overlaps in the Thue-Morse sequence" is in this paper:
http://arxiv.org/abs/0706.0907.
If there is some nonempty string of letters $A$ that's said thrice in a row, $AAA$, then $A=xB$ where $x$ is the first letter of $A$ and $B$ is the rest of the string ($B$ might be empty), then there is $AAA=xBxBxB$, but even $xBxBx$ doesn't appear in the sequence, thus $xBxBxB=AAA$ doesn't appear.
edited Jan 1 at 15:34
Brahadeesh
6,42442363
answered Apr 20 '12 at 12:40
EkuurhEkuurh
17210
$endgroup$
add a comment |
$begingroup$
Ah, a beautiful riddle.
The answer is the Thue-Morse sequence.
Defined as follows:
Starting with $a(0)$, $a(n)$ is equal to $B$ if $n$ has an odd number of $1$s in his binary representation, and $I$ otherwise.
The theorem (never saying the same thing thrice in a row) is a special case of "no overlaps", where overlap means $xAxAx$ where $x$ is a letter and $A$ is a (possibly empty) string of letters.
The proof of "no overlaps in the Thue-Morse sequence" is in this paper:
http://arxiv.org/abs/0706.0907.
If there is some nonempty string of letters $A$ that's said thrice in a row, $AAA$, then $A=xB$ where $x$ is the first letter of $A$ and $B$ is the rest of the string ($B$ might be empty), then there is $AAA=xBxBxB$, but even $xBxBx$ doesn't appear in the sequence, thus $xBxBxB=AAA$ doesn't appear.
edited Jan 1 at 15:34
Brahadeesh
6,42442363
answered Apr 20 '12 at 12:40
EkuurhEkuurh
17210
$endgroup$
add a comment |
$begingroup$
Ah, a beautiful riddle.
The answer is the Thue-Morse sequence.
Defined as follows:
Starting with $a(0)$, $a(n)$ is equal to $B$ if $n$ has an odd number of $1$s in his binary representation, and $I$ otherwise.
The theorem (never saying the same thing thrice in a row) is a special case of "no overlaps", where overlap means $xAxAx$ where $x$ is a letter and $A$ is a (possibly empty) string of letters.
The proof of "no overlaps in the Thue-Morse sequence" is in this paper:
http://arxiv.org/abs/0706.0907.
If there is some nonempty string of letters $A$ that's said thrice in a row, $AAA$, then $A=xB$ where $x$ is the first letter of $A$ and $B$ is the rest of the string ($B$ might be empty), then there is $AAA=xBxBxB$, but even $xBxBx$ doesn't appear in the sequence, thus $xBxBxB=AAA$ doesn't appear.
edited Jan 1 at 15:34
Brahadeesh
6,42442363
answered Apr 20 '12 at 12:40
EkuurhEkuurh
17210
$endgroup$
Ah, a beautiful riddle.
The answer is the Thue-Morse sequence.
Defined as follows:
Starting with $a(0)$, $a(n)$ is equal to $B$ if $n$ has an odd number of $1$s in his binary representation, and $I$ otherwise.
The theorem (never saying the same thing thrice in a row) is a special case of "no overlaps", where overlap means $xAxAx$ where $x$ is a letter and $A$ is a (possibly empty) string of letters.
The proof of "no overlaps in the Thue-Morse sequence" is in this paper:
http://arxiv.org/abs/0706.0907.
If there is some nonempty string of letters $A$ that's said thrice in a row, $AAA$, then $A=xB$ where $x$ is the first letter of $A$ and $B$ is the rest of the string ($B$ might be empty), then there is $AAA=xBxBxB$, but even $xBxBx$ doesn't appear in the sequence, thus $xBxBxB=AAA$ doesn't appear.
edited Jan 1 at 15:34
Brahadeesh
6,42442363
answered Apr 20 '12 at 12:40
EkuurhEkuurh
17210
edited Jan 1 at 15:34
Brahadeesh
6,42442363
edited Jan 1 at 15:34
Brahadeesh
6,42442363
edited Jan 1 at 15:34
Brahadeesh
6,42442363
6,42442363
answered Apr 20 '12 at 12:40
EkuurhEkuurh
17210
answered Apr 20 '12 at 12:40
EkuurhEkuurh
17210
answered Apr 20 '12 at 12:40
EkuurhEkuurh
17210
17210
add a comment |
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%2f95480%2ftalks-using-just-two-words-such-that-the-same-thing-is-never-said-three-times-i%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
10
$begingroup$
This is the Thue-Morse sequence, q.v.
$endgroup$
– Gerry Myerson
Dec 31 '11 at 19:09
5
$begingroup$
This falls under the umbrella concept of combinatorics on words. This sequence if known as the Thue-Morse sequence. The latter Wikipedia page lists the 'cubefree' property, but without proof :-). Happy Sylvester/New Year to you all depending on your time zone (and time of reading)!
$endgroup$
– Jyrki Lahtonen
Dec 31 '11 at 19:13
3
$begingroup$
as one of my teachers once said: now it has a name and we need no longer be afraid of it ;-) I still don't know how to solve it..
$endgroup$
– user20266
Dec 31 '11 at 19:17
4
$begingroup$
cs.umb.edu/~offner/files/thue.pdf :) (Warning: Might contain spoilers ^^)
$endgroup$
– Listing
Dec 31 '11 at 19:18
1
$begingroup$
@Listing yes, it does. Contain spoilers, that is.
$endgroup$
– user20266
Dec 31 '11 at 19:54