- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] Problem Puzzler 1999
by Christian Boyer 10 May '06

10 May '06

Jean-Paul Delahaye publishes in the new issue of Pour La Science a very interesting article on Sudokus. He asked a very strange Sudoku problem WITHOUT any given numbers, only ">" and "<" signs between cells. He mentions that this problem was published in Puzzler, 1999, and that he does not know the solution. I have the solution, sent this morning to J.-P. Delahaye. Now looking for "Puzzler 1999" on Google, I find that Ed Pegg Jr. wrote an article in September 2005 including the same astonishing puzzle, figure 7 "Greater Than Sudoku" in: http://www.maa.org/editorial/mathgames/mathgames_09_05_05.html Perhaps that somebody else had already the solution? Ed, did you receive a solution to your article? Christian.

3 8

[math-fun] Super-fractals: kind of generalization
by Eric Angelini 10 May '06

10 May '06

Hello Math-Fun and SeqFan, ... for those interested, please see «Note of May 10th», at the bottom of the page: http://www.cetteadressecomportecinquantesignes.com/Decimation.htm Best, É.

1 0

[math-fun] Reverse then Add (RADD) sequences
by N. J. A. Sloane 08 May '06

08 May '06

Dear Math Fun: A correspondent from Belgium, Luc Stevens suggested looking at the sequences that I now call RADD sequences (not to be confused with the old RATS, Reverse, Add Then Sort sequences): T(S,Q) is formed by starting with S; to get later terms, reverse previous term annd add Q. (Of course leading zeros are omitted.) For a summary of these sequences, see my article "Sequences of RADD type" that is linked to A117831. This gives a lot of data, including many references to new entries in the OEIS. Example: T(1,1) is 1,2,3,4,5,6,7,8,9,10,2,3,4,5,6,7,... (A117230) which reaches a cycle of length 9 in 1 step. But T(1,10) never cycles (A117841). My question is, has anyone seen any previous work on these sequences? How can they possibly be new? Surely someone must have determined which ones cycle and which do not? Can anyone supply references? Neil

1 0

[math-fun] Adam Polito Kleber
by Michael Kleber 07 May '06

07 May '06

Jessica Polito, Michael Kleber, and Daniel Polito Kleber are delighted to announce the arrival of Adam Polito Kleber Friday, 5 May, 10:24 p.m., 8 lbs. 9 oz. Mother, father, and big brother are all happily resting at home. Visitors (healthy ones) are generally welcome, but please call first.

1 0

Re: [math-fun] quantifier depth
by Henry Baker 06 May '06

06 May '06

Are you interested in quantifier depth as an indicator of difficulty? I seem to recall that many of the decision procedures get an exponential in quantifier depth. But keep in mind that Hilbert's Tenth Problem has only existential quantifiers, although they are quantifiers over the integers, and this problem is undecidable. At 01:00 PM 5/6/2006, Schroeppel, Richard wrote: >What's the maximum quantifier depth for doing everyday mathematics? > >I count groups of quantifiers of the same type as 1, so that a block >of variables of the shape (all x,y,z), or the statement that there's >a magic square of size 3x3 (exists a,b,c,d,e,f,g,h,i) are counted >as one quantifier. So I'm really talking about Alternating Quantifier >Depth. > >The definition of "a function f is continuous at a point x" has depth 3: > > (all epsilon) (exists delta) (all y) > 0 < |y-x| < delta => |f(y)-f(x)| < epsilon > >and "f is continuous" is also depth 3: > > (all x,epsilon) (exists delta) (all y) etc. etc. > >The theorem that "the sum of continuous functions is continuous" >is depth 5: > > (all f,g) (exists h) (all x,epsilon) (exists delta) (all y) > h(x) = f(x)+g(x) And { 0 < |y-x| < delta => ... } > >So it looks like routine math might use a maximum depth of 8 or so. >Presumably there are a few specialties that go much deeper. (?) >Evaluating a game tree is an example. > >Rich

1 0

[math-fun] Solvable sudoku?
by Bernie Cosell 06 May '06

06 May '06

I was wondering: how does one determine: 1) if a particular sudoku grid is solvable at all, and 2) if a particular sudoku grid is solvable solely by "logic". I realize that there's some disagreement as to which procedures are allowed in "logic only" solutions, but still: is there some way, short of brute-force solving [either with full guess/retrace (1 above) or only using some set of deduction-rules (2 above)] for figuring out if a grid is solvable? /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--

3 2

Re: [math-fun] quantifier depth
by dasimov＠earthlink.net 06 May '06

06 May '06

Rich writes: << What's the maximum quantifier depth for doing everyday mathematics? . . . So it looks like routine math might use a maximum depth of 8 or so. Presumably there are a few specialties that go much deeper. (?) Evaluating a game tree is an example. >> The theorem T(n): "For every finite perfect information 2-player game of maximum length n, one player has a strategy" has the following proof ***for each n***, in which F1, S3, etc., mean the First player's 1st play, the Second player's 3rd play, etc. ~[(all F1) (exist S1) (all F2) (exist S2) . . . (all Fn) (exist Sn) such that S wins] <=> (exist F1) (all S1) (exist F2) (all S2) . . . (exist Fn) (all Sn) such that F wins. This is depth 2n, of course. Is there a way to prove the obvious fact: (all n) T(n) within the same elementary logic system (set theory?) by, say, induction? In any case, is it true that the theorem (all n) T(n) requires arbitrarily high depth? Or is there a more direct proof of (all n) T(n) ? --Dan

1 0

[math-fun] quantifier depth
by Schroeppel, Richard 06 May '06

06 May '06

What's the maximum quantifier depth for doing everyday mathematics? I count groups of quantifiers of the same type as 1, so that a block of variables of the shape (all x,y,z), or the statement that there's a magic square of size 3x3 (exists a,b,c,d,e,f,g,h,i) are counted as one quantifier. So I'm really talking about Alternating Quantifier Depth. The definition of "a function f is continuous at a point x" has depth 3: (all epsilon) (exists delta) (all y) 0 < |y-x| < delta => |f(y)-f(x)| < epsilon and "f is continuous" is also depth 3: (all x,epsilon) (exists delta) (all y) etc. etc. The theorem that "the sum of continuous functions is continuous" is depth 5: (all f,g) (exists h) (all x,epsilon) (exists delta) (all y) h(x) = f(x)+g(x) And { 0 < |y-x| < delta => ... } So it looks like routine math might use a maximum depth of 8 or so. Presumably there are a few specialties that go much deeper. (?) Evaluating a game tree is an example. Rich

2 1

[math-fun] Ma & Pa Kettle: 5 * 14 = 25
by Marc LeBrun 06 May '06

06 May '06

A friend sent me a .wmv file of an amusing clip where Ma & Pa Kettle give multiple proofs that 25 / 5 = 14. For those interested, I'd enjoy forwarding a link to it, but I don't know where to find it on the Internet. If any of you know, please clue me in. Thanks!

2 1

Re: [math-fun] Re: favorite theorem
by dasimov＠earthlink.net 04 May '06

04 May '06

Michael Kleber wrote: << > A set is finite if there exists no bijection of it onto one of its > proper subsets. Unfortunately, that's not true. Or rather, there are models of set theory in which this definition ("Dedekind-finite") is equivalent to the usual notion of "finite", but there are others in which it is not. The Axiom of Choice is more than enough to imply they are equivalent, but that seems like much more than you want to get into if you're looking for beautiful stand-alone theorems. >> Actually, in suggesting the exercise [that boils down to] There is an injection i: X u {X} -> X <=> There is a surjection s: X -> X u {X}, it struck me that the => direction is simple enough, but the <= direction seems to require the Axiom of Choice. I.e., =>: ----------- Define a surjection S_i: X -> X u {X} via S_i(x) = i^(-1)(x), if x is in Im(i); else S_i(x) = X. But for <=: ------------- Define an injection I_s: X u {X} -> X via I_s(x) = some member of s^(-1)(x), if x is in s^(-1)(X); else I_s(x) = some member of s^(-1)(X). (I'm not sure how to get around the use of AC in <=.) --Dan

2 1