You are Here: Home >< Maths

# Desperately need help!!!! Combinatorics | latin squares Watch

1. 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)

THANKS! X
2. 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.
3. 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.
4. OMG Thank you so much for this!

Surprisingly your solution actually makes sense to me
5. hehe my pleasure

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: December 9, 2010
Today on TSR

Find out how.

### Want £10K to start a business?

Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.