5uples around a table (hard puzzle)
Moderators: jestingrabbit, Moderators General, Prelates
5uples around a table (hard puzzle)
Hi everyone,
We have 252 5uples extracted from 10 numbers (1 to 10).
C(10,5)=252
We want to place them under constraint around a circular table.
Definition 1 :
Two 5uples are called brothers if they share 4 numbers.
Example : 12345 and 123410 are brothers.
Each 5uple has 25 brothers (C(5,4)*(C(5,1)).
Brotherhood is not transitive :
A=12345
B=12346
C=12367
A is brother of B but not brother of C
B is brother of A and brother of C
C is brother of B but not of A
Definition 2 :
We call distance d the number of seats at left and at right of some 5uple sitting around the table.
Example : d=5
We count 5 seats at left and 5 seats at right of a sitting 5uple.
The challenge is to place all the 252 5uples around a circular table such as if we choose any 5uple no brother will be sitting at the distance d with d maximal.
Example : if the maximal value is 8 then any 5uple out of the 252 will NOT have a brother sitting at the distance 8.
What is the value of d?
What are the seats choosen for the 252 5uples or in other words how are they going to be placed?
We have 252 5uples extracted from 10 numbers (1 to 10).
C(10,5)=252
We want to place them under constraint around a circular table.
Definition 1 :
Two 5uples are called brothers if they share 4 numbers.
Example : 12345 and 123410 are brothers.
Each 5uple has 25 brothers (C(5,4)*(C(5,1)).
Brotherhood is not transitive :
A=12345
B=12346
C=12367
A is brother of B but not brother of C
B is brother of A and brother of C
C is brother of B but not of A
Definition 2 :
We call distance d the number of seats at left and at right of some 5uple sitting around the table.
Example : d=5
We count 5 seats at left and 5 seats at right of a sitting 5uple.
The challenge is to place all the 252 5uples around a circular table such as if we choose any 5uple no brother will be sitting at the distance d with d maximal.
Example : if the maximal value is 8 then any 5uple out of the 252 will NOT have a brother sitting at the distance 8.
What is the value of d?
What are the seats choosen for the 252 5uples or in other words how are they going to be placed?
Re: 5uples around a table (hard puzzle)
Goahead52 wrote:Definition 2 :
We call distance d the number of seats at left and at right of some 5uple sitting around the table.
I do not understand you definition of distance here. Doesn't a given position have just one seat to its left and to its right?
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Re: 5uples around a table (hard puzzle)
Sorry if you misunderstood my problem.
At left of each 5uple there are 5uples sitting each one on a seat. When I say distance it means that you start counting from the left :1,2,3,....,d. Equally from the right : 1,2,3,...,d.
It was clear to all people who tried to answer the problem on other forums anyway.
My wording was not clear enough. If so I`m sorry I`m not native english speaker.
At left of each 5uple there are 5uples sitting each one on a seat. When I say distance it means that you start counting from the left :1,2,3,....,d. Equally from the right : 1,2,3,...,d.
It was clear to all people who tried to answer the problem on other forums anyway.
My wording was not clear enough. If so I`m sorry I`m not native english speaker.
Re: 5uples around a table (hard puzzle)
So you mean a distance between two seats? For example, the 5tuples within distance 5 of a given 5tuple are the ones that are up to five seats in either direction? That's what I thought you had meant, but then:
In that case, what do you mean by the maximal distance? If distance isn't a derived quantity of a single seat, then it doesn't really make sense to talk about the maximal distance.
Unless you mean the maximal distance between any two seats, in which case that maximal distance is 126 and the problem is trivial. Just pair each 5tuple with its complement; then no 5tuple is paired with one of its brothers. Seat pairs diametrically across from each other, and then no 5tuple is seated at maximal distance away from one of its brothers, because the one seat that's at maximal distance is occupied by a nonbrother.
In that case, what do you mean by the maximal distance? If distance isn't a derived quantity of a single seat, then it doesn't really make sense to talk about the maximal distance.
Unless you mean the maximal distance between any two seats, in which case that maximal distance is 126 and the problem is trivial. Just pair each 5tuple with its complement; then no 5tuple is paired with one of its brothers. Seat pairs diametrically across from each other, and then no 5tuple is seated at maximal distance away from one of its brothers, because the one seat that's at maximal distance is occupied by a nonbrother.
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Re: 5uples around a table (hard puzzle)
I think he means no brother will be sitting within distance d, where d is to be maximized.
Given a particular 4tuple identifier, you have a set of 26 tuples. These 26 tuples are arranged along the circle such that the distance between any two is maximized. Now, for a single identifier, this would simply involve spacing them equally around the circle. However, each tuple actually has 5 different 4tuple identifiers. So you have to take into account those as well.
I did some preliminary analysis and don't think a solution (if one exists) will have symmetry.
Given a particular 4tuple identifier, you have a set of 26 tuples. These 26 tuples are arranged along the circle such that the distance between any two is maximized. Now, for a single identifier, this would simply involve spacing them equally around the circle. However, each tuple actually has 5 different 4tuple identifiers. So you have to take into account those as well.
I did some preliminary analysis and don't think a solution (if one exists) will have symmetry.
This is a block of text that can be added to posts you make. There is a 300 character limit.
Re: 5uples around a table (hard puzzle)
What is required as condition is that in the range of d seats at left and d seats at right no brother is sitting there. There is no need for symmetry.
Let us that a 5uple is sitting in some seat (number 72 for example) then if the maximal distance is 4 for example : no brother will be sitting in seats : 7374757671706968. That is the only condition. The distance should be applied to any 5uple. If it holds than it is ok. If someone find 5 as maximal distance then 4 is not. There exists a maximal distance holding for any 5uple.
Let us that a 5uple is sitting in some seat (number 72 for example) then if the maximal distance is 4 for example : no brother will be sitting in seats : 7374757671706968. That is the only condition. The distance should be applied to any 5uple. If it holds than it is ok. If someone find 5 as maximal distance then 4 is not. There exists a maximal distance holding for any 5uple.
Re: 5uples around a table (hard puzzle)
Cradarc wrote:I think he means no brother will be sitting within distance d, where d is to be maximized.
Given a particular 4tuple identifier, you have a set of 26 tuples. These 26 tuples are arranged along the circle such that the distance between any two is maximized. Now, for a single identifier, this would simply involve spacing them equally around the circle. However, each tuple actually has 5 different 4tuple identifiers. So you have to take into account those as well.
I did some preliminary analysis and don't think a solution (if one exists) will have symmetry.
This one is very hard.
Until now no one answered to it either here or on other forums (french, english).
Re: 5uples around a table (hard puzzle)
So, just to be absolutely clear: the goal is to maximize the shortest distance between any two brothers (and then the target value of d is one less than this shortest distance)?
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Re: 5uples around a table (hard puzzle)
The goal is to find d maximal such as :
if you choose any 5uple on the table no brother will be sitting within that distance d (left and right).
Fining d=1 is easy (you did it) by putting 5uple and their complement : 12345 near 678910 and so on.
But d=1 is not maximal.
It exists for sure a value of d maximal (you have 252! possibilities of placing the 5uples).
if you choose any 5uple on the table no brother will be sitting within that distance d (left and right).
Fining d=1 is easy (you did it) by putting 5uple and their complement : 12345 near 678910 and so on.
But d=1 is not maximal.
It exists for sure a value of d maximal (you have 252! possibilities of placing the 5uples).
Re: 5uples around a table (hard puzzle)
There is a tricky way to split the problem in 2.
If you take 12345 and all his brothers + the 5uples sharing 3 numbers you will obtain a set of 126 5uples.
You do the same for 678910.
You will obtain 2 sets of 126 5uples.
Then you try to solve one of the 2 sets by sorting the set such as d maximal.
One you find d maximal then you have just to insert one by one the elements of the second set.
A naive algorithm to solve the set of 126 5uple is to start by one 5uple and as long as you find 5uples not brother in a choosen d you continue until the end.
If the d choosen is for example 4 then you try bigger value 5. Until you reach the maximal value.
If you take 12345 and all his brothers + the 5uples sharing 3 numbers you will obtain a set of 126 5uples.
You do the same for 678910.
You will obtain 2 sets of 126 5uples.
Then you try to solve one of the 2 sets by sorting the set such as d maximal.
One you find d maximal then you have just to insert one by one the elements of the second set.
A naive algorithm to solve the set of 126 5uple is to start by one 5uple and as long as you find 5uples not brother in a choosen d you continue until the end.
If the d choosen is for example 4 then you try bigger value 5. Until you reach the maximal value.
Re: 5uples around a table (hard puzzle)
Here is the split of 252 5uples.
The first set contains 126 5uples :
1,2,3,4,5
1,2,3,4,6
1,2,3,4,7
1,2,3,4,8
1,2,3,4,9
1,2,3,4,10
1,2,3,5,6
1,2,3,5,7
1,2,3,5,8
1,2,3,5,9
1,2,3,5,10
1,2,4,5,6
1,2,4,5,7
1,2,4,5,8
1,2,4,5,9
1,2,4,5,10
1,3,4,5,6
1,3,4,5,7
1,3,4,5,8
1,3,4,5,9
1,3,4,5,10
2,3,4,5,6
2,3,4,5,7
2,3,4,5,8
2,3,4,5,9
2,3,4,5,10
1,2,3,6,7
2,3,4,6,7
1,2,3,6,8
1,2,3,7,8
2,3,5,6,7
2,3,4,6,8
2,3,4,7,8
2,3,5,6,8
2,3,5,7,8
1,2,4,6,7
1,2,5,6,7
1,3,4,6,7
1,2,4,6,8
1,2,4,7,8
2,4,5,6,7
1,2,3,6,9
1,2,3,6,10
1,2,3,7,9
1,2,3,7,10
1,3,5,6,7
1,2,5,7,8
1,3,4,7,8
1,2,5,6,8
1,3,4,6,8
2,3,4,6,9
2,3,4,7,9
2,3,4,6,10
2,3,4,7,10
2,4,5,7,8
2,4,5,6,8
3,4,5,6,7
1,2,3,8,9
1,2,3,8,10
2,3,4,8,9
1,3,5,6,8
2,3,5,7,9
1,3,5,7,8
2,3,5,6,9
2,3,4,8,10
2,3,5,7,10
2,3,5,6,10
3,4,5,7,8
3,4,5,6,8
2,3,5,8,9
2,3,5,8,10
1,2,4,7,9
1,2,4,6,9
1,2,4,7,10
1,2,4,6,10
1,4,5,6,7
1,2,4,8,9
1,2,5,6,9
1,3,4,6,9
1,2,5,7,9
1,3,4,7,9
1,2,4,8,10
1,3,4,6,10
1,2,5,7,10
1,3,4,7,10
1,2,5,6,10
2,4,5,6,9
1,4,5,7,8
2,4,5,7,9
1,4,5,6,8
2,4,5,6,10
2,4,5,7,10
1,2,3,9,10
1,2,5,8,9
1,3,4,8,9
1,3,5,7,9
1,3,5,6,9
1,2,5,8,10
1,3,4,8,10
2,3,4,9,10
2,4,5,8,9
1,3,5,6,10
1,3,5,7,10
3,4,5,7,9
3,4,5,6,9
2,4,5,8,10
3,4,5,6,10
3,4,5,7,10
1,3,5,8,9
1,3,5,8,10
2,3,5,9,10
3,4,5,8,9
3,4,5,8,10
1,2,4,9,10
1,4,5,6,9
1,4,5,7,9
1,4,5,7,10
1,4,5,6,10
1,2,5,9,10
1,3,4,9,10
1,4,5,8,9
2,4,5,9,10
1,4,5,8,10
1,3,5,9,10
3,4,5,9,10
1,4,5,9,10
The second set is built using the complement.
Example
12345 will give 678910
12346 will 578910 and so on
So if we solve the first by placing any 5uple distant within d distance from his 2 brothers (one at left and the other at right) then we need just to insert between 2 elements of the first the complement picked from the second set.
12345
678910 (complement)
12367
458910 (complement)
and so on
I have found that d>=10 is doable.
I did not finish my job.
There are still some unsorted 5uples.
The first set contains 126 5uples :
1,2,3,4,5
1,2,3,4,6
1,2,3,4,7
1,2,3,4,8
1,2,3,4,9
1,2,3,4,10
1,2,3,5,6
1,2,3,5,7
1,2,3,5,8
1,2,3,5,9
1,2,3,5,10
1,2,4,5,6
1,2,4,5,7
1,2,4,5,8
1,2,4,5,9
1,2,4,5,10
1,3,4,5,6
1,3,4,5,7
1,3,4,5,8
1,3,4,5,9
1,3,4,5,10
2,3,4,5,6
2,3,4,5,7
2,3,4,5,8
2,3,4,5,9
2,3,4,5,10
1,2,3,6,7
2,3,4,6,7
1,2,3,6,8
1,2,3,7,8
2,3,5,6,7
2,3,4,6,8
2,3,4,7,8
2,3,5,6,8
2,3,5,7,8
1,2,4,6,7
1,2,5,6,7
1,3,4,6,7
1,2,4,6,8
1,2,4,7,8
2,4,5,6,7
1,2,3,6,9
1,2,3,6,10
1,2,3,7,9
1,2,3,7,10
1,3,5,6,7
1,2,5,7,8
1,3,4,7,8
1,2,5,6,8
1,3,4,6,8
2,3,4,6,9
2,3,4,7,9
2,3,4,6,10
2,3,4,7,10
2,4,5,7,8
2,4,5,6,8
3,4,5,6,7
1,2,3,8,9
1,2,3,8,10
2,3,4,8,9
1,3,5,6,8
2,3,5,7,9
1,3,5,7,8
2,3,5,6,9
2,3,4,8,10
2,3,5,7,10
2,3,5,6,10
3,4,5,7,8
3,4,5,6,8
2,3,5,8,9
2,3,5,8,10
1,2,4,7,9
1,2,4,6,9
1,2,4,7,10
1,2,4,6,10
1,4,5,6,7
1,2,4,8,9
1,2,5,6,9
1,3,4,6,9
1,2,5,7,9
1,3,4,7,9
1,2,4,8,10
1,3,4,6,10
1,2,5,7,10
1,3,4,7,10
1,2,5,6,10
2,4,5,6,9
1,4,5,7,8
2,4,5,7,9
1,4,5,6,8
2,4,5,6,10
2,4,5,7,10
1,2,3,9,10
1,2,5,8,9
1,3,4,8,9
1,3,5,7,9
1,3,5,6,9
1,2,5,8,10
1,3,4,8,10
2,3,4,9,10
2,4,5,8,9
1,3,5,6,10
1,3,5,7,10
3,4,5,7,9
3,4,5,6,9
2,4,5,8,10
3,4,5,6,10
3,4,5,7,10
1,3,5,8,9
1,3,5,8,10
2,3,5,9,10
3,4,5,8,9
3,4,5,8,10
1,2,4,9,10
1,4,5,6,9
1,4,5,7,9
1,4,5,7,10
1,4,5,6,10
1,2,5,9,10
1,3,4,9,10
1,4,5,8,9
2,4,5,9,10
1,4,5,8,10
1,3,5,9,10
3,4,5,9,10
1,4,5,9,10
The second set is built using the complement.
Example
12345 will give 678910
12346 will 578910 and so on
So if we solve the first by placing any 5uple distant within d distance from his 2 brothers (one at left and the other at right) then we need just to insert between 2 elements of the first the complement picked from the second set.
12345
678910 (complement)
12367
458910 (complement)
and so on
I have found that d>=10 is doable.
I did not finish my job.
There are still some unsorted 5uples.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: 5uples around a table (hard puzzle)
How much work has been done on the upper bound for d? Obviously d<=42, because there are 252 seats around the table, and 6 of the 5uples are mutual brothers. Also, a tuple has more brothers than just the one in a group of 6, so they would have to be placed at different distances, so d cannot be 42 (thus d<=41). Are there any more refined upper bounds for d?
Edit: d is not 41, as fitting the 25 neighbors around the circle with only 3+3+5+5+7=23 spots for the rings to go without violating d=41 is impossible.
Edit: d is not 41, as fitting the 25 neighbors around the circle with only 3+3+5+5+7=23 spots for the rings to go without violating d=41 is impossible.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: 5uples around a table (hard puzzle)
In any case it is a very hard puzzle.
I stopped working on it.
My goal was to work on bigger sets n>10
As I did not find a way to solve i for n=10 so I abandoned it for now.
I stopped working on it.
My goal was to work on bigger sets n>10
As I did not find a way to solve i for n=10 so I abandoned it for now.
Who is online
Users browsing this forum: No registered users and 12 guests