The New Sudoku Players' Forum

[Smythe Dakota]

Continuing in the projective geometry vain --

If N-1 is prime, one can construct a projectve plane with N points on each line as follows:

The points are:

1. Ordered pairs (x,y) where x and y are each integers in the range 0 through N-2 inclusive.
2. "Ordered singles" m in the range 0 through N-2 inclusive.
3. An "ordered zero" (an extra phantom point with no particular name).

The lines are:

A. Equations of the form y=xM+B where M and B are integers in the range 0 through N-2 inclusive.
B. Equations of the form x=A where A is an integer in the range 0 through N-2 inclusive.
C. An extra phantom line with no equations attached.

Points of type 1 are called "ordinary points". Points of types 2 and 3 are called "points at infinity".

Lines of types A and B are called "ordinary lines". The line of type C is called the "line at infinity".

An ordinary point is defined to be on an ordinary line in case the coordinates satisfy the equation. (All arithmetic is done modulo N-1). A type 2 point at infinity is defined to be on a type A ordinary line in case m=M. The type 3 point at infinity is on all type B ordinary lines. All points at infinity (types 2 and 3) are on the line at infinity (type C). No other "on" relationships exist, e.g. no ordinary point is on the line at infinity.

All of the above works only if N-1 is prime. Otherwise, the arithmetic and geometry don't work, e.g. if N=5 we have 2*2=0 which really screws things up.

That's not to say projective planes don't exist with N=5, just that they can't be constructed as described above. Such planes probably wouldn't enjoy the Pappas and Desargues properties (for those of you who know about such things), however.

Bill Smythe

[ronk]

rep'nA, please wait for roughly a day for ronk to figure it out himself...

Thanks for the thought, but I've given up.

[re'born]

Here is a similar problem:

25 of the top Sudoku players in the world come together for a 6-day tournament to decide who is the best. Each day, all 25 players lunch together in a banquet hall containing 5 tables which each sit 5 people. The organizer would like to seat people so that each player sits at the same table as every other player at least once. Can you help the organizer?

[udosuk]

Here is a similar problem:

Similar, but yours is easier than mine...


abcde
fghij
klmno
pqrst
uvwxy

afkpu
bglqv
chmrw
dinsx
ejoty

agmsy
bhntu
ciopv
djkqw
eflrx

ahoqx
bikry
cjlsu
dfmtv
egnpw

ailtw
bjmpx
cfnqy
dgoru
ehksv

ajnrv
bfosw
cgktx
dhlpy
eimqu

Just don't ask people to solve 36 players, 7 days, 6 tables...

[re'born]

Here is a similar problem:

Similar, but yours is easier than mine...

Just don't ask people to solve 36 players, 7 days, 6 tables...

But 49 people, 8 days and 7 tables should not be substantially harder. Or for that matter, try 289 people, 18 days and 17 tables.

[udosuk]

But 49 people, 8 days and 7 tables should not be substantially harder. Or for that matter, try 289 people, 18 days and 17 tables.

Yes they're easy... There is nothing interesting about it when the number of people is a square of prime... How about 64 people, 81 people and 100 people? (36 people is proved to be impossible...)

Regarding the student puzzle, here is a hint for those who haven't solved it or given up yet: why is a 4x4 diagonal sudoku relevant?

Oh and sorry Bill... Your projective geometry stuff is fascinating, but I wonder would those short of a Maths degree be scared away by all the jargons and stuffs... Projective plane is one method to solve this, but there are also other methods more "user friendly" to our community here...

PS: How do I make this appear: "     "?

[re'born]

But 49 people, 8 days and 7 tables should not be substantially harder. Or for that matter, try 289 people, 18 days and 17 tables.

Yes they're easy... There is nothing interesting about it when the number of people is a square of prime...

I wouldn't say that there is nothing interesting about it. To me, the fact that one can write down a general method for p^2 people, p+1 days and p tables is quite interesting.

[udosuk]

I wouldn't say that there is nothing interesting about it. To me, the fact that one can write down a general method for p^2 people, p+1 days and p tables is quite interesting.

The facts and the ideas themselves are quite interesting, but the solving process isn't once you get the "routine"... Meanwhile the case 64, 81 and even 16 (which is equivalent to my problem) has much more challenging and intriguing solving processes... I've just found out that the case of 100 has been ruled out by some maths experts some years ago using a supercomputer working for 9 years... Perhaps it would take 9 hours or less these days using a 1THz nanocomputer...

Here I'll include my systems to work out the (7,7,3) and (13,13,4) cases...

The (7,7,3) case:

Arrange a,b,c,d,e,f,g in 7 groups of 3, so that all letters are grouped with every other letter exactly once.

To start we group 'a' with the remaining 6 letters to form 3 groups:
1. abc
2. ade
3. afg

For the remaining 4 groups, we have to use the 6 letters other than 'a'.

First we arrange the last 2 letters "fg" to form a 2x2 Latin square:

Code: Select all

f g
g f

Next, we put the 2 letters before "de" along each column respectively:

Code: Select all

df eg
dg ef

Lastly, we put the 2 remaining letters "bc" along each row respectively:

Code: Select all

bdf beg
cdg cef

And thus we obtain the remaining 4 groups:
4. bdf
5. beg
6. cdg
7. cef

The (13,13,4) case:

Arrange a,b,c,d,e,f,g,h,i,j,k,l,m in 13 groups of 4, so that all letters are grouped with every other letter exactly once.

To start we group 'a' with the remaining 12 letters to form 4 groups:
1. abcd
2. aefg
3. ahij
4. aklm

For the remaining 9 groups, we have to use the 12 letters other than 'a'.

First we arrange the last 3 letters "klm" to form a 3x3 Latin square:

Code: Select all

k l m
m k l
l m k

Next we put in the 3 letters before "hij" to form a 3x3 Graeco-Latin square:

Code: Select all

hk il jm
im jk hl
jl hm ik

Next, we put the 3 letters before "efg" along each column respectively:

Code: Select all

ehk fil gjm
eim fjk ghl
ejl fhm gik

Lastly, we put the 3 remaining letters "bcd" along each row respectively:

Code: Select all

behk bfil bgjm
ceim cfjk cghl
dejl dfhm dgik

And thus we obtain the remaining 9 groups:
5. behk
6. bfil
7. bgjm
8. ceim
9. cfjk
10. cghl
11. dejl
12. dfhm
13. dgik

However, if you try to apply this method straight on the (21,21,5) case, you're bound to run into trouble... That's where our 4x4 diagonal sudoku comes to rescue... I'll post it next time when I finish writing it up...


And a little tip on posting:

To display multiple spaces without the [code] tags, you cannot use normal spaces (as typed with your spacebar)... Instead you need a special char called the "non-breaking" space, accessible by typing Alt-0160 on your numpad. That way you can type in as many spaces in a row as you like, and in tiny font as well... (Using the "Replace All" feature with your Notepad etc helps a lot too!)

Five     spaces     apart     !     

[udosuk]

Here is how to solve the (21,21,5) case, using our favourite pastime as the tool :

The (21,21,5) case:

Arrange the 21 consonants in 21 groups of 5, so that all letters are grouped with every other letter exactly once.

To start we group 'b' with the remaining 20 letters to form 5 groups:
1. bcdfg
2. bhjkl
3. bmnpq
4. brstv
5. bwxyz

For the remaining 16 groups, we have to use the 20 letters other than 'b'.

If we arrange the last 2 sets of 4 letters ("rstv","wxyz") into a random Graeco-Latin square,
it is not easy to put in the remaining 3 sets of 4 letters ("cdfg","hjkl","mnpq"),
because aside from rows & columns there isn't a simple 3rd way to divide the grid.
That's where a 4x4 diagonal Sudoku comes to help.

First we try to arrange the 4 letters "rstv" to form a 4x4 diagonal Sudoku:

Code: Select all

r s t v
t v . .
. . . .
. . . .

Using Sudoku skills, the above setup will allow us to easily fill a "most canonical" 4x4 diagonal Sudoku grid:

Code: Select all

r s t v
t v r s
v t s r
s r v t

Next, we try to put in the last 4 letters "wxyz" such that the resulting grid is a Graeco-Latin square,
and both sets of 4 letters each form a 4x4 diagonal Sudoku grid:

Code: Select all

rw sx ty vz
t. v. r. s.
v. t. s. r.
s. r. v. t.

Again using Sudoku skills, we can fill in "wxyz" to the grid while fulfilling the above conditions:

Code: Select all

rw sx ty vz
tz vy rx sw
vx tw sz ry
sy rz vw tx

Here we can see the advantage:
the blocks and the main diagonals imply that both "2+2" broken diagonals must contain totally different symbols.
Hence the 2 main diagonals and the 2 "2+2" broken diagonals divide the grid into 4 totally different sections.

Therefore we put the 4 letters before, "mnpq" along each main diagonal/"2+2" broken diagonal respectively:

Code: Select all

mrw nsx pty qvz
ntz mvy qrx psw
pvx qtw msz nry
qsy prz nvw mtx

Next, we put the 4 letters before "hjkl" along each column respectively:

Code: Select all

hmrw jnsx kpty lqvz
hntz jmvy kqrx lpsw
hpvx jqtw kmsz lnry
hqsy jprz knvw lmtx

Lastly, we put the 4 remaining letters "cdfg" along each row respectively:

Code: Select all

chmrw cjnsx ckpty clqvz
dhntz djmvy dkqrx dlpsw
fhpvx fjqtw fkmsz flnry
ghqsy gjprz gknvw glmtx

And thus we obtain the remaining 16 groups:
6. chmrw
7. cjnsx
8. ckpty
9. clqvz
10. dhntz
11. djmvy
12. dkqrx
13. dlpsw
14. fhpvx
15. fjqtw
16. fkmsz
17. flnry
18. ghqsy
19. gjprz
20. gknvw
21. glmtx

For the larger size cases, the pattern is (n^2-n+1, n^2-n+1, n).

When (n-1) is prime, there is a easy general way to make up a (n-1)x(n-1) square grid with n letters in each cell. So (31,31,6), (57,57,8), (133,133,12) etc are quite easy to work out.

But when (n-1) is composite it gets quite complicated. For 6 (43,43,7) it has been proved impossible because no Graeco-Latin square of order 6 exists (the "36 officers problem"). For 10 (111,111,11) as I mentioned someone has run a computer for 9 years to prove it's impossibility...

However, it was proven that when (n-1) is a prime power (e.g. 4=2^2, 8=2^3, 9=3^2) then it's possible to solve in a non-trivial way. Hopefully 8x8 and 9x9 Sudoku grids with some heavy additional constraints could help in solving the (73,73,9) and (91,91,10) cases...

I bet nobody guessed this problem was Sudoku-related when I first posted it...

And rep'nA, you have worked out the correct answer too... I think you were using group theory etc?

[ronk]

I bet nobody guessed this problem was Sudoku-related when I first posted it...

Very nice, and the permutation you posted has overall diagonal symmetry too

Code: Select all

  | 1  2  3  4  5 | 6  7  8  9 |10 11 12 13 |14 15 16 17 | 18 19 20 21 |
--+---------------+------------+------------+------------+-------------+
b | X  X  X  X  X |            |            |            |             |
c | X             | X  X  X  X |            |            |             |
d | X             |            | X  X  X  X |            |             |
f | X             |            |            | X  X  X  X |             |
g | X             |            |            |            | X  X  X  X  |
--+---------------+------------+------------+------------+-------------+
h |    X          | X          | X          | X          | X           |
j |    X          |    X       |    X       |    X       |    X        |
k |    X          |       X    |       X    |       X    |       X     |
l |    X          |          X |          X |          X |          X  |
--+---------------+------------+------------+------------+-------------+
m |       X       | X          |    X       |       X    |          X  |
n |       X       |    X       | X          |          X |       X     |
p |       X       |       X    |          X | X          |    X        |
q |       X       |          X |       X    |    X       | X           |
--+---------------+------------+------------+------------+-------------+
r |          X    | X          |       X    |          X |    X        |
s |          X    |    X       |          X |       X    | X           |
t |          X    |       X    | X          |    X       |          X  |
v |          X    |          X |    X       | X          |       X     |
--+---------------+------------+------------+------------+-------------+
w |             X | X          |          X |    X       |       X     |
x |             X |    X       |       X    | X          |          X  |
y |             X |       X    |    X       |          X | X           |
z |             X |          X | X          |       X    |    X        |
--+---------------+------------+------------+------------+-------------+

[re'born]

And rep'nA, you have worked out the correct answer too... I think you were using group theory etc?

Yes. Working out the smallest example you gave did not help me see the pattern (though it does fit the pattern I eventually found). So I worked out that the next example would be the 13,13,4 case. Here I used the symmetric group on 3 letters, Sym(3), to help find the permutations. This doesn't work for the 21,21,5 case as Sym(4) has elements of the form (12) and (12)(34) which cause problems. However, if you only take the odd permutations, i.e., elements of Sym(4)\Alt(4), then you can arrange things in such a way as to make things work. I won't elaborate any further as I doubt anyone is interested in a mini-lecture on elementary group theory.

I haven't thought about the higher cases yet, so I don't know if this method will work (at least for the cases where it has a chance).

[udosuk]

Thanks for the info, guys... I think I need to grab a text book to revise about symmetric groups etc...

Meanwhile there is an alternative system to work out the (21,21,5) case, which would produce a different but isomorphic solution to the one I (and rep'nA) worked out:

The (21,21,5) case:

The semester lasts 21 weeks.
The class consists of 21 students.
Each week 5 of the students are rostered to form a duty group.
At the end of the semester, each student must have been on duty for exactly 5 weeks.
Also, each student must have been grouped with everyone else.

Using the 21 consonants to represent the students...

Suppose 'b' is the class monitor. And "cdfgh" are 5 prefects.
The remaining 15 students are partitioned into 3 normal sets of 5: "jklmn", "pqrst", "vwxyz".

The first 5 weeks would see the class monitor grouped with a prefect and 1 member from each normal set:
1. bcjpv
2. bdkqw
3. bflrx
4. bgmsy
5. bhntz

After that the class monitor won't need to be on duty anymore and will focus on monitoring.

In week 6 the 5 prefects will be on duty together, to get familiar with the work.
6. cdfgh

After that each of the 15 remaining weeks will see a prefect act as a leader, leading 4 "normal" students.

The next 5 weeks will have 2 students from each of normal set 1 & 2 to join a prefect they haven't been grouped with:
7. cknrs
8. djlst
9. fkmpt
10. glnpq
11. hjmqr

The next 5 weeks will have 2 students from each of normal set 2 & 3 to join a prefect they haven't been grouped with:
12. cqtxy
13. dpryz
14. fqsvz
15. grtvw
16. hpswx

The last 5 weeks will have 2 students from each of normal set 1 & 3 to join a prefect they haven't been grouped with:
17. clmwz
18. dmnvx
19. fjnwy
20. gjkxz
21. hklvy

Note: when assigning students from week 7 to 21, we construct a 5x3 array of the 3 sets involved:

Code: Select all

c j p
   /
d k q
 /
f l r
 \
g m s
   \
h n t

And we try to group students along the '<' shape, wrapping on the edges if necessary.

I don't know why this works... And apparently we can apply similar routines to work on the (7,7,3) and (13,13,4) cases, as well as higher cases... However I'm still more inclined to the "Sudoku" approach...

[udosuk]

Just when you think you've figured out a problem, you discover a shortcut that makes the whole thing a easy cake for the kid...

No need for any projective geometry... OR group theory... Or Sudoku/Latin squares...

What you need is just a simple set of numbers, called the "Cyclic Difference Set" (here is a simple introduction)... With it you can generate any answer totally painlessly...

For an example, just try to work out the (7,7,3) case... You need a size-3 CDS for modulo 7 (0..6)... {0,1,3} is a trivial answer:

Code: Select all

  0 1 3
 +-----
0|. 1 3
1|6 . 2
3|4 5 .

Now, just write down the 7 letters on a row, and mark the 3 positions according to the CDS:

Code: Select all

0 1   3
A B C D E F G

Next, write down the next 2 rows starting with the marked letters, following the same cyclic order:

Code: Select all

A B C D E F G
B C D E F G A
D E F G A B C

Now the 7 columns will give us the answer directly! (It'll take some thinking to see why it must be true, but it works like magic!)

For the (13,13,4) case, just work out a size-4 CDS for modulo 13 (0..12):

Code: Select all

   0  1  3  9
 +-----------
0| .  1  3  9
1|12  .  2  8
3|10 11  .  6
9| 4  5  7  .

({0,1,4,6} is another possible CDS...)

Then we list out the 4 rows of letters:

Code: Select all

0 1   3           9
A B C D E F G H I J K L M
B C D E F G H I J K L M A
D E F G H I J K L M A B C
J K L M A B C D E F G H I

See? Just 15 seconds of work and you get all the answers...

Finally, for the (21,21,5) case, it took some trying but I'm sure it's not too hard to find the size-5 CDS {0,1,4,14,16} for modulo 21 (0..20):

Code: Select all

    0  1  4 14 16
  +--------------
 0| .  1  4 14 16
 1|20  .  3 13 15
 4|17 18  . 10 12
14| 7  8 11  .  2
16| 5  6  9 19  .

0 1     4                  14  16
B C D F G H J K L M N P Q R S T V W X Y Z
C D F G H J K L M N P Q R S T V W X Y Z B
G H J K L M N P Q R S T V W X Y Z B C D F
S T V W X Y Z B C D F G H J K L M N P Q R
V W X Y Z B C D F G H J K L M N P Q R S T

Using this method higher order problems such as (57,57,8) and (73,73,9) can be solved in no time, once you work out the CDS {0 1 3 13 32 36 43 52} and {0 1 12 20 26 30 33 35 57} respectively...