Last week I rather unexpectedly was waylaid by a math problem, which I spent 5 days working on to the exclusion of everything else — eating, sleeping, studying chess,… A college friend of mine sent me the following question, which he discovered 25 years ago when he was in grad school and was not able to solve. Here is the problem:
There are an even number of players in a chess club, and they are going to split at random into two teams who will play against each other. The rules of the competition are supposed to be that the top player on team 1 plays against the top player on team 2, the second player on team 1 plays against the second player on team 2, etc. However, one of the coaches decides to cheat and rearrange the order of players on his team. Is there a strategy that will give his team a higher expected win total than it would have by following the rules? If so, what is the best strategy?
[Some clarifications if you actually want to work on the problem yourself: For simplicity, assume that all the players have different strengths, and that the stronger player will always beat the weaker player. You could try to solve the problem using the actual Elo model, but that would make it much harder, and it’s already hard enough as it is. Also, note that the cheating coach has to decide on his players’ seeding order independent of who is on the teams. So, for example, if he decides to play them in the order 3-1-5-2-4, he has to stick with that order no matter who the players on the other team are. Or to put it in a different way, he has perfect information about the strength of the players on his team, but no information about the strength of the players on the other team. Except he knows the other coach will rank them honestly.]
For those who don’t want to spend 5 days thinking about it, I’ll give you some partial answers. Yes, the cheating coach can do better. For example, with 4 players on the team he should play them in the order 4-1-2-3. The intuitive idea behind this is that the match 4 (on his team) versus 1′ (on the other team) is almost a guaranteed loss, but the other three matches (1 versus 2′, 2 versus 3′, and 3 versus 4′) have fairly high probabilities of being won by the cheating team. When you crunch the numbers, you’ll find that the cheating team wins, on average, 164/70 or 2.34 games with this strategy, versus (of course) 2 games if they don’t cheat.
For a mathematician, of course, the fascinating question is: Does this work for all values of N? (Where N is the number of players on each team.) Using a computer, my friend worked out the optimal strategies all the way up to N=13 (which involves some really gigantic numbers). He conjectures that the optimal strategy is always to “throw” a small number of games (say, x games) by playing your weakest player against the other team’s strongest, your second weakest against the second strongest, etc. Then from the x+1-st position on, you put your players in the normal, uncheating order. For example, if there are 8 players on the team, the best cheating strategy is to play them in the order 8-7-1-2-3-4-5-6. In other words, you “throw” the top 2 games for a pretty good shot at winning most of the other 6.
However, my friend wasn’t able to prove that the optimal strategy has this form, and after 5 days of working on the problem I couldn’t prove it either. Hey, he’s had 25 years to think about it, and I’ve only had 5 days! Also, even if the optimal strategy is of this form, we still don’t know the optimal choice for x, the number of games to “throw.”
If any of you have ideas or even proofs, let me know!
By the way, it was really interesting to immerse myself totally in a math problem. I hadn’t done it to this extent for years — basically since I changed careers and became a writer. It reminded me of what is so exciting about doing mathematics. It’s a lot like reading a novel. If you’re working on a hard enough problem, it will constantly surprise you. You never know what’s coming next, a breakthrough or a setback.
It also made me realize (which is probably obvious) that chess is sort of a substitute for math for me, now that I no longer do mathematical research as a career. However, chess is really not a completely adequate replacement for math. The reason is that the “problems” you have to solve in chess simply do not have the depth of math problems. A really good chess position can keep you discovering new things for hours — but not for days, weeks, months, or even years the way a good math problem can.
I realize that I am risking the wrath of my readers by saying this! However, I want to emphasize that by no means am I saying that chess is “inferior” to math. It’s just different; similar in many respects, but ultimately different, and the kind of satisfaction you get from it is different.
{ 4 comments… read them below or add one }
Math may pose “deeper” problems than chess, but when was the last time a top mathematician got hired as a fashion model?
🙂
The first question is what is the expected win total? Assuming the players are truly chosen at random, I would expect that half of the time the players on a board would outrank their opponent and half of the time they wouldn’t. So the answer to that question would be 50%, plus or minus some random error factor. Naturally it is possible that by random chance all of the players on one team will outrank each of the players on the other team, but the probability of that is extraordinarily low.
The best strategy to guarantee a winning percent that exceeds 50% seems pretty clear to me. The best strategy to optimize that winning percentage is a much harder question.
My solution to the first problem in strategy is to take the number of players on the cheating team,(N) divide by two,(N/2) and then subtract one.(N/2-1) That formula produces the number of players that will be shifted from the bottom of the list to the top. I would also play the shifted players in reverse ranking order. So, if I had 8 boards, n/2-1 =3. My board order would be 8,7,6 (shifting three players up and reversing the ranking order) then 1,2,3,4,5. You are almost certain to win the bottom three boards, and playing your number 6 player on bard three gives you a better chance to win that board than playing your number 8 player there..
I should point out that I am not a mathematician and can not prove any of these conjectures, but my solution feels right to me in an intuitive sense.
I have no idea how to solve the optimal solution question.
Your solution to me seems like the optimal and best solution, but I am no mathematician … But just thinking about Elo… If you sacrifice your 4th board to your opponents 1st board you have only sacrificed 1 point but in turn you have gained the maximum amount of Elo advantage possible to your other 3 players … Which should significantly increase there chance of winning there games so 4 1 2 3 seems to be the best solution … But to prove it??? I could never do that hehe
Hi Bryon, thanks for commenting on this post. It allows me to bring it up to date! My friend, who proposed the problem, has used a computer to find the optimal strategies for teams up to 20 players, and — under a mild assumption we haven’t proved yet — to find the probably optimal strategies for up to 500 players. Bottom line is that when there are 6 or fewer players, you should “sacrifice” one game. When there are 7 to 12 players, you should sacrifice two.
However, for those who are not satisfied with computer calculations (and what chess player would be?) I’m also pretty close to solving the problem analytically. It actually has a beautiful solution, which I will definitely write about here when I get enough of the details tied down. Roughly speaking, the number of games to sacrifice (where n is the number of players on each team) is sqrt(n ln n/2), where sqrt denotes the square root and ln is the natural logarithm. This is an overestimate, but not a very bad one. For example, for n greater than 90, you should sacrifice at least sqrt (n ln n/4) games and at most sqrt (n ln n/2) games.
{ 1 trackback }