Wikipedia:Reference desk/Archives/Mathematics/2013 August 18

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 18

Asymptotic Problem

One of the first problems in N.G. De Bruijin's Asymptotic Methods in Analysis is prove the integral between 1 and x of (1+1/t)dt= e*x-1/2e*log(x)+O(1) for x >1. Now, as a hint it gives prove e^-1(1+1/t^t=1-1/2(t^-1)+O(t^-2) for t is greater than or equal to 1. Is there an error in the hint? I don't see how a 1/t term can be big oh of 1/(t^2)? — Preceding unsigned comment added by 211.31.22.140 (talk) 04:29, 18 August 2013 (UTC)

Why would you even consider applying asymptotic analysis to the integral $\int _{1}^{x}(1+1/t)\,dt$? Sławomir Biały (talk) 13:44, 18 August 2013 (UTC)

There's a typo somewhere, maybe the integrand should be exp(1+1/t)? --RDBury (talk) 22:34, 18 August 2013 (UTC)

Because de Bruijin told me to? There's no error in the integral :) — Preceding unsigned comment added by 130.102.158.16 (talk) 23:31, 20 August 2013 (UTC)

Intraconference/intradivisional scheduling as pairing off elements from different sets

I was doing some armchair thinking about the re-organization and re-partitioning of teams of my favorite sports leagues into conferences/divisions/subdivisions and ran into this intraconference/intradivisional scheduling problem, which I'll express abstractly as follows: suppose you have a finite number of sets, which might contain different numbers of elements (all elements in all sets are distinct). Under what conditions is a "complete pairing", which I'll define as pairing off all elements of all sets such that no element is paired with another element from the same set, possible?

Obviously, if there are an odd total number of elements, a complete pairing is impossible (though, note that complete pairings are possible in some cases even if some or all sets have an odd number of elements, as long as the total number of elements of all sets is even). But even when there an even total number of elements, sometimes a pairing is possible, and sometimes not. And a complete pairing is possible in at least some cases even if sets contain an unequal number of elements.

For example, suppose you have two sets, A = {A1, A2, A3, A4} and B = {B1, B2}. In this case, a complete pairing is impossible: you can pair off A1 x B1 and A2 x B2, but then A3 and A4 have nobody outside their set to pair off with.

As another example, let's add a set C = {C1, C2, C3, C4} to the above. In this case, a complete pairing is now possible. First you pair off as many members of A and C as you can: A1 x C1, A2 x C2, A3 x C3. That leaves A4 and C4 left over, which you then pair off with B via A4 x B1 and C4 x B2 to get a complete pairing.

So, to recap, the above examples use a very small number of sets with small numbers of elements, but if we were to allow the number of sets and their sizes to grow to very large numbers, under what conditions would a complete pairing be possible?

—SeekingAnswers (reply) 08:07, 18 August 2013 (UTC)

There are two necessary conditions:

1. The total count is even.
2. No set so so big that it has more elements than the others put together.

Let's say you start with a collection that meets these conditions. Match an element with the biggest set with one of the remaining sets, it doesn't matter which, and if there's a tie for biggest then break it randomly. Remove these elements and you get a collection that still meets the above two conditions (check this). Continue until all sets are empty. This process can be turned into an inductive proof that the above two conditions are sufficient as well.

For example, if your initial set sizes are 5, 3, 2, 2, then step by step the process might give set sizes:

5, 3, 2, 2

4, 3, 2, 1

3, 3, 2, 0

3, 2, 1, 0

2, 1, 1, 0

1, 1, 0, 0

0, 0, 0, 0

With different choices it might go:

5, 3, 2, 2

4, 2, 2, 2

3, 2, 2, 1

2, 2, 1, 1

1, 1, 1, 1

1, 1, 0, 0

0, 0, 0, 0

You could view the problem as one of solving a system of inequalities; for example for four sets the problem would be: Given a, b, c, d>=0, find p, q, r, s, t, u>=0 so that a=p+q+r b=p+s+t c=q+s+u d=r+t+u, with the added requirement that all unknowns be integers. Without the integer requirement it's a problem in convex polytopes and with it it's more of an integer programming problem. --RDBury (talk) 22:30, 18 August 2013 (UTC)

Nicely done, thank you! I like your algorithm. :) —SeekingAnswers (reply) 19:21, 20 August 2013 (UTC)

Why do the combination of two negative signs give a positive result?

If I multiply (-2 x -3), then I will get positive 6. Here, the product of two negative numbers gives a positive number. Why is it so? Concepts of Physics (talk) 15:30, 18 August 2013 (UTC)

It's the only answer that makes sense, arithmetically. For an intuitive feel for it, you can think of multiplying by −1 as the instruction "reverse direction". So multiplying by −1 twice, i.e. −1 × −1, reverses the direction twice which just leaves you facing the same direction, i.e. does nothing. And of course multiplying by +1 does nothing. So −1 × −1 must be +1.

The example you give −2 × −3, is just −1 × 2 × −1 × 3, or (−1 × −1) × (2 × 3),or +1 × 6 = 6.--JohnBlackburne^words_deeds 15:43, 18 August 2013 (UTC)

Because two wrongs make a right. Less facetiously, and rather imprecisely but it gives the general idea, think of a negative number as the negation of a number, putting the word "not" in front of something to apply it to that something, in which case a second "not" cancels out the first "not". If you are "not not on the Wikipedia mathematics reference desk", then you are on the Wikipedia mathematics reference desk. —SeekingAnswers (reply) 17:22, 18 August 2013 (UTC)

And you can easily prove what JohnBlackburne and SeekingAnswers are saying, i.e. that -x = (-1)*x from the definition of -x. It basically boils down to the following. For each number x there exists a number y such that x + y = 0. We say that y = -x. Then this y is unique, also the defining equation for -x implies that -y = -(x) = x. Since y = (-1)*x satisfies the defining equation for -x, you have that (-1)*x = -x. Count Iblis (talk) 22:56, 18 August 2013 (UTC)

Let m be the solution to the equation m+1=0. That is, m is minus one. Multiply the equation by m and get mm+m=0. Add 1 to both sides of the equation and get mm+m+1 = 1. Use the defining equation m+1=0 and get mm = 1. So minus times minus is plus. Bo Jacoby (talk) 07:37, 19 August 2013 (UTC).

We know that every number subtracted from itself is zero, right ? Let's write this for both x and minus x:

x - x = 0

and

(-x) - (-x) = 0

By comparing these two equations, we can easily deduce that x is the same as - (-x). Or, just as easily:

x = x - 0 = x - (x - x) = x - x - (-x) = 0 - (-x) = - (-x)

—————

Still not convinced ? Let's try to visualize it geometrically ! Imagine four points along a single straight line segment: A-B-C-D. Now, the segment AC can be written as AC = AD - CD = AD - (BD - BC). At the same time, AC can also be written as AC = AD - BD + BC. From where we deduce that +BC is the same as - (-BC).

—————

Math not really your thing ? Well, let's try a more logical or philosophical approach then ! Imagine the number zero as a mirror, or as the clear surface of a lake, and when a number looks into it, it sees its own reflection in it, standing on the other side. So, "minus minus x" would mean the reflection of the reflection... which is of course the object standing on the opposite side of the reflected image, namely the number itself.

— 79.113.220.106 (talk) 09:10, 19 August 2013 (UTC)

The way it was explained to me at school was as follows:

Imagine you are on (say) the third floor of a building with stairs going up to the fourth floor and down to the second floor. Walking forward is considered as + and walking backwards is considered as -. Facing upstairs is + and facing downstairs is -. If you face upstairs and walk forwards you go up, which is positive (+ x + = +). If you face upstairs and walk backwards you go down, which is negative (+ x - = -). If you face downstairs and walk forward you go down (- x + = -) and finally, if you face downstairs and walk backwards you go up (- x - = +) Widneymanor (talk) 10:08, 19 August 2013 (UTC)

Ima

Continued product of (Pa*Pb-2)/(Pa*Pb)

What is the continued product of (Pa*Pb-2)/(Pa*Pb), starting from Pa=3, where Pb>Pa. I.e., (13/15)*(19/21)*(33/35)*(31/33)*(53/55)*(75/77)*(37/39)*... There are two cases:

• Where the continued product stops when Pb reaches some large enough finite value.
• Where the continued product (i.e., Pb) goes to infinity.

In this second case, if the answer is 0, then I want the (Continued Product)*(Pb, as Pb goes to infinity). I have looked in OEIS, but did not find anything. Bh12 (talk) 16:48, 18 August 2013 (UTC)

I'm not sure what Pa and Pb refer to here, but there is a criterion for the convergence of the infinite product that is clearly relevant: if $a_{n}\geq 0$ then the infinite product $\prod _{n=1}^{\infty }(1-a_{n})$ converges (to a nonzero number) if and only if the infinite series $\sum _{n=1}^{\infty }a_{n}$ converges. Sławomir Biały (talk) 17:53, 18 August 2013 (UTC)

He means $\prod _{i=2}^{\infty }\prod _{j=i+1}^{\infty }{\frac {p_{i}p_{j}-2}{p_{i}p_{j}}}$, where $p_{i}$ is the ith prime number. -- Meni Rosenfeld (talk) 20:42, 18 August 2013 (UTC)

Then it diverges to zero, by the result that I quoted and a well-known theorem. (As to the second part of the question, the answer is infinity, since the divergence of the product to zero is much slower than the growth of the primes.) Sławomir Biały (talk) 23:02, 18 August 2013 (UTC)

1. Yes, Pa and Pn are primes. 2. What is meant by "Then it diverges to zero"? Is that a typo?

See Infinite product A product going to 0 is said to diverge, since it's analogous to a sum going to negative infinity. -- Meni Rosenfeld (talk) 06:19, 22 August 2013 (UTC)