Wikipedia:Reference desk/Archives/Mathematics/2011 January 23

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 23

Tournament pairing question

There is a chess tournament of eight players. Each round there are four games, one player against another. If a pair of players have played in one round they cannot be paired again in a later round (a condition of the Swiss system tournament). For instance, round one pairings might be 1&2, 3&4, 5&6, 7&8 - none of these pairings should not occur in any subsequent rounds. Is it always possible to have five rounds (with eight players) without two players being paired with each other twice? (If it is not possible, how likely is it?) Bubba73 ^{You talkin' to me?} 06:19, 23 January 2011 (UTC)

Yes, you can have up to 7 rounds such that every player gets to play every other player. Number the players in binary form 000 to 111. The rounds are numbered from 001 to 111, that is, all the numbers except for all zeroes. In every round you then find each player's opponent by XORing his number with the round number.

This principle works for every number of players that is a power of 2. One can also have 6 players play 5 rounds (12,34,56 - 23,45,61 - 14,26,35 - 15,24,36 - 13,25,46). I don't know whether it is possible for other numbers of players. –Henning Makholm (talk) 06:47, 23 January 2011 (UTC)

OK, I didn't ask the question correctly. After four rounds of pairings under the condition that no player is paired with the same one twice, is it possible that the fifth round cannot be paired with that condition? That is, is it possible to construct a valid pairing of the first four rounds that would make it not possible to pair the fifth round? Bubba73 ^{You talkin' to me?} 07:15, 23 January 2011 (UTC)

I've tried and failed to do this, so I think it is impossible to be blocked at any round however awkwardly one has allocated the pairings in previous rounds, though I haven't managed to prove that it is always possible to complete the rounds. Perhaps Henning can find a neat proof? Dbfirs 13:15, 23 January 2011 (UTC)

... (later note) ... but I was wrong! Dbfirs 08:51, 25 January 2011 (UTC)

Start with a complete graph on eight vertices. A pairing of the players for a round of the tournament corresponds to a perfect matching in the graph; after each round, delete that perfect matching from the graph. After four rounds, the graph you will be left with is a cubic graph, since every player has played exactly four others. There are only five cubic graphs on eight vertices (see Table of simple cubic graphs#8 nodes), and all of them are Hamiltonian (in particular, they all have a perfect matching), so it is always possible to pair up the players for the fifth round. (There is a description of the LCF notation used to describe the simple cubic graphs earlier in the Wikipedia article, but I couldn't figure out what it was saying; MathWorld has a clearer explanation with examples.) —Bkell (talk) 14:22, 23 January 2011 (UTC)

OK, this occurred yesterday in a scholastic chess tournament, Swiss system, five rounds, eight players. For the fifth round, the software said that there was no valid way to make the pairings. It seemed to me that this shouldn't happen. The software accepts restrictions such as color assignments, but with all restrictions off, it still said that there was no set of pairings that adhered to Swiss system rules, without pairing a pair that had already played each other. I haven't got the data to see exactly why yet. It could be because of the nature of a Swiss, with like scores playing like scores, or something. Bubba73 ^{You talkin' to me?} 16:21, 23 January 2011 (UTC)

Yes, I think there must have been some other implicit restriction. I tried this just with a very simple grid, colouring in squares representing pairs of teams that had already been matched. The problem is hardly sufficiently complex to require a computer. Dbfirs 16:53, 23 January 2011 (UTC)

For eight players it is easy, but some of the sections have approximately 40 players, and you have to pair them according to the Swiss system rules, and a computer helps a lot. Bubba73 ^{You talkin' to me?} 17:31, 23 January 2011 (UTC)

Definitely worthwhile using a computer for 40 players. Dbfirs 18:09, 23 January 2011 (UTC)

Yes, and besides just doing the pairing, it prints lists for the players (and for the director to reference). It prints forms to record the results so they are input back into the software for scoring, etc. And it determines the final scores and winners (calculates tiebreaks too). Bubba73 ^{You talkin' to me?} 20:45, 23 January 2011 (UTC)

Do you have a record of who played who in the other rounds? If you give us that information, someone can work out an explicit set of pairings that works. The general proof already given seems plausible to me (although it's not really my area), but an explicit solution for this particular case may be more convincing. Chances are, the software's algorithm is flawed. Perhaps it tries too hard to make people play against others with similar scores and doesn't find all possible solutions. --Tango (talk) 18:27, 23 January 2011 (UTC)

I don't have the data yet, but I should within a few days. Bubba73 ^{You talkin' to me?} 20:45, 23 January 2011 (UTC)

The computer was presumably applying the black-white alternation rule, or the score-matching rule too strictly. It will sometimes be necessary to relax one or both of these rules to avoid repeat matchings. Dbfirs 20:52, 23 January 2011 (UTC)

The director had the black/white rule off. He also must not have had the score-matching rule too tight, because the pairing that the software recommended had a player with 3 points after 4 rounds paired with one with 1.5. (Of course, that may have been the best match. Bubba73 ^{You talkin' to me?} 00:16, 24 January 2011 (UTC)

The score-matching rule might need to be turned off completely for later rounds, but this should be built into the program. The most likely explanation (assuming no bug in the program) is that an error had been made in the data input. Dbfirs 08:18, 24 January 2011 (UTC)

Back to original answers to the wrong question. An easy way for all N (N is even) players to play all other players in (N-1) rounds is to (conceptually) sit them across a long table as pairs for round 1. One player (say top left player) stays still, the others all move clockwise 1 seat every round. -- SGBailey (talk) 15:44, 24 January 2011 (UTC)

Yes, that is a standard round-robin tournament. But even with that, if you don't follow a pattern you can get in a situation where there is no valid set of pairings for a round. I was wondering if something similar to that happened here. I should have the actual data soon. Bubba73 ^{You talkin' to me?} 16:39, 24 January 2011 (UTC)

Can you give an example of "if you don't follow a pattern you can get in a situation where there is no valid set of pairings for a round"? I couldn't generate this, despite deliberately trying to get stuck. Dbfirs 19:56, 24 January 2011 (UTC)

Sure. With six players

1. Round 1. 1 v 4, 2 v 5, 3 v 6
2. Round 2. 1 v 5, 2 v 6, 3 v 4
3. Round 3. 1 v 6, 2 v 4, 3 v 5

and the only remaining games are among 1, 2, 3 and 4, 5, 6, which cannot be paired off. Similarly, there is a way to make things unpairable with eight players. The idea here is to leave a 3-cycle and a 5-cycle of unplayed matches with 2 rounds to go, as follows:

1. Round 1. 1 v 6, 3 v 7, 5 v 8, 2 v 4
2. Round 2. 3 v 6, 5 v 7, 2 v 8, 1 v 4
3. Round 3. 5 v 6, 2 v 7, 4 v 8, 1 v 3
4. Round 4. 2 v 6, 4 v 7, 1 v 8, 3 v 5
5. Round 5. 4 v 6, 1 v 7, 3 v 8, 2 v 5

and after round 5, the only matches left to be played are the 3 matches among 6, 7, and 8, and the 5 matches among 1, 2, 3, 4, and 5 between consecutively-numbered (mod 5) players. RJaguar3 | u | t 00:01, 25 January 2011 (UTC)

Something like this happened in a 1970 tournament I played in. It was a team event (team of three against another team), set up for a five-round Swiss. Only six teams showed up. The tournament director didn't try to do a proper round-robin, thinking that any pairings would work (seems reasonable). We got to round 4 (I think it was) and there was no valid set of pairings. Bubba73 ^{You talkin' to me?} 01:15, 25 January 2011 (UTC)

Thanks RJaguar3 for showing that my intuitive guess was wrong! This illustrates the danger of generalising from a limited number of trials. The simple grid model that I used wasn't really suitable for the task and caused me to miss the (now) obvious. The tournaments can be finished, of course, but not in neat rounds. Perhaps the answer is to use a better-written computer program without bugs. Dbfirs 08:51, 25 January 2011 (UTC)

I got the data (crosstable) for the tournament. There are valid pairings for the fifth round where no one plays someone they have played before, but it required that someone with 3 points be paired against someone with only 1 point, and that is a violation of the Swiss tournament guidelines (but that is the best with the limited number of players). The program did not come up with that set of pairings. The director tried many swaps, and the program always objected. Bubba73 ^{You talkin' to me?} 20:53, 25 January 2011 (UTC)

Ah, so the bug was not in the pairing of the first four rounds, but in the over-emphasis on score-matching. It seems strange that this could not be switched off as an option. Send it back to the suppliers as unsuitable for its purpose and get a refund! Dbfirs 22:03, 25 January 2011 (UTC)

Well, the Swiss rule is that the player with 3 points would be paired from one from the next lower score group (players with the same score). But there were no eligible players in the next two lower score groups - an unusual situation because there were so few players. Bubba73 ^{You talkin' to me?} 23:02, 25 January 2011 (UTC)

... but the Swiss rule is not intended to go to five rounds with only eight players, is it? Dbfirs 00:28, 26 January 2011 (UTC)

You're right. Three rounds suffice for eight players. Usually there are more, but this time the high school section had eight, the middle school section had eight, and the elementry school section had 39. It is set up in advance for five rounds. Bubba73 ^{You talkin' to me?} 02:51, 26 January 2011 (UTC)

Quick question - showing an equation is insoluble (?)

Hi all,

I'm looking at solving Pell's equation and its variants, and I am having trouble showing an equation is insoluble in integers. I've already solved $x^{2}-31y^{2}=1$ and $x^{2}-31y^{2}=4$ using continued fraction convergents, and now I'm being asked to determine whether $x^{2}-31y^{2}=5$ is soluble in integers. Given that the previous 2 equations are, I suspect this one isn't. As such, I've tried playing around with a little modular arithmetic to derive some sort of contradiction, but all I keep getting is special cases (taking modulo 3, have y=3j+1, x=3k, then modulo 4 have k congruent to 1 or 3 mod 4, j congruent to to 1 or 3 mod 4, and so on), so I don't think that's going to come out nicely. Could anyone suggest how to show that this equation is insoluble? Most of the work is based around continued fractions so if there is such a solution then that's fine, but if there's something nice and simple using (e.g.) modular arithmetic which comes out cleanly, I'd be very happy too. Then again, perhaps I'm wrong and it is in fact soluble!

Thankyou for any help! :) Mathmos6 (talk) 12:28, 23 January 2011 (UTC)

$6^{2}-31\times 1^{2}=5$

$657^{2}-31\times 118^{2}=5$

$17583^{2}-31\times 3158^{2}=5$ Gandalf61 (talk) 15:17, 23 January 2011 (UTC)

There is a simpler solution... Algebraist 15:26, 23 January 2011 (UTC)

Indeed - just realised that and added it. Gandalf61 (talk) 15:28, 23 January 2011 (UTC)

... and then $1997274^{2}-31\times 358721^{2}=5$. Solutions are numerators and denominators of every fourth c.f. convergent to sqrt(31) - see OEIS sequence A041050 and sequence A041051. Gandalf61 (talk) 15:36, 23 January 2011 (UTC)

Ah, how foolish of me, should check simple solutions rather than trying to second-guess the questions :-) I didn't know the convergents solved these equations when the RHS was equal to anything but 1 - thankyou! Mathmos6 (talk) 19:16, 23 January 2011 (UTC)

Number system that subtracts as well as adds

In Mathematics made difficult, the author introduces a number system using subtraction as well as addition. The system is otherwise like decimal, but instead of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, it uses 4, 3, 2, 1, 0, 1, 2, 3, 4, 5. The natural numbers go like this:

• 0, 1, 2, 3, 4, 5, 14, 13, 12, 11, 10, 11, 12, 13, 14, 15, 24, 23, 22, 21, 20, 21, 22, 23, 24, 25...

My question is, does this system form a bijection with the decimal system, in other words, every natural number that can be written in one system can be written in exactly one way in the other system? JIP | Talk 19:34, 23 January 2011 (UTC)

I'm no expert in this area, but I know that every non-zero integer has two representations as a decimal number, for example 1 = 1.000… and 1 = 0.999…; where the … means infinite repetition of the previous digit. Thus:

$1+\lim _{m\to \infty }\left(\sum _{i=1}^{m}{\frac {0}{10^{i}}}\right)=\lim _{n\to \infty }\left(\sum _{j=1}^{n}{\frac {9}{10^{j}}}\right)=1\,.$

This might cause problems. There are lots of really smart guys and girls on here that know a lot more than me about this. I'm sure they'll give you an exact answer. But, in the meantime, I hope my reply serves as food for thought. — Fly by Night (talk) 20:41, 23 January 2011 (UTC)

It's just a decimal form of balanced ternary. I would be very surprised if there were any difficulties expressing rational numbers in that system, although it's possible there would be a difference between the irrational numbers that can be expressed in decimal and those that can be expressed in balanced decimal. I'd have to think about it... --Tango (talk) 20:54, 23 January 2011 (UTC)

I think that for every positive (probably negative too, but let's keep it simple) number, there is a unique balanced decimal expansion (Edit: except when the unbalanced expansion ends in all 5's, in which case there are two balanced expansions). In fact the digit $b_{i}$ of the balanced expansion can be found from digits $a_{i},\ a_{i+1}$ of an unbalanced expansion, $b_{i}=a_{i}-10[a_{i}>5]+[a_{i+1}>5]\;\!$. That this works should be provable by induction.

If this is true, then every rational number has a recurring unbalanced expansion and hence a recurring balanced one as well. Conversely, every recurring unbalanced expansion is rational, by evaluating the geometric sum. Also, numbers that end in all 0/9 in unbalanced have just one expansion in balanced. -- Meni Rosenfeld (talk) 11:12, 24 January 2011 (UTC)

... but you need a convention to decide whether the canonical balanced expansion of 5/9 is 0.5555..... or 1.4444..... Gandalf61 (talk) 13:19, 24 January 2011 (UTC)

Thanks, I've added this to my comment and hopefully it's correct now. -- Meni Rosenfeld (talk) 15:18, 24 January 2011 (UTC)

Stating the obvious here, but the system you describe is clearly countably infinite. Therefore it does indeed "form a bijection with the decimal system" for natural numbers. Staecker (talk) 13:24, 24 January 2011 (UTC)