Hey I've only just joined TSR after being a guest for a couple years lol.
Ok I really need help with a little combinatorics problem. I swear combinatorics will be the death of me at university!
Here it is:
Let A be a Latin square of order n. Suppose that, for some positive integer r < n, only the numbers 1,...,r occur in the first r rows and r columns of A.
Show that n => 2r
(ie. show that n "is larger than or equal to" 2r)
Please please please!!! any help is better than no help at all
Desperately need help!!!! Combinatorics | latin squares Watch
- Thread Starter
- 09-12-2010 22:29
- 09-12-2010 22:37
Ok ill do my best, though im not sure this answer will suffice.
If you have a latin square of size r by r. you can fit all the different 1-r elements in this square by putting equal elements in diagonals. Now if you inspect the rth+1 column which lies just outside the square and is empty, you will see that if you wanted to fill it you would need r distinct elements, not equal to any of the 1-r elements you currently have used. Therefore n must contain at least another r elements.
Hope this makes sense.Last edited by methusaleh; 09-12-2010 at 22:38.
- 09-12-2010 22:42
Actually the initial configuration of the r by r square doesnt even matter-so long as it is latin.
just look at row one of the rby r square, you will have the numbers 1-r, therefore in column r+1 for row 1 you will have to put a number not belonging to the set (1...r).
Then you look at the second row in the column r+1, you cannot have the numbers 1-r, and in addition you cannot have the element you just put in row 1, column r+1.
If you continue this analysis you will see you need at least r more different elements to complete the n by n square.Last edited by methusaleh; 09-12-2010 at 22:46.
- Thread Starter
- 09-12-2010 22:56
OMG Thank you so much for this!
Surprisingly your solution actually makes sense to me
- 09-12-2010 23:51
hehe my pleasure