June 2019 - mathfun@mailman.xmission.com

Re: [math-fun] optimal advance tournament scheduling
by Dan Asimov 19 Jun '19

19 Jun '19

Tomas, please remind me of just what the program is computing — thanks. —Dan ----- Okay, I wrote and ran the code for the 8/4 case over the six graphs and this is what I got. I'm a bit surprised we get so much information . . . the graphs are in the order I gave the graph list before. TL;DR: the pretty graph we've been talking about is, indeed, the best one. ... ... Average bits 22.6464 18:1728 19:2352 20:3504 21:7200 22:4152 23:6528 24:5712 25:3576 26:3120 27:1608 28:840 ... ... -----

2 2

Re: [math-fun] optimal advance tournament scheduling
by Keith F. Lynch 19 Jun '19

19 Jun '19

I'm thinking out loud (silently, since this is typing, not talking) about how to program the "optimal advance tournament scheduling" problem. Partly to clarify my own thoughts, and partly in hopes that someone else will find any errors or come up with better ideas. (For instance Mike Beeler noticed I said, and looked up, "trivalent" when I meant "tetravalent." Thanks.) First, I've decided not to bother excluding non-connected graphs, as there are so few that it would take more time to exclude them than getting rid of them would save. We're only dealing with graphs that have 8 vertices and 16 edges. How can such a graph be non-connected? Can it have 4 vertices in each piece? No. A complete graph on 4 vertices is 6 edges, for a total of 12. (I didn't mention earlier, as it was too obvious, that no player will play more than one game with each other player, as the additional game would provide no new information.) What about 5 and 3? Still no, as the complete graphs on 5 and 3 have a total of 13 edges. What about 6 and 2? Yes, but there's only one such graph; it consists of the complete graphs of 6 and 2 vertices. And the score of that is 16, regardless of which players are in which positions, since we have complete information about the ordering of the 6 and complete information about the ordering of the other 2, but no information that relates any of the former to either of the latter, and 28 - 2*6 = 16. Knowing the score of that arrangement will be a useful test of my program. What about 7 and 1? Yes. There are at most (21 choose 16)*8 labeled graphs. That's 162792, a very small proportion of the 30421755 total labeled graphs, about 1/187. (Both numbers are actually smaller, as I'm ignoring symmetries.) What about graphs in more than two pieces? There aren't any. Not with 8 vertices and 16 edges. All graphs will always be represented by an 8x8 matrix with a 1 at both A,B and B,A meaning that A and B play a game, and 0 in both those locations meaning that they don't. There will be 16 1s and 12 0s in each half of the (symmetric) matrix, excluding the main diagonal (whose contents are irrelevant). Or, if it's a directed graph, with a 1 at A,B and a 0 at B,A meaning that A won a game against B, a 1 at B,A and a 0 at A,B meaning that B won a game against A, a 0 in both locations if they didn't play each other, and a 1 in both locations if there's a bug in my program. I can see two main approaches. I can generate all 30-million+ labeled graphs. In each case each vertex number will be the same as the player rank number. I need to solve each of them, by placing an arrow on each edge, from the stronger (lower numbered) to the weaker (higher numbered) player. I then raise that directed-graph non-symmetric matrix to every power, 1 through 7, add those 7 matrices together, and subtract the number of 0s in the sum matrix (other than those on the main diagonal) from 28 to get the score. After doing that with all 30 million+, I average the scores over the equivalent graphs, i.e. those which are identical except for the labels on the vertices, i.e. those whose non-directed matrices are identical under a permutation of the rows combined with an identical permutation of the columns. The other approach is to somehow generate only one of each equivalent graph. I could then try all 8! ways of assigning player rank numbers to vertex numbers (instead of those numbers always being the same), and figure out the score of each of them by the above method, then take the average of the scores. But I can get away with only trying 8!/2 ways, doubling the speed, due to symmetry. If I always put player 1 on one of vertices 1 through 4 rather than 5 through 8, I don't lose any information, since I'm only excluding mirror-image arrangements, in which the players are ranked in the opposite order, and those have the exact same scores. (Digression: Decades ago I noticed these same two kinds of symmetries in magic squares. How many order-4 magic squares with numbers 1-16 (or 0-15, or any other 16 equally spaced numbers) are there? The number usually given is 880, in which rotations and reflection are allowed. But you can permute the rows if you permute the columns the same way. That brings it down to 220. But there's also a very different kind of magic-preserving symmetry: Reverse the order of the numbers. That doesn't knock it down to 110, however, due to a broken symmetry, i.e. that transform sometimes links an arrangement back to a permutation of itself rather than to a distinct arrangement. If I recall correctly, it knocks it down to 166. I recall that at about the same time I was counting 4x4 magic square, our listmaster was doing the same with 5x5. I recall reading that he used the row-permutation symmetry, but I don't know whether he also used the number reversal symmetry.) While I'm averaging the scores of the equivalent graphs, I can also keep track of whether the maximum score of any of them is always 28, (and if it's not, whether it's because I've stumbled into one of the few non-connected graphs), and what the minimum score is, and any other statistic anyone is interested in, within reason. So, how can I find only one of each set of equivalent graphs? I can put the 12 0s and 16 1s in the upper right half of the (non-directional, symmetric) matrix in order, left to right, top to bottom, to make a unique 28-bit number, and define the canonical one as being the smallest in the equivalence class, but that doesn't help me *generate* it, as contrasted with generating all 30-million+ matrices and discarding most of them. And now to catch up on replies in this thread: Mike Beeler <mikebeeler2(a)gmail.com> wrote: > In the real world, there could be a further scheduling criteria > about ?exhaustion?, if an otherwise worse player can beat a better > player if the better player has played more games. Exhaustion isn't an issue if, as I suspect Dan meant, every player is playing simultaneously. Also, it contradicts my arbitrary axioms of consistency and transitivity. > Even further, the games each has played perhaps should be weighted > by the (estimated) strength of the opponent. Estimated by whom, how? We have no information about any of the players other than whom they beat and whom they are beaten by in this 16-game tournament. > I agree, there might be some graphs that suck. That is, the graph > is all in one piece, but no outcome of the games allows a complete > ranking of all the players. In Dan?s case of 8 players and 16 > games, it is merely my intuition that there are no such graphs. I tried, with pen and paper, to find a connected graph without a non-looping path of length 7. Perhaps a stellate graph, in which several short loops emanate from one very busy player? I wasn't able to find one. But then I didn't try very hard. Any graph with a non-looping path of length 7 will have a perfect score for at least two possible rankings of players. And graphs without such a path, if any exist, might have a perfect score anyway. It's one more thing to have my program check for. Mike Beeler <mikebeeler2(a)gmail.com> wrote: > Indeed, my concern is with the definition of "the maximum > information = about player's strengths=E2=80=9D, as Dan put it. > In a competition, it = may be more important to identify the top > player(s) than to obtain the = maximum information theoretic > information. If so, the organizer would have arranged the tournament to seek that information, by repeatedly choosing the winners of each game and pitting them against each other. But Dan said that who plays whom doesn't depend on who wins which games, so I conclude that the organizer doesn't care more about who is the best player than about the rankings of the other players.

4 4

[math-fun] Dots and Triangles
by Tomas Rokicki 19 Jun '19

19 Jun '19

Dots and Boxes is a nice simple children's game, right? Elwyn Berlekamp (the "wyn" in Winning Ways) showed us the surprising depths to this game. Here's a tiny variant on a tiny board; just nine triangles. You get to choose to go first or second. Can you beat it? I'm finding it surprisingly difficult. https://tomas.rokicki.com/dottri.html This should work on your mobile phone too. -tom -- -- http://cube20.org/ -- http://golly.sf.net/ --

5 8

Re: [math-fun] optimal advance tournament scheduling
by Keith F. Lynch 17 Jun '19

17 Jun '19

A lurker wrote: > Excellent approach to Dan=E2=80=99s question. Thanks. I have no idea why you didn't CC the list. I'm returning this thread to the list but hiding your name since you apparently don't want your post to be seen on the list. And, as always, and unlike most people on the list, I'm quoting as little as necessary to establish context. > One suggestion =E2=80=94 = besides computing the average score, it > might be interesting to also = note the minimum score. I might as well, since it's almost no extra effort. I'm not sure whether you mean the worst case for a given graph, given all possible vertex labelings, or the worst graph averaged over all vertex labelings for that graph. I'm assuming the former. I could call yours (best worst-case over orderings) the Rawlsian metric, and mine (best average over orderings) the Randian metric. > For instance, in Dan=E2=80=99s cube with great = diagonals, color > alternate corners along edges black and white. All = games are > then between a black and a white. If, say, whites always lose = to > blacks, the only ranking is that the 4 blacks are better than the 4 > = whites, with no ordering in either group. True, but I'm not sure that's a bad thing. The player at 000 plays the players at 001, 010, 100, and 111, all of which are indeed of opposite parity (color) to 000, but so what? > That sounds like an unhelpful = result, even if very unlikely. Odds of that are 1/35, if I haven't screwed up. But even if it happens, is it really that bad? There are 3 independent paths of length 2 to each of the other three, same-parity, players. To get from 000 to 011 for instance, you can go through 001, 010, or 111. If each edge is equally and independently likely to point in either direction, then chances that at least one of the three paths works is 7/8. Looked at another way, of the players at 000, 011, and a specified one of the three points that link them, chances are 1/3 that that specified point is between them in playing ability, determining 000 and 011's playing ability order. Since there are three such points, the chance of failure is (2/3)^3, 8/27, about 0.3. By symmetry, the same argument applies to every other two non-adjacent vertices. Very likely, Dan's arrangement is optimal. It's certainly very compact and symmetrical. I now suspect that by "sessions," Dan meant that all eight players always play simultaneously, pairwise on four boards. Thus the whole tournament only takes as long as four consecutive games, even though sixteen games are played. This would also force each player to play exactly three other players, i.e. the graph is trivalent, rather than some players playing more games than others. According to A002851, there are only two (!) unlabeled order-eight trivalent graphs. That would certainly speed up my program. Trying all 40320 labelings on both of them would be effectively instantaneous, even with raising an 8 by 8 matrix to the 7th power for each ot them. If only I could be sure that one or both of them would be optimal, rather than a graph representing some players playing more games than other. It seems likely, but I can't be certain. Dan found one of the two unlabeled order-eight trivalent graphs. What's the other one? > I think that if the graph is =E2=80=9Cin one piece=E2=80=9D, the > maximum = score will always be a complete ordering of the players, > thus 28, so = it=E2=80=99s not worth keeping track of the max. I wasn't planning on keeping track, but I'm not convinced that every connected graph has a maximum score of 28. Very likely some connected graphs just suck. If it's always possible to find a path of length 7 that doesn't loop, then you could get 28 by ordering the players in order of ability along that path. But I'm not convinced that there's always such a path. (Here I'm not just counting trivalent graphs.)

3 2

Re: [math-fun] [seqfan] Re: A263484
by Fred Lunnon 17 Jun '19

17 Jun '19

Below T(n, k) denotes the number of permutations on n symbols decomposing consecutively into just k separate permutations, see A059438, A263484; a(n) = T(n, 1) denotes number indecomposable, see A003319. Kindly colleagues have pointed out to me an efficient algorithm for these numbers, under OEIS entry A059438 (sans row-reversal). Since the Mathematica program supplied there is not straightforward to decipher nor to motivate, a short discussion seems appropriate. Once pointed out it becomes obvious that every permutation, if decomposing into k parts, also decomposes into two permutations with k-l and l parts respectively, for any 0 <= l <= k . In particular, setting l = 1 yields the convolution: for k > 1 , T(n,k) = \sum_{k-1 <= i <= n-1} T(i,k-1) a(n-i) ; where a(n) = T(n, 1) may be computed separately for n > 0 via: a(n) = n! - \sum_{1 <= i <= n-1} i! a(n-i) . So in a nutshell T(n,k) equals the n-shifted k-fold convolution of a(n) . But that is a little tricky to spot immediately, because T(n,n-k) happens to be polynomial in n of degree k : a natural though fruitless initial response is to focus on these deceptively promising polynomials instead, suggesting a presumptive reason for the existence of mysteriously row-reversed A263484 in the first place. The reliance on a(n) may furthermore be eliminated by noticing that row n sums to n! ; whence for n > 0 , T(n,1) = n! - \sum_{2 <= i <= n} T(n,j) . Attention to argument support and evaluation order now produces the Maple program below, reasonably readable --- albeit compromised by logically vacuous "proc() ... end()" brackets necessary to circumvent one of Maple's numerous syntactic idiosyncrasies! Clean copy available at https://www.dropbox.com/s/8tdz9499suazcd2/A263484_%26_A059438.txt Fred Lunnon [16/06/19] ############################################################ restart; nmax := 12; krodel := proc(p, q) if p = q then 1 else 0 fi end; for n from 1 to nmax do for k from n by -1 to 1 do T[n][k] := proc() if k = 0 and n >= k then krodel(n, k) elif k = 1 then n! - add(T[n][k], k = 2..n) else add( T[i][k-1]*T[n-i][1], i = k-1..n-1) fi end() od od: [seq( [seq( T[n][k], k = 1..n)], n = 1..nmax)]; # triangle [seq( seq( T[n][k], k = 1..n), n = 1..nmax)]; # A059438 [seq( seq( T[n][n+1-k], k = 1..n), n = 1..nmax)]; # A263484 [seq( T[n][1], n = 1..nmax)]; # A003319 ############################################################ [ [1], [1, 1], [3, 2, 1], [13, 7, 3, 1], [71, 32, 12, 4, 1], [461, 177, 58, 18, 5, 1], [3447, 1142, 327, 92, 25, 6, 1], [29093, 8411, 2109, 531, 135, 33, 7, 1], [273343, 69692, 15366, 3440, 800, 188, 42, 8, 1], [2829325, 642581, 125316, 24892, 5226, 1146, 252, 52, 9, 1], [31998903, 6534978, 1135329, 200344, 37690, 7572, 1582, 328, 63, 10, 1], [392743957, 72754927, 11348623, 1786101, 300170, 54598, 10598, 2122, 417, 75, 11, 1], NULL]; On 6/15/19, Fred Lunnon <fred.lunnon(a)gmail.com> wrote: > I had not noticed that embarrassingly simple recurrence! WFL > > > On 6/15/19, Georg.Fischer <georg.fischer(a)t-online.de> wrote: >> Hi Fred, >> >> thank you. In the meantime Alois has extended >> the triangle to 150 rows. So the initial question >> and my change (which was a bit too hasty) are >> resolved. The MMA program in A059438 computes >> 150 rows in some 20 seconds. >> >> @Alois: Thank you too, also for the typo. >> >> Best regards - Georg >> >> Am 14.06.2019 um 19:10 schrieb Fred Lunnon: >>> On 6/14/19, Fred Lunnon <fred.lunnon(a)gmail.com> wrote: >>>> To: GF, AW, JS, CS --- >>>> >>>> FYI attached A263484 & A059438 (rows reversed) for 1 <= n <= 12 . >>>> >>>> This seems about as far as is reasonable to push my dumb Maple >>>> program (shared on request). >>>> >>>> There are hints in Stanley (2005) of a somewhat faster algorithm, >>>> enumerating compositions or partitions instead of permutations; >>>> I don't currently quite see how to make that work. >>>> >>>> By the way, note Comtet's generating function for the long diagonal >>>> A003319 . >>>> >>>> WFL >>>> >>>> >>>> On 6/13/19, Georg.Fischer <georg.fischer(a)t-online.de> wrote: >>>>> Christian Stump posted a note on >>>>> <https://math.stackexchange.com/questions/3257689>. >>>>> >>>>> I tried to put all together in <https://oeis.org/draft/A263484>: >>>>> - Allan's comment and name change, >>>>> - Fred's and Christian's "more" terms (up to row 9) >>>>> - the link to the math.stackexchange.org discussion >>>>> Please feel free to amend/change that draft. >>>>> >>>>> Regards - Georg >>>>> >>>>> -- >>>>> Seqfan Mailing list - http://list.seqfan.eu/ >>>>> >>>> >> >> -- >> Dr. Georg Fischer, Rotteckring 19, D-79341 Kenzingen >> Tel. (07644) 913016, +49 175 160 7788, www.punctum.com >> >

1 0

[math-fun] What the Eck?
by Bill Gosper 16 Jun '19

16 Jun '19

Neil Sloane has Numberphiled a perplexing integer sequence: https://www.youtube.com/watch?v=etMJxB-igrc —rwg

6 8

[math-fun] (Second try) optimal advance tournament scheduling
by Dan Asimov 16 Jun '19

16 Jun '19

Second try: Sorry about not writing this up better the first time. ººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººº Suppose we want to invent a schedule of matchups for 8 players, meeting in 4 sessions of head-to-head pairings — so after all 4 sessions (and 16 games in all) *the maximum information about player's strengths* can be extracted from the results. (In some sense!) (The schedule is to be decided in advance, independent of any tournament outcomes.) I'd guess you want to *ensure* that the "versus graph" edges connect those nodes who've played each other) is, by the end, in just one piece. But what else might be important? Note: To simplify the problem, assume that the entire schedule of play is determined in advance, and is independent of any outcomes. E.g., for 8 players and 4 sessions ((n,s) = (8,4)), one could label each vertex of a regular octagon with the players' names and use each of the 4 families of parallel lines between pairs of vertices as the matchup schedule for one of the 4 sessions. Here's an alternative schedule: Instead of an octagon, use the 8 vertices of a cube, 3 of whose matchups can each be defined by one family of parallel edges of the cube; the 4th matchup could be between endpoints of each great diagonal. Is one of these better than the other for extracting the best guess as to players' relative rankings? (If they're combinatorially equivalent (CE), then of course they're equal in information content, but CE-ness looks unlikely.) —Dan P.S. In order to truly solve this problem, we'd have to define it first: In what *sense* is an optimal schedule optimal? And what about (n,s) ≠ (8,4) ?

3 2

Re: [math-fun] optimal advance tournament scheduling
by Keith F. Lynch 16 Jun '19

16 Jun '19

I'm not sure what simplifying assumptions I should make. So, unless you (Dan) object, I'll assume: Consistency: If A can ever beat B, A can always beat B. Transitivity: If A can beat B and B can beat C, then A can beat C. Ordering: No two players are equal in ability, and (equivalently, given consistency) there are no tie games. I'm not sure of the significance of "sessions," as contrasted with simply the total number of games. Given that "the schedule is to be decided in advance, independent of any tournament outcomes," the order in which they play, and whether any games are simultaneous, is irrelevant. Only which players play which other players matters. Unless I'm not understanding the problem correctly. For 8 players it would take 28 games for every player to play every other player, representing the unique complete graph with 8 vertices. With only 16 games (the number of games you specified) there are about 30 million possible labeled graphs. That's a small enough number that it's practical to simply try all of them (on a computer) and see which do best. I'll do so unless you tell me I'm misunderstanding the problem or unless someone comes up with a cleverer solution. I think it's unambiguous what "the maximum information about players' strengths" means, given my assumptions. For every pair of players, we want to know which one would win if they were to play each other. That's 28 bits. For every pair for which we can't deduce who would win, subtract 1 bit. Given transitivity, there's actually only log2(8!), about 15.3, bits. The difference from 28 is due to the fact that it's often possible to deduce whether A or B would win a game even if they never played each other. Specifically, this is possible iff there's a path on the *directed* (by who won that game) version of the versus graph that links them, in either direction. Since 15.3 is less than the 16 bits that 16 games provide, it's (barely) possible that there is a perfect solution. I agree that the versus graph should be in one piece, since if it wasn't, there would no way to rate anyone in one piece of the graph against anyone in any other piece. I think you want to maximize the average weighted number of paths between each pair of players. Weight a path by counting each path of length N as having weight 1/2^(N-1), to account for the odds that the N segments of the path won't all point the same way. This assumes that the directions are random and uncorrelated, which may be wrong, given transitivity, i.e. there can't be any loops in the directed graph. Given the lack of loops, the directed graph can always be drawn such that the arrows always point down, like water flowing in unpressurized pipes. Of course we won't be able to draw it that way until we know who won each game. Thoughts on programming: I plan to label each graph vertex with 1 through 16, those being the rankings of the players, and iterate over all 30421755 (28 choose 16) vertex-labeled directed graphs. Of course it would be cheating to choose the ones that get a perfect score, e.g. the ones in which player N plays player N+1 for N=1 through 7 and the other 9 games can be ignored. Instead, for each graph I'd take the average score over all 40320 (8!) graphs that are identical except that the labels are permuted and, equivalently, the directions are changed. For each relabeled (hence re-directed) graph I'd score it by raising its adjacency matrix to successive powers, 1 through 7 (7 being the longest possible path), and seeing if A,B or B,A is non-zero in any of these matrices. For each non-zero a,b pair, (A!=B) add a point, for a maximum score of 28. (Note that A,B and B,A can't both be non-zero unless I screw up somewhere.) (An adjacency matrix has a 1 at A,B iff there's an arrow from A to B, i.e. if player A beat player B in a game, and is 0 otherwise. The Nth power of this matrix is non-zero at A,B iff there's a path of length exactly N from A to B, e.g. for N = 3, if player A beat a player who beat a player who beat B.) I'm still trying to figure out how not to waste time testing equivalent (under relabeling) graphs. Not just because it would be slow and ugly, but because I don't want to see 40320 equivalent best solutions presented to me. Other than this, I have the whole program written (except for the typing part).

1 0

Re: [math-fun] Pronunciation question
by Keith F. Lynch 15 Jun '19

15 Jun '19

James Propp <jamespropp(a)gmail.com> wrote: > Though I?ve been advised that when it comes to pronouncing Dutch > vowels it?s impossible for Americans to get it right, so the > important thing is to say it in an American accent lest you mislead > people into thinking your pronunciation is correct! People are all the time "correcting" my pronunciation of "Dirichlet," the man best known for proving infinitely many primes are in the form A mod B if A and B have no factors in common, insisting that the t is silent. It isn't. He was German, not French. He was the brother in law of Felix Mendelssohn, the composer who was best known for his wedding march, one of the most recognizable tunes in the world. Small world. To avoid future problems with pronouncing the names of mathematicians, Americans and Brits should try harder to make all future mathematical discoveries. I look forward to learning Smith's proof of the Riemann Hypothesis, or, better yet, Jones's proof of the Adams Hypothesis. It's shameful that we've let someone as unpronounceable as Erdos get so far ahead of us.

4 3

[math-fun] Optimal advance tournament scheduling
by Dan Asimov 15 Jun '19

15 Jun '19

Near me there was a little chess tournament today, which brought up some interesting experimental design questions. I know nothing of Experimental Design, but here's the kind of thing: There were 8 players altogether, and only time enough for 4 sessions (during each of which, 4 pairs are matched up to complete one game per pair). Without defining the question formally: Suppose we want to invent a schedule of matchups for this situation so that after all 4 sessions (and 16 games in all) *the maximum information about player's strengths* can be extracted from the results. It seems intuitively clear that you want to avoid the node-edge graph of who has played whom is, by the end, in just one piece. But what else might be important? Note: To simplify the problem, assume that the entire schedule of play is determined in advance, and is independent of any outcomes. E.g., for today's situation (4 sessions, 8 players) one could label each vertex of a regular octagon with the players' names and use each of the 4 families of parallel lines between pairs of vertices as the matchup schedule for one of the 4 sessions. Is that optimal? And of course, what about other numbers than 8 and 4 ? —Dan

1 0