Mixing
Partitioning ${1,cdots,k}$ into $p$ subsets with equal sums
Let $p$ be a prime. For which $k$ can the set ${1,cdots,k}$ be partitioned into
$p$ subsets with equal sums of elements ?
Obviously, $pmid k(k+1)$. Hence, $pmid k$ or $pmid k+1$. All we have to do now is to show a construction. But I can't find one. I have tried partitioning the set and choose one element from each set but that hasn't yielded anything.
Any hint will be appreciated.
combinatorics elementary-number-theory contest-math
edited Dec 27 '15 at 3:23
Matt Samuel
37.2k63465
asked Dec 4 '15 at 12:23
rah4927
1,6611138
|
show 3 more comments
Let $p$ be a prime. For which $k$ can the set ${1,cdots,k}$ be partitioned into
$p$ subsets with equal sums of elements ?
Obviously, $pmid k(k+1)$. Hence, $pmid k$ or $pmid k+1$. All we have to do now is to show a construction. But I can't find one. I have tried partitioning the set and choose one element from each set but that hasn't yielded anything.
Any hint will be appreciated.
combinatorics elementary-number-theory contest-math
edited Dec 27 '15 at 3:23
Matt Samuel
37.2k63465
asked Dec 4 '15 at 12:23
rah4927
1,6611138
Well, I'd eliminate the trivial case when $p=2$ first....then you're just looking at dividing it into 2 sets with equal sums, which should be possible iff $k$ is even.
– Alan
Dec 4 '15 at 12:28
1
$p=k$ or $p=k+1$ won't work; but $2p=k$ and $2p=k+1$ have simple constructions.
– Empy2
Dec 4 '15 at 12:30
@Alan, I think $frac{k(k+1)}2$ must be even.
– Empy2
Dec 4 '15 at 12:31
1
@michael Ahh, yeah, the pairing will require k to be a multiple of 4, not 2. True.
– Alan
Dec 4 '15 at 12:33
@Alan or $k$ could be congruent to $3$ modulo $4$.
– Arthur
Dec 4 '15 at 12:46
|
show 3 more comments
Let $p$ be a prime. For which $k$ can the set ${1,cdots,k}$ be partitioned into
$p$ subsets with equal sums of elements ?
Obviously, $pmid k(k+1)$. Hence, $pmid k$ or $pmid k+1$. All we have to do now is to show a construction. But I can't find one. I have tried partitioning the set and choose one element from each set but that hasn't yielded anything.
Any hint will be appreciated.
combinatorics elementary-number-theory contest-math
edited Dec 27 '15 at 3:23
Matt Samuel
37.2k63465
asked Dec 4 '15 at 12:23
rah4927
1,6611138
Let $p$ be a prime. For which $k$ can the set ${1,cdots,k}$ be partitioned into
$p$ subsets with equal sums of elements ?
Obviously, $pmid k(k+1)$. Hence, $pmid k$ or $pmid k+1$. All we have to do now is to show a construction. But I can't find one. I have tried partitioning the set and choose one element from each set but that hasn't yielded anything.
Any hint will be appreciated.
combinatorics elementary-number-theory contest-math
combinatorics elementary-number-theory contest-math
edited Dec 27 '15 at 3:23
Matt Samuel
37.2k63465
asked Dec 4 '15 at 12:23
rah4927
1,6611138
edited Dec 27 '15 at 3:23
Matt Samuel
37.2k63465
asked Dec 4 '15 at 12:23
rah4927
1,6611138
edited Dec 27 '15 at 3:23
Matt Samuel
37.2k63465
edited Dec 27 '15 at 3:23
Matt Samuel
37.2k63465
edited Dec 27 '15 at 3:23
Matt Samuel
37.2k63465
37.2k63465
asked Dec 4 '15 at 12:23
rah4927
1,6611138
asked Dec 4 '15 at 12:23
rah4927
1,6611138
asked Dec 4 '15 at 12:23
rah4927
1,6611138
1,6611138
Well, I'd eliminate the trivial case when $p=2$ first....then you're just looking at dividing it into 2 sets with equal sums, which should be possible iff $k$ is even.
– Alan
Dec 4 '15 at 12:28
1
$p=k$ or $p=k+1$ won't work; but $2p=k$ and $2p=k+1$ have simple constructions.
– Empy2
Dec 4 '15 at 12:30
@Alan, I think $frac{k(k+1)}2$ must be even.
– Empy2
Dec 4 '15 at 12:31
1
@michael Ahh, yeah, the pairing will require k to be a multiple of 4, not 2. True.
– Alan
Dec 4 '15 at 12:33
@Alan or $k$ could be congruent to $3$ modulo $4$.
– Arthur
Dec 4 '15 at 12:46
|
show 3 more comments
Well, I'd eliminate the trivial case when $p=2$ first....then you're just looking at dividing it into 2 sets with equal sums, which should be possible iff $k$ is even.
– Alan
Dec 4 '15 at 12:28
1
$p=k$ or $p=k+1$ won't work; but $2p=k$ and $2p=k+1$ have simple constructions.
– Empy2
Dec 4 '15 at 12:30
@Alan, I think $frac{k(k+1)}2$ must be even.
– Empy2
Dec 4 '15 at 12:31
1
@michael Ahh, yeah, the pairing will require k to be a multiple of 4, not 2. True.
– Alan
Dec 4 '15 at 12:33
@Alan or $k$ could be congruent to $3$ modulo $4$.
– Arthur
Dec 4 '15 at 12:46
Well, I'd eliminate the trivial case when $p=2$ first....then you're just looking at dividing it into 2 sets with equal sums, which should be possible iff $k$ is even.
– Alan
Dec 4 '15 at 12:28
Well, I'd eliminate the trivial case when $p=2$ first....then you're just looking at dividing it into 2 sets with equal sums, which should be possible iff $k$ is even.
– Alan
Dec 4 '15 at 12:28
1
1
$p=k$ or $p=k+1$ won't work; but $2p=k$ and $2p=k+1$ have simple constructions.
– Empy2
Dec 4 '15 at 12:30
$p=k$ or $p=k+1$ won't work; but $2p=k$ and $2p=k+1$ have simple constructions.
– Empy2
Dec 4 '15 at 12:30
@Alan, I think $frac{k(k+1)}2$ must be even.
– Empy2
Dec 4 '15 at 12:31
@Alan, I think $frac{k(k+1)}2$ must be even.
– Empy2
Dec 4 '15 at 12:31
1
1
@michael Ahh, yeah, the pairing will require k to be a multiple of 4, not 2. True.
– Alan
Dec 4 '15 at 12:33
@michael Ahh, yeah, the pairing will require k to be a multiple of 4, not 2. True.
– Alan
Dec 4 '15 at 12:33
@Alan or $k$ could be congruent to $3$ modulo $4$.
– Arthur
Dec 4 '15 at 12:46
@Alan or $k$ could be congruent to $3$ modulo $4$.
– Arthur
Dec 4 '15 at 12:46
|
show 3 more comments
1 Answer
1
active
oldest
votes
For a prime natural number $p$, we say that a positive integer $k$ is $p$-splittable if ${1,2,ldots,k}$ can be partitioned into $p$ subsets with the same sum. If $p=2$, then it follows that $kequiv 0pmod{4}$ or $kequiv -1pmod{4}$. For an odd prime $p$, we have $kequiv 0pmod{p}$ or $kequiv-1pmod{p}$. It can be easily seen that, for $kinmathbb{N}$ and for any prime natural number $p$, if $k$ is $p$-splittable, then $k+2p$ is $p$-splittable (by adding ${k+1,k+2p}$, ${k+2,k+2p-1}$, $ldots$, ${k+p,k+p+1}$ to the $p$ partitioning sets of ${1,2,ldots,k}$).
Since $k=3$ and $k=4$ are $2$-splittable, any natural number of the form $4t-1$ or $4t$, where $tinmathbb{N}$, is $2$-splittable, and no other number is $2$-splittable. Also, for any odd prime natural number $p$, $k=2p-1$ and $k=2p$ are $p$-splittable, which means that any natural number of the form $2pt-1$ or $2pt$, where $tinmathbb{N}$, is $p$-splittable. Clearly, $k=p-1$ and $k=p$ are not $p$-splittable for odd $p$. We, however, claim that $k=3p-1$ or $k=3p$ are $p$-splittable for odd $p$, which would then imply that any natural number of the form $pt-1$ or $pt$ where $tgeq 2$ is an integer is $p$-splittable, and nothing else is $p$-splittable.
First, assume that $pequiv 1pmod{4}$, say $p=4r+1$ for some $rinmathbb{N}$. If $k=3p-1=12r+2$, then consider the partition of ${1,2,ldots,k}$ into ${6r+1,12r+2}$, ${6r+2,12r+1}$, $ldots$, ${9r+1,9r+2}$, ${1,2,3,6r-2,6r-1,6r}$, ${4,5,6,6r-5,6r-4,6r-3}$, $ldots$, ${3r-2,3r-1,3r,3r+1,3r+2,3r+3}$. If $k=3p=12r+3$, then consider the partition ${6r+3,12r+3}$, ${6r+4,12r+2}$, $ldots$, ${9r+2,9r+4}$, ${1,2,3,6r-1,6r,6r+1}$, ${4,5,6,6r-4,6r-3,6r-2}$, $ldots$, ${3r-2,3r-1,3r,3r+2,3r+3,3r+4}$, ${3r+1,6r+2,9r+3}$.
Now, assume that $pequiv -1pmod{4}$, say $p=4r-1$ for some $rinmathbb{N}$. If $k=3p-1=12r-4$, then consider the partition ${6r-2,12r-4}$, ${6r-1,12r-5}$, $ldots$, ${9r-4,9r-2}$, ${1,2,3,6r-5,6r-4,6r-3}$, ${4,5,6,6r-8,6r-7,6r-6}$, $ldots$, ${3r-5,3r-4,3r-3,3r+1,3r+2,3r+3}$, ${3r-2,3r-1,3r,9r-3}$. If $k=3p=12r-3$, then consider the partition ${6r,12r-3}$, ${6r+1,12r-4}$, $ldots$, ${9r-2,9r-1}$, ${1,2,3,6r-4,6r-3,6r-2}$, ${4,5,6,6r-7,6r-6,6r-5}$, $ldots$, ${3r-5,3r-4,3r-3,3r+2,3r+3,3r+4}$, ${3r-2,3r-1,3r,3r+1,6r-1}$.
Question: What if $p$ is not prime? I conjecture the following:
(1) If $p$ is odd, then, for any $jin{-1,0,1,2,ldots,p-2}$ such that $pmid j(j+1)$, every integer of the form $tp+j$, where $tgeq 2$ is an integer, is $p$-splittable, and nothing else is $p$-splittable.
(2) If $p$ is even, then, for any $jin{-1,0,1,2,ldots,2p-2}$ such that $pmid frac{j(j+1)}{2}$, every integer of the form $2tp+j$, where $tinmathbb{N}$, is $p$-splittable, and nothing else is $p$-splittable.
This question is also posted here: $p$-Splittable Integers.
edited Apr 13 '17 at 12:20
Community♦
1
answered Dec 4 '15 at 13:44
Batominovski
33.7k33292
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%2f1559650%2fpartitioning-1-cdots-k-into-p-subsets-with-equal-sums%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
For a prime natural number $p$, we say that a positive integer $k$ is $p$-splittable if ${1,2,ldots,k}$ can be partitioned into $p$ subsets with the same sum. If $p=2$, then it follows that $kequiv 0pmod{4}$ or $kequiv -1pmod{4}$. For an odd prime $p$, we have $kequiv 0pmod{p}$ or $kequiv-1pmod{p}$. It can be easily seen that, for $kinmathbb{N}$ and for any prime natural number $p$, if $k$ is $p$-splittable, then $k+2p$ is $p$-splittable (by adding ${k+1,k+2p}$, ${k+2,k+2p-1}$, $ldots$, ${k+p,k+p+1}$ to the $p$ partitioning sets of ${1,2,ldots,k}$).
Since $k=3$ and $k=4$ are $2$-splittable, any natural number of the form $4t-1$ or $4t$, where $tinmathbb{N}$, is $2$-splittable, and no other number is $2$-splittable. Also, for any odd prime natural number $p$, $k=2p-1$ and $k=2p$ are $p$-splittable, which means that any natural number of the form $2pt-1$ or $2pt$, where $tinmathbb{N}$, is $p$-splittable. Clearly, $k=p-1$ and $k=p$ are not $p$-splittable for odd $p$. We, however, claim that $k=3p-1$ or $k=3p$ are $p$-splittable for odd $p$, which would then imply that any natural number of the form $pt-1$ or $pt$ where $tgeq 2$ is an integer is $p$-splittable, and nothing else is $p$-splittable.
First, assume that $pequiv 1pmod{4}$, say $p=4r+1$ for some $rinmathbb{N}$. If $k=3p-1=12r+2$, then consider the partition of ${1,2,ldots,k}$ into ${6r+1,12r+2}$, ${6r+2,12r+1}$, $ldots$, ${9r+1,9r+2}$, ${1,2,3,6r-2,6r-1,6r}$, ${4,5,6,6r-5,6r-4,6r-3}$, $ldots$, ${3r-2,3r-1,3r,3r+1,3r+2,3r+3}$. If $k=3p=12r+3$, then consider the partition ${6r+3,12r+3}$, ${6r+4,12r+2}$, $ldots$, ${9r+2,9r+4}$, ${1,2,3,6r-1,6r,6r+1}$, ${4,5,6,6r-4,6r-3,6r-2}$, $ldots$, ${3r-2,3r-1,3r,3r+2,3r+3,3r+4}$, ${3r+1,6r+2,9r+3}$.
Now, assume that $pequiv -1pmod{4}$, say $p=4r-1$ for some $rinmathbb{N}$. If $k=3p-1=12r-4$, then consider the partition ${6r-2,12r-4}$, ${6r-1,12r-5}$, $ldots$, ${9r-4,9r-2}$, ${1,2,3,6r-5,6r-4,6r-3}$, ${4,5,6,6r-8,6r-7,6r-6}$, $ldots$, ${3r-5,3r-4,3r-3,3r+1,3r+2,3r+3}$, ${3r-2,3r-1,3r,9r-3}$. If $k=3p=12r-3$, then consider the partition ${6r,12r-3}$, ${6r+1,12r-4}$, $ldots$, ${9r-2,9r-1}$, ${1,2,3,6r-4,6r-3,6r-2}$, ${4,5,6,6r-7,6r-6,6r-5}$, $ldots$, ${3r-5,3r-4,3r-3,3r+2,3r+3,3r+4}$, ${3r-2,3r-1,3r,3r+1,6r-1}$.
Question: What if $p$ is not prime? I conjecture the following:
(1) If $p$ is odd, then, for any $jin{-1,0,1,2,ldots,p-2}$ such that $pmid j(j+1)$, every integer of the form $tp+j$, where $tgeq 2$ is an integer, is $p$-splittable, and nothing else is $p$-splittable.
(2) If $p$ is even, then, for any $jin{-1,0,1,2,ldots,2p-2}$ such that $pmid frac{j(j+1)}{2}$, every integer of the form $2tp+j$, where $tinmathbb{N}$, is $p$-splittable, and nothing else is $p$-splittable.
This question is also posted here: $p$-Splittable Integers.
edited Apr 13 '17 at 12:20
Community♦
1
answered Dec 4 '15 at 13:44
Batominovski
33.7k33292
add a comment |
For a prime natural number $p$, we say that a positive integer $k$ is $p$-splittable if ${1,2,ldots,k}$ can be partitioned into $p$ subsets with the same sum. If $p=2$, then it follows that $kequiv 0pmod{4}$ or $kequiv -1pmod{4}$. For an odd prime $p$, we have $kequiv 0pmod{p}$ or $kequiv-1pmod{p}$. It can be easily seen that, for $kinmathbb{N}$ and for any prime natural number $p$, if $k$ is $p$-splittable, then $k+2p$ is $p$-splittable (by adding ${k+1,k+2p}$, ${k+2,k+2p-1}$, $ldots$, ${k+p,k+p+1}$ to the $p$ partitioning sets of ${1,2,ldots,k}$).
Since $k=3$ and $k=4$ are $2$-splittable, any natural number of the form $4t-1$ or $4t$, where $tinmathbb{N}$, is $2$-splittable, and no other number is $2$-splittable. Also, for any odd prime natural number $p$, $k=2p-1$ and $k=2p$ are $p$-splittable, which means that any natural number of the form $2pt-1$ or $2pt$, where $tinmathbb{N}$, is $p$-splittable. Clearly, $k=p-1$ and $k=p$ are not $p$-splittable for odd $p$. We, however, claim that $k=3p-1$ or $k=3p$ are $p$-splittable for odd $p$, which would then imply that any natural number of the form $pt-1$ or $pt$ where $tgeq 2$ is an integer is $p$-splittable, and nothing else is $p$-splittable.
First, assume that $pequiv 1pmod{4}$, say $p=4r+1$ for some $rinmathbb{N}$. If $k=3p-1=12r+2$, then consider the partition of ${1,2,ldots,k}$ into ${6r+1,12r+2}$, ${6r+2,12r+1}$, $ldots$, ${9r+1,9r+2}$, ${1,2,3,6r-2,6r-1,6r}$, ${4,5,6,6r-5,6r-4,6r-3}$, $ldots$, ${3r-2,3r-1,3r,3r+1,3r+2,3r+3}$. If $k=3p=12r+3$, then consider the partition ${6r+3,12r+3}$, ${6r+4,12r+2}$, $ldots$, ${9r+2,9r+4}$, ${1,2,3,6r-1,6r,6r+1}$, ${4,5,6,6r-4,6r-3,6r-2}$, $ldots$, ${3r-2,3r-1,3r,3r+2,3r+3,3r+4}$, ${3r+1,6r+2,9r+3}$.
Now, assume that $pequiv -1pmod{4}$, say $p=4r-1$ for some $rinmathbb{N}$. If $k=3p-1=12r-4$, then consider the partition ${6r-2,12r-4}$, ${6r-1,12r-5}$, $ldots$, ${9r-4,9r-2}$, ${1,2,3,6r-5,6r-4,6r-3}$, ${4,5,6,6r-8,6r-7,6r-6}$, $ldots$, ${3r-5,3r-4,3r-3,3r+1,3r+2,3r+3}$, ${3r-2,3r-1,3r,9r-3}$. If $k=3p=12r-3$, then consider the partition ${6r,12r-3}$, ${6r+1,12r-4}$, $ldots$, ${9r-2,9r-1}$, ${1,2,3,6r-4,6r-3,6r-2}$, ${4,5,6,6r-7,6r-6,6r-5}$, $ldots$, ${3r-5,3r-4,3r-3,3r+2,3r+3,3r+4}$, ${3r-2,3r-1,3r,3r+1,6r-1}$.
Question: What if $p$ is not prime? I conjecture the following:
(1) If $p$ is odd, then, for any $jin{-1,0,1,2,ldots,p-2}$ such that $pmid j(j+1)$, every integer of the form $tp+j$, where $tgeq 2$ is an integer, is $p$-splittable, and nothing else is $p$-splittable.
(2) If $p$ is even, then, for any $jin{-1,0,1,2,ldots,2p-2}$ such that $pmid frac{j(j+1)}{2}$, every integer of the form $2tp+j$, where $tinmathbb{N}$, is $p$-splittable, and nothing else is $p$-splittable.
This question is also posted here: $p$-Splittable Integers.
edited Apr 13 '17 at 12:20
Community♦
1
answered Dec 4 '15 at 13:44
Batominovski
33.7k33292
add a comment |
For a prime natural number $p$, we say that a positive integer $k$ is $p$-splittable if ${1,2,ldots,k}$ can be partitioned into $p$ subsets with the same sum. If $p=2$, then it follows that $kequiv 0pmod{4}$ or $kequiv -1pmod{4}$. For an odd prime $p$, we have $kequiv 0pmod{p}$ or $kequiv-1pmod{p}$. It can be easily seen that, for $kinmathbb{N}$ and for any prime natural number $p$, if $k$ is $p$-splittable, then $k+2p$ is $p$-splittable (by adding ${k+1,k+2p}$, ${k+2,k+2p-1}$, $ldots$, ${k+p,k+p+1}$ to the $p$ partitioning sets of ${1,2,ldots,k}$).
Since $k=3$ and $k=4$ are $2$-splittable, any natural number of the form $4t-1$ or $4t$, where $tinmathbb{N}$, is $2$-splittable, and no other number is $2$-splittable. Also, for any odd prime natural number $p$, $k=2p-1$ and $k=2p$ are $p$-splittable, which means that any natural number of the form $2pt-1$ or $2pt$, where $tinmathbb{N}$, is $p$-splittable. Clearly, $k=p-1$ and $k=p$ are not $p$-splittable for odd $p$. We, however, claim that $k=3p-1$ or $k=3p$ are $p$-splittable for odd $p$, which would then imply that any natural number of the form $pt-1$ or $pt$ where $tgeq 2$ is an integer is $p$-splittable, and nothing else is $p$-splittable.
First, assume that $pequiv 1pmod{4}$, say $p=4r+1$ for some $rinmathbb{N}$. If $k=3p-1=12r+2$, then consider the partition of ${1,2,ldots,k}$ into ${6r+1,12r+2}$, ${6r+2,12r+1}$, $ldots$, ${9r+1,9r+2}$, ${1,2,3,6r-2,6r-1,6r}$, ${4,5,6,6r-5,6r-4,6r-3}$, $ldots$, ${3r-2,3r-1,3r,3r+1,3r+2,3r+3}$. If $k=3p=12r+3$, then consider the partition ${6r+3,12r+3}$, ${6r+4,12r+2}$, $ldots$, ${9r+2,9r+4}$, ${1,2,3,6r-1,6r,6r+1}$, ${4,5,6,6r-4,6r-3,6r-2}$, $ldots$, ${3r-2,3r-1,3r,3r+2,3r+3,3r+4}$, ${3r+1,6r+2,9r+3}$.
Now, assume that $pequiv -1pmod{4}$, say $p=4r-1$ for some $rinmathbb{N}$. If $k=3p-1=12r-4$, then consider the partition ${6r-2,12r-4}$, ${6r-1,12r-5}$, $ldots$, ${9r-4,9r-2}$, ${1,2,3,6r-5,6r-4,6r-3}$, ${4,5,6,6r-8,6r-7,6r-6}$, $ldots$, ${3r-5,3r-4,3r-3,3r+1,3r+2,3r+3}$, ${3r-2,3r-1,3r,9r-3}$. If $k=3p=12r-3$, then consider the partition ${6r,12r-3}$, ${6r+1,12r-4}$, $ldots$, ${9r-2,9r-1}$, ${1,2,3,6r-4,6r-3,6r-2}$, ${4,5,6,6r-7,6r-6,6r-5}$, $ldots$, ${3r-5,3r-4,3r-3,3r+2,3r+3,3r+4}$, ${3r-2,3r-1,3r,3r+1,6r-1}$.
Question: What if $p$ is not prime? I conjecture the following:
(1) If $p$ is odd, then, for any $jin{-1,0,1,2,ldots,p-2}$ such that $pmid j(j+1)$, every integer of the form $tp+j$, where $tgeq 2$ is an integer, is $p$-splittable, and nothing else is $p$-splittable.
(2) If $p$ is even, then, for any $jin{-1,0,1,2,ldots,2p-2}$ such that $pmid frac{j(j+1)}{2}$, every integer of the form $2tp+j$, where $tinmathbb{N}$, is $p$-splittable, and nothing else is $p$-splittable.
This question is also posted here: $p$-Splittable Integers.
edited Apr 13 '17 at 12:20
Community♦
1
answered Dec 4 '15 at 13:44
Batominovski
33.7k33292
For a prime natural number $p$, we say that a positive integer $k$ is $p$-splittable if ${1,2,ldots,k}$ can be partitioned into $p$ subsets with the same sum. If $p=2$, then it follows that $kequiv 0pmod{4}$ or $kequiv -1pmod{4}$. For an odd prime $p$, we have $kequiv 0pmod{p}$ or $kequiv-1pmod{p}$. It can be easily seen that, for $kinmathbb{N}$ and for any prime natural number $p$, if $k$ is $p$-splittable, then $k+2p$ is $p$-splittable (by adding ${k+1,k+2p}$, ${k+2,k+2p-1}$, $ldots$, ${k+p,k+p+1}$ to the $p$ partitioning sets of ${1,2,ldots,k}$).
Since $k=3$ and $k=4$ are $2$-splittable, any natural number of the form $4t-1$ or $4t$, where $tinmathbb{N}$, is $2$-splittable, and no other number is $2$-splittable. Also, for any odd prime natural number $p$, $k=2p-1$ and $k=2p$ are $p$-splittable, which means that any natural number of the form $2pt-1$ or $2pt$, where $tinmathbb{N}$, is $p$-splittable. Clearly, $k=p-1$ and $k=p$ are not $p$-splittable for odd $p$. We, however, claim that $k=3p-1$ or $k=3p$ are $p$-splittable for odd $p$, which would then imply that any natural number of the form $pt-1$ or $pt$ where $tgeq 2$ is an integer is $p$-splittable, and nothing else is $p$-splittable.
First, assume that $pequiv 1pmod{4}$, say $p=4r+1$ for some $rinmathbb{N}$. If $k=3p-1=12r+2$, then consider the partition of ${1,2,ldots,k}$ into ${6r+1,12r+2}$, ${6r+2,12r+1}$, $ldots$, ${9r+1,9r+2}$, ${1,2,3,6r-2,6r-1,6r}$, ${4,5,6,6r-5,6r-4,6r-3}$, $ldots$, ${3r-2,3r-1,3r,3r+1,3r+2,3r+3}$. If $k=3p=12r+3$, then consider the partition ${6r+3,12r+3}$, ${6r+4,12r+2}$, $ldots$, ${9r+2,9r+4}$, ${1,2,3,6r-1,6r,6r+1}$, ${4,5,6,6r-4,6r-3,6r-2}$, $ldots$, ${3r-2,3r-1,3r,3r+2,3r+3,3r+4}$, ${3r+1,6r+2,9r+3}$.
Now, assume that $pequiv -1pmod{4}$, say $p=4r-1$ for some $rinmathbb{N}$. If $k=3p-1=12r-4$, then consider the partition ${6r-2,12r-4}$, ${6r-1,12r-5}$, $ldots$, ${9r-4,9r-2}$, ${1,2,3,6r-5,6r-4,6r-3}$, ${4,5,6,6r-8,6r-7,6r-6}$, $ldots$, ${3r-5,3r-4,3r-3,3r+1,3r+2,3r+3}$, ${3r-2,3r-1,3r,9r-3}$. If $k=3p=12r-3$, then consider the partition ${6r,12r-3}$, ${6r+1,12r-4}$, $ldots$, ${9r-2,9r-1}$, ${1,2,3,6r-4,6r-3,6r-2}$, ${4,5,6,6r-7,6r-6,6r-5}$, $ldots$, ${3r-5,3r-4,3r-3,3r+2,3r+3,3r+4}$, ${3r-2,3r-1,3r,3r+1,6r-1}$.
Question: What if $p$ is not prime? I conjecture the following:
(1) If $p$ is odd, then, for any $jin{-1,0,1,2,ldots,p-2}$ such that $pmid j(j+1)$, every integer of the form $tp+j$, where $tgeq 2$ is an integer, is $p$-splittable, and nothing else is $p$-splittable.
(2) If $p$ is even, then, for any $jin{-1,0,1,2,ldots,2p-2}$ such that $pmid frac{j(j+1)}{2}$, every integer of the form $2tp+j$, where $tinmathbb{N}$, is $p$-splittable, and nothing else is $p$-splittable.
This question is also posted here: $p$-Splittable Integers.
edited Apr 13 '17 at 12:20
Community♦
1
answered Dec 4 '15 at 13:44
Batominovski
33.7k33292
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Dec 4 '15 at 13:44
Batominovski
33.7k33292
answered Dec 4 '15 at 13:44
Batominovski
33.7k33292
answered Dec 4 '15 at 13:44
Batominovski
33.7k33292
33.7k33292
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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%2f1559650%2fpartitioning-1-cdots-k-into-p-subsets-with-equal-sums%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
Well, I'd eliminate the trivial case when $p=2$ first....then you're just looking at dividing it into 2 sets with equal sums, which should be possible iff $k$ is even.
– Alan
Dec 4 '15 at 12:28
1
$p=k$ or $p=k+1$ won't work; but $2p=k$ and $2p=k+1$ have simple constructions.
– Empy2
Dec 4 '15 at 12:30
@Alan, I think $frac{k(k+1)}2$ must be even.
– Empy2
Dec 4 '15 at 12:31
1
@michael Ahh, yeah, the pairing will require k to be a multiple of 4, not 2. True.
– Alan
Dec 4 '15 at 12:33
@Alan or $k$ could be congruent to $3$ modulo $4$.
– Arthur
Dec 4 '15 at 12:46