Results 1 to 4 of 4

Math Help - Permutations

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Permutations

    25 boys and 25 girls sit around a table. Is it always possible to find a person both of whose neighbours are girls?
    I don't think this is true. I worked with 5 boys and 5 girls to manufacture situations where it wasn't true. I want to avoid writing out a counterexample with 50 people!

    Is there a way to approach this using permutations? It seems to be that if you put them in Boy/Girl order, and then switch the two people before the person with two girls as neighbours then you get a nice counterexample.

    Swapping people around seems like it can be done using permutations.

    Anyway, I hope someone can help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Anonymous1's Avatar
    Joined
    Nov 2009
    From
    Big Red, NY
    Posts
    517
    Thanks
    1
    Can you manufacture a situation for the 5 boy, 5 girl case? Because I can't.

    You could argue that it if it holds for 25 boys and 25 girls, than it holds for two equal and odd amounts of boys and girls. Of course 1 boy and 1 girl does not work though.

    Here is the 3 case. Boys=1 Girls=0

    0 0
    111

    Now try to place the last girl.
    Last edited by Anonymous1; April 5th 2010 at 02:39 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by Anonymous1 View Post
    Can you manufacture a situation for the 5 boy, 5 girl case? Because I can't.

    You could argue that it if it holds for 25 boys and 25 girls, than it holds for two equal and odd amounts of boys and girls. Of course 1 boy and 1 girl does not work though.

    Here is the 3 case. Boys=1 Girls=0

    0 0
    111

    Now try to place the last girl.
    This. I couldn't find a way to do 5 either, or for any odd number. For even it's easy, just have everybody arranged in 2,2,2,2, etc. But with odd you will have one extra of each boy and girl to slot in somewhere. Then wherever they go there will be someone with 2 girls on each side.

    Post your solution to the 5 of each version. If you can do that then you can generalize for any odd numbered version.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Anonymous1's Avatar
    Joined
    Nov 2009
    From
    Big Red, NY
    Posts
    517
    Thanks
    1
    Quote Originally Posted by Showcase_22 View Post
    25 boys and 25 girls sit around a table. Is it always possible to find a person both of whose neighbours are girls?
    True.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Permutations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 13th 2009, 06:10 AM
  2. Permutations
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: November 26th 2009, 10:55 PM
  3. Permutations
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 28th 2009, 03:27 PM
  4. permutations
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 18th 2009, 02:38 AM
  5. Permutations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 16th 2008, 07:59 PM

Search Tags


/mathhelpforum @mathhelpforum