wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Happy Competitors
        
(Message started by: THUDandBLUNDER on Jan 24^th, 2005, 2:05pm)

Title: Happy Competitors
Post by THUDandBLUNDER on Jan 24^th, 2005, 2:05pm

The n² participants in a competition are seated in an n x n square. According to their results, all the competitors have been given different rankings. Each person asks his or her immediate neighbours (sitting left, right, ahead, or behind) what ranking they have. A competitor will be happy if at most one neighbour has a better ranking. What is the maximum possible number of happy competitors?

Title: Re: Happy Competitors
Post by JocK on Jan 24^th, 2005, 3:29pm

I go for [hide] the integer part of (n+1)[sup2]/2 - 1 [/hide]...

Title: Re: Happy Competitors
Post by Deedlit on Mar 24^th, 2005, 12:56am

Hello! Just stumbled onto these forums, and I was pretty impressed with the level of mathematics that people display here.

I haven't got the answer yet, but you can get at least 5/8 n^2. Color the board as a checkerboard, and add in black squares to form plus signs; you can tile the plane with these, and it has density 5/8. Basically the center of the plus sign will beat the ends, and the ends will beat everyone else, so everyone in a plus sign will be happy. In a square you can always take advantage of the border to push it a little past 5/8.

For small boards, you can do a little better by having concentric rings, starting from the outer border; for n=2,3,4,5,6 you get 4,8,12,17,24 happy people with this strategy.

It might be hard to prove an exact maximum for all n here, but asymptotics are probably not too hard.

Title: Re: Happy Competitors
Post by Deedlit on Mar 26^th, 2005, 11:19pm

There's a better strategy that gets at least 2/3 n^2:

AAAAAAAAAA
ABABABABAB
BABABABABA
AAAAAAAAAA
ABABABABAB
BABABABABA
...

where the A's are happy people, the B's are unhappy people. This gives:

for n = 6k: 4k(6k) happy people
for n = 6k+1: (4k + 1)(6k + 1) happy people
for n = 6k+2: (4k + 1.5)(6k + 2) happy people
for n = 6k+3: (4k + 2)(6k + 3) + 1 happy people
for n = 6k+4: (4k + 3)(6k + 4) happy people
for n = 6k+5: (4k + 3.5)(6k+5) + 0.5 happy people

This is the best that can be done taking every third row, but I can't prove it for all cases. However, this is in fact the maximum density of happy people. If we let h be that density, a be the density of happy neighbors to happy people, and b be the density of happy neighbors to unhappy people, we have

h = a(1-h) + bh <= 1 - h + bh
h (2-b) <= 1
h <= 1/(2-b)

Since each happy-happy neighboring gives a happy person one loss, the average number of happy neighbors to happy people is no more than two, so b <= 1/2, and h <= 2/3.

If there isn't a numerical ranking, but just a directed graph of who beats who (so loops are possible) then we can get

AAAAAAAAAA
AABABABABA
ABABABABAB
AAAAAAAAAA
ABABABABAB
BABABABABA
AAAAAAAAAA
...

this gives an improvement of one happy person every six rows. Using this strategy, and taking advantage of odd n when possible, we get:

n = 6k: 4k(6k) + k happy people
n = 6k+1: (4k + 1)(6k + 1) + k happy people
n = 6k+2: (4k + 1.5)(6k + 2) + k + 1 happy people
n = 6k+3: (4k + 2)(6k + 3) + k + 1 happy people
n = 6k+4: (4k + 3)(6k + 4) + k + 1 happy people
n = 6k+5: (4k + 3.5)(6k + 5) + k + 1.5 happy people

In general, a configuration of happy people is possible if every connected component of happy people (everyone in the group is connected either vertically or horizontally) contains at most one circuit. If there is a circuit, then the arrows must go in a loop around the circuit, and all remaining arrows must be directed outward from the loop. This works exactly when there isn't another circuit. Of course, if there isn't a circuit at all, we can just pick anyone and direct all arrows away from him.

For the original problem, there cannot be a circuit. So the problem is really to find the maximum number of squares that do not contain any circuits. I imagine this is a known result, somewhere.