Wikipedia:Reference desk/Archives/Mathematics/2008 March 28

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

March 28

Competition draw algorithm

Can anyone describe or point me at a suitable algorithm for doing the draw for a competition I am running in the near future. Effectively I want to run a "5 round knock out" where everyone keeps playing (Effectively a swiss). This is simple if there are 32 players, winners play winners, losers play equal losers etc. EG for a 3 round event with 8 players (winners in capitals) we would get: Round 1 - Ab Cd Ef Gh, Round 2 - Ac Eg Bd Fh, Round 3 - Ae Bf Cg Dh and declare A the winner. However what do I do with fewer than 32 players (eg 30 or 28 or 26...)? An even number can be guaranteed (I'll enter or not as required). But I don't want any byes. I want all to play in each round. TIA -- SGBailey (talk) 00:26, 28 March 2008 (UTC)

If everyone plays each round, it's not a knock out, surely? Why not just use Swiss? --Tango (talk) 00:37, 28 March 2008 (UTC)

Set of even, prime, and positive numbers/integers

Well gee, this is diddly-squat compared to what you guys normally deal with, but I am unfortunately stuck on this simple question:

Which of the following sets of numbers has the property that the product of any two numbers in the set is also a number in the set?

I. The set of even integers

II. The set of prime numbers

III. The set of positive numbers

Given:

(A) I only

(B) II only

(C) I and III only

(D) II and III only

(E) I, II, and III

--~~MusicalConnoisseur~~ Got Classical? 04:59, 28 March 2008 (UTC)

Have you tried constructing counterexamples? Like, you could look for two even numbers whose product isn't even, etc. Anything you can find a counterexample for, you can eliminate. -GTBacchus^(talk) 05:02, 28 March 2008 (UTC)

Well, though I'm far from a math whiz, I think it's an established rule that any even numbers multiplied together create an even product.

However, I have tried using counterexamples, but I just drew a blank. Probably an elaboration on my question would be whether or not 0 or 2 are considered even. --~~MusicalConnoisseur~~ Got Classical? 05:06, 28 March 2008 (UTC)

Never mind, I just figured it out...didn't consider a "hypothetical" situation. The question about triangles, though, is still unfathomable. --~~MusicalConnoisseur~~ Got Classical? 05:13, 28 March 2008 (UTC)

Area of a triangle

Another easy question:

One side of a triangle has length 6 and a second side has length 7. Which of the following could be the area of this triangle?

I. 13

II. 21

III. 24

Given:

(A) I only

(B) II only

(C) III only

(D) I and II only

(E) I, II, and III

--~~MusicalConnoisseur~~ Got Classical? 05:03, 28 March 2008 (UTC)

Er, we're not here to do your homework for you, but the area of a triangle given any two sides a and b and the angle between them $\theta$ is ${\frac {1}{2}}ab\sin \theta$ (hint). x42bn6 Talk Mess 05:18, 28 March 2008 (UTC)

Actually this doesn't look like homework. It looks like practice for the SAT. --Trovatore (talk) 05:43, 28 March 2008 (UTC)

I hate to say this, but it's not what x42bn6 thinks... Since the degree of the angle hasn't been provided, sin can't be used in this situation.

And, yes, my questions came from an SAT prep textbook; x42bn6 hasn't done my homework. By the way, I'd just figured out that the answer is D just before x42bn6's post.--~~MusicalConnoisseur~~ Got Classical? 05:59, 28 March 2008 (UTC)

I know the angle is not given, because you don't need it. There are criteria for it to be a valid triangle, and if it is a valid triangle, then it must have a valid, er, angle, for lack of a better phrase. And "homework" I take to mean "answers" - we're not meant to spoonfeed answers, but dropping hints or explaining things are what should be done. Lest this be turned into a homework-solving ground.

Since you have the answer, $\sin \theta ={\frac {2A}{ab}}$ where A is the area. If ${\frac {2A}{ab}}>1$, then it's not a valid triangle, which is why #3 is not valid (${\frac {48}{42}}>1$). x42bn6 Talk Mess 06:29, 28 March 2008 (UTC)

The angles of a triangle range between 0 and 90 degrees. $\sin \theta$ ranges between 0 and 1 for $0<{\theta }<{\frac {\pi }{2}}$. --PalaceGuard008 (Talk) 08:46, 28 March 2008 (UTC)

They can range between 0 and 180 degrees (which does not make a difference for the range of the sine).  --Lambiam 09:04, 28 March 2008 (UTC)

Silly me. What was I thinking... --PalaceGuard008 (Talk) 09:28, 28 March 2008 (UTC)

Assuming this is meant to test logical reasoning rather than knowledge of trigonometry, you could reason (in a non-rigorous way) as follows. Put two copies of the triangle "back to back" to make a parallelogram with sides of length a and b. The area of this parallelogram is obviously greatest when its sides are perpendicular, when it is in fact a rectangle with area ab. Once you move away from the perpendicular, the parallelogram starts to collapse and its area decreases, right down to an area of 0 when it is fully collapsed. So the parallelogram's area can be any value between 0 and ab, and the triangle's area can be any value between 0 and ab/2. Same answer, different route. Gandalf61 (talk) 10:03, 28 March 2008 (UTC)

Hint: the area of this triangle will be maximum when the two sides mentioned are at right angles (see equations above) - that gives you a maximum area for the triangle.87.102.16.238 (talk) 14:01, 28 March 2008 (UTC)

As a matter of fact, Gandalf61, that's how I reasoned it out, too. =) --~~MusicalConnoisseur~~ Got Classical? 04:48, 29 March 2008 (UTC)

The marriage problem

So named by Hermann Weyl.

Let $B$ be a set of boys, and assume that each boy b knows a finite set of girls $G_{b}$. The problem is to marry each boy to a girl of his acquaintance, injectively. A necessary condition is that each set of n boys knows collectively at least n girls. Prove that this condition is sufficient.

The case where $B$ is finite can be shown by induction. For the infinite case, consider the product

$\prod _{b\in B}G_{b},$

each $G_{b}$ having the discrete topology, and apply Tychonoff's theorem.  — merge 23:49, 28 March 2008 (UTC)

So what is the question?  --Lambiam 00:41, 29 March 2008 (UTC)

"Prove that this condition is sufficient". --Tango (talk) 01:10, 29 March 2008 (UTC)

But the OP has given the answer! Algebraist 07:56, 29 March 2008 (UTC)

All the OP has given is something to consider and a theorem to apply. That doesn't prove the statement. It may be obvious to you, but us lesser mortals require a few extra lines! The theorem tells us that that product is compact - where do we go from there? --Tango (talk) 15:25, 29 March 2008 (UTC)

Actually, I thought the induction was the hard part. That (at least in the version I know) requires a trick (explained at marriage theorem), while the infinite case is a standard compactness argument. We don't seem to have an article on compactness arguments in combinatorics, for some reason; perhaps some-one who understands them better than me should write one. Anyway, I would have done this one by Zorn, but here's the Tychonov argument. An element of the product is a function that maps every boy to a girl he knows; we need an element that's injective. For every finite set X of boys, consider the subset C of the product consisting of functions that are injective on that set (and arbitrary elsewhere). These sets C are closed by definition of the product topology, and non-empty by the finite case of the theorem. In fact, since a finite union of finite sets is finite, we have that any finite intersection of these sets is non-empty. Thus since the product is compact, the intersection of all the Cs is non-empty. Any element of this intersection gives us the matching we want. Algebraist 21:40, 29 March 2008 (UTC)

Posted to share a nice problem and a very pretty little proof that I at least found somewhat surprising. (I actually came up with the "dual" one, in terms of open covers.) My enjoyment is only slightly dampened by hearing the argument described as "standard".  ;)  — merge 12:06, 30 March 2008 (UTC)

Standard arguments can be pretty too. Anyway, if you liked that one, here are some variants:

Suppose any set of n boys knows at least n - k girls. Show you can marry off all but k boys.

Suppose any set of n boys knows at least nk girls. Show you can give each boys k wives (but each girl only one husband).

Replace the girls with vectors and the boys with sets of vectors. Suppose for any set of n 'boys', the corresponding 'girls' span a space of dimension at least n. Show that we can pick a 'girl' for each 'boy' so the set of 'girls' chosen is linearly independent. Algebraist 12:53, 30 March 2008 (UTC)

I read that as "Collectively, 10 boys know at least 10 girls" This is NOT sufficient. You must also assume an even distribution. If Boy B1 knows 8 girls G1,G2,G3....G8, but boys B2-B10 each only know girls G5-G10, then each boy cannot be married to a girl he already knows. Simply having as many girls as boys is not enough. -SandyJax (talk) 20:47, 3 April 2008 (UTC)

"Perfect" partition of the reals (continued)

Continued (and copied) from Wikipedia:Reference desk/Archives/Mathematics/2008 March 25#"Perfect" partition of the reals, since it was archived just after a new comment was added - I've copied the new comments below.

Belated response to Bacchus

GTBacchus wrote above

Hmmm... another nice symmetry would be that any real translation of one of the two sets is either onto itself or onto its complement.

Turns out you can't do that, for quite trivial reasons (though it took me a long time to figure out that it was trivial :-). Suppose you have a partition of the reals into sets A and B with this property, and without loss of generality take 0 to be in A. Then for any real a in A, write a+A for the set $\{a+a'|a'\in A\}$, and notice that a+A must equal A. That's because, by hypothesis, the only other possibility is that a+A equals B. But a itself is an element of a+A (because it equals a+0, and 0 is in A), and a is not an element of B, so a+A cannot equal B.

Similarly, for b taken from B, b+B must equal A. Otherwise b+B would have to equal B, which means b would be an element of b+B, which means b would equal $b+b'$ for some $b'$ in B. But the only possible such $b'$ is 0, and 0 is not an element of B.

Now notice that for any real number x, 2x must be an element of A, because either x is in A, in which case 2x is an element of x+A which in that case equals A, or x is in B, in which case 2x is an element of x+B which in that case again equals A.

But every real number is twice some real number. So every real number belongs to A, and B must be empty.

This is not a terribly robust argument, in that it depends strongly on the status of zero and on the translates of the sets being exactly equal to one of the two sets. I'm not sure what would happen if, say, you left zero out of the mix and demanded only that for any x, x+A (resp. x+B) be a subset of either A or B. --Trovatore (talk) 05:08, 28 March 2008 (UTC)

Ooh, thank you! I hadn't given the matter another thought, but this is cool. It's neat to apply your argument to A=the set of even integers and B=the set of odd integers. Everything makes sense, right up until "every x is twice some other number", which is not true in the integers, so it's clear why this is possible in the ring of the integers, and not in the field of the reals, nor in the rationals, because you didn't use completeness in your argument. It seems... that your argument would hold in any field, no? No, Z/2Z is a finite field with the partition A={0}, B={1}. I guess the desired partition is impossible in a field with more than two elements. -GTBacchus^(talk) 00:48, 29 March 2008 (UTC)

It probably fails for any field of characteristic 2: since 2 isn't a unit you can't half numbers, so not every number is twice another number. --Tango (talk) 01:19, 29 March 2008 (UTC)

Seems robust to me. The status of 0 is what it is, I see no problem with depending on it - how can you leave it out of the mix? It's a real number, so it has to go somewhere. And the sets being exactly equal was a requirement of the problem, so there's certainly no problem depending on that. --Tango (talk) 01:19, 29 March 2008 (UTC)

"Robust" in the sense of "easily generalizable to small variants of the original problem". --Trovatore (talk) 01:35, 29 March 2008 (UTC)

I don't think 0 itself matters. You can take any other point on the line as reference. Say you have a partition of the reals into sets A and B with this property, and without loss of generality take O to be in A. (O for origin.) Then for any real a in A, write a+A for the set $\{a+a'-O|a'\in A\}$, and notice that a+A must equal A. That's because, by hypothesis, the only other possibility is that a+A equals B. But a is an element of a+A (let a' = O), and a is not an element of B, so a+A cannot equal B. Similarly, for b taken from B, b+B must equal A. Otherwise b+B would have to equal B, which means b would be an element of b+B, which means b would equal b + b' - O for some b' in B. But the only possible such b' is O, and O is not an element of B. Now notice that for any real number x, 2x-O must be an element of A, because either x is in A, in which case 2x-O is an element of x+A which in that case equals A, or x is in B, in which case 2x-O is an element of x+B which in that case again equals A. But for every x, there is some y so that 2y-O=x. So every real number belongs to A, and B must be empty. Black Carrot (talk) 23:34, 29 March 2008 (UTC)

If it helps clarify that, the idea is to move the entire line over a bit, use the new 0 to do whatever you wanted, then move it back. For instance, a+A goes from a+a' to (a-O)+(a'-O)+O, which simplifies to a+a'-O. That's how you move the 0 point of any vector space around, and this is a vector space in one dimension. Black Carrot (talk) 23:40, 29 March 2008 (UTC)

By the way, the original question is still on the board. Winding up on an archive page after editing isn't unusual. It's a glitch that showed up a few months ago, when we changed formats. Black Carrot (talk) 00:10, 30 March 2008 (UTC)