January 2004 - mathfun@mailman.xmission.com

[math-fun] devil's staircase
by R. William Gosper 09 Jan '04

09 Jan '04

In 1985 I animated an infinte zoom on a continuous function satisfying: f([0,1]) -> [0,1], f(0) = 0, f(1) = 1, f'(x) < 0 almost everywhere. In fact, f' went arbitrarily negative. A simpler case, with f' = -1 A.E., is 2 d(x) - x, where d is the devil's staircase. Two (slightly nonstandard?) recipes for d(x): inf ==== n \ floor(2 x) 1. Invert g(x) = 2 > ----------- . / n + 1 ==== 3 n = 1 2. Write x in base 3, change all 2s to 1s, stop after the first 1 (if ever), interpret in base 2. A Macsyma function, exact on rationals: dvl(x):=if x=0 then 0 else if integerp(denom(x)/3) then dvl(3*x)/2 else block([p:period(denom(x),3),l:floor(logb(3,x)),a:0], x:x/3^l, for j:0 thru max(l,0)+p do (a:2*a, if x>1 then (a:a+1,if x>2 then x:x-2 else return(j)),x:3*x), if %%=done then (divide(a,2^p)*2^min(0,l),%%[1]+%%[2]/(2^p-1)) else a*2^(l-%%)); period(modulus,b):=(modulus/b, if integerp(%%) then period(%%,b) else for d in divisors(totient(modulus)) do if nummod(?cbexpt(b,d)-1,modulus)=0 then return(d)); (c198) map(dvl,[0,1/4,3/13,1]) 1 2 (d198) [0, -, -, 1] 3 7 g preserves rationality and irrationality, is increasing, and is continuous except at dyadic rationals. d is continuous and preserves rationality but not irrationality. d^-1 is defined except at dyadic rationals. A Fourier series which repeats the staircase with period 1: 1/2-sum((1-(-1)^k*prod(1-2*sin(((%pi*k)/(3^n)))^2,n,1,inf))*sin(2*%pi*k*t)/k,k,1,inf) inf /===\ k | | 2 %pi k inf (1 - (- 1) | | (1 - 2 sin (-----))) sin(2 %pi k t) ==== | | n \ n = 1 3 > ----------------------------------------------------- / k ==== 1 k = 1 - - -----------------------------------------------------------. 2 %pi (from my paper in the McCarthy Festschrift). Like a school bell, it only rings between periods (empirically confirming the continuity of the staircase.) Unlike the ruler function, g is "semicontinuous", i.e., has no isolated values. A semicontinuous version of the ruler function might be h(x):= sum(floor(n*x)/n^2,n,1,inf), whose inverse is a devil's staircase with steps at every rational. That this inverse has a finite domain (i.e., h has a finite range) proves that the rationals have measure 0. Two other semicontinuous functions with jumps at the dyadic rationals are Gray-to-binary and its inverse, when extended to reals simply by breezing past the binary point. Since this doesn't preserve integerhood, they aren't strictly extensions. Exact-on-rationals: g2b(x):=if x=0 then 0 else if evenp(denom(x)) then g2b(2*x)/2 else block([p:2*period(denom(x),2),a:0,b:0,c,l:bitsin(x)],c:2^(l-1), thru p+1+l:max(l,0) do a:2*a+if x<c then (x:2*x,b) else (x:2*(x-c),b:c-b), divide(a/c,2^p)*c/2^l,%%[1]+%%[2]/(2^p-1)); b2g(n):=if evenp(denom(n)) then b2g(2*n)/2 else block([p:period(denom(n),2)],floor(n*2^(1+p)), divide(logxor(%%,?ash(%%,-1)),2^p),(%%[1]+%%[2]/(2^p-1))/2); bitsin(x):=1+floor(logb(2,x)); And because they are 1:1 on (right-infinite) bit strings, they are *not* 1:1 on reals, due to the ambiguity of dyadic rationals: (c208) map(g2b,[0,1/5,1/4,1/3,1/2,2/3,3/4,4/5,1]) 2 1 2 4 1 8 (d208) [0, --, -, -, 1, -, -, --, 2] 15 2 5 5 2 15 (c209) map(b2g,%) 1 3 1 3 2 3 4 (d209) [0, -, -, -, -, -, -, -, 3] 5 4 3 2 3 4 5 Denominators can jump exponentially: (c211) g2b(1/19) 9914 (d211) ------ 262145 (c212) b2g(%) 1 (d212) -- 19 (c213) b2g(%) 47 (d213) ---- 1022 (c214) g2b(%) 1 (d214) -- 19 --rwg

1 0

[math-fun] Generating derangements
by MCKAY＠vax2.concordia.ca 09 Jan '04

09 Jan '04

I found accidently that permutations with specified numbers of fixed points satisfy a recursive enumeration similar to unrestricted ( and n!). This must be in the sci.math archives somewhere. It should give a clue how to generate them too. John McKay

1 0

Re: [math-fun] Secret Santa problem
by MCKAY＠vax2.concordia.ca 09 Jan '04

09 Jan '04

id 1AezY0-00019T-08 for <mckay(a)vax2.concordia.ca>; Fri, 09 Jan 2004 09:31:44 -0700 Received: from blanca.unet.brandeis.edu ([129.64.99.169]) by mailman.xmission.com with esmtp (Exim 3.35 #1 (Debian)) id 1AezXp-00019N-00 for <math-fun(a)mailman.xmission.com>; Fri, 09 Jan 2004 09:31:33 -0700 Received: from brandeis.edu (dhcp-129-64-53-68.math.brandeis.edu [129.64.53.68])i09GVWH8009745 for <math-fun(a)mailman.xmission.com>; Fri, 09 Jan 2004 11:31:32 -0500 Date: Fri, 09 Jan 2004 11:31:32 -0500 From: Michael Kleber <kleber(a)brandeis.edu> Subject: Re: [math-fun] Secret Santa problem In-reply-to: <5.1.1.6.2.20040108141003.02c45528(a)mail.well.com> Sender: math-fun-bounces+mckay=vax2.concordia.ca(a)mailman.xmission.com To: math-fun <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: <48D20E1A-42C1-11D8-9D9A-000A95D7FED2(a)brandeis.edu> MIME-version: 1.0 (Apple Message framework v553) X-Mailer: Apple Mail (2.553) Content-type: text/plain; format=flowed; charset=US-ASCII Content-transfer-encoding: 7bit Precedence: list X-BeenThere: math-fun(a)mailman.xmission.com X-Mailman-Version: 2.1.1 X-Scanned-By: MIMEDefang 2.35 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 Marc LeBrun wrote: > OK, tastes differ. I don't recall any restriction to n-cycles. I > actually enjoy the craziness of not knowing what size cycle you will > wind up in. Since yesterday, I've taken an unscientific poll. My desire for n-cycles is clearly in the minority, so I'll abandon it. Many people agreed with you completely, seeing the small cycle possibility as a feature, not a bug. Some had a third option entirely: ideally, there should be no 2-cycles, but anything else is fine. > Your method will work fine for n-cycles. In fact, more simply, since > we basically hide the random permutation by leaving the envelopes face > down during the shift step, we might as well just write our names in > the clear on the fronts as well. Oof, right, I knew I had an extra layer of complexity in there -- a vestige of an earlier scheme I'd been thinking of. Thank you. > Although this is mechanically a smidgen trickier than just drawing > names, and might be cleverly improved somehow, I think it's > conceptually comparable since the ephemeral global information still > is just a single random permutation. Good, glad it passes the test of having the right smell for a solution. > Now what about those pesky derangements? Okay, this shouldn't be too bad. There is an easy *almost* correct answer. One so-so way to generate a random derangement a_1, a_2,..., a_n is as follows: --------- 1) Start with all a_i = i 2) For i from 1 to n-1, swap the value of a_i with one of a_{i+1},...,a_n, chosen at random --------- This can easily be modified into the desired type of blind generation scheme: --------- 1) Each person writes her own name on a piece of paper, folds it, puts it in an envelope, and writes her own name on the outside of the envelope in such a way that if you fold the flap over backwards, it covers up her own name. Put all these anonymized envelopes into the hat. 2) Pick a random pair of envelopes out of the hat, swap the pieces of paper inside them, then put *one* of them back into the hat. The other one is finished: unfold its flap to reveal whose envelope it is and give it to them; the name inside is the person they give gifts to. Keep this up right through swapping the contents of the last two envelopes. --------- It's easy to see that no one gives themselves gifts: the first time my envelope gets drawn from the hat, my name is removed from it, and then either my envelope or my name is immediately out of circulation. This is so-so because it doesn't generate derangements uniformly at random. Since we picked envelopes in a random order, no particular person is treaded asymmetrically, of course! But some cycle structures are more or less likely than they "ought" to be. I haven't tried to analyze it in detail, but I suspect you get too few 2-cycles, for example. Probably the person who is handed their envelope in the first pass through step 2 can make some guesses as to the length of the cycle they're in. Anyone want to really do this calculation? It might be interesting... I'll have to think more about whether there's an easy variant that will give uniform distribution to the derangements generated --- without giving out more information. (I may have one that will give all derangements but where the people watching will know the number of disjoint cycles, for example.) --Michael Kleber kleber(a)brandeis.edu _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

Fwd: Re: [math-fun] Secret Santa problem
by Otto Smith 08 Jan '04

08 Jan '04

The only real problem here is determining a practical way to generate a random derangement without a computer. This requires unique kinds of algorithms that can be carried out as a party game. Clearly a computer could generate a random derangement. This is a directed graph consisting only of directed cycles, Isolated vertices (or self loops) are not allowed, where each person is assigned a vertex and an edge. The secret santa as an n-cycle random permutation is generated by the algorithm I posted as a two step algorithm. First; it randomly generates a set of directed edges from a given set of vertices (the aliases), and second; each person randomly chooses an edge where they are assigned both a vertex and the edge. That is a new secret alias that they make public, and a secret friend that they keep secret. Here is a way to generate a derangement that can include any number of cycles. Again we first generate the edges, and then each person randomly chooses an edge. ALGORITHM: Everyone is publicly given an envelope with unique number and a white card with a matching number. They may secretly place their white card in anyone elses envelope. A person is free to look at the cards in their envelope. If they have more than one card, they must take any cards in excess of one and distribute them secretly to envelopes which have no cards with the restriction that they may not put a card into an envelope with the same number as is on the white card they are placing. When everyone has one white card in their envelope they are randomly given a two colored card with a unique secret name on the blue side. They find the person who has the number of the white card that is in their envelope and ask them to secretly write their secret name on the red side of colored the card. They do not look at the card and place the colored card in a hat. Each person then draws a card from the hat with their new blue public name and their new red secret friend. DISCUSSION: In fact, some of the players in this game may be able to deduce whether short cycles exist, but because of the double blind where names are assigned to numbers without general knowledge of the participants, although they may be able to deduce some of the geometry they will not be able to deduce their secret santa. Regards Otto otto(a)olympus.net >For secret santa as a n-cycle random permutation. >Generator stage: >1 N folks stands in a circle each has an envelope., they each draw > X, a random unique alias from a hat. They make up two cards. > One says I give to X, the other says I am X. They put the I am > X card in there own envelope and the I give to X card in the > envelope of the person on their right. >Finding secret stage. >2. The envelopes are put in a hat and each person draws an envelope. > They make the I am X alias public and keep the I give to alias. >Regards >Otto >otto(a)olympus.net On Thursday 08 January 2004 12:54, Michael Kleber wrote: > Marc LeBrun wrote: > > That is, a random derangement of the entire set is selected but each > > participant is only allowed to know their own assignment. > > My impression of Secret Santa is that you're supposed to have a random > n-cycle, not > just a random derangement. With a random derangement, for example, you > might end > up with a bunch of pairs of people each unknowingly just exchanging > gifts with each > other, which seems to me undesirable. > > Making a random n-cycle out of a random permutation is easy, of course: > each person > gives gifts to the person who comes after them in the permutation. > This is like taking a > permutation written in 1-line notation, and putting parens around it to > make it into an > n-cycle written in cycle structure notation. Each n-cycle can appear > in n different ways, > of course. (So, obviously, 1/n of all permutations of n things are > n-cycles.) > > Of course, the interesting question is generating things secretly, > modeled on pulling > names out of a hat. I stayed my hand moments before sending out email > based on the > > same idea Gene Salamin proposed: > > Divide the problem into two stages. First, secretly assign numbers to > > people by drawing sealed numbers from a hat. Second, generate a random > > derangement; this need not be done secretly. > > But then you only know the secret number of the person you're giving a > gift to, > not the name! It's the decoding (secretly) that's tricky. > > Here's the best idea I've come up with. It's pretty baroque, and I'm > sure there's > something better. > > --------- > 1) Each person gets a secret code name, just as Gene said. > Practically, I'd do this by > closing your eyes and pointing to a random word on a random page of a > dictionary. > > 2) Each person: > a. writes their real name on a piece of paper, > b. folds that paper up so the name can't be seen, > c. puts it in an envelope, > d. writes their secret code name on the outside of the envelope, and > e. puts that envelope into a second, larger envelope, in such a way > that > it is possible to open both flaps to get to the inside piede of > paper. (!) > > 3) These overstuffed envelopes get put in a hat and are drawn out > randomly, and > put in a stack in that random order. > > 4) Make this random permutation into a random n-cycle: open both flaps > of each > doubled envelope, take out the folded paper inside it, and put it into > the previous > doubled envelope. (The folded paper from the first envelope goes in > the last one.) > > 5) Put all the envelopes back into the hat, mix them up again, and then > take > them all out and remove the inner paper-in-envelopes from their outer > covers. > > 6) Each person can now safely take the (inner) envelope with their own > secret > dictionary word written on it, and read the name on the folded paper > inside it > to see their giftee. > --------- > > The second, outer set of envelopes is a little bit of overkill. It > would suffice to > draw the paper-in-one-envelopes out of the hat face down, so that no > one got > to see the secret code names written on the underside of them. (It's > easier to > open envelope flaps when they are face down anyway.) > > It's not immediately obvious that we need to preserve secrecy during > step (4); > nothing would be given away then and there if the secret code names were > visible. But secrecy would then be compromised in step (6), where > people > reveal their secret code names. > > Improvements welcomed, since this looks pretty bad to me. (But for > Marc's > motivating n=5, it will certainly work!) > > --Michael Kleber > kleber(a)brandeis.edu > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun -------------------------------------------------------

1 0

Re: [math-fun] Secret Santa problem
by Dan Hoey 08 Jan '04

08 Jan '04

Thu, 08 Jan 2004 11:18:25 -0800 Marc LeBrun <mlb(a)fxpt.com> Can you think of a way to generate secret derangements that's about as natural as drawing names from a hat? Thu, 08 Jan 2004 14:44:12 EST Michael B Greenwald <mbgreen(a)central.cis.upenn.edu> Drawing names from two hats? Split the names randomly, partitioning the group into reds and greens.... If the population is odd, partition the group into [n/3] reds, [(n+1)/3] greens, and [(n+2)/3] yellows. Yellows put their names into the red hat, with excess into the green; reds put their names into the green hat, with excess into the yellow; greens put their names into the yellow hat. Then each person draws from their own color of hat. That unfortunately removes the mystery from trios and the red member of quintets. And it spoils the seasonal color scheme. Dan

3 5

Re: [math-fun] Secret Santa problem
by Dan Hoey 08 Jan '04

08 Jan '04

Eugene Salamin <gene_salamin(a)yahoo.com> wrote: > Here is one way to generate derangements with equal probability. Place > numbers 2 to n in a hat. Draw a number; it becomes p(1). Put 1 into > the hat and withdraw 2 if it is not p(1). Draw a number; it becomes > p(2). Replace 2 if it is not p(1), and withdraw 3 if it is not p(1) or > p(2). Draw a number; it becomes p(3). And so on. I think you can derange 1,...,n-1 and have nothing to pick for p(n). Dan

1 0

[math-fun] What's the analog of "innumeracy" and "illiteracy" for science?
by Mike Speciner 08 Jan '04

08 Jan '04

>From today's CNN.com: To compensate for the earth's powerful gravitational force that is slowly pulling the station toward earth, the engines of a Russian Progress M-48 capsule that docked with the station in August will lift it higher later in the day.

2 1

[math-fun] small area convex lattice polygons, again
by Chris Landauer 08 Jan '04

08 Jan '04

hihi, all - (0) B&T i've also had a lot of trouble reading Barany and Tokushige, due to its peculiar seeming notations and missing definitions, and i'm still trying to fill in the omissions in the first few pages - i will make my notes available when i finally like them as a way to understand the first pages of that paper (and have checked them with the authors) (1) i think i have a better SL(2,Z) normalization process as before, make the first two vertices (0,0) and (1,0), and number the vertices counterclockwise from 0 for (0,0) now for a minimum area polygon, vertex 2 or vertex n-1 has y = 1 (otherwise, you can move vertexes 0 and 1 at least one unit in the positive y direction and start over with a smaller area polygon, possibly after also reducing for edge-interior lattice points) if vertex 2 has y=1, then reflect the polygon about the line x=1/2 (and renumber the vertices), so we can assume that vertex n-1 has y=1, and it is therefore (x,1) for some x now use the matrix (1 0) from SL(2,Z), that fixes vertices 0 and 1, (-x 1) and maps vertex n-1 = (x,1) into (0,1) (i am doing all matrix multiplication from the right side) this means the the polygon lies entirely in the first quadrant this normalization accounts for most of the SL(2,Z) elements, but it still doesn't necessarily account for reflection (the case above in which both vertex 2 and vertex n-1 have y=1 could still lead to two distinct polygons under SL(2,Z)), so i still need to use the SL(2,Z) reduction program in the corner terminology i used before, we now have corner3 consisting of exactly one edge (0,1) to (0,0), and corner 1 consisting of exactly one edge of the form (x,y) to (x,y+1) when n is even, and at most one edge (the same one) when n is odd here x is the width of the enclosing rectangle, y+1 is the height when the vertical edge is present, and then x+y+1 is the diameter, or y is the height when the vertical edge is absent, and then x+y is the diameter (i'm always using manhattan=l1 distance unless otherwise indicated) in both cases, we get perimeter = 2*diameter in all case, we have turned the geometry problem into a fraction problem (which ought to make it easier) i imagine that this will further speed up the program, and i will know later on today more soon, cal Chris Landauer Aerospace Integration Science Center The Aerospace Corporation cal(a)aero.org

1 0

[math-fun] Re: small area convex lattice polygons
by Dan Hoey 07 Jan '04

07 Jan '04

Chris Landauer wrote: > Similary, I noticed that among all of the minimum area polygons that > my program found for even n, all of them were centrally symmetric > (that is, the second half edge directions are the negatives of the > first half ones). I think that there is a simple proof of this > (perhaps less cryptic and subscripty than the one in Barany and > Tokushiga).... Define an "extremal pair of vertices" of a convex polygon to be a pair of vertices that are the intersection of the polygon with two parallel lines. For each vertex v there is at least one vertex v' such that v, v' is an extremal pair; in a centrally symmetric polygon there is exactly one. Consider the extremal pairs (v,v'), taking vertices v in order around the polygon, and taking v' in the same order for each v. Let f(v,v') be the the number of vertices from v to v' (counting in the same order, and counting only one of v,v'). f(v,v') can increase or decrease by at most one from one pair to the next, and f(v,v')+f(v',v)=2n. So there must be some pair for which f(v,v')=n. Take such a pair, cut the polygon in two parts through the line vv', and paste two copies of one part together. This is a centrally convex polygon, and if we never choose the larger of two unequal parts the new polygon will have area at most that of the original polygon. So for any minimal area 2n-gon, we can find a symmetric 2n-gon with the same area. I'm surprised, though, to hear that _all_ minimal 2n-gons were symmetric. I would have expected some chimerae--mismatched pairs of equal area. Perhaps there's something else going on here. I will say that I have not been able to get through even the third page of Barany&Tokushiga. I think they are talking about the relationship between a centrally-symmetric polygon and the convex hull of its edge vectors, but I haven't been able to read it in a way that looks believable. They write "Area P(C)" but I'm not sure what P(C) is supposed to mean; also they write "A(C)" but they only define A(n)--is that supposed to mean Area(C)? Anyone care to explain it? The paper is at http://www.renyi.hu/~barany/cikkek.ps/hide.ps . Dan

1 0

[math-fun] Re: small area convex lattice polygons
by Chris Landauer 07 Jan '04

07 Jan '04

hihi, all - I wrote: > Dan Hoey wrote (paraphrased): > > > > ...it's not a proof... > > > > This is of course true. ... > > ...all of the minimum area polygons that my program found for even n are > centrally symmetric (that is, the second half edge directions are the > negatives of the first half ones). > ... I am presently writing the code to use this observation in a different > systematic search program. > This program has now run systematically through all the even n<=50 in less than an hour total (it got the same polygon answers for even n<=20 as my other program, in much less time): min min min longest n area perim edge 22 164 62 5 24 210 72 5 26 274 80 5 28 345 90 5 30 430 98 5 32 523 108 5 34 632 118 5 36 749 128 5 38 890 138 5 40 1039 148 5 42 1222 162 7 44 1412 176 7 46 1620 192 7 48 1847 202 7 50 2100 214 7 It should be noted still that the minimum longest edge and minimum perimeter do not necessarily occur with the same polygon, but they are minima over the minimum area polygons found of that size. Also, the minimum longest edge found and minimum perimeter can be less then the above entries, at a small cost in area (there is an n=22 polygon with perimeter 60 and longest edge 4, but it has area 167). Finally, the random search found these same minima for n<=30. more soon, cal Chris Landauer Aerospace Integration Science Center The Aerospace Corporation cal(a)aero.org

1 0