September 2007 - mathfun@mailman.xmission.com

[math-fun] A060900 formula
by David Wilson 05 Sep '07

05 Sep '07

A060900 is the number of unrestricted walks with n edges starting at the origin on the 3/8 square lattice. There is a recursive formula there, though I don't remember putting it there, I could have. Given the nature of the sequence and the number of matching elements, I'm sure the formula is correct, but I admit inability to prove it. However, I have been told the formula is conjectural, and if there is not a proof, it should be marked as such. It is just seems aggravating that I can't come up with one. Anyway, thought the seqfans might want to take a look at it, I know my betters are out there. Similarly, can we come up with a formula for A060897 or A060898? Can we confirm the formula for A060898?

1 0

[math-fun] gefundenes Fressen 2
by wouter meeussen 04 Sep '07

04 Sep '07

consider the table of necklace polynomials, n beads, c<=n colours, substitute colour k by Exp[2 Pi I k/c], Table[NecklacePolynomial[n,Exp[2 I Pi Range[c]/c],Cyclic]//FullSimplify,{n,13},{c,n}] and find: {1}, {1,1}, {1,0,2}, {1,2,0,2}, {1,0,0,0,4}, {1,2,4,0,0,2}, {1,0,0,0,0,0,6}, {1,4,0,6,0,0,0,4}, {1,0,8,0,0,0,0,0,6}, {1,4,0,0,12,0,0,0,0,4}, {1,0,0,0,0,0,0,0,0,0,10}, {1,8,16,12,0,8,0,0,0,0,0,4}, {1,0,0,0,0,0,0,0,0,0,0,0,12}, and that might very well be: if c|n then Sum(d|(n/c), phi(c d) d^(n/c/d) /n) else 0 or, Table[If[MemberQ[Divisors[n],c], Fold[ #1 + EulerPhi[c #2]c^(n/c/#2)/(n) &, 0, Divisors[n/c]],0 ],{n,20},{c,n}] which is nice too, Wouter. earlier: ----- Original Message ----- From: "wouter meeussen" <wouter.meeussen(a)pandora.be> To: "math-fun" <math-fun(a)mailman.xmission.com> Sent: Saturday, July 28, 2007 9:57 PM Subject: [math-fun] gefundenes Fressen (a cheap find) > Imagine a necklace with n beads of up to n colours, > say n=3 beads made of colours x[1], x[2] and x[3], > then these are counted by: > > Table[NecklacePolynomial[n,Array[x,n],Cyclic],{n,3,3}] > {x[1]^3 + x[1]^2*x[2] + x[1]*x[2]^2 + x[2]^3 + x[1]^2*x[3] + > 2*x[1]*x[2]*x[3] + > x[2]^2*x[3] + x[1]*x[3]^2 + x[2]*x[3]^2 + x[3]^3} > > now, change the colours into complex roots of 1 > x[k] -> E^(2I Pi k/n) > so that they do a 'complex cancellation' on the unit circle, > and, hey presto, the whole caboodle collapses to EulerPhi[n]: > > EulerPhi[n] == NecklacePolynomial[n,E^(2I Pi Range[n]/n),Cyclic] > > which is nice... > > Wouter.

1 1

[math-fun] violating transitivity
by Michael Speciner 04 Sep '07

04 Sep '07

My daughter asked me a question based on a homework assignment: Given n objects, and a choice of a comparison (<, =, >) between each of the nChoose2 pairs of them, what is the maximum number of the nChoose3 triples of the objects that can simultaneously violate transitivity (e.g. A > B >= C >= A)? --ms

4 3

Re: [Fwd: Re: [math-fun] violating transitivity]
by Mike Speciner 04 Sep '07

04 Sep '07

Jason, Think of A > B (which is the same as B < A) to mean preferring A to B. And A = B to mean no preference between A and B. You get to pick the preferences between each pair of objects. Some sets of choices will be consistent with a transitive relation, some won't. I'm looking for a choice that results in the maximum amount of inconsistencies with transitivity. For example, with three objects, let's call them rock, paper, scissors, I might have rock < paper < scissors < rock. --ms >> From: Jason <jason(a)lunkwill.org> >> Date: 2007/09/04 Tue PM 02:18:18 CDT >> To: math-fun <math-fun(a)mailman.xmission.com> >> Subject: Re: [math-fun] violating transitivity > >> On Tue, 4 Sep 2007, Michael Speciner wrote: >> >>> My daughter asked me a question based on a homework assignment: >>> >>> Given n objects, and a choice of a comparison (<, =, >) between each of the >>> nChoose2 pairs of them, what is the maximum number of the nChoose3 triples >>> of the objects that can simultaneously violate transitivity (e.g. A > B >= C >>>> = A)? >> You must be using a specialized definition of <,=,> if A>B>=C>=A is true. Can >> you be more specific? >> >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >

1 0

[math-fun] Toss Up Komi
by Thane Plambeck 04 Sep '07

04 Sep '07

Target is selling a game called Toss Up. It comes with 10 identical 6-sided dice and a rulebook. Each die has 3 green faces, 2 yellow faces, and 1 red face. http://www.areyougame.com/Interact/item.asp?itemno=PA7367 On a player's turn, he starts by rolling all 10 dice. Dice that come up as green are added to the player's score, one point per die, and are put aside. The player then has the option to roll again with the remaining dice. If at least one is green, all the just-rolled greens are then put aside, he gets that many more points, and he has the option to roll again, etc. If ever the player fails to roll a green and also has at least one red, he is bankrupted. His total accumulated score becomes zero and all the dice are passed to the next player. If alternatively he manages to score ten points, he gets to start over with all ten again. Finally, a player can also decide to stop at any time, passing the dice on to the next player at any point. Whoever is the first to score 100 points wins. In a two person game, it's presumably got to be advantageous to be the first to roll. But suppose the second player is given a "fair" initial positive score X (ie, a komi) to compensate for that. What is X? -- Thane Plambeck tplambeck(a)gmail.com http://www.plambeck.org/ehome.htm

4 10

Re: [math-fun] Toss Up Komi
by Eugene Salamin 04 Sep '07

04 Sep '07

As Neller and Presser say, "There is no known general method for solving equations of the form x = max(Ax+b, A'x+b')." Assuming A, A', b, b' are fixed given numbers, the graph of y = max(Ax+b, A'x+b') is continuous, piecewise linear, and consists of two segments. Its intersection with y = x consists of 0, 1, 2 or points or a continuum, and these are the solutions. Gene ____________________________________________________________________________________ Got a little couch potato? Check out fun summer activities for kids. http://search.yahoo.com/search?fr=oni_on_mail&p=summer+activities+for+kids&…

6 12

[math-fun] Neal Koblitz article on Math vs Crypto
by Richard Schroeppel 03 Sep '07

03 Sep '07

Neal Koblitz's article in the Notices, The Uneasy Relationship Between Mathematics and Cryptography is available, apparently free, at http://www.ams.org/notices/200708/tx070800972p.pdf I disagree with Neal on a number of points, but the article does discuss several interesting issues. Rich

1 0

Re: [math-fun] Constructing a constrained sudoku grid
by Bernie Cosell 02 Sep '07

02 Sep '07

one funster emailed me privately: > Well, I would start with a grid "clued" with your diagonal. > That should get you there pretty fast if one exists. And I can't imagine that I missed that approach! I tried to start with a grid and manipulate it to have the desired diagonal. By just starting with the desired diagonal, I could then add "possible" cells until the solver fills in the rest of the grid. Very neat. I easily banged out several more with little trouble. THANKS! Given this approach, it makes me think that every legal diagonal can be extended to a full grid [where I think the only 'legality' constraint is that none of the three 3x3's on the diagonal contain a repeated #]. Just have the solver show you all the remaining possibilities for each unfilled and un-deduced cell, and fill in the unfilled-ones at random... Thanks all for both the sample-grids for me to use and suggestions for how I could generate more! /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--

1 0

Re: [math-fun] Constructing a constrained sudoku grid
by Bernie Cosell 02 Sep '07

02 Sep '07

On 2 Sep 2007 at 1:14, Michael Reid wrote: > i didn't do anything special; started with a solved sudoku grid, > then permuted rows and columns and permuted the labels 1-9 to get it. Boy, I don't know how you managed that. I tried that approach on a dozen or more solved-grids and couldn't get it to work out [hence my inquiry]. There are a couple million ways to relabel the grid and after that I'm not sure how many different ways there would be arrange the digits on the diagonal and you can permute the blocks-of-nine, and I guess I just never hit on a combination that would work. I wonder if the way the numbers work out if you were just lucky or if I was unlucky...:o) /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--

1 0

[math-fun] Constructing a constrained sudoku grid
by Bernie Cosell 02 Sep '07

02 Sep '07

I want to construct an ordinary 9x9 sudoku grid [I'm not worrying [yet] about clueing it to be unique, solvable, proper difficulty, etc, I'm just working on "making the constrained Latin square" part now]. What I want is the main diagonal to be 1, 2, 3, 3, 4, 5, 6, 4, 5. I've been dinking around with generating sudoku squares and then relabeling and rotating rows and columns (within the six "3-wide" row and column blocks, of course) and trying to get that pattern on the diagonal. So far, I haven't been able to manage it, which has left me with three questions: 1) can *any*sudoku square be shifted/relabeled to get that pattern [that is, is it just lack of smarts/tenacity on my part that the few grids I've tried brute-forcing into that pattern don't work? [I'd guess not. I'm guessing that among the equivalence classes of sudoku grids some will admit my desired diagonal pattern and some won't. 2) Is it possible that there is *NO* sudoku square with the desired pattern on the diagonal [that is, is there some constraint I don't understand in setting up a Latin square?]. Again, I'm guessing [hoping actually..:o)] not: Just as I'm guessing that some equiv classes will for-sure not allow my diagonal pattern, I'm also guessing that for ANY diagonal pattern [and the one I want in particular], there'll always be at least ONE equivalence class that'll allow it. 3) and the middle ground: if it IS possible, but just not for any particular sudoku grid I'm left with a quandry: There are a zillion equivalence classes of 9x9 Latin squares (fewer, I guess of legal sudoku grids but probably still "zillions")... and so how might I go about *finding* one that has the desired main-diagonal constraint? /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--

2 1