November 2005 - mathfun@mailman.xmission.com

Re: [math-fun] Sudoku "chain" analysis
by Michael Reid 08 Nov '05

08 Nov '05

of course it's a matter of semantics whether such chains are "guessing". personally, i would not consider them to be guessing, rather more advanced rules than "this column must contain a 5, which must be in this square". how about something like "if a=1, then b=2, and then c=3 ... which forces a contradiction. so a =/= 1." is that "guessing"? i would say "no". > be y" really doesn't change its nature to my view. And so I'm still not > convinced that that particular grid can be solved without guessing.. the response from the automated system(?) seems cleaner than the chains i found ... but requires translation into humanese, or better yet, mathematics. ) I tossed it at Sudoku Susser, which is excellent at defining ) logical steps. Turns out this is an XY-wing example. ) ) * Squares R4C1 (XY), R6C3 (XZ) and R4C9 (YZ) form an XY-Wing pattern on <9>. ) All squares that are buddies of both the XZ and YZ squares cannot be <9>. ) ) R4C2 - removing <9> from <39> leaving <3>. ) R6C9 - removing <9> from <49> leaving <4>. i'm not familiar with "wings", "buddies", etc. but can surmise their meaning by examining the grid: +-------+-------+-------+ | 3 6 7 | . 4 . | 5 9 2 | | 9 5 2 | 3 7 6 | 4 1 8 | | 8 1 4 | 2 5 9 | 6 3 7 | +-------+-------+-------+ | e h 8 | 6 2 . | 7 5 g | | 5 . 6 | 4 9 . | 2 8 1 | | . 2 f | . 8 5 | 3 6 i | +-------+-------+-------+ | 6 4 3 | 9 1 2 | 8 7 5 | | . . . | . 3 4 | 9 2 6 | | 2 . . | . 6 . | 1 4 3 | +-------+-------+-------+ we have e in {1, 4} , f in {1, 9} and g in {4, 9} . since f =/= e =/= g , we have 9 in {f, g} . (note the duality between squares and values.) then from f =/= h =/= g , we have h =/= 9 , and similarly i =/= 9 . that determines the values h = 3 and i = 4 , and the remaining values are easy to fill in from here. is that "guessing"? my opinion is "no", but noone has ever cared about my opinion anyway! mike

1 0

[math-fun] a month in the laboratory
by R. William Gosper 08 Nov '05

08 Nov '05

can often save an afternoon in the library. I seem to have convinced myself that the probability that an nxn bitmatrix will have (mod 2) rank = k is 2 n - k + 1 k + 1 (n - k) (p ; p) (p ; p) p k n - k P(n,k) := -------------------------------------------, (p; p) n - k if the entries are 1 with probability p. Thus the peculiar base p identity Sum P(n,k) = 1. k In particular, the probability of being nonsingular is just (p;p)_n. Can someone tell me whose wheel I have reinvented? --rwg PS to anyone still running my Macsyma ehancements: Is ROW_REDUCE a no-op? It was on my machine until I replaced (defun $row_reduce (x) ...) with (define-autoload "c:\\rwg\\climax\\algebra\\matrix" $row_reduce) in /macsyma/macsyma2/system/init.lsp .

1 2

[math-fun] Sudoku "chain" analysis
by Bernie Cosell 08 Nov '05

08 Nov '05

I now *DO* vaguely recall when that technique was discussed a while back. And I can see a [perhaps nontrivial?] philosophical/semantic battle over whether it involves "guessing" or not. My take is that it *DOES* involve guessing and so isn't a "legit" Sudoku procedure -- since it begins with "this cell must be x or y... if it is x then <search to some end condition>; else if it is y <search to some end condition>" sure sounds like a "guess" technique; the fact that it ends with "some other cell must be Z" as opposed to "the original cell has to be y" really doesn't change its nature to my view. And so I'm still not convinced that that particular grid can be solved without guessing.. /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--

1 0

[math-fun] New drug on the market
by dasimov＠earthlink.net 07 Nov '05

07 Nov '05

There's a new drug on the market that looks like just the ticket for math-funners. See http://www.panexa.com/. --Dan

2 1

Re: [math-fun] (no subject) (fwd)
by Michael Reid 07 Nov '05

07 Nov '05

> Here is a Sudoku 'almost' finished that still needs a 'guess' (I think) > +-------+-------+-------+ | 3 6 7 | . 4 . | 5 9 2 | | 9 5 2 | 3 7 6 | 4 1 8 | | 8 1 4 | 2 5 9 | 6 3 7 | +-------+-------+-------+ | . d 8 | 6 2 c | 7 5 . | | 5 . 6 | 4 9 . | 2 8 1 | | . 2 b | a 8 5 | 3 6 . | +-------+-------+-------+ | 6 4 3 | 9 1 2 | 8 7 5 | | . . . | . 3 4 | 9 2 6 | | 2 . . | . 6 . | 1 4 3 | +-------+-------+-------+ > > Can you complete without a guess to eliminate an option? this can be done with the technique described as "forcing chains" by michael kleber in a message a few months back. i've labeled the relevant squares above. square (a) is either 1 or 7. if square (a) is 1, then square (b) is 9. if square (a) if 7, then square (c) is 1, and then square (d) is 3, so again square (b) must be 9. thus in either case, square (b) must be 9. the rest can easily be filled in from here. mike

1 0

[math-fun] (no subject) (fwd)
by Richard Guy 07 Nov '05

07 Nov '05

Can some of you sudoku experts comment on the following query? Thanks in anticipation. R. Here is a Sudoku 'almost' finished that still needs a 'guess' (I think) 367|.4.|592 952|376|418 814|259|637 ----------- ..8|62.|75. 5.6|49.|281 .2.|.85|36. ----------- 643|912|875 ...|.34|926 2..|.6.|143 Can you complete without a guess to eliminate an option?

2 2

RE: [math-fun] Re: your sequence from Oct 12
by dasimov＠earthlink.net 06 Nov '05

06 Nov '05

Some interesting ways to represent numbers in the interval (a,b): Given (say positive) reals a < T < b, with T not of the form (K*a + L*b)/M for any integers K >= 0, L > = 0, M >= 1, create a sequence S_n of a's and b's as follows: S_1 = a. Let avg_n denote (S_1 + . . . + S_n) / n If avg_n > T, then S_(n+1) = a; if avg_n < T, then S_(n+1) = b; if avg_n = T, the sequence terminates. E.g., let a = 1, b = 2, and T = sqrt(2). Then what is the sequence of 1's and 2's ??? --------------------------------------------------------- This is of course equivalent to doing the analogous thing with multiplication and the geometric mean; this view often leads to more interesting-sounding questions. E.g., let P_0 = 1. If (P_1*...*P_n) < e^n, then P_(n+1) = 3; else P_(n+1) = 2. This last example brings up some questions: Is there a simple formula for P_n ? Are the lengths of runs on 2 or on 3 unbounded? Does the ratio R_n = (# 2's in P_1 through P_n) / (# 3's in P_1 through P_n) approach a limit as n -> oo ? If not, does log(R_n) remain bounded as n -> oo ? Does {R_n} have a lim sup or lim inf, and if so what are they? Etc., etc. --Dan

2 2

[math-fun] Sudokus and bimagic squares
by Christian Boyer 04 Nov '05

04 Nov '05

Bonjour, There is a link between sudokus and bimagic squares (magic squares remaining magic when the numbers are squared). Sudoku A: 258 147 369 147 369 258 369 258 147 825 714 936 714 936 825 936 825 714 582 471 693 471 693 582 693 582 471 Sudoku B: 294 618 753 753 294 618 618 753 294 942 186 537 537 942 186 186 537 942 429 861 375 375 429 861 861 375 429 Apply 9*(A-1) + B, you get: 11 45 67 6 28 62 25 50 75 7 32 57 20 54 76 15 37 71 24 46 80 16 41 66 2 36 58 72 13 38 55 8 33 77 21 52 59 3 34 81 22 47 64 17 42 73 26 51 68 12 43 63 4 29 40 65 18 35 60 1 48 79 23 30 61 5 49 74 27 44 69 10 53 78 19 39 70 14 31 56 9 This square is bimagic with: 1) consecutive integers from 1 to 81. 2) magic, sum S1 = 369. 3) and more interesting: square each number, and the square remains magic, sum S2 = 20049. Of course, it does not work for each couple of sudokus, i.e. if you want that the generated square use distinct integers. I will add a page on that, in the next update of multimagie.com Christian.

1 1