Post by Warp

Posted: 2/19/2010 9:52 PM

Quote

Mister

Player (172)

Joined: 12/28/2007
Posts: 235
Location: Japan, Sapporo

Randil wrote:

As many of you probably know, the exponential function is larger than any polynomial for sufficiently large x values. To illustrate this, let's say we have an arbitrary polynomial of degree n, P(x) = a(0) + a(1)*x + a(2)*x^2 + ... + a(n)*x^n. Find an x0 such that exp(x)>P(x) for all x>=x0.

We may assume a(k) to be positive. Define x_0 to be twice the greatest value among the (n+1-k)-th roots of a(k).(n+1)! for k=0,...,n; then we have for x > x_0, 　　exp(x) - P(x) > x^(n+1)/(n+1)! - P(x) 　　= x^(n+1).[1 - sum_{k=0,...,n}(a(k).(n+1)x^(k-n-1))] 　　> x^(n+1).[1 - sum_{k=0,...,n}(2^(k-n-1))] 　　> 0. This estimation would be sharper when the lower coefficients of the polynomial P move badly but it is still far from the best because we cut off the exponential power series by a certain term. Any other approaches in different viewpoints?

Retired because of that deletion event. Projects (~~WIP~~ RIP): VIP3 all-exits "almost capeless yoshiless", VIP2 all-exits, TSRP2 "normal run"

Posted: 2/20/2010 9:51 PM

Quote

Truncated

Editor, Reviewer, Experienced player (968)

Joined: 4/17/2004
Posts: 3107
Location: Sweden

I have one... Assume you have a regular deck of cards with 52 cards. You shuffle this deck by splitting it in two halves, let's call it the bottom half and the top half. You mix the cards by taking every other from the top half and the bottom half. For simplicity, let's say the top card of the top half is first, so it always stays on top. It's the most common shuffle type: http://www.youtube.com/watch?v=uh8iMZY4Nb4 Now... how many such shuffles do you need to perform before you are back to the original order of the deck?

Posted: 2/20/2010 10:45 PM

Quote

arflech

He/Him

Joined: 5/3/2008
Posts: 1120

This algorithm can be described like this: If the initial position n is 26a+b or equivalently (a,b), where a is 0 or 1 and b ranges from 0 to 25 (positions range from 0 to 51, equivalently b=n mod 26 and a=(n-b)/26), then the position after shuffling is 2b+a. Notice what happens to the card in position 1 (the card just below the top), a.k.a. the orbit of this element under the map... 1 (0,1) start 2 (0,2) 1 shuffle 4 (0,4) 2 shuffles 8 (0,8) 3 shuffles 16 (0,16) 4 shuffles 32 (1,6) 5 shuffles 13 (0,13) 6 shuffles 26 (1,0) 7 shuffles 1 (0,1) 8 shuffles so it takes at least 8 shuffles to bring the deck back to its original order; more specifically it takes a multiple of 8 let's look at the card in position 3... 3 (0,3)->6 (0,6)->12 (0,12)->24 (0,24)->48 (1,22)->45 (1,19)->39 (1,13)->27 (1,1)->3 (0,3) also 8 shuffles it looks like there are 2 orbits of length 1 (card 0 (0,0) and card 51 (1,25)), 6 orbits of length 8, and 1 orbit of length 2: 17 (0,17)->34 (1,8)->17 (0,17) just to check, I will lay out the remaining 4 orbits of length 8... 5 (0,5)->10 (0,10)->20 (0,20)->40 (1,14)->29 (1,3)->7 (0,7)->14 (0,14)->28 (1,2)->5 (0,5) 9 (0,9)->18 (0,18)->36 (1,10)->21 (0,21)->42 (1,16)->33 (1,7)->15 (0,15)->30 (1,4)->9 (0,9) 11 (0,11)->22 (0,22)->44 (1,18)->37 (1,11)->23 (0,23)->46 (1,20)->41 (1,15)->31 (1,5)->11 (0,11) 19 (0,19)->38 (1,12)->25 (0,25)->50 (1,24)->49 (1,23)->47 (1,21)->43 (1,17)->35 (1,9)->19 (0,19) I cheated by looking it up on MathWorld and found that it really does simplify things: the so-called "in-shuffle" in which the top card of the bottom half ends up on top requires 52 iterations to get to the original order! The in-shuffle sends a card in position 26a+b, where a is 0 or 1 and b ranges from 0 to 25, to 2b+1-a, and the single orbit (starting at the top card) is 0 (0,0)->1 (0,1)->3 (0,3)->7 (0,7)->15 (0,15)->31 (1,5)->10 (0,10)->21 (0,21)->43 (1,17)->34 (1,8)->16 (0,16)->33 (1,7)->14 (0,14)->29 (1,3)->6 (0,6)->13 (0,13)->27 (1,1)->2 (0,2)->5 (0,5)->11 (0,11)->23 (0,23)->47 (1,21)->42 (1,16)->32 (1,6)->12 (0,12)->25 (0,25)->51 (1,25)->50 (1,24)->48 (1,22)->44 (1,18)->36 (1,10)->20 (0,20)->41 (1,15)->30 (1,4)->8 (0,8)->17 (0,17)->35 (1,9)->18 (0,18)->37 (1,11)->22 (0,22)->45 (1,19)->38 (1,12)->24 (0,24)->49 (1,23)->46 (1,20)->40 (1,14)->28 (1,2)->4 (0,4)->9 (0,9)->19 (0,19)->39 (1,13)->26 (1,0)->0 (0,0) I'm sure that someone has studied the orbits of the in-shuffle on more general sets (the out-shuffle on a deck is equivalent to the in-shuffle on a deck with 2 fewer cards); for decks of size 2k, the group action can be defined by letting each position n be represented as (a,b) where b=n (mod k) and a=(n-b)/k, so that n=ak+b, and then the action sends n->2b+1-a.

i imgur com/QiCaaH8 png

Posted: 2/20/2010 11:29 PM
(Edited: 2/21/2010 1:06 AM)

Quote

Kuwaga

Joined: 10/20/2006
Posts: 1248

I'll completely disregard the top card and the bottom card, as they never change positions at all. For the remaining 50, you can also completely disregard the exact path they'll take through the deck. It's only important to note that the only thing, that determines the position in the deck each card will arrive at, is their position in the deck before each shuffle. And that they all arrive at unique positions, obviously. To arrive back home again after the first shuffle, a card first has to reach the position the card that now has taken its original place had before the first shuffle. And to reach that position... Edit: (I inserted this paragraph by editing after arflech pointed out that my argument was flawed. Unfortunately, this makes it sound way too complicated though) The number of cards has been arbitrarily selected, so the whole thing would work with 48 cards as well - as well as with any number of cards divisable by 2. So, at this point it could either require "number of cards" steps, "number of cards/2" steps or exactly 2 steps, or it wouldn't work in all cases. By imagining the shuffling process (following only one card), it becomes obvious that it can't be only 2 steps. If you simulate the whole process with 2 cards (4 in total counting top and bottom cards), it takes 2 steps, so it's "number of cards" steps. So, in the process, each card will have taken each of all possible 50 positions once. That makes it 50 shuffles. Btw, the path they take is "new position=(position*2)%(number of cards+1)". (Only counting (among) the moving cards and starting to count at 1!)

Truncated wrote:

For simplicity, let's say the top card of the top half is first, so it always stays on top.

Ironically, this makes the problem harder to solve. ;)

Posted: 2/20/2010 11:37 PM

Quote

arflech

He/Him

Joined: 5/3/2008
Posts: 1120

Kuwaga wrote:

I'll completely disregard the top card and the bottom card, as they never change positions at all. For the remaining 50, you can also completely disregard the exact path they'll take through the deck. It's only important to note that the only thing, that determines the position in the deck each card will arrive at, is their position in the deck before each shuffle. And that they all arrive at unique positions, obviously. To arrive back home again after the first shuffle, a card first has to reach the position the card that now has taken its original place had before the first shuffle. And to reach that position... So, in the process, each card will have taken each of all possible 50 positions once. That makes it 50 shuffles. Btw, the path they take is "new position=(position*2)%(number of cards+1)". (Only counting (among) the moving cards!)
Truncated wrote:
For simplicity, let's say the top card of the top half is first, so it always stays on top.
Ironically, this makes the problem harder to solve. ;)

sorry, it actually did make the problem easier to solve, and your analysis is flawed; read the post just above yours, in which I show exactly where each card goes and what the orbits are

i imgur com/QiCaaH8 png

Posted: 2/20/2010 11:49 PM

Quote

Kuwaga

Joined: 10/20/2006
Posts: 1248

No, it didn't. He insisted on out-shuffle instead of in-shuffle, which requires an additional thinking step. Sorry to tell you that there are no orbits of 8, not sure how you came to that conclusion. How can there be orbits of 8, when there are obviously also orbits of 50? An orbit of 50 requires 50 different positions (if the shuffling process always stays the same, which it does), an orbit of 8 would already occupy 8 positions. Besides, 50 isn't even divisable by 8. -.- The thing you looked up at MathWorld makes the cards move exactly as in my formula. lol Edit: My original argument is flawed, though, as well. I'll see if I can fix it. Edit 2: I tried my best, but am not satisfied with the result. My approach to all of these problems is to brute force them with educated guesses btw. Logic isn't one of my strenghts, but I can get it down when it comes to it. :p

Posted: 2/21/2010 2:27 AM

Quote

arflech

He/Him

Joined: 5/3/2008
Posts: 1120

Kuwaga, as you may have noticed, there are in fact no orbits of 50; there are however 6 orbits of length 8, an orbit of length 2, and 2 orbits of length 1, and I spelled all of them out already.

i imgur com/QiCaaH8 png

Posted: 2/21/2010 2:55 AM
(Edited: 2/21/2010 3:18 AM)

Quote

Kuwaga

Joined: 10/20/2006
Posts: 1248

How come it takes 50 shuffles and not 8 then? Wouldn't the lowest common multiple of all different orbit sizes determine the number of required iterations? You're probably making a mistake when switching between the halves of the deck in your simulation. Edit: It seems you were right for some reason I can't comprehend yet. XD

Posted: 2/21/2010 3:07 AM

Quote

arflech

He/Him

Joined: 5/3/2008
Posts: 1120

Kuwaga wrote:

How come it takes 50 shuffles and not 8 then? Wouldn't the lowest common multiple of all different orbit sizes determine the number of required iterations?

it doesn't take 50 shuffles, that's the point should I make an animated GIF showing what happens?

i imgur com/QiCaaH8 png

Posted: 2/21/2010 3:21 AM
(Edited: 2/21/2010 4:09 AM)

Quote

Kuwaga

Joined: 10/20/2006
Posts: 1248

No, sorry, it seems you were right for some reason I can't comprehend yet. It really takes 8 shuffles. o_o I was (mistakingly) assuming you agreed that it'd take 50 shuffles because of these two quotes:

arflech wrote:

the so-called "in-shuffle" in which the top card of the bottom half ends up on top requires 52 iterations to get to the original order!

arflech wrote:

the out-shuffle on a deck is equivalent to the in-shuffle on a deck with 2 fewer cards

I assumed that an in-shuffle with 50 cards would take 50 iterations, that's the same error in reasoning that let me come to my initial wrong result in the first place. Edit: I'll now take a deck of cards and analyze what really happens until I fully understand it (or until I give up) as my punishment. :( At least my formula was right. (I hope) :( I hate those occasions where I'm so confident I'm right, but turn out to be wrong anyway in the end. Argh..

Posted: 2/21/2010 3:28 AM

Quote

arflech

He/Him

Joined: 5/3/2008
Posts: 1120

no, all I meant by that is that, for example, an out-shuffle with 52 cards is the same as an in-shuffle with 50 cards to put it another way, an out-shuffle with 54 cards would take 52 iterations to return to the original order

i imgur com/QiCaaH8 png

Posted: 2/21/2010 3:54 AM

Quote

Truncated

Editor, Reviewer, Experienced player (968)

Joined: 4/17/2004
Posts: 3107
Location: Sweden

Thanks arflech and Kuwaga. It was fun to see this being explained. :) I think it is interesting that the number of shuffles isn't larger, since there are so many (52!) possible orderings of a deck. After reading Wolfram Alpha, it seems that 52 cards -> 52 in-shuffles is not a coincidence. I happens for decksizes N where N+1 is prime.

Posted: 2/21/2010 9:22 AM

Quote

arflech

He/Him

Joined: 5/3/2008
Posts: 1120

Here's one that any careful student of Calculus II should be able to figure out: The Maclaurin series of 1/(1-x) is 1+x+x^2+x^3+...+x^n+... That is, it's the sum from n=0 to infinity of x^n Also, by continuing polynomial long division, 1/(x-1) can be shown to be 1/x+1/x^2+1/x^3+... and it resembles a Laurent series centered at 0 That is, it's the sum from n=-infinity to -1 of x^n So it would seem that the doubly-infinite sum, from n=-infinity to infinity, of x^n, which looks like ...+x^3+x^2+x+1+1/x+1/x^2+1/x^3+... must be the same as 1/(1-x)+1/(x-1), which equals 0. However, it is obvious at least for positive real values of x that this sum grows without bound (i.e., goes to infinity) because the terms in one direction or the other grow without bound. How can this happen?

i imgur com/QiCaaH8 png

Posted: 2/21/2010 1:23 PM

Quote

Tub

Joined: 6/25/2005
Posts: 1377

You cannot just replace both terms, because both equations are only valid for a limited set of x, and those sets do not intersect. As you noticed, the resulting formula is valid for exactly no x at all (or if it actually were valid for any x, we cannot deduce it this way). The first equation is only valid for -1 < x < 1. I'm not sure about the second equation. Obviously, it doesn't hold for any 0 < x < 1. I'm not yet convinced it holds for any x > 1. But why shouldn't it? Polynomial division is supposed to work for arbitrary x (except zeros of the divisor), in this case any x != 1. But: Polynomial long division as I have learned it requires that deg(dividend) >= deg(divisor) and I've been told to stop at "result 0, remainder 1". Not sure what happens if you choose to ignore those.

m00

Posted: 2/22/2010 1:03 AM

Quote

petrie911

Joined: 7/16/2006
Posts: 635

Tub has about the right of it. The series for 1/(1-x) is valid only for |x| < 1 and the series for 1/(x-1) is valid only for |x| > 1. As such, the set in which they are both valid is {}, and so the set for which ...1/x^3+1/x^2+1/x+1+x+x^2+x^3... = 0 is {}.

Posted: 2/22/2010 3:16 AM

Quote

Tub

Joined: 6/25/2005
Posts: 1377

petrie911 wrote:

the series for 1/(x-1) is valid only for |x| > 1.

yeah, but.. why? where did that limitation creep in?

m00

Posted: 2/22/2010 9:29 AM

Quote

arflech

He/Him

Joined: 5/3/2008
Posts: 1120

In order for an infinite series to converge, its terms must approach 0; if |x|<1, the general term 1/x^n grows without bound, and if |x|=1, the general term still has absolute value 1 but never approaches 0. Anyway the solution offered by petrie911 is correct, and Tub's solution begged the question "what about for complex numbers?" When I mentioned "resembles a Laurent series" I was being a bit coy, because it is a Laurent series, although most Laurent series are centered around a singularity rather than a point at which the function is analytic, and the behavior of their terms can be used to determine whether it's a removable singularity (no terms of negative order), a pole of order n (the terms don't go beyond 1/(x-a)^n where a is the singularity), or an essential singularity (the order of the negative terms goes to -infinity). Essential singularities are awesome sights to behold in the study of complex analysis: In every neighborhood of (open set containing) an essential singularity of a function, every complex number with possibly one exception is attained as a value infinitely many times. If you look at the graph of e^(-1/x^2) on the real number line, it looks smooth and extremely flat near the origin and going out to infinity, but if you visualize its behavior as a function of a complex variable it looks like utter chaos near the origin; in the following links let z=x+y*i, where x and y are real. |e^(-1/z^2)| arg(e^(-1/z^2)) Re(e^(-1/z^2)) Im(e^(-1/z^2)) It looks well-behaved enough when you look at its absolute value, but looking at the other plots is enough to elicit screams of WTF.

i imgur com/QiCaaH8 png

Posted: 2/23/2010 9:49 AM

Quote

arflech

He/Him

Joined: 5/3/2008
Posts: 1120

If three spheres are tangent to each other and to a plane, and their points of tangency to this plane form a triangle of side lengths 6, 8, and 10, what are the radii of the spheres?

i imgur com/QiCaaH8 png

Posted: 2/23/2010 3:06 PM

Quote

Randil

Skilled player (1885)

Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden

Let's call the sides of the triangle s1,s2 and s3 and the radii of the spheres r1,r2 and r3. Let us view the situation from above, so that the spheres become circles with radii r1,r2 and r3. These circles have their centers at s1,s2,s3 respectively. Since the spheres are tangent, these circles will also be tangent. The circles will tangent on the sides of the triangle. Because of this, the length of each side of the triangle is the sum of the radii of the two circles that have their centers at the edges of this side. We get this equation system: r1+r2=6 r1+r3=10 r2+r3=8 which has the unique solution r1=4, r2=2, r3=6.

My own page on this site.

Posted: 2/23/2010 3:14 PM

Quote

Tub

Joined: 6/25/2005
Posts: 1377

Randil wrote:

Since the spheres are tangent, these circles will also be tangent.

no. You're using the inverse: you know your circles to be tangent, thus you claim the spheres would be, too. view from the side:

    ###
  #######
 #########
 #########
###########
###########
 #########  ##
 ######### ####
  #######  ####
    ###     ##
---------------  <- plane

the corresponding circles would touch (if viewed from above), but the spheres don't.

m00

Posted: 2/23/2010 3:30 PM

Quote

Randil

Skilled player (1885)

Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden

You are right, my mistake. I took this into consideration and gave this another try: If we view the situation from the side, it will look like this:

Doing this for all three sides, and applying the pythagorian theorem give us after som simplification: 4*r1*r2=6^2 4*r1*r3=10^2 4*r2*r3=8^2 that has the only positive solution r1=15/4, r2=12/5, r3=20/3. Is this right?

My own page on this site.

Posted: 2/23/2010 3:41 PM

Quote

Tub

Joined: 6/25/2005
Posts: 1377

Randil: yeah, I ended up with the same three equations. Was too lazy to actually solve it, though. In any case, a simple geometric observation tells me there's only one solution, so does the linear system you get when you log() both sides of the equations.

m00

Posted: 2/23/2010 7:55 PM

Quote

arflech

He/Him

Joined: 5/3/2008
Posts: 1120

Randil, you're winner

Warp wrote:

That reminds me of another problem related to spheres: Assume you have four identical spheres. Three of them are laying on a plane so that they touch each other. The fourth sphere is resting on top of the other three (so that it touches all of them). What is the height of this structure? Bonus: Assume there's a fifth, smaller sphere in the middle of this structure, touching all the other four spheres. What is the radius and height (distance from the plane) of this fifth sphere?

If the radius of each sphere is r, the tetrahedron connecting the 4 spheres has edge length 2r; then the median of each face has length r*sqrt(3), and the circumradius of each face is 2r/sqrt(3), so using the Pythagorean theorem, the height of the tetrahedron is 2r*sqrt(2/3), and then the height of the structure is 2(1+sqrt(2/3))r. The circumradius of this tetrahedron is r*sqrt(3/2), so the radius of the smaller sphere is (sqrt(3/2)-1)r, and the distance between the top of this sphere and the plane is 2r*sqrt(2/3); the distance between the center of the tetrahedron and the plane is (1+1/sqrt(6))r.

i imgur com/QiCaaH8 png

Posted: 4/5/2010 1:11 AM

Quote

arflech

He/Him

Joined: 5/3/2008
Posts: 1120

As you may know, the Chinese policy that penalizes families with more than one child has led to a horrible gender-ratio imbalance as many families make damn sure their one child is a boy; consider the effect of a revised policy that would allow families to try for a boy as much as possible but then mandate no more children after that boy (it may be easier to look first at a variant of the policy that also sets a limit on the total number of children). Another one to consider comes from ARIS 2008, the American Religious Identification Survey: 41% of the 9% of respondents who had no religion at age 12 joined a religion by the time of the survey, while only 12% of the 81% of respondents who had a religion at age 12 had lost it by the time of the survey; the result is that the non-religious portion of the population has grown, as about 4% of respondents got religion between age 12 and the time of the survey, while 11% of respondents lost it, for a net gain of 7 percentage points for the non-religious crowd (this specific figure has questionable validity, however, because the respondents were of varying ages at the time of the survey, rather than being segregated into narrow age cohorts; the non-religious portion at survey time was 15%, which is within rounding error of what may be derived above as 9%+7%=16%). Despite the lack of segregation into age cohorts, imagine that the above figures are valid for modeling the lack of religion among Americans from pre-adolescence to pre-middle-age; that is, 41% of people raised non-religious become religious, and 12% of people raised religious become non-religious. Absent some grander societal shift (like the one that made lack of religion tolerable beyond the educated elites in the first place), what would the stable religious and non-religious portions of the population be? It surely isn't the case that the non-religious portion increases by 7 percentage points every 30 years or so under this model; rather, as the non-religious portion increases, its rate of increase as a percentage of the population will decline until a stable proportion is reached. This could be treated as a Markov process, but this can be greatly simplified, so that no matrix operations are needed.

i imgur com/QiCaaH8 png