Article View: rec.puzzles
Article #2656Combinatorical problem
From: Matthew Newman
Date: Mon, 11 Jan 1993 17:10
Date: Mon, 11 Jan 1993 17:10
16 lines
1162 bytes
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!mnewmanShow 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