Author |
Topic: Happy Competitors (Read 1825 times) |
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Happy Competitors
« on: Jan 24th, 2005, 2:05pm » |
 Quote  Modify
|
The n2 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?
|
|
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Happy Competitors
« Reply #1 on: Jan 24th, 2005, 3:29pm » |
Quote Modify
|
I go for the integer part of (n+1)[sup2]/2 - 1 ...
|
| « Last Edit: Jan 24th, 2005, 3:33pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Happy Competitors
« Reply #2 on: Mar 24th, 2005, 12:56am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Happy Competitors
« Reply #3 on: Mar 26th, 2005, 11:19pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print