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

[math-fun] Secret Santa -> random derangements
by Allan C. Wechsler 10 Jan '04

10 Jan '04

As seems to be my style recently, I'm not going to actually develop an algorithm for random derangements, but instead will suggest the outline of one in the hopes that some energetic funster will do all the hard work. We want to produce a random derangement on N items. Start by figuring out how many such derangements there are; say there are M of them. Select a random number between 0 and M-1. This will be the "index" of the derangement we will generate; call it K. Initialize a variable to K: this is the "residual index", and we will be decrementing it as we leaf through the derangements in a certain order. (Eudora's spell-checker doesn't like "decrementing" (or "Eudora's"!).) Element 0 can go to 1, 2, ... M-1. Calculate the number of derangements that take 0 to 1. If this number is less than or equal to the residual index, decrement the residual index by this amount. Now calculate the number of derangements that will take 0 to 2. Repeat this process until the number of derangements that takes 0 someplace is less than the residual index, and nail that sucker: 0 will go to that place, which we may call 0'. Now we must decide where to put 1. Calculate the number of derangements that take 0 to 0' and 1 to 0. If this number is less than the residual index, decrement the residual index and go on to the next legal place that 1 can go. These legal places will be everywhere except 1 and 0'. Eventually we will decide on a 1', because the number of derangements that take 0 to 0' and 1 to 1' will be greater than the residual index. Similarly, we decide on 2', 3', 4', and so on; eventually we will reach a point where the residual index is 0 and everything else is forced. (The code probably won't have to notice this specially, this being one of those examples of something that looks like a special case to a human, but is just business as usual to a program.) Essentially we have invented a numbering scheme for derangements, and it is blatantly clear that all derangements have an equal likelihood of being picked. Missing from this description is the algorithm for calculating the number of derangements with some values given; I do not know how hairy such a procedure is. In is conceivable that there is another, simpler, more elegant technique, but the recent observation about factorizations of derangement censuses gives me an intuition that this will be hard to find. -ACW

2 1

[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