🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: rec.puzzles
Article #2656

Combinatorical problem

#2656
From: Matthew Newman
Date: Mon, 11 Jan 1993 17:10
16 lines
1162 bytes
Does anyone know the status on the following problem ?

Let S(n) be the set of all permutations of the integers 1..n
Let T(n) be the set of all transpositions (i.e. swapping
two numbers).

For which n can one find a set B(n) such that for all p in S(n)
either p is in B(n), or p differs by exactly one transposition
from an element of B(n), and such that no two elements from B(n)
differ by exactly one transposition ?

If such a B(n) exists, then it is of size n!/[1+n(n-1)/2] since
each element from B(n) differs by exactly one transposition from
n(n-1)/2 elements from S(n), thus we can rule out n=3,4,5. It is
trivially possible for n=2, and in 1974 (!) no other affirmative
solution was known.
Technical Details
Message-ID: <1993Jan11.171053.5143@client40.comlab.ox.ac.uk>
Path: arc1-ca.pugleaf.net!sparky!uunet!pipex!bnr.co.uk!uknet!comlab.ox.ac.uk!comlab.ox.ac.uk!mnewman

Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!pipex!bnr.co.uk!uknet!comlab.ox.ac.uk!comlab.ox.ac.uk!mnewman
From: mnewman@comlab.ox.ac.uk (Matthew Newman)
Newsgroups: rec.puzzles,sci.math
Subject: Combinatorical problem
Message-ID: <1993Jan11.171053.5143@client40.comlab.ox.ac.uk>
Date: 11 Jan 93 17:10:53 GMT
Sender: mnewman@comlab.ox.ac.uk (Matthew Newman)
Organization: Oxford University Computing Laboratory, UK
Lines: 16
Originator: mnewman@client40.comlab