5-uples around a table (hard puzzle)

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

5-uples around a table (hard puzzle)

Postby Goahead52 » Sun Sep 13, 2015 6:27 pm UTC

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)

Postby Cauchy » Sun Sep 13, 2015 11:35 pm UTC

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.

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

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

Postby Goahead52 » Sun Sep 13, 2015 11:43 pm UTC

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)

Postby Cauchy » Mon Sep 14, 2015 12:43 am UTC

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.

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

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

Postby Cradarc » Mon Sep 14, 2015 2:24 am UTC

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.

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

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

Postby Goahead52 » Mon Sep 14, 2015 11:27 am UTC

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.

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

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

Postby Goahead52 » Mon Sep 14, 2015 5:12 pm UTC

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)

Postby Cauchy » Mon Sep 14, 2015 7:19 pm UTC

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.

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

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

Postby Goahead52 » Mon Sep 14, 2015 7:32 pm UTC

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).

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

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

Postby Goahead52 » Mon Sep 14, 2015 7:43 pm UTC

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.

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

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

Postby Goahead52 » Thu Sep 17, 2015 1:32 am UTC

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)

Postby tomtom2357 » Tue Jan 12, 2016 2:30 pm UTC

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.

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

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

Postby Goahead52 » Tue Feb 09, 2016 5:35 pm UTC

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.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 8 guests