Hey there! Sign in to join this conversationNew here? Join for free

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

    • Thread Starter
    Offline

    0
    ReputationRep:
    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

    THANKS! X
    Offline

    1
    ReputationRep:
    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.
    Offline

    1
    ReputationRep:
    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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    OMG Thank you so much for this!

    Surprisingly your solution actually makes sense to me
    Offline

    1
    ReputationRep:
    hehe my pleasure
 
 
 
  • 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
    What newspaper do you read/prefer?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • 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

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