Mixing
Applied Set Theory
$begingroup$
I have a somewhat obscure set theory question, which may or may not have an answer.
Let $A$ be the set of all integers from $0$ to $2n-1$, where $n in Bbb{N}$. Let $B={{b_0,b_1,b_2,dots,bn}}$ contain $n$ unique arbitrary elements of A. Let $C=A setminus B={{c_0,c_1,c_2,dots,c_n}}.$
(Note: $A = B cup C$)
$D={{(b_0+k)pmod{2n}, (b_1+k)pmod{2n}, (b_2+k)pmod{2n},dots,(b_n+k) pmod{2n}}}$ where $k in Bbb{Z}$. Under what conditions would $D=C$?
It's easy to come up with examples where this holds true, and it's easy to come up with examples where there does not exist an integer $k$ whereby $D=C$, but I'm having trouble generalising the conditions required for the elements of B such that it is necessarily true.
For the purpose of context, I'm trying to come up with an analytic way of determining whether a tone row (in music) is palindromic (ie. a palindrome) or not. If you ascribe a number to each of the musical notes ($0$ through $2n-1$), you can think of that as the original set of $12$ notes (for $n=6$).
$B$ is like the semi-tone row, and if there is another tone row that is a transposition of $B$ (this would be $D$), that also complements $A$ (this would be $C$), then the semi-tone row could be used to create a palindromic tone row.
It wouldn't be hard to have a computer iterate a given solution, however, I would be interested in seeing if there is a more analytic solution.
Thank you!
combinatorics number-theory
edited Jan 30 at 5:51
toric_actions
1108
asked Jan 29 at 15:55
AMacDonaldAMacDonald
6
$endgroup$
add a comment |
$begingroup$
I have a somewhat obscure set theory question, which may or may not have an answer.
Let $A$ be the set of all integers from $0$ to $2n-1$, where $n in Bbb{N}$. Let $B={{b_0,b_1,b_2,dots,bn}}$ contain $n$ unique arbitrary elements of A. Let $C=A setminus B={{c_0,c_1,c_2,dots,c_n}}.$
(Note: $A = B cup C$)
$D={{(b_0+k)pmod{2n}, (b_1+k)pmod{2n}, (b_2+k)pmod{2n},dots,(b_n+k) pmod{2n}}}$ where $k in Bbb{Z}$. Under what conditions would $D=C$?
It's easy to come up with examples where this holds true, and it's easy to come up with examples where there does not exist an integer $k$ whereby $D=C$, but I'm having trouble generalising the conditions required for the elements of B such that it is necessarily true.
For the purpose of context, I'm trying to come up with an analytic way of determining whether a tone row (in music) is palindromic (ie. a palindrome) or not. If you ascribe a number to each of the musical notes ($0$ through $2n-1$), you can think of that as the original set of $12$ notes (for $n=6$).
$B$ is like the semi-tone row, and if there is another tone row that is a transposition of $B$ (this would be $D$), that also complements $A$ (this would be $C$), then the semi-tone row could be used to create a palindromic tone row.
It wouldn't be hard to have a computer iterate a given solution, however, I would be interested in seeing if there is a more analytic solution.
Thank you!
combinatorics number-theory
edited Jan 30 at 5:51
toric_actions
1108
asked Jan 29 at 15:55
AMacDonaldAMacDonald
6
$endgroup$
$begingroup$
Please edit the title: it's not a set theory question!
$endgroup$
– YuiTo Cheng
Jan 30 at 7:39
add a comment |
$begingroup$
I have a somewhat obscure set theory question, which may or may not have an answer.
Let $A$ be the set of all integers from $0$ to $2n-1$, where $n in Bbb{N}$. Let $B={{b_0,b_1,b_2,dots,bn}}$ contain $n$ unique arbitrary elements of A. Let $C=A setminus B={{c_0,c_1,c_2,dots,c_n}}.$
(Note: $A = B cup C$)
$D={{(b_0+k)pmod{2n}, (b_1+k)pmod{2n}, (b_2+k)pmod{2n},dots,(b_n+k) pmod{2n}}}$ where $k in Bbb{Z}$. Under what conditions would $D=C$?
It's easy to come up with examples where this holds true, and it's easy to come up with examples where there does not exist an integer $k$ whereby $D=C$, but I'm having trouble generalising the conditions required for the elements of B such that it is necessarily true.
For the purpose of context, I'm trying to come up with an analytic way of determining whether a tone row (in music) is palindromic (ie. a palindrome) or not. If you ascribe a number to each of the musical notes ($0$ through $2n-1$), you can think of that as the original set of $12$ notes (for $n=6$).
$B$ is like the semi-tone row, and if there is another tone row that is a transposition of $B$ (this would be $D$), that also complements $A$ (this would be $C$), then the semi-tone row could be used to create a palindromic tone row.
It wouldn't be hard to have a computer iterate a given solution, however, I would be interested in seeing if there is a more analytic solution.
Thank you!
combinatorics number-theory
edited Jan 30 at 5:51
toric_actions
1108
asked Jan 29 at 15:55
AMacDonaldAMacDonald
6
$endgroup$
I have a somewhat obscure set theory question, which may or may not have an answer.
Let $A$ be the set of all integers from $0$ to $2n-1$, where $n in Bbb{N}$. Let $B={{b_0,b_1,b_2,dots,bn}}$ contain $n$ unique arbitrary elements of A. Let $C=A setminus B={{c_0,c_1,c_2,dots,c_n}}.$
(Note: $A = B cup C$)
$D={{(b_0+k)pmod{2n}, (b_1+k)pmod{2n}, (b_2+k)pmod{2n},dots,(b_n+k) pmod{2n}}}$ where $k in Bbb{Z}$. Under what conditions would $D=C$?
It's easy to come up with examples where this holds true, and it's easy to come up with examples where there does not exist an integer $k$ whereby $D=C$, but I'm having trouble generalising the conditions required for the elements of B such that it is necessarily true.
For the purpose of context, I'm trying to come up with an analytic way of determining whether a tone row (in music) is palindromic (ie. a palindrome) or not. If you ascribe a number to each of the musical notes ($0$ through $2n-1$), you can think of that as the original set of $12$ notes (for $n=6$).
$B$ is like the semi-tone row, and if there is another tone row that is a transposition of $B$ (this would be $D$), that also complements $A$ (this would be $C$), then the semi-tone row could be used to create a palindromic tone row.
It wouldn't be hard to have a computer iterate a given solution, however, I would be interested in seeing if there is a more analytic solution.
Thank you!
combinatorics number-theory
combinatorics number-theory
edited Jan 30 at 5:51
toric_actions
1108
asked Jan 29 at 15:55
AMacDonaldAMacDonald
6
edited Jan 30 at 5:51
toric_actions
1108
asked Jan 29 at 15:55
AMacDonaldAMacDonald
6
edited Jan 30 at 5:51
toric_actions
1108
edited Jan 30 at 5:51
toric_actions
1108
edited Jan 30 at 5:51
toric_actions
1108
1108
asked Jan 29 at 15:55
AMacDonaldAMacDonald
6
asked Jan 29 at 15:55
AMacDonaldAMacDonald
6
asked Jan 29 at 15:55
AMacDonaldAMacDonald
6
6
$begingroup$
Please edit the title: it's not a set theory question!
$endgroup$
– YuiTo Cheng
Jan 30 at 7:39
add a comment |
$begingroup$
Please edit the title: it's not a set theory question!
$endgroup$
– YuiTo Cheng
Jan 30 at 7:39
$begingroup$
Please edit the title: it's not a set theory question!
$endgroup$
– YuiTo Cheng
Jan 30 at 7:39
$begingroup$
Please edit the title: it's not a set theory question!
$endgroup$
– YuiTo Cheng
Jan 30 at 7:39
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
For $B$, you say it contains $n$ elements, but define it as $B = left{b_0,b_1,ldots,b_n right}$ which contains $n + 1$ elements. I believe based on $A$ containing $2n$ elements that you mean both $B$ and $C$ are to contain $n$ elements. To make things simpler, I will continue to have the index start at $0$, but have it end at index $n - 1$, for both sets.
With sets, the order of elements doesn't matter. However, to help solve the problem, consider all $b_i$ and $c_i$ to be in increasing order. Also, let $d_i$ be the elements of your set $D$.
You ask for a "more analytical solution". The following describes what is required in a fairly efficient mechanism to determine your answer, with it being about as analytical as I believe it's possible to be in general. However, I can't guarantee it, so perhaps somebody can provide you with a more analytical answer. Otherwise, if your computer implementation doesn't already use this, then you may wish to change it to do so.
First, define the difference function on the set elements of $B$ to be
$$B_1left(iright) =
begin{cases}
b_{i + 1} - b_{i} & 0 le i lt n - 1 \
left(b_0 + 2nright) - b_{i} & i = n - 1
end{cases} tag{1}label{eq1}$$
Similarly, define the difference function on the set elements of $C$ to be
$$C_1left(iright) =
begin{cases}
c_{i + 1} - c_{i} & 0 le i lt n - 1 \
left(c_0 + 2nright) - c_{i} & i = n - 1
end{cases} tag{2}label{eq2}$$
Next, define the set $E$ where each element $e_i$ is $B_1left(iright)$ and the set $F$ where each element $f_i$ is $C_1left(iright)$
To determine whether or not $D = C$ for some $k$, you need to check for $F$ being a shifted version of $E$. In particular, find all $i$ where $e_0 = f_i$. For each such $i$, check if all next differences of $E$ matches those of $F$, with wrapping when reach $n - 1$. In other words, see if $e_i = f_{left(i + jright) pmod{n}}$ for all $0 le j le n - 1$. A value of $k$ which may work can be found if and only if you have found such an $i$ for all of these differences to match. In the case where there is such an $i$, then any $k equiv c_i - b_0 pmod{2n}$ will work to determine the $d_m$ values for $0 le m le n - 1$.
To see why this works, consider your $d_m$ values for a given value of $k$. They will keep increasing until possibly the remainder goes to a value less than the previous value. This can only happen at most once. This is the point where the matching set values in $C$ much have reached the end. To match each such set value, the differences must match, which is why I am using eqref{eq1} and eqref{eq2} to do this checking through $E$ and $F$.
I hope this explanation is clear enough. To help see this, consider an example for $n = 4$ of $B = left{1, 4, 6, 7right}$ and $C = left{0, 2, 3, 5right}$. In this case, $E = left{3, 2, 1, 2right}$ and $F = left{2, 1, 2, 3right}$. It's fairly easy to see visually that $F$ is $E$ shifted to the left by $1$ element, with the first element going to the end. Thus, in this case, any $k$ where $k equiv c_4 - b_0 = 5 - 1 = 4 pmod{2n}$ will give that $D = C$. In particular, let $k = 4$. Then, $d_0 = 1 + 4 equiv 5 pmod 8$, $d_1 = 4 + 4 equiv 0 pmod 8$, $d_2 = 6 + 4 equiv 2 pmod 8$ and $d_3 = 7 + 4 equiv 3 pmod 8$. Putting this together, $D = left{5, 0, 2, 3right}$ which is the same as $C$ but in a different order, i.e., where the last element is moved to the front.
Next, consider $B = left{1, 4, 5, 7right}$ and $C = left{0, 2, 3, 6right}$. In this case, $E = left{3, 1, 2, 2right}$ and $F = left{2, 1, 3, 2right}$. Here, $e_0$ only matches $f_2$, but $e_1 neq f_3$. As the values don't match, there is no value of $k$ for which $D = C$. You can verify this, if you wish, manually by going through all $k$ from $0$ to $7$, inclusive, or programmatically.
In general, for anything other than relatively small values of $n$, it will not be easy to solve this manually, but certain cases where $D neq C$ are possible to quite quickly verify. Nonetheless, even for relatively large values of $n$, this should be a relatively fast algorithm to run on a computer.
Note there are a few small enhancements you can make, including if checking manually. For example, you can keep track of how many elements of $E$ are $1, 2, ...$, and likewise for $F$. If any counts don't match between the $2$ sets, then you know that $D neq C$ always, but there may also be cases where the counts all match but where there is still no $k$ which can be used. Another enhancement is that you only need to check for $n - 1$ differences matching between $E$ and $F$ as the last difference would then need to match as well since the sums of the differences is always $2n$.
answered Jan 30 at 5:32
John OmielanJohn Omielan
4,4762215
$endgroup$
add a comment |
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%2f3092334%2fapplied-set-theory%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$
For $B$, you say it contains $n$ elements, but define it as $B = left{b_0,b_1,ldots,b_n right}$ which contains $n + 1$ elements. I believe based on $A$ containing $2n$ elements that you mean both $B$ and $C$ are to contain $n$ elements. To make things simpler, I will continue to have the index start at $0$, but have it end at index $n - 1$, for both sets.
With sets, the order of elements doesn't matter. However, to help solve the problem, consider all $b_i$ and $c_i$ to be in increasing order. Also, let $d_i$ be the elements of your set $D$.
You ask for a "more analytical solution". The following describes what is required in a fairly efficient mechanism to determine your answer, with it being about as analytical as I believe it's possible to be in general. However, I can't guarantee it, so perhaps somebody can provide you with a more analytical answer. Otherwise, if your computer implementation doesn't already use this, then you may wish to change it to do so.
First, define the difference function on the set elements of $B$ to be
$$B_1left(iright) =
begin{cases}
b_{i + 1} - b_{i} & 0 le i lt n - 1 \
left(b_0 + 2nright) - b_{i} & i = n - 1
end{cases} tag{1}label{eq1}$$
Similarly, define the difference function on the set elements of $C$ to be
$$C_1left(iright) =
begin{cases}
c_{i + 1} - c_{i} & 0 le i lt n - 1 \
left(c_0 + 2nright) - c_{i} & i = n - 1
end{cases} tag{2}label{eq2}$$
Next, define the set $E$ where each element $e_i$ is $B_1left(iright)$ and the set $F$ where each element $f_i$ is $C_1left(iright)$
To determine whether or not $D = C$ for some $k$, you need to check for $F$ being a shifted version of $E$. In particular, find all $i$ where $e_0 = f_i$. For each such $i$, check if all next differences of $E$ matches those of $F$, with wrapping when reach $n - 1$. In other words, see if $e_i = f_{left(i + jright) pmod{n}}$ for all $0 le j le n - 1$. A value of $k$ which may work can be found if and only if you have found such an $i$ for all of these differences to match. In the case where there is such an $i$, then any $k equiv c_i - b_0 pmod{2n}$ will work to determine the $d_m$ values for $0 le m le n - 1$.
To see why this works, consider your $d_m$ values for a given value of $k$. They will keep increasing until possibly the remainder goes to a value less than the previous value. This can only happen at most once. This is the point where the matching set values in $C$ much have reached the end. To match each such set value, the differences must match, which is why I am using eqref{eq1} and eqref{eq2} to do this checking through $E$ and $F$.
I hope this explanation is clear enough. To help see this, consider an example for $n = 4$ of $B = left{1, 4, 6, 7right}$ and $C = left{0, 2, 3, 5right}$. In this case, $E = left{3, 2, 1, 2right}$ and $F = left{2, 1, 2, 3right}$. It's fairly easy to see visually that $F$ is $E$ shifted to the left by $1$ element, with the first element going to the end. Thus, in this case, any $k$ where $k equiv c_4 - b_0 = 5 - 1 = 4 pmod{2n}$ will give that $D = C$. In particular, let $k = 4$. Then, $d_0 = 1 + 4 equiv 5 pmod 8$, $d_1 = 4 + 4 equiv 0 pmod 8$, $d_2 = 6 + 4 equiv 2 pmod 8$ and $d_3 = 7 + 4 equiv 3 pmod 8$. Putting this together, $D = left{5, 0, 2, 3right}$ which is the same as $C$ but in a different order, i.e., where the last element is moved to the front.
Next, consider $B = left{1, 4, 5, 7right}$ and $C = left{0, 2, 3, 6right}$. In this case, $E = left{3, 1, 2, 2right}$ and $F = left{2, 1, 3, 2right}$. Here, $e_0$ only matches $f_2$, but $e_1 neq f_3$. As the values don't match, there is no value of $k$ for which $D = C$. You can verify this, if you wish, manually by going through all $k$ from $0$ to $7$, inclusive, or programmatically.
In general, for anything other than relatively small values of $n$, it will not be easy to solve this manually, but certain cases where $D neq C$ are possible to quite quickly verify. Nonetheless, even for relatively large values of $n$, this should be a relatively fast algorithm to run on a computer.
Note there are a few small enhancements you can make, including if checking manually. For example, you can keep track of how many elements of $E$ are $1, 2, ...$, and likewise for $F$. If any counts don't match between the $2$ sets, then you know that $D neq C$ always, but there may also be cases where the counts all match but where there is still no $k$ which can be used. Another enhancement is that you only need to check for $n - 1$ differences matching between $E$ and $F$ as the last difference would then need to match as well since the sums of the differences is always $2n$.
answered Jan 30 at 5:32
John OmielanJohn Omielan
4,4762215
$endgroup$
add a comment |
$begingroup$
For $B$, you say it contains $n$ elements, but define it as $B = left{b_0,b_1,ldots,b_n right}$ which contains $n + 1$ elements. I believe based on $A$ containing $2n$ elements that you mean both $B$ and $C$ are to contain $n$ elements. To make things simpler, I will continue to have the index start at $0$, but have it end at index $n - 1$, for both sets.
With sets, the order of elements doesn't matter. However, to help solve the problem, consider all $b_i$ and $c_i$ to be in increasing order. Also, let $d_i$ be the elements of your set $D$.
You ask for a "more analytical solution". The following describes what is required in a fairly efficient mechanism to determine your answer, with it being about as analytical as I believe it's possible to be in general. However, I can't guarantee it, so perhaps somebody can provide you with a more analytical answer. Otherwise, if your computer implementation doesn't already use this, then you may wish to change it to do so.
First, define the difference function on the set elements of $B$ to be
$$B_1left(iright) =
begin{cases}
b_{i + 1} - b_{i} & 0 le i lt n - 1 \
left(b_0 + 2nright) - b_{i} & i = n - 1
end{cases} tag{1}label{eq1}$$
Similarly, define the difference function on the set elements of $C$ to be
$$C_1left(iright) =
begin{cases}
c_{i + 1} - c_{i} & 0 le i lt n - 1 \
left(c_0 + 2nright) - c_{i} & i = n - 1
end{cases} tag{2}label{eq2}$$
Next, define the set $E$ where each element $e_i$ is $B_1left(iright)$ and the set $F$ where each element $f_i$ is $C_1left(iright)$
To determine whether or not $D = C$ for some $k$, you need to check for $F$ being a shifted version of $E$. In particular, find all $i$ where $e_0 = f_i$. For each such $i$, check if all next differences of $E$ matches those of $F$, with wrapping when reach $n - 1$. In other words, see if $e_i = f_{left(i + jright) pmod{n}}$ for all $0 le j le n - 1$. A value of $k$ which may work can be found if and only if you have found such an $i$ for all of these differences to match. In the case where there is such an $i$, then any $k equiv c_i - b_0 pmod{2n}$ will work to determine the $d_m$ values for $0 le m le n - 1$.
To see why this works, consider your $d_m$ values for a given value of $k$. They will keep increasing until possibly the remainder goes to a value less than the previous value. This can only happen at most once. This is the point where the matching set values in $C$ much have reached the end. To match each such set value, the differences must match, which is why I am using eqref{eq1} and eqref{eq2} to do this checking through $E$ and $F$.
I hope this explanation is clear enough. To help see this, consider an example for $n = 4$ of $B = left{1, 4, 6, 7right}$ and $C = left{0, 2, 3, 5right}$. In this case, $E = left{3, 2, 1, 2right}$ and $F = left{2, 1, 2, 3right}$. It's fairly easy to see visually that $F$ is $E$ shifted to the left by $1$ element, with the first element going to the end. Thus, in this case, any $k$ where $k equiv c_4 - b_0 = 5 - 1 = 4 pmod{2n}$ will give that $D = C$. In particular, let $k = 4$. Then, $d_0 = 1 + 4 equiv 5 pmod 8$, $d_1 = 4 + 4 equiv 0 pmod 8$, $d_2 = 6 + 4 equiv 2 pmod 8$ and $d_3 = 7 + 4 equiv 3 pmod 8$. Putting this together, $D = left{5, 0, 2, 3right}$ which is the same as $C$ but in a different order, i.e., where the last element is moved to the front.
Next, consider $B = left{1, 4, 5, 7right}$ and $C = left{0, 2, 3, 6right}$. In this case, $E = left{3, 1, 2, 2right}$ and $F = left{2, 1, 3, 2right}$. Here, $e_0$ only matches $f_2$, but $e_1 neq f_3$. As the values don't match, there is no value of $k$ for which $D = C$. You can verify this, if you wish, manually by going through all $k$ from $0$ to $7$, inclusive, or programmatically.
In general, for anything other than relatively small values of $n$, it will not be easy to solve this manually, but certain cases where $D neq C$ are possible to quite quickly verify. Nonetheless, even for relatively large values of $n$, this should be a relatively fast algorithm to run on a computer.
Note there are a few small enhancements you can make, including if checking manually. For example, you can keep track of how many elements of $E$ are $1, 2, ...$, and likewise for $F$. If any counts don't match between the $2$ sets, then you know that $D neq C$ always, but there may also be cases where the counts all match but where there is still no $k$ which can be used. Another enhancement is that you only need to check for $n - 1$ differences matching between $E$ and $F$ as the last difference would then need to match as well since the sums of the differences is always $2n$.
answered Jan 30 at 5:32
John OmielanJohn Omielan
4,4762215
$endgroup$
add a comment |
$begingroup$
For $B$, you say it contains $n$ elements, but define it as $B = left{b_0,b_1,ldots,b_n right}$ which contains $n + 1$ elements. I believe based on $A$ containing $2n$ elements that you mean both $B$ and $C$ are to contain $n$ elements. To make things simpler, I will continue to have the index start at $0$, but have it end at index $n - 1$, for both sets.
With sets, the order of elements doesn't matter. However, to help solve the problem, consider all $b_i$ and $c_i$ to be in increasing order. Also, let $d_i$ be the elements of your set $D$.
You ask for a "more analytical solution". The following describes what is required in a fairly efficient mechanism to determine your answer, with it being about as analytical as I believe it's possible to be in general. However, I can't guarantee it, so perhaps somebody can provide you with a more analytical answer. Otherwise, if your computer implementation doesn't already use this, then you may wish to change it to do so.
First, define the difference function on the set elements of $B$ to be
$$B_1left(iright) =
begin{cases}
b_{i + 1} - b_{i} & 0 le i lt n - 1 \
left(b_0 + 2nright) - b_{i} & i = n - 1
end{cases} tag{1}label{eq1}$$
Similarly, define the difference function on the set elements of $C$ to be
$$C_1left(iright) =
begin{cases}
c_{i + 1} - c_{i} & 0 le i lt n - 1 \
left(c_0 + 2nright) - c_{i} & i = n - 1
end{cases} tag{2}label{eq2}$$
Next, define the set $E$ where each element $e_i$ is $B_1left(iright)$ and the set $F$ where each element $f_i$ is $C_1left(iright)$
To determine whether or not $D = C$ for some $k$, you need to check for $F$ being a shifted version of $E$. In particular, find all $i$ where $e_0 = f_i$. For each such $i$, check if all next differences of $E$ matches those of $F$, with wrapping when reach $n - 1$. In other words, see if $e_i = f_{left(i + jright) pmod{n}}$ for all $0 le j le n - 1$. A value of $k$ which may work can be found if and only if you have found such an $i$ for all of these differences to match. In the case where there is such an $i$, then any $k equiv c_i - b_0 pmod{2n}$ will work to determine the $d_m$ values for $0 le m le n - 1$.
To see why this works, consider your $d_m$ values for a given value of $k$. They will keep increasing until possibly the remainder goes to a value less than the previous value. This can only happen at most once. This is the point where the matching set values in $C$ much have reached the end. To match each such set value, the differences must match, which is why I am using eqref{eq1} and eqref{eq2} to do this checking through $E$ and $F$.
I hope this explanation is clear enough. To help see this, consider an example for $n = 4$ of $B = left{1, 4, 6, 7right}$ and $C = left{0, 2, 3, 5right}$. In this case, $E = left{3, 2, 1, 2right}$ and $F = left{2, 1, 2, 3right}$. It's fairly easy to see visually that $F$ is $E$ shifted to the left by $1$ element, with the first element going to the end. Thus, in this case, any $k$ where $k equiv c_4 - b_0 = 5 - 1 = 4 pmod{2n}$ will give that $D = C$. In particular, let $k = 4$. Then, $d_0 = 1 + 4 equiv 5 pmod 8$, $d_1 = 4 + 4 equiv 0 pmod 8$, $d_2 = 6 + 4 equiv 2 pmod 8$ and $d_3 = 7 + 4 equiv 3 pmod 8$. Putting this together, $D = left{5, 0, 2, 3right}$ which is the same as $C$ but in a different order, i.e., where the last element is moved to the front.
Next, consider $B = left{1, 4, 5, 7right}$ and $C = left{0, 2, 3, 6right}$. In this case, $E = left{3, 1, 2, 2right}$ and $F = left{2, 1, 3, 2right}$. Here, $e_0$ only matches $f_2$, but $e_1 neq f_3$. As the values don't match, there is no value of $k$ for which $D = C$. You can verify this, if you wish, manually by going through all $k$ from $0$ to $7$, inclusive, or programmatically.
In general, for anything other than relatively small values of $n$, it will not be easy to solve this manually, but certain cases where $D neq C$ are possible to quite quickly verify. Nonetheless, even for relatively large values of $n$, this should be a relatively fast algorithm to run on a computer.
Note there are a few small enhancements you can make, including if checking manually. For example, you can keep track of how many elements of $E$ are $1, 2, ...$, and likewise for $F$. If any counts don't match between the $2$ sets, then you know that $D neq C$ always, but there may also be cases where the counts all match but where there is still no $k$ which can be used. Another enhancement is that you only need to check for $n - 1$ differences matching between $E$ and $F$ as the last difference would then need to match as well since the sums of the differences is always $2n$.
answered Jan 30 at 5:32
John OmielanJohn Omielan
4,4762215
$endgroup$
For $B$, you say it contains $n$ elements, but define it as $B = left{b_0,b_1,ldots,b_n right}$ which contains $n + 1$ elements. I believe based on $A$ containing $2n$ elements that you mean both $B$ and $C$ are to contain $n$ elements. To make things simpler, I will continue to have the index start at $0$, but have it end at index $n - 1$, for both sets.
With sets, the order of elements doesn't matter. However, to help solve the problem, consider all $b_i$ and $c_i$ to be in increasing order. Also, let $d_i$ be the elements of your set $D$.
You ask for a "more analytical solution". The following describes what is required in a fairly efficient mechanism to determine your answer, with it being about as analytical as I believe it's possible to be in general. However, I can't guarantee it, so perhaps somebody can provide you with a more analytical answer. Otherwise, if your computer implementation doesn't already use this, then you may wish to change it to do so.
First, define the difference function on the set elements of $B$ to be
$$B_1left(iright) =
begin{cases}
b_{i + 1} - b_{i} & 0 le i lt n - 1 \
left(b_0 + 2nright) - b_{i} & i = n - 1
end{cases} tag{1}label{eq1}$$
Similarly, define the difference function on the set elements of $C$ to be
$$C_1left(iright) =
begin{cases}
c_{i + 1} - c_{i} & 0 le i lt n - 1 \
left(c_0 + 2nright) - c_{i} & i = n - 1
end{cases} tag{2}label{eq2}$$
Next, define the set $E$ where each element $e_i$ is $B_1left(iright)$ and the set $F$ where each element $f_i$ is $C_1left(iright)$
To determine whether or not $D = C$ for some $k$, you need to check for $F$ being a shifted version of $E$. In particular, find all $i$ where $e_0 = f_i$. For each such $i$, check if all next differences of $E$ matches those of $F$, with wrapping when reach $n - 1$. In other words, see if $e_i = f_{left(i + jright) pmod{n}}$ for all $0 le j le n - 1$. A value of $k$ which may work can be found if and only if you have found such an $i$ for all of these differences to match. In the case where there is such an $i$, then any $k equiv c_i - b_0 pmod{2n}$ will work to determine the $d_m$ values for $0 le m le n - 1$.
To see why this works, consider your $d_m$ values for a given value of $k$. They will keep increasing until possibly the remainder goes to a value less than the previous value. This can only happen at most once. This is the point where the matching set values in $C$ much have reached the end. To match each such set value, the differences must match, which is why I am using eqref{eq1} and eqref{eq2} to do this checking through $E$ and $F$.
I hope this explanation is clear enough. To help see this, consider an example for $n = 4$ of $B = left{1, 4, 6, 7right}$ and $C = left{0, 2, 3, 5right}$. In this case, $E = left{3, 2, 1, 2right}$ and $F = left{2, 1, 2, 3right}$. It's fairly easy to see visually that $F$ is $E$ shifted to the left by $1$ element, with the first element going to the end. Thus, in this case, any $k$ where $k equiv c_4 - b_0 = 5 - 1 = 4 pmod{2n}$ will give that $D = C$. In particular, let $k = 4$. Then, $d_0 = 1 + 4 equiv 5 pmod 8$, $d_1 = 4 + 4 equiv 0 pmod 8$, $d_2 = 6 + 4 equiv 2 pmod 8$ and $d_3 = 7 + 4 equiv 3 pmod 8$. Putting this together, $D = left{5, 0, 2, 3right}$ which is the same as $C$ but in a different order, i.e., where the last element is moved to the front.
Next, consider $B = left{1, 4, 5, 7right}$ and $C = left{0, 2, 3, 6right}$. In this case, $E = left{3, 1, 2, 2right}$ and $F = left{2, 1, 3, 2right}$. Here, $e_0$ only matches $f_2$, but $e_1 neq f_3$. As the values don't match, there is no value of $k$ for which $D = C$. You can verify this, if you wish, manually by going through all $k$ from $0$ to $7$, inclusive, or programmatically.
In general, for anything other than relatively small values of $n$, it will not be easy to solve this manually, but certain cases where $D neq C$ are possible to quite quickly verify. Nonetheless, even for relatively large values of $n$, this should be a relatively fast algorithm to run on a computer.
Note there are a few small enhancements you can make, including if checking manually. For example, you can keep track of how many elements of $E$ are $1, 2, ...$, and likewise for $F$. If any counts don't match between the $2$ sets, then you know that $D neq C$ always, but there may also be cases where the counts all match but where there is still no $k$ which can be used. Another enhancement is that you only need to check for $n - 1$ differences matching between $E$ and $F$ as the last difference would then need to match as well since the sums of the differences is always $2n$.
answered Jan 30 at 5:32
John OmielanJohn Omielan
4,4762215
edited Jan 30 at 8:45
answered Jan 30 at 5:32
John OmielanJohn Omielan
4,4762215
answered Jan 30 at 5:32
John OmielanJohn Omielan
4,4762215
answered Jan 30 at 5:32
John OmielanJohn Omielan
4,4762215
4,4762215
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%2f3092334%2fapplied-set-theory%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
$begingroup$
Please edit the title: it's not a set theory question!
$endgroup$
– YuiTo Cheng
Jan 30 at 7:39