## 5-uples around a table (hard puzzle)

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### 5-uples around a table (hard puzzle)

Hi everyone,

We have 252 5-uples 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 5-uples are called brothers if they share 4 numbers.
Example : 1-2-3-4-5 and 1-2-3-4-10 are brothers.
Each 5-uple has 25 brothers (C(5,4)*(C(5,1)).
Brotherhood is not transitive :
A=1-2-3-4-5
B=1-2-3-4-6
C=1-2-3-6-7

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 5-uple sitting around the table.

Example : d=5
We count 5 seats at left and 5 seats at right of a sitting 5-uple.

The challenge is to place all the 252 5-uples around a circular table such as if we choose any 5-uple no brother will be sitting at the distance d with d maximal.

Example : if the maximal value is 8 then any 5-uple 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 5-uples or in other words how are they going to be placed?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

### Re: 5-uples around a table (hard puzzle)

Goahead52 wrote:Definition 2 :

We call distance d the number of seats at left and at right of some 5-uple 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.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: 5-uples around a table (hard puzzle)

Sorry if you misunderstood my problem.
At left of each 5-uple there are 5-uples 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.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

### Re: 5-uples around a table (hard puzzle)

So you mean a distance between two seats? For example, the 5-tuples within distance 5 of a given 5-tuple 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 5-tuple with its complement; then no 5-tuple is paired with one of its brothers. Seat pairs diametrically across from each other, and then no 5-tuple is seated at maximal distance away from one of its brothers, because the one seat that's at maximal distance is occupied by a non-brother.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

### Re: 5-uples 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 4-tuple 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 4-tuple 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.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: 5-uples 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 5-uple 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 : 73-74-75-76-71-70-69-68. That is the only condition. The distance should be applied to any 5-uple. 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 5-uple.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: 5-uples 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 4-tuple 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 4-tuple 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).

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

### Re: 5-uples 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.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: 5-uples around a table (hard puzzle)

The goal is to find d maximal such as :
if you choose any 5-uple 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 5-uple and their complement : 1-2-3-4-5 near 6-7-8-9-10 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 5-uples).

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: 5-uples around a table (hard puzzle)

There is a tricky way to split the problem in 2.
If you take 1-2-3-4-5 and all his brothers + the 5-uples sharing 3 numbers you will obtain a set of 126 5-uples.
You do the same for 6-7-8-9-10.
You will obtain 2 sets of 126 5-uples.
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 5-uple is to start by one 5-uple and as long as you find 5-uples 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.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: 5-uples around a table (hard puzzle)

Here is the split of 252 5-uples.

The first set contains 126 5-uples :

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
1-2-3-4-5 will give 6-7-8-9-10
1-2-3-4-6 will 5-7-8-9-10 and so on

So if we solve the first by placing any 5-uple 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.

1-2-3-4-5
6-7-8-9-10 (complement)
1-2-3-6-7
4-5-8-9-10 (complement)
and so on

I have found that d>=10 is doable.
I did not finish my job.
There are still some unsorted 5-uples.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: 5-uples 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 5-uples 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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: 5-uples 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.