January 2004 - mathfun@mailman.xmission.com

[math-fun] odometer word game
by Richard Schroeppel 03 Jun '04

03 Jun '04

zimb zinc chromatic chromatid Rich

2 1

[math-fun] 4 pile nim
by Thane Plambeck 01 Apr '04

01 Apr '04

David Gale writes: > Before I start here's something more in the math-fun spirit. I'm offering two hundred bucks ($200) for a solution of the following Nim variant. > There are 4 piles, ordinary Nim rules, the only difference being that the game ends when three of the four piles are empty. OK---I'll bite, if no one else will. Case I: (Single non-empty heap) Answer: *0 (the game is already over) everything is a P position, ie 2nd player to move wins. Case II: (Two nonempty heaps, sizes m and n). Everything is an N-position. A wiinning move to take everything in one of the heaps. For extra credit (but not for the $200), after a few minutes of noodling I got the nim heap equivalent is BitXor[m-1,n-1] +1. Case III: (Three nonempty heaps, sizes r,s,t). Assume r <= s <= t. Every move involving taking a whole heap leads to a (Case II) N position. What are the three heap P positions? 1,1,1 is a P position for example. Then 1,1,t for other t>1 is always an N position, since there's a move to 1,1,1. It looks like the P positions are in one-to-one correspondence with every pair (a,b) = (s-r, t-s) with a, b nonnegative. Ie, the P position (1,1,1) corresponds to the choice (a,b) = (0,0), and (for example), the P position (2,3,4) corresponds to the choice (1,1), (and for another example), (4,6,7) corresponds to (2,1), ET CETERA, where I don't really know what ET CETERA means. Assuming this correspondence is valid, how to recover r from a and b? This should be achievable---but not after two glasses of chianti. Is it hopeless to give a formula for the Case III nim equivalent? Case IV: (Four nonempty heaps). Hmmm.... Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.plambeck.org

5 5

[math-fun] limit question
by Mike Stay 04 Feb '04

04 Feb '04

Does anyone happen to know what the limit of the sum of the nth catalan number over 4^n is? inf ___ \ C(n) > ---- /__ 4^n n=0 Thanks! -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

5 4

[math-fun] Two questions in geometric combinatorics
by asimovd＠aol.com 01 Feb '04

01 Feb '04

(I don't know whether either of these problems has been solved. Here are the 3D versions of what could asked of any dimension.) 1. Analogous to a recent question posed here about triangles: Let A_n denote a regular tetrahedral arrangement of points in 3-space, n to an edge. (The layers successively contain 1, 3, 6,... points.) Define a "tetrad" to be any four mutually adjacent points of A_n. QUESTION: For which n is it possible to partition A_n into disjoint tetrads ??? Call such an n "tetrizable". Clearly, any such n = 0 (mod 4). It's not hard to show that the number of points #(A_n) is divisible by 4 exactly when n = 0,2,4,6, or 7 (mod 8). QUESTION: More concretely, n = 2 is the first tetrizable number. What is the next one (if any) ??? --------------------------------------------------------------- 2. Given any arrangement of congruent spheres in 3-space where any two are either disjoint or tangent, consider the graph formed by using each sphere as a node and each tangency as an edge. Call such a graph a "packing graph". QUESTION: What is the maximum chromatic number of a packing graph (if the maximum exists) ??? ------------------------------------------------------------- --Dan Asimov -- NOTE: Please direct any responses to <asimov(a)msri.org>, since I may not keep this AOL e-address much longer -- thanks.

4 4

Re: [math-fun] twenty questions
by James Propp 30 Jan '04

30 Jan '04

The discussion of Twenty Questions reminded me of a game I learned from Alan Frank (who I believe also invented it), called "Plenty Questions". In this game, all queries must take the form "Is it more like X or Y?" In the warm-up version of the game, that's the only constraint. But in the real version of the game, there's a further catch: each question must re-use the better of the two matches from the previous question. That is, if the answer to "Is it more like X or Y?" is "X", then the next question must be of the form "Is it more like X or Z?", whereas if the answer to "Is it more like X or Y?" is "Y", then the next question must be of the form "Is it more like Y or Z?". This game is rather frustrating to play, because one usually spends lots of time stuck at local optima, obtaining no new information from one's successive questions. But what's interesting about the game is that it is in fact playable. I would have expected it to be unplayable, given how big "thing-space" is. (Though now that I think about it, I believe that one reason that the game is playable by humans is that the answerer, bored with always saying the same thing, sometimes changes his/her criteria in mid-game so as to be able to move to a new local optimum, and in the course of going to a new optimum, he/she reveals new information about the target.) It'd be Interesting to know more about the "thing-space" of the game Twenty Questions, and the distribution of people's choices. Is it governed by by Zipf's Law? What is its entropy? Jim Propp

1 0

[math-fun] Re: Record of Unitary Amicable Pair
by Richard Guy 30 Jan '04

30 Jan '04

Can someone check this? As I have neither the expertise nor the equipment, I shouldn't be querying this, but the fact that the two numbers differ by such a small factor as 53 seems surprising, as do the two 81-digit primes whose first 35 digits are the same. R. On Fri, 30 Jan 2004, y.kohmoto wrote: > I found a record of Unitary AP which has 317 digits. > > 2 ^ 4 * 3 * 5 ^ 4 * 7 ^ 5 * 11 * 13 * 19 ^ 2 * 23 * 29 * 31 * 97 * 101 * > 127 * 137 * 151 * 181 * 191 * 227 * 251 * 313 ^ 2 * 1523 * 17569 * 18119 * > 22193 * 42767 * 133157 * 1594471 * 3592427 * 12755767 * 16563721580414291 * > 3692133344284919899954037 *1107640003285475969986211099 * > 509326829322602570550995760607650943 > *756709374175283588981851230229946163884862251*10645931718799413777310016871 > 8026852747401678766160269617017644971540715800242987 > > 2 ^ 4 * 3 * 5 ^ 4 * 7 ^ 5 * 11 * 13 * 19 ^ 2 * 23 * 29 * 31 * 97 * 101 * > 127 * 137 * 151 * 181 * 191 * 227 * 251 * 313 ^ 2 * 1523 * 17569 * 18119 * > 22193 * 42767 * 133157 * 1594471 * 3592427 * 12755767 * 16563721580414291 * > 3692133344284919899954037 *1107640003285475969986211099 * > 509326829322602570550995760607650943 *53* > 14013136558801547944108356115369373207909921*1064593171879941377731001687180 > 26854246807290557925899636611749316063659704331051 > > Yasutoshi Kohmoto > http://boat.zero.ad.jp/~zbi74583/another02.htm >

1 0

Re: [math-fun] limit question
by Mike Stay 30 Jan '04

30 Jan '04

Thanks! I came across it while trying to calculate an upper bound on Chaitin's Omega number for Chris Barker's language Iota. Programs in Iota are completely binary trees (that is, 0 or two children). Internal nodes (1's) apply the left branch to the right, and leaf nodes (0's) are a universal combinator. Omega is inf ___ \ > (number of n-bit self-delimiting programs that halt) / 2^n /__ n=1 In Iota, programs are self-delimiting--as soon as there are more leaf nodes than internal nodes, you know you're done. The number of ways to do that for a bit string of length 2n+1 is C(n). The probability that a string starts with a prefix containing more zeros than ones approaches certainty. So I guess the limit is another way of saying, "You can't make a syntax error in Iota!" ----- Original Message Follows ----- > > > > about : > > inf > ___ > \ C(n) > > ---- = 2. > /__ 4^n > n=0 > > > The limit is 2. > > C(n) is slightly lower than 4^n, while the principal term > is 4^n, eventually the sum converge to 2, I am not a > combinatorist or a wilf-zeilbergerologist but I can say > that there is probably a variety of ways to show that. > > As a number theorist I would suggest, the series slowly > increases so it means you can apply lots of tests for > series on it validating the convergence of the sum. > > simon plouffe > > -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

4 4

Subj: RE: [math-fun] twenty questions
by MCKAY＠vax2.concordia.ca 29 Jan '04

29 Jan '04

Twenty questions provides 20 bits. What if you know that at most k of the answers may be wrong? John

7 8

Re: [math-fun] twenty questions
by MCKAY＠vax2.concordia.ca 27 Jan '04

27 Jan '04

From: IN%"math-fun(a)mailman.xmission.com" "math-fun" 27-JAN-2004 11:59:35.15 To: IN%"math-fun(a)mailman.xmission.com" "math-fun" CC: IN%"math-fun(a)mailman.xmission.com" Subj: RE: [math-fun] twenty questions Return-path: <math-fun-bounces+mckay=vax2.concordia.ca(a)mailman.xmission.com> Received: from clyde.concordia.ca (clyde.Concordia.CA [132.205.1.1]) by vax2.concordia.ca (PMDF V6.2 #30759) with ESMTP id <01L5W5CS7TR6007B7O(a)vax2.concordia.ca> for mckay(a)vax2.concordia.ca (ORCPT mckay(a)vax2.concordia.ca) Tue, 27 Jan 2004 11:59:34 -0400 (EDT) Received: from mailman.xmission.com (mailman.xmission.com [198.60.22.29]) by clyde.concordia.ca (8.12.10/8.12.10) with ESMTP id i0RGw3Od225121 for <mckay(a)vax2.concordia.ca>; Tue, 27 Jan 2004 11:59:24 -0500 (EST) Received: from localhost ([127.0.0.1] helo=mailman.xmission.com) by mailman.xmission.com with esmtp (Exim 3.35 #1 (Debian)) id 1AlW0j-0005Sc-08 for <mckay(a)vax2.concordia.ca>; Tue, 27 Jan 2004 09:24:21 -0700 Received: from mta9.adelphia.net ([68.168.78.199]) by mailman.xmission.com with esmtp (Exim 3.35 #1 (Debian)) id 1AlW0a-0005SJ-00 for <math-fun(a)mailman.xmission.com>; Tue, 27 Jan 2004 09:24:12 -0700 Received: from Maxwell.adelphia.net ([67.23.244.164]) by mta9.adelphia.net (InterMail vM.5.01.06.05 201-253-122-130-105-20030824) with ESMTP id <20040127162341.XJLN27240.mta9.adelphia.net(a)Maxwell.adelphia.net> for <math-fun(a)mailman.xmission.com>; Tue, 27 Jan 2004 11:23:41 -0500 Date: Tue, 27 Jan 2004 11:23:41 -0500 From: Jud McCranie <j.mccranie(a)adelphia.net> Subject: Re: [math-fun] twenty questions In-reply-to: <004b01c3e3d9$55eb05a0$a52efea9@TASSO> Sender: math-fun-bounces+mckay=vax2.concordia.ca(a)mailman.xmission.com X-Sender: j.mccranie(a)mail.adelphia.net To: math-fun <math-fun(a)mailman.xmission.com> Cc: math-fun(a)mailman.xmission.com Errors-to: math-fun-bounces+mckay=vax2.concordia.ca(a)mailman.xmission.com Reply-to: math-fun <math-fun(a)mailman.xmission.com> Message-id: <6.0.1.1.2.20040127112234.01d72290(a)mail.adelphia.net> MIME-version: 1.0 X-Mailer: QUALCOMM Windows Eudora Version 6.0.1.1 Content-type: text/plain; format=flowed; charset=us-ascii Precedence: list X-BeenThere: math-fun(a)mailman.xmission.com X-Mailman-Version: 2.1.1 X-Scanned-By: MIMEDefang 2.35 References: <004b01c3e3d9$55eb05a0$a52efea9@TASSO> List-Post: <mailto:math-fun@mailman.xmission.com> List-Subscribe: <http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>, <mailto:math-fun-request@mailman.xmission.com?subject=subscribe> List-Unsubscribe: <http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>, <mailto:math-fun-request@mailman.xmission.com?subject=unsubscribe> List-Archive: <http://mailman.xmission.com/cgi-bin/mailman/private/math-fun> List-Help: <mailto:math-fun-request@mailman.xmission.com?subject=help> List-Id: math-fun <math-fun.mailman.xmission.com> Original-recipient: rfc822;mckay(a)vax2.concordia.ca At 01:55 AM 1/26/2004, Thane Plambeck wrote: >I played this game of twenty questions, where the computer does the guessing. > >http://y.20q.net:8095/btest I tried "photographic film", and it didn't get it in 30 guesses. Probably the closest guess was a plastic bag. _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] twenty questions
by Thane Plambeck 27 Jan '04

27 Jan '04

I played this game of twenty questions, where the computer does the guessing. http://y.20q.net:8095/btest My unknown was "Einstein's Theory of General Relativity" On question 19, the computer guessed "the study of trigonometry." On question 21, it guessed "pi." Not bad, if extra time was needed Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.plambeck.org

3 2