Author |
Topic: One of each (Read 441 times) |
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender:
Posts: 1884
|
|
One of each
« on: Sep 5th, 2004, 11:45pm » |
Quote Modify
|
another bubbling away in my head puzzle. Need to make room. Can't find it, so here we go... n x n grid, n colours/numbers etc and n of each of them- ie if n=3, 3 red, 3 blue and 3 green counters. You can place these counters in the grid so that there is only one of each in every row and every column. That's not so hard. (at least, for small values of n) It gets trickier when you have to take into account the main diagonals. Then, clearly, n=2 is impossible. As is n=3. n=4 works. I can not get n=6 to work. I have come up with little explanations, which I like, but question their validity. So... is it possible? When is the next value of n not possible?
|
« Last Edit: Sep 5th, 2004, 11:54pm by Noke Lieu » |
IP Logged |
a shade of wit and the art of farce.
|
|
|
asterix
Guest
|
Is it only the 2 main diagonals that are not allowed a repeat? In that case a solution is 134625 261534 325461 452316 516243 643152
|
|
IP Logged |
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender:
Posts: 1884
|
|
Re: One of each
« Reply #2 on: Sep 6th, 2004, 5:50pm » |
Quote Modify
|
My admiration for you grows Asterix, whomever you are. Presumably you did that with the help of silicon, rather than just nutting it out? please so, what is the next value of n? Is there one?
|
|
IP Logged |
a shade of wit and the art of farce.
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: One of each
« Reply #3 on: Sep 7th, 2004, 3:50am » |
Quote Modify
|
I conjecture it's possible for all n>3
|
« Last Edit: Sep 7th, 2004, 5:10am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: One of each
« Reply #4 on: Sep 7th, 2004, 5:44am » |
Quote Modify
|
I think I have a general solution for odd n > 3, moreso, the same number never occurs twice on _any_ diagonal. It's just a matter of overlaying N different solutions of the N-queens problems. (Which is easy to do for odd numbers, but harder for even ones)
|
« Last Edit: Sep 7th, 2004, 5:45am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: One of each
« Reply #5 on: Sep 8th, 2004, 4:28pm » |
Quote Modify
|
For odd n, this seems to work: Let the first row, R1 be 1,2,3,...,n We form the second row R2 by cyclic right shift of R1 by 2. R3 = cyclic right shift of R2 by 2 and so on. Even n is tougher as towr noted.
|
|
IP Logged |
|
|
|
asterix
Guest
|
That method doesn't work for all odd n. If n is divisible by 3, the Southwest-Northeast diagonal will repeat multiples of 3.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: One of each
« Reply #7 on: Sep 9th, 2004, 7:58am » |
Quote Modify
|
on Sep 8th, 2004, 8:02pm, asterix wrote:That method doesn't work for all odd n. If n is divisible by 3, the Southwest-Northeast diagonal will repeat multiples of 3. |
| You are right.
|
|
IP Logged |
|
|
|
|