August 2013 - mathfun@mailman.xmission.com

[math-fun] "firewall paradox" about black holes
by Warren D Smith 13 Aug '13

13 Aug '13

in NY Times today, graphic is here: http://www.nytimes.com/interactive/2013/08/13/science/0813-sci-blackhole.ht… does my (already discussed) quantum decoherence picture already resolve this paradox? Needs thought...

1 1

[math-fun] oops Re: convex hull
by Steve Witham 13 Aug '13

13 Aug '13

>In 2D at least, there's a linear-time algorithm that works something >like the linear-time median... According to the Cormen, Leiserson, >Rivest & Stein _Algorithms_ book (the fat one with the mobile on the >cover). Oops, sorry, that's apparently when the input is a polygon. --Steve

1 0

Re: [math-fun] convex hull
by Steve Witham 13 Aug '13

13 Aug '13

>From: Warren D Smith <warren.wds(a)gmail.com> > >convex hull of N points in 2D (or in 3D) can be computed in O(NlogN) steps and >that is best possible in certain models of computation (e.g. algebraic >decision tree model). In 2D at least, there's a linear-time algorithm that works something like the linear-time median... According to the Cormen, Leiserson, Rivest & Stein _Algorithms_ book (the fat one with the mobile on the cover). --Steve

2 1

[math-fun] maximum quadrilateral area
by Warren D Smith 12 Aug '13

12 Aug '13

With given sides occurs when the quad is inscribable in (i.e. inscribed in) a circle (and this indeed does not depend on the order of the sides due to Brahmagupta's area formula). It is also interesting that the "max area happens when quad inscribable" theorem is an "absolute" theorem, i.e. it works in both euclidean and nonEuclidean geometries. And the fact the area then is independent of the side-ordering also is "absolute" (which should be obvious). (I'm recounting all this from memory, since I recall proving this theorem a long time ago. I was going to put it in a paper I never finished.)

1 0

[math-fun] Three problems
by Stuart Errol Anderson 12 Aug '13

12 Aug '13

Three problems sent to me by Stephen Johnson Hi Stuart, My coworker has a son attending the Massachusetts Institute of Technology. My coworker's son brings him fun programming and math problems, and here I'd like to share two of them with you. Feel free, if you wish, to share these with others. ================================================= First - Egg Dropping. You are given two fresh, uncooked eggs, and a 100-story building. (Assume you have very sturdy eggs, or else you're on a moon with very low gravity.) Your challenge is to identify exactly what is the highest floor from which an egg can be dropped, without breaking. For example, if an egg breaks when dropped from floor 73 but not from floor 72, you need to distinguish between the two and tell me the highest floor is 72. Rules - you have only two eggs. Once an egg breaks, it can never be used again to test another floor. If an egg doesn't break, it is just as sturdy as it was to begin with. (They don't wear out - they are binary eggs - either perfectly whole or completely broken.) You are asked to complete this task with the minimum number of drop tests. Not knowing ahead of time which is the threshold floor, what should your strategy be, to minimize the "worst case" number of drops, and still identify the highest floor for a safe drop? Finally, generalize the problem - for any number of floors, and also for any number of eggs. The strategy is markedly different if you have 3 eggs, or 4, etc. =================================================== Second - Marble Picking. You are given a bag containing N green marbles, and N red marbles. You cannot look inside the bag, but you are assured there are exactly N of each color. You are allowed to pick out marbles from the bag one at a time and look at them, without replacing them. Once a marble is out, it stays out. For each green marble you pick, you get a point. For each red, you lose a point. What is the strategy for picking out marbles to maximize your number of points? Should you play at all? And second, if you should, at what point should you stop? The answer is different depending on N - when to stop depends on how many points you have (if any), and what the total N is. =================================================== This last one is not from my friend's son - it was in an old pile of my papers. I probably copied it from Dudeney or some other publisher of such puzzles. Sorry I cannot tell you the source. Third - Maximum Quadrilateral Area. Given that the lengths of the 4 sides of a quadrilateral are in arithmetic progression, say S, S+U, S+2U, and S+3U - what is the maximum area that can be enclosed? I have this problem written down, but I have not solved it yet. I ran a few specific examples that seem to indicate there is a single unique solution. I.e. if my examples are correct, it doesn't seem to matter what order the sides are placed. That surprised me. I have to work on it some more. =====================================================

2 1

Re: [math-fun] H.Baker's |exp(ix)|=1 request
by Henry Baker 12 Aug '13

12 Aug '13

Very elegant, thank you! As a simple case, |z'/z|=1, for any complex number z, so in particular, |z'/z|=1 for any _Gaussian integer_ z. At 05:47 AM 8/11/2013, Warren D Smith wrote: >What you want is exp(ix) =approx= (A+Bi) / (C+Di) >where A,B,C,D are real polynomials in x with A^2+B^2=C^2+D^2. > >For example if A=C=even, B=-D=odd, this is achieved and also > exp(-ix)=conjugate(exp(ix)) is always satisfied.

1 0

Re: [math-fun] Can carries create correlations?
by hilarie＠xmission.com 11 Aug '13

11 Aug '13

Are you interested in the experiment design or the distribution of middle bits? 1. For two random k-bit numbers, the middle bit distribution gets closer to 50-50 as k gets larger, I believe. 2. If you are asking about the distribution of middle bits for a fixed number M and its product with a randomly chosen set of other numbers (the set of all member ids), that will depend on the distribution of bits in the member ids. If there aren't many of those ids, the imbalance could be significant. 3. If you want to make sure each experiment has a different set of members assigned to each group, you'll need to choose randomly from all such sets. N and the number of bits in N seem irrelevant. Hilarie Quoting Marc LeBrun <mlb(a)well.com>: > Can we show the middle bit of a product of a random integer with another > integer is random? > > Motivating application: We're doing a long series of experiments where in > each experiment we need to randomly assign statistically half the members of > a population to a control group and the other half to a test group. We > don't want the assignments to be correlated across different experiments. > > Further, we happen to have a random K-bit integer N assigned to each member. > > How many independent experiments can these N help us do? > > Obviously we can do K, by extracting the M-th bit of N, 0<=M<=K, to define > group assignments in the M-th experiment. > > And of course we can do 2^K-1, using the parity of the bitwise AND of M & N, > 1<=M<=2^K-1. XORing a bunch of random bits seems clearly unbiased. > > Now, as an alternative to the AND-and-parity calculation, can we instead > justify just taking the "middle bit" of the double-wide product M * N? > > The middle bit is essentially the XOR of N and bit-reversed M, plus carries. > > So the XOR contribution is the same as with the AND-and-parity approach, but > can carries create correlations? > >

1 0

[math-fun] 2D convex hull
by Warren D Smith 11 Aug '13

11 Aug '13

convex hull of N points in 2D (or in 3D) can be computed in O(NlogN) steps and that is best possible in certain models of computation (e.g. algebraic decision tree model). There are many algorithms, perhaps the simplest are "randomized incremental" where you add points in random order, updating a convex hullish data structure as you go and for those algorithms the O(NlogN) is only in expectation over the randomness. For 2D, you need only to compute 3x3 determinant-signs in exact arithmetic (sign of area of a triangle), also expressible using 2x2 determinants. In general a primitive to compute sign of (D+1)x(D+1) determinant will suffice.

3 5

[math-fun] Describe f(a/b)=a/(b+1)?
by Marc LeBrun 11 Aug '13

11 Aug '13

Dumb questions I¹m not sure even how to ask: could someone help describe or visualize the following function f? For rational x = a/b (in lowest terms) let f(x) = a/(b+1) So for instance we can say things like x/2 <= f(x) < x. Next, to extend f to real x, we observe that in sequences of rationals x_n ³converging on² x the denominators (almost always) grow, so that f(x_n) ³approaches² x. So let¹s define f as the identity on irrational values. What else can we say about f? Is it continuous? What about its derivative? Fourier transform? It¹s sure ³bumpy², but is it ³fractally²?

4 4

[math-fun] Can carries create correlations?
by Marc LeBrun 11 Aug '13

11 Aug '13

Can we show the middle bit of a product of a random integer with another integer is random? Motivating application: We¹re doing a long series of experiments where in each experiment we need to randomly assign statistically half the members of a population to a control group and the other half to a test group. We don't want the assignments to be correlated across different experiments. Further, we happen to have a random K-bit integer N assigned to each member. How many independent experiments can these N help us do? Obviously we can do K, by extracting the M-th bit of N, 0<=M<=K, to define group assignments in the M-th experiment. And of course we can do 2^K-1, using the parity of the bitwise AND of M & N, 1<=M<=2^K-1. XORing a bunch of random bits seems clearly unbiased. Now, as an alternative to the AND-and-parity calculation, can we instead justify just taking the "middle bit" of the double-wide product M * N? The middle bit is essentially the XOR of N and bit-reversed M, plus carries. So the XOR contribution is the same as with the AND-and-parity approach, but can carries create correlations?

3 2