Mixing
Special subdivision of numbers from 1 to 99
$begingroup$
I've been lately working on a problem I still can't solve. The problem is:
Can we divide numbers from 1 to 99 into 33 groups of three numbers, such that in every group one number is the sum of the two remaining elements?
Thank you in advance for any help or indication :)
number-theory arithmetic additive-combinatorics
edited Oct 4 '13 at 17:58
Dennis Meng
1,3371713
asked Oct 4 '13 at 17:15
mounaimmounaim
1907
$endgroup$
add a comment |
$begingroup$
I've been lately working on a problem I still can't solve. The problem is:
Can we divide numbers from 1 to 99 into 33 groups of three numbers, such that in every group one number is the sum of the two remaining elements?
Thank you in advance for any help or indication :)
number-theory arithmetic additive-combinatorics
edited Oct 4 '13 at 17:58
Dennis Meng
1,3371713
asked Oct 4 '13 at 17:15
mounaimmounaim
1907
$endgroup$
add a comment |
$begingroup$
I've been lately working on a problem I still can't solve. The problem is:
Can we divide numbers from 1 to 99 into 33 groups of three numbers, such that in every group one number is the sum of the two remaining elements?
Thank you in advance for any help or indication :)
number-theory arithmetic additive-combinatorics
edited Oct 4 '13 at 17:58
Dennis Meng
1,3371713
asked Oct 4 '13 at 17:15
mounaimmounaim
1907
$endgroup$
I've been lately working on a problem I still can't solve. The problem is:
Can we divide numbers from 1 to 99 into 33 groups of three numbers, such that in every group one number is the sum of the two remaining elements?
Thank you in advance for any help or indication :)
number-theory arithmetic additive-combinatorics
number-theory arithmetic additive-combinatorics
edited Oct 4 '13 at 17:58
Dennis Meng
1,3371713
asked Oct 4 '13 at 17:15
mounaimmounaim
1907
edited Oct 4 '13 at 17:58
Dennis Meng
1,3371713
asked Oct 4 '13 at 17:15
mounaimmounaim
1907
edited Oct 4 '13 at 17:58
Dennis Meng
1,3371713
edited Oct 4 '13 at 17:58
Dennis Meng
1,3371713
edited Oct 4 '13 at 17:58
Dennis Meng
1,3371713
1,3371713
asked Oct 4 '13 at 17:15
mounaimmounaim
1907
asked Oct 4 '13 at 17:15
mounaimmounaim
1907
asked Oct 4 '13 at 17:15
mounaimmounaim
1907
1907
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
If it works for $n$ then it works for $4n$ and $4n+3$.
This can be seen as follows:
assume it works for $n$, then it works for the even numbers until $2n$ (just multiply everything by 2).
Now we take following combinations:
$(2n+1)+(2n+2)=4n+3$, $(2n-1)+(2n+3)=4n+2$, $(2n-3)+(2n+4)=4n+1$, $ldots$, $1+(3n+2)=3n+3$.
The only numbers we did not use are the even numbers until $2n$.
An analogous argument shows that it works for $4n$ if it works for $n$.
user7530 has shown that it works for $n=24$ in another answer, so we have an affirmative answer, since $99=4*24+3$.
(Thanks for showing the error in my previous answer, Dennis. I hope this one makes more sense.)
answered Oct 4 '13 at 21:05
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
$begingroup$
(Yeah, this makes more sense. Nice one!)
$endgroup$
– Dennis Meng
Oct 4 '13 at 23:05
$begingroup$
I've been working on your mathematical analysis Leen..You can't just multiply everything by 2..lot of numbers will repeat..One number can't appear in two groups :) Otherwise, Could you give the final combinations for 99 ?
$endgroup$
– user99151
Oct 6 '13 at 15:28
$begingroup$
@mounmain:[[8,20,28],[6,24,30],[16,18,34],[14,22,36],[12,26,38],[10,32,42],[4,40,44],[2,46,48],[1,74,75],[3, 73,76],[5,72,77],[7,71,78],[9,70,79],[11,69,80],[13,68,81],[15,67,82],[17,66,83],[19,65,84],[21,64,85],[ 23,63,86],[25,62,87],[27,61,88],[29,60,89],[31,59,90],[33,58,91],[35,57,92],[37,56,93],[39,55,94],[41,54, 95],[43,53,96],[45,52,97],[47,51,98],[49,50,99]]
$endgroup$
– miracle173
Oct 7 '13 at 0:52
$begingroup$
@mounaim: multiplying by 2 is a linear operation. If there were no duplicates before the multiplication, there will be no duplicates after the multiplication. Clearly you only have covered even numbers after the multiplication.
$endgroup$
– Leen Droogendijk
Oct 7 '13 at 4:30
$begingroup$
@mounmain: I don't know how to access your old acount you should open a question in meta.math.stackexchange.com
$endgroup$
– miracle173
Oct 7 '13 at 21:35
|
show 1 more comment
$begingroup$
Not an answer, but some numerical data, generated using the following quick code:
#include <vector>
#include <iostream>
#include <cstdlib>
using namespace std;
void getCandidates(int sum, const vector<bool> &nums, vector<int> &choices)
{
choices.clear();
for(int i=0; i<(sum-1)/2; i++)
{
if(nums[i] && nums[sum-i-2] && i != sum-i-2)
{
choices.push_back(i);
}
}
}
bool recurse(const vector<bool> &nums)
{
int max=-1;
for(int i=0; i<nums.size(); i++)
{
if(nums[i])
max = i;
}
if(max == -1)
{
return true;
}
vector<int> cands;
getCandidates(max+1, nums, cands);
for(int i=0; i<cands.size(); i++)
{
vector<bool> copy = nums;
copy[max] = false;
copy[cands[i]] = false;
copy[max-cands[i]-1] = false;
if(recurse(copy))
return true;
}
return false;
}
void testSize(int size)
{
vector<bool> nums;
for(int i=0; i<size; i++)
nums.push_back(true);
cout << size << ": ";
if(recurse(nums))
cout << "yes";
else
cout << "no";
cout << endl;
}
int main()
{
for(int i=0; i<33; i++)
testSize(3*i);
return 0;
}
Output so far is pasted below. Worst-case runtime is exponential, so it may never get to 99, but I'll keep this updated as the program keeps running.
0: yes
3: yes
6: no
9: no
12: yes
15: yes
18: no
21: no
24: yes
27: yes
30: no
33: no
36: yes
39: yes
42: no
45: no
48: yes
51: yes
54: no
57: no
60: yes
63: yes
So far the answer seems to be "yes" whenever $n$ satisfies the necessary condition that $frac{n(n+1)}{2}$ is even.
EDIT: Here is the solution for 24 as requested by Leen above.
(14, 4, 10) (15, 3, 12) (17, 8, 9) (18, 7, 11) (19, 6, 13) (21, 5, 16) (22, 2, 20) (24, 1, 23)
answered Oct 4 '13 at 18:44
user7530user7530
34.8k759113
$endgroup$
1
$begingroup$
A couple observations that might help speed things up: any group of three has to contain either all even or one even and two odd numbers
$endgroup$
– Dennis Meng
Oct 4 '13 at 19:07
$begingroup$
Of course $n(n+1)/2$ must be even. Each "pod" has a sum of twice the largest element, hence even.
$endgroup$
– Oscar Lanzi
Jan 12 at 10:23
add a comment |
$begingroup$
Generalise $n$ and let $n=3m$. This problem is a laxer version of the following more restrictive one:
Partition ${1, dots, 3m}$ into $m$ 3-sets ${x_i, y_i, z_i}$, $i=1, dots, m$, where $x_i+y_i=z_i$ and $y_ileqslant m$.
This more restrictive problem is equivalent to one studied by Skolem and another studied by Nickerson. Nickerson's problem is in turn a variant of a problem studied by Langford. Nowakowski, ch.1, states these problems, shows equivalences among them, and also gives solutions, for which he cites Davies and Skolem (the latter two citations are taken from
the bibliography in Nowakowski).
R. J. Nowakowski. Generalizations of the Langford-Skolem problem. MS Thesis, Dept. Math., Univ. Calgary, May 1975.
R.O. Davies. On Langford's Problem. II, Math. Gaz. 43 (1959), pp.253-255.
T. Skolem. On certain distributions of integers in pairs with given differences. Math. Scand. 5 (1957), pp.57-58; M.R. 19, 1159.
answered Jan 12 at 10:06
Rosie FRosie F
1,302315
$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%2f514796%2fspecial-subdivision-of-numbers-from-1-to-99%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$
If it works for $n$ then it works for $4n$ and $4n+3$.
This can be seen as follows:
assume it works for $n$, then it works for the even numbers until $2n$ (just multiply everything by 2).
Now we take following combinations:
$(2n+1)+(2n+2)=4n+3$, $(2n-1)+(2n+3)=4n+2$, $(2n-3)+(2n+4)=4n+1$, $ldots$, $1+(3n+2)=3n+3$.
The only numbers we did not use are the even numbers until $2n$.
An analogous argument shows that it works for $4n$ if it works for $n$.
user7530 has shown that it works for $n=24$ in another answer, so we have an affirmative answer, since $99=4*24+3$.
(Thanks for showing the error in my previous answer, Dennis. I hope this one makes more sense.)
answered Oct 4 '13 at 21:05
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
$begingroup$
(Yeah, this makes more sense. Nice one!)
$endgroup$
– Dennis Meng
Oct 4 '13 at 23:05
$begingroup$
I've been working on your mathematical analysis Leen..You can't just multiply everything by 2..lot of numbers will repeat..One number can't appear in two groups :) Otherwise, Could you give the final combinations for 99 ?
$endgroup$
– user99151
Oct 6 '13 at 15:28
$begingroup$
@mounmain:[[8,20,28],[6,24,30],[16,18,34],[14,22,36],[12,26,38],[10,32,42],[4,40,44],[2,46,48],[1,74,75],[3, 73,76],[5,72,77],[7,71,78],[9,70,79],[11,69,80],[13,68,81],[15,67,82],[17,66,83],[19,65,84],[21,64,85],[ 23,63,86],[25,62,87],[27,61,88],[29,60,89],[31,59,90],[33,58,91],[35,57,92],[37,56,93],[39,55,94],[41,54, 95],[43,53,96],[45,52,97],[47,51,98],[49,50,99]]
$endgroup$
– miracle173
Oct 7 '13 at 0:52
$begingroup$
@mounaim: multiplying by 2 is a linear operation. If there were no duplicates before the multiplication, there will be no duplicates after the multiplication. Clearly you only have covered even numbers after the multiplication.
$endgroup$
– Leen Droogendijk
Oct 7 '13 at 4:30
$begingroup$
@mounmain: I don't know how to access your old acount you should open a question in meta.math.stackexchange.com
$endgroup$
– miracle173
Oct 7 '13 at 21:35
|
show 1 more comment
$begingroup$
If it works for $n$ then it works for $4n$ and $4n+3$.
This can be seen as follows:
assume it works for $n$, then it works for the even numbers until $2n$ (just multiply everything by 2).
Now we take following combinations:
$(2n+1)+(2n+2)=4n+3$, $(2n-1)+(2n+3)=4n+2$, $(2n-3)+(2n+4)=4n+1$, $ldots$, $1+(3n+2)=3n+3$.
The only numbers we did not use are the even numbers until $2n$.
An analogous argument shows that it works for $4n$ if it works for $n$.
user7530 has shown that it works for $n=24$ in another answer, so we have an affirmative answer, since $99=4*24+3$.
(Thanks for showing the error in my previous answer, Dennis. I hope this one makes more sense.)
answered Oct 4 '13 at 21:05
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
$begingroup$
(Yeah, this makes more sense. Nice one!)
$endgroup$
– Dennis Meng
Oct 4 '13 at 23:05
$begingroup$
I've been working on your mathematical analysis Leen..You can't just multiply everything by 2..lot of numbers will repeat..One number can't appear in two groups :) Otherwise, Could you give the final combinations for 99 ?
$endgroup$
– user99151
Oct 6 '13 at 15:28
$begingroup$
@mounmain:[[8,20,28],[6,24,30],[16,18,34],[14,22,36],[12,26,38],[10,32,42],[4,40,44],[2,46,48],[1,74,75],[3, 73,76],[5,72,77],[7,71,78],[9,70,79],[11,69,80],[13,68,81],[15,67,82],[17,66,83],[19,65,84],[21,64,85],[ 23,63,86],[25,62,87],[27,61,88],[29,60,89],[31,59,90],[33,58,91],[35,57,92],[37,56,93],[39,55,94],[41,54, 95],[43,53,96],[45,52,97],[47,51,98],[49,50,99]]
$endgroup$
– miracle173
Oct 7 '13 at 0:52
$begingroup$
@mounaim: multiplying by 2 is a linear operation. If there were no duplicates before the multiplication, there will be no duplicates after the multiplication. Clearly you only have covered even numbers after the multiplication.
$endgroup$
– Leen Droogendijk
Oct 7 '13 at 4:30
$begingroup$
@mounmain: I don't know how to access your old acount you should open a question in meta.math.stackexchange.com
$endgroup$
– miracle173
Oct 7 '13 at 21:35
|
show 1 more comment
$begingroup$
If it works for $n$ then it works for $4n$ and $4n+3$.
This can be seen as follows:
assume it works for $n$, then it works for the even numbers until $2n$ (just multiply everything by 2).
Now we take following combinations:
$(2n+1)+(2n+2)=4n+3$, $(2n-1)+(2n+3)=4n+2$, $(2n-3)+(2n+4)=4n+1$, $ldots$, $1+(3n+2)=3n+3$.
The only numbers we did not use are the even numbers until $2n$.
An analogous argument shows that it works for $4n$ if it works for $n$.
user7530 has shown that it works for $n=24$ in another answer, so we have an affirmative answer, since $99=4*24+3$.
(Thanks for showing the error in my previous answer, Dennis. I hope this one makes more sense.)
answered Oct 4 '13 at 21:05
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
If it works for $n$ then it works for $4n$ and $4n+3$.
This can be seen as follows:
assume it works for $n$, then it works for the even numbers until $2n$ (just multiply everything by 2).
Now we take following combinations:
$(2n+1)+(2n+2)=4n+3$, $(2n-1)+(2n+3)=4n+2$, $(2n-3)+(2n+4)=4n+1$, $ldots$, $1+(3n+2)=3n+3$.
The only numbers we did not use are the even numbers until $2n$.
An analogous argument shows that it works for $4n$ if it works for $n$.
user7530 has shown that it works for $n=24$ in another answer, so we have an affirmative answer, since $99=4*24+3$.
(Thanks for showing the error in my previous answer, Dennis. I hope this one makes more sense.)
answered Oct 4 '13 at 21:05
Leen DroogendijkLeen Droogendijk
6,1351716
edited Jan 12 at 10:32
answered Oct 4 '13 at 21:05
Leen DroogendijkLeen Droogendijk
6,1351716
answered Oct 4 '13 at 21:05
Leen DroogendijkLeen Droogendijk
6,1351716
answered Oct 4 '13 at 21:05
Leen DroogendijkLeen Droogendijk
6,1351716
6,1351716
$begingroup$
(Yeah, this makes more sense. Nice one!)
$endgroup$
– Dennis Meng
Oct 4 '13 at 23:05
$begingroup$
I've been working on your mathematical analysis Leen..You can't just multiply everything by 2..lot of numbers will repeat..One number can't appear in two groups :) Otherwise, Could you give the final combinations for 99 ?
$endgroup$
– user99151
Oct 6 '13 at 15:28
$begingroup$
@mounmain:[[8,20,28],[6,24,30],[16,18,34],[14,22,36],[12,26,38],[10,32,42],[4,40,44],[2,46,48],[1,74,75],[3, 73,76],[5,72,77],[7,71,78],[9,70,79],[11,69,80],[13,68,81],[15,67,82],[17,66,83],[19,65,84],[21,64,85],[ 23,63,86],[25,62,87],[27,61,88],[29,60,89],[31,59,90],[33,58,91],[35,57,92],[37,56,93],[39,55,94],[41,54, 95],[43,53,96],[45,52,97],[47,51,98],[49,50,99]]
$endgroup$
– miracle173
Oct 7 '13 at 0:52
$begingroup$
@mounaim: multiplying by 2 is a linear operation. If there were no duplicates before the multiplication, there will be no duplicates after the multiplication. Clearly you only have covered even numbers after the multiplication.
$endgroup$
– Leen Droogendijk
Oct 7 '13 at 4:30
$begingroup$
@mounmain: I don't know how to access your old acount you should open a question in meta.math.stackexchange.com
$endgroup$
– miracle173
Oct 7 '13 at 21:35
|
show 1 more comment
$begingroup$
(Yeah, this makes more sense. Nice one!)
$endgroup$
– Dennis Meng
Oct 4 '13 at 23:05
$begingroup$
I've been working on your mathematical analysis Leen..You can't just multiply everything by 2..lot of numbers will repeat..One number can't appear in two groups :) Otherwise, Could you give the final combinations for 99 ?
$endgroup$
– user99151
Oct 6 '13 at 15:28
$begingroup$
@mounmain:[[8,20,28],[6,24,30],[16,18,34],[14,22,36],[12,26,38],[10,32,42],[4,40,44],[2,46,48],[1,74,75],[3, 73,76],[5,72,77],[7,71,78],[9,70,79],[11,69,80],[13,68,81],[15,67,82],[17,66,83],[19,65,84],[21,64,85],[ 23,63,86],[25,62,87],[27,61,88],[29,60,89],[31,59,90],[33,58,91],[35,57,92],[37,56,93],[39,55,94],[41,54, 95],[43,53,96],[45,52,97],[47,51,98],[49,50,99]]
$endgroup$
– miracle173
Oct 7 '13 at 0:52
$begingroup$
@mounaim: multiplying by 2 is a linear operation. If there were no duplicates before the multiplication, there will be no duplicates after the multiplication. Clearly you only have covered even numbers after the multiplication.
$endgroup$
– Leen Droogendijk
Oct 7 '13 at 4:30
$begingroup$
@mounmain: I don't know how to access your old acount you should open a question in meta.math.stackexchange.com
$endgroup$
– miracle173
Oct 7 '13 at 21:35
$begingroup$
(Yeah, this makes more sense. Nice one!)
$endgroup$
– Dennis Meng
Oct 4 '13 at 23:05
$begingroup$
(Yeah, this makes more sense. Nice one!)
$endgroup$
– Dennis Meng
Oct 4 '13 at 23:05
$begingroup$
I've been working on your mathematical analysis Leen..You can't just multiply everything by 2..lot of numbers will repeat..One number can't appear in two groups :) Otherwise, Could you give the final combinations for 99 ?
$endgroup$
– user99151
Oct 6 '13 at 15:28
$begingroup$
I've been working on your mathematical analysis Leen..You can't just multiply everything by 2..lot of numbers will repeat..One number can't appear in two groups :) Otherwise, Could you give the final combinations for 99 ?
$endgroup$
– user99151
Oct 6 '13 at 15:28
$begingroup$
@mounmain:
[[8,20,28],[6,24,30],[16,18,34],[14,22,36],[12,26,38],[10,32,42],[4,40,44],[2,46,48],[1,74,75],[3, 73,76],[5,72,77],[7,71,78],[9,70,79],[11,69,80],[13,68,81],[15,67,82],[17,66,83],[19,65,84],[21,64,85],[ 23,63,86],[25,62,87],[27,61,88],[29,60,89],[31,59,90],[33,58,91],[35,57,92],[37,56,93],[39,55,94],[41,54, 95],[43,53,96],[45,52,97],[47,51,98],[49,50,99]]$endgroup$
– miracle173
Oct 7 '13 at 0:52
$begingroup$
@mounmain:
[[8,20,28],[6,24,30],[16,18,34],[14,22,36],[12,26,38],[10,32,42],[4,40,44],[2,46,48],[1,74,75],[3, 73,76],[5,72,77],[7,71,78],[9,70,79],[11,69,80],[13,68,81],[15,67,82],[17,66,83],[19,65,84],[21,64,85],[ 23,63,86],[25,62,87],[27,61,88],[29,60,89],[31,59,90],[33,58,91],[35,57,92],[37,56,93],[39,55,94],[41,54, 95],[43,53,96],[45,52,97],[47,51,98],[49,50,99]]$endgroup$
– miracle173
Oct 7 '13 at 0:52
$begingroup$
@mounaim: multiplying by 2 is a linear operation. If there were no duplicates before the multiplication, there will be no duplicates after the multiplication. Clearly you only have covered even numbers after the multiplication.
$endgroup$
– Leen Droogendijk
Oct 7 '13 at 4:30
$begingroup$
@mounaim: multiplying by 2 is a linear operation. If there were no duplicates before the multiplication, there will be no duplicates after the multiplication. Clearly you only have covered even numbers after the multiplication.
$endgroup$
– Leen Droogendijk
Oct 7 '13 at 4:30
$begingroup$
@mounmain: I don't know how to access your old acount you should open a question in meta.math.stackexchange.com
$endgroup$
– miracle173
Oct 7 '13 at 21:35
$begingroup$
@mounmain: I don't know how to access your old acount you should open a question in meta.math.stackexchange.com
$endgroup$
– miracle173
Oct 7 '13 at 21:35
|
show 1 more comment
$begingroup$
Not an answer, but some numerical data, generated using the following quick code:
#include <vector>
#include <iostream>
#include <cstdlib>
using namespace std;
void getCandidates(int sum, const vector<bool> &nums, vector<int> &choices)
{
choices.clear();
for(int i=0; i<(sum-1)/2; i++)
{
if(nums[i] && nums[sum-i-2] && i != sum-i-2)
{
choices.push_back(i);
}
}
}
bool recurse(const vector<bool> &nums)
{
int max=-1;
for(int i=0; i<nums.size(); i++)
{
if(nums[i])
max = i;
}
if(max == -1)
{
return true;
}
vector<int> cands;
getCandidates(max+1, nums, cands);
for(int i=0; i<cands.size(); i++)
{
vector<bool> copy = nums;
copy[max] = false;
copy[cands[i]] = false;
copy[max-cands[i]-1] = false;
if(recurse(copy))
return true;
}
return false;
}
void testSize(int size)
{
vector<bool> nums;
for(int i=0; i<size; i++)
nums.push_back(true);
cout << size << ": ";
if(recurse(nums))
cout << "yes";
else
cout << "no";
cout << endl;
}
int main()
{
for(int i=0; i<33; i++)
testSize(3*i);
return 0;
}
Output so far is pasted below. Worst-case runtime is exponential, so it may never get to 99, but I'll keep this updated as the program keeps running.
0: yes
3: yes
6: no
9: no
12: yes
15: yes
18: no
21: no
24: yes
27: yes
30: no
33: no
36: yes
39: yes
42: no
45: no
48: yes
51: yes
54: no
57: no
60: yes
63: yes
So far the answer seems to be "yes" whenever $n$ satisfies the necessary condition that $frac{n(n+1)}{2}$ is even.
EDIT: Here is the solution for 24 as requested by Leen above.
(14, 4, 10) (15, 3, 12) (17, 8, 9) (18, 7, 11) (19, 6, 13) (21, 5, 16) (22, 2, 20) (24, 1, 23)
answered Oct 4 '13 at 18:44
user7530user7530
34.8k759113
$endgroup$
1
$begingroup$
A couple observations that might help speed things up: any group of three has to contain either all even or one even and two odd numbers
$endgroup$
– Dennis Meng
Oct 4 '13 at 19:07
$begingroup$
Of course $n(n+1)/2$ must be even. Each "pod" has a sum of twice the largest element, hence even.
$endgroup$
– Oscar Lanzi
Jan 12 at 10:23
add a comment |
$begingroup$
Not an answer, but some numerical data, generated using the following quick code:
#include <vector>
#include <iostream>
#include <cstdlib>
using namespace std;
void getCandidates(int sum, const vector<bool> &nums, vector<int> &choices)
{
choices.clear();
for(int i=0; i<(sum-1)/2; i++)
{
if(nums[i] && nums[sum-i-2] && i != sum-i-2)
{
choices.push_back(i);
}
}
}
bool recurse(const vector<bool> &nums)
{
int max=-1;
for(int i=0; i<nums.size(); i++)
{
if(nums[i])
max = i;
}
if(max == -1)
{
return true;
}
vector<int> cands;
getCandidates(max+1, nums, cands);
for(int i=0; i<cands.size(); i++)
{
vector<bool> copy = nums;
copy[max] = false;
copy[cands[i]] = false;
copy[max-cands[i]-1] = false;
if(recurse(copy))
return true;
}
return false;
}
void testSize(int size)
{
vector<bool> nums;
for(int i=0; i<size; i++)
nums.push_back(true);
cout << size << ": ";
if(recurse(nums))
cout << "yes";
else
cout << "no";
cout << endl;
}
int main()
{
for(int i=0; i<33; i++)
testSize(3*i);
return 0;
}
Output so far is pasted below. Worst-case runtime is exponential, so it may never get to 99, but I'll keep this updated as the program keeps running.
0: yes
3: yes
6: no
9: no
12: yes
15: yes
18: no
21: no
24: yes
27: yes
30: no
33: no
36: yes
39: yes
42: no
45: no
48: yes
51: yes
54: no
57: no
60: yes
63: yes
So far the answer seems to be "yes" whenever $n$ satisfies the necessary condition that $frac{n(n+1)}{2}$ is even.
EDIT: Here is the solution for 24 as requested by Leen above.
(14, 4, 10) (15, 3, 12) (17, 8, 9) (18, 7, 11) (19, 6, 13) (21, 5, 16) (22, 2, 20) (24, 1, 23)
answered Oct 4 '13 at 18:44
user7530user7530
34.8k759113
$endgroup$
1
$begingroup$
A couple observations that might help speed things up: any group of three has to contain either all even or one even and two odd numbers
$endgroup$
– Dennis Meng
Oct 4 '13 at 19:07
$begingroup$
Of course $n(n+1)/2$ must be even. Each "pod" has a sum of twice the largest element, hence even.
$endgroup$
– Oscar Lanzi
Jan 12 at 10:23
add a comment |
$begingroup$
Not an answer, but some numerical data, generated using the following quick code:
#include <vector>
#include <iostream>
#include <cstdlib>
using namespace std;
void getCandidates(int sum, const vector<bool> &nums, vector<int> &choices)
{
choices.clear();
for(int i=0; i<(sum-1)/2; i++)
{
if(nums[i] && nums[sum-i-2] && i != sum-i-2)
{
choices.push_back(i);
}
}
}
bool recurse(const vector<bool> &nums)
{
int max=-1;
for(int i=0; i<nums.size(); i++)
{
if(nums[i])
max = i;
}
if(max == -1)
{
return true;
}
vector<int> cands;
getCandidates(max+1, nums, cands);
for(int i=0; i<cands.size(); i++)
{
vector<bool> copy = nums;
copy[max] = false;
copy[cands[i]] = false;
copy[max-cands[i]-1] = false;
if(recurse(copy))
return true;
}
return false;
}
void testSize(int size)
{
vector<bool> nums;
for(int i=0; i<size; i++)
nums.push_back(true);
cout << size << ": ";
if(recurse(nums))
cout << "yes";
else
cout << "no";
cout << endl;
}
int main()
{
for(int i=0; i<33; i++)
testSize(3*i);
return 0;
}
Output so far is pasted below. Worst-case runtime is exponential, so it may never get to 99, but I'll keep this updated as the program keeps running.
0: yes
3: yes
6: no
9: no
12: yes
15: yes
18: no
21: no
24: yes
27: yes
30: no
33: no
36: yes
39: yes
42: no
45: no
48: yes
51: yes
54: no
57: no
60: yes
63: yes
So far the answer seems to be "yes" whenever $n$ satisfies the necessary condition that $frac{n(n+1)}{2}$ is even.
EDIT: Here is the solution for 24 as requested by Leen above.
(14, 4, 10) (15, 3, 12) (17, 8, 9) (18, 7, 11) (19, 6, 13) (21, 5, 16) (22, 2, 20) (24, 1, 23)
answered Oct 4 '13 at 18:44
user7530user7530
34.8k759113
$endgroup$
Not an answer, but some numerical data, generated using the following quick code:
#include <vector>
#include <iostream>
#include <cstdlib>
using namespace std;
void getCandidates(int sum, const vector<bool> &nums, vector<int> &choices)
{
choices.clear();
for(int i=0; i<(sum-1)/2; i++)
{
if(nums[i] && nums[sum-i-2] && i != sum-i-2)
{
choices.push_back(i);
}
}
}
bool recurse(const vector<bool> &nums)
{
int max=-1;
for(int i=0; i<nums.size(); i++)
{
if(nums[i])
max = i;
}
if(max == -1)
{
return true;
}
vector<int> cands;
getCandidates(max+1, nums, cands);
for(int i=0; i<cands.size(); i++)
{
vector<bool> copy = nums;
copy[max] = false;
copy[cands[i]] = false;
copy[max-cands[i]-1] = false;
if(recurse(copy))
return true;
}
return false;
}
void testSize(int size)
{
vector<bool> nums;
for(int i=0; i<size; i++)
nums.push_back(true);
cout << size << ": ";
if(recurse(nums))
cout << "yes";
else
cout << "no";
cout << endl;
}
int main()
{
for(int i=0; i<33; i++)
testSize(3*i);
return 0;
}
Output so far is pasted below. Worst-case runtime is exponential, so it may never get to 99, but I'll keep this updated as the program keeps running.
0: yes
3: yes
6: no
9: no
12: yes
15: yes
18: no
21: no
24: yes
27: yes
30: no
33: no
36: yes
39: yes
42: no
45: no
48: yes
51: yes
54: no
57: no
60: yes
63: yes
So far the answer seems to be "yes" whenever $n$ satisfies the necessary condition that $frac{n(n+1)}{2}$ is even.
EDIT: Here is the solution for 24 as requested by Leen above.
(14, 4, 10) (15, 3, 12) (17, 8, 9) (18, 7, 11) (19, 6, 13) (21, 5, 16) (22, 2, 20) (24, 1, 23)
answered Oct 4 '13 at 18:44
user7530user7530
34.8k759113
edited Oct 4 '13 at 21:55
answered Oct 4 '13 at 18:44
user7530user7530
34.8k759113
answered Oct 4 '13 at 18:44
user7530user7530
34.8k759113
answered Oct 4 '13 at 18:44
user7530user7530
34.8k759113
34.8k759113
1
$begingroup$
A couple observations that might help speed things up: any group of three has to contain either all even or one even and two odd numbers
$endgroup$
– Dennis Meng
Oct 4 '13 at 19:07
$begingroup$
Of course $n(n+1)/2$ must be even. Each "pod" has a sum of twice the largest element, hence even.
$endgroup$
– Oscar Lanzi
Jan 12 at 10:23
add a comment |
1
$begingroup$
A couple observations that might help speed things up: any group of three has to contain either all even or one even and two odd numbers
$endgroup$
– Dennis Meng
Oct 4 '13 at 19:07
$begingroup$
Of course $n(n+1)/2$ must be even. Each "pod" has a sum of twice the largest element, hence even.
$endgroup$
– Oscar Lanzi
Jan 12 at 10:23
1
1
$begingroup$
A couple observations that might help speed things up: any group of three has to contain either all even or one even and two odd numbers
$endgroup$
– Dennis Meng
Oct 4 '13 at 19:07
$begingroup$
A couple observations that might help speed things up: any group of three has to contain either all even or one even and two odd numbers
$endgroup$
– Dennis Meng
Oct 4 '13 at 19:07
$begingroup$
Of course $n(n+1)/2$ must be even. Each "pod" has a sum of twice the largest element, hence even.
$endgroup$
– Oscar Lanzi
Jan 12 at 10:23
$begingroup$
Of course $n(n+1)/2$ must be even. Each "pod" has a sum of twice the largest element, hence even.
$endgroup$
– Oscar Lanzi
Jan 12 at 10:23
add a comment |
$begingroup$
Generalise $n$ and let $n=3m$. This problem is a laxer version of the following more restrictive one:
Partition ${1, dots, 3m}$ into $m$ 3-sets ${x_i, y_i, z_i}$, $i=1, dots, m$, where $x_i+y_i=z_i$ and $y_ileqslant m$.
This more restrictive problem is equivalent to one studied by Skolem and another studied by Nickerson. Nickerson's problem is in turn a variant of a problem studied by Langford. Nowakowski, ch.1, states these problems, shows equivalences among them, and also gives solutions, for which he cites Davies and Skolem (the latter two citations are taken from
the bibliography in Nowakowski).
R. J. Nowakowski. Generalizations of the Langford-Skolem problem. MS Thesis, Dept. Math., Univ. Calgary, May 1975.
R.O. Davies. On Langford's Problem. II, Math. Gaz. 43 (1959), pp.253-255.
T. Skolem. On certain distributions of integers in pairs with given differences. Math. Scand. 5 (1957), pp.57-58; M.R. 19, 1159.
answered Jan 12 at 10:06
Rosie FRosie F
1,302315
$endgroup$
add a comment |
$begingroup$
Generalise $n$ and let $n=3m$. This problem is a laxer version of the following more restrictive one:
Partition ${1, dots, 3m}$ into $m$ 3-sets ${x_i, y_i, z_i}$, $i=1, dots, m$, where $x_i+y_i=z_i$ and $y_ileqslant m$.
This more restrictive problem is equivalent to one studied by Skolem and another studied by Nickerson. Nickerson's problem is in turn a variant of a problem studied by Langford. Nowakowski, ch.1, states these problems, shows equivalences among them, and also gives solutions, for which he cites Davies and Skolem (the latter two citations are taken from
the bibliography in Nowakowski).
R. J. Nowakowski. Generalizations of the Langford-Skolem problem. MS Thesis, Dept. Math., Univ. Calgary, May 1975.
R.O. Davies. On Langford's Problem. II, Math. Gaz. 43 (1959), pp.253-255.
T. Skolem. On certain distributions of integers in pairs with given differences. Math. Scand. 5 (1957), pp.57-58; M.R. 19, 1159.
answered Jan 12 at 10:06
Rosie FRosie F
1,302315
$endgroup$
add a comment |
$begingroup$
Generalise $n$ and let $n=3m$. This problem is a laxer version of the following more restrictive one:
Partition ${1, dots, 3m}$ into $m$ 3-sets ${x_i, y_i, z_i}$, $i=1, dots, m$, where $x_i+y_i=z_i$ and $y_ileqslant m$.
This more restrictive problem is equivalent to one studied by Skolem and another studied by Nickerson. Nickerson's problem is in turn a variant of a problem studied by Langford. Nowakowski, ch.1, states these problems, shows equivalences among them, and also gives solutions, for which he cites Davies and Skolem (the latter two citations are taken from
the bibliography in Nowakowski).
R. J. Nowakowski. Generalizations of the Langford-Skolem problem. MS Thesis, Dept. Math., Univ. Calgary, May 1975.
R.O. Davies. On Langford's Problem. II, Math. Gaz. 43 (1959), pp.253-255.
T. Skolem. On certain distributions of integers in pairs with given differences. Math. Scand. 5 (1957), pp.57-58; M.R. 19, 1159.
answered Jan 12 at 10:06
Rosie FRosie F
1,302315
$endgroup$
Generalise $n$ and let $n=3m$. This problem is a laxer version of the following more restrictive one:
Partition ${1, dots, 3m}$ into $m$ 3-sets ${x_i, y_i, z_i}$, $i=1, dots, m$, where $x_i+y_i=z_i$ and $y_ileqslant m$.
This more restrictive problem is equivalent to one studied by Skolem and another studied by Nickerson. Nickerson's problem is in turn a variant of a problem studied by Langford. Nowakowski, ch.1, states these problems, shows equivalences among them, and also gives solutions, for which he cites Davies and Skolem (the latter two citations are taken from
the bibliography in Nowakowski).
R. J. Nowakowski. Generalizations of the Langford-Skolem problem. MS Thesis, Dept. Math., Univ. Calgary, May 1975.
R.O. Davies. On Langford's Problem. II, Math. Gaz. 43 (1959), pp.253-255.
T. Skolem. On certain distributions of integers in pairs with given differences. Math. Scand. 5 (1957), pp.57-58; M.R. 19, 1159.
answered Jan 12 at 10:06
Rosie FRosie F
1,302315
answered Jan 12 at 10:06
Rosie FRosie F
1,302315
answered Jan 12 at 10:06
Rosie FRosie F
1,302315
answered Jan 12 at 10:06
Rosie FRosie F
1,302315
1,302315
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%2f514796%2fspecial-subdivision-of-numbers-from-1-to-99%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
