Wikipedia:Reference desk/Archives/Mathematics/2007 July 17

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.

July 17

Proof by definition

Resolved

What is the name of the fallacy where a proposition is proved by postulating that it is true? (eg. Thereom: x=2. Proof: I define x to be =2, so x=2, therefore QED!) Similarily in logic. (eg. Thereom: x exist. Proof: I define x to be necessary, therefore x necessarily exists.)Freethought 101 01:39, 17 July 2007 (UTC)

I think you're looking for tautology (logic). — Laura Scudder ☎ 02:14, 17 July 2007 (UTC)

Or maybe begging the question. PrimeHunter 02:17, 17 July 2007 (UTC)

Thanks. It definitely is the fallacy "begging the question" to which I was refering.Freethought 101 15:40, 17 July 2007 (UTC)

Connect6 and strategy stealing

Does the strategy-stealing argument apply to Connect6? NeonMerlin 01:58, 17 July 2007 (UTC)

Not in any obvious form. If white has a winning strategy, then black can 'throw away' his first stone in classic strategy-stealing fashion, but then white gets to place two stones, and so the necessary symmetry doesn't apply. Though it doesn't say so explicitly, the article seems to imply that the result (given best play) is unknown. Algebraist 09:28, 17 July 2007 (UTC)

Agreed. If Black got to play two stones on his first move then strategy-stealing would apply and you could prove that White has no winning strategy. But since he only gets to play one stone that type of argument doesn't apply so it's not clear which side has the advantage. Dugwiki 21:29, 17 July 2007 (UTC)

Recommended reading

Does anyone think that the mathematics reference desk (or WP:WPM) should have a "recommended" reading list for mathematics topics. We already have similar things at the bottom of articles but perhaps something more centralized and general could be helpful. Thoughts?--Cronholm¹⁴⁴ 20:32, 17 July 2007 (UTC)

This sounds extremely useful. Of course, this would lead to the usual problems of "recommended" being subjective and therefore the question of whether it is really appropriate. -- Meni Rosenfeld (talk) 00:29, 18 July 2007 (UTC)

Well, I was thinking that we (WP:WPM) could put together a list through collaboration (we could userfy it to avoid POV problems) and provide a little summary of what the book addresses and the recommended prerequisites etc... and do it for each major field of mathematics. That way people looking for recommendations in the future can get a feel for the printed options out there.--Cronholm¹⁴⁴ 00:37, 18 July 2007 (UTC)

First person who share the same birthday with any person in front

At a movie theater, the manager announces that they will give one (and only one) free ticket to the first person in line whose birthday is the same as someone who has already bought a ticket. You have the option of getting in the ticket line at any time. Assuming that you don't know anyone else's birthday, that birthdays are uniformly distributed randomly throughout the year, etc.,

What position in line gives you the greatest chance of being the First Duplicate birthday?

Obviously the first in line has zero chance of sharing a birthday with the person(s) in front.

The second person in line has 1/365 chance of sharing a birthday with the person(s) in front.

The third person has ... Eh?, This is where I got stuck!

202.168.50.40 23:48, 17 July 2007 (UTC)

What have you tried thus far (other than just computing the first two)? We don't really help with homework unless you have taken a good shot at it yourself. --Cronholm¹⁴⁴ 00:15, 18 July 2007 (UTC)

[edit conflict]A free ticket? That's all? Who are they trying to fool? :)

Anyway, the third person will be the winner iff the second person is not the winner (which means that 1st and 2nd have different birthdays) and the third has the same birthday as one of them. The probability of the first condition is ${\tfrac {364}{365}}$. Given that, the probability of the second condition is ${\tfrac {2}{365}}$. So 3rd wins with probability ${\tfrac {364\cdot 2}{365^{2}}}$. 4th with probability ${\tfrac {364\cdot 363\cdot 3}{365^{3}}}$, and so on.

All of this, of course, under the assumption that nobody was born on February 29th!

To find the optimal solution, try forumalting how the probability for each person relates to the one before, and find out what the number needs to be in order to start decreasing. -- Meni Rosenfeld (talk) 00:20, 18 July 2007 (UTC)

By the way, I'm not sure this is homework. As I recall, this IP address belongs to a person who used to write under the name Ohanian and doesn't have a habit of asking HW questions here. -- Meni Rosenfeld (talk) 00:25, 18 July 2007 (UTC)

Meni, how the hell do you remember IP/name stuff like that! ~ hydnjo talk 00:36, 18 July 2007 (UTC)

Well, that's a memorable IP, the person has had enough activity here to remember, and my memory isn't clogged up by actually important things :) -- Meni Rosenfeld (talk) 00:40, 18 July 2007 (UTC)

Well, in that case I would recommend taking a smaller sample space,assume there are ten days in the year, and look at the trend using Meni's recommended approach. This might help you get a feel for the problem.--Cronholm¹⁴⁴ 00:42, 18 July 2007 (UTC)

I think Birthday paradox and related articles gives much of the reasoning behind solving this problem and similar?87.102.23.249 12:26, 18 July 2007 (UTC)

The further back on the line you go the more likely it is that someone else has had a matching birthday, so it's better to be near the front.87.102.23.249 12:29, 18 July 2007 (UTC)

To some extent, yes, but if you go through the calculation you will see that being among the first few is not optimal. The optimal place is a rather small number, though, and the birthday paradox does indeed give some insight as to why that is so. -- Meni Rosenfeld (talk) 12:49, 18 July 2007 (UTC)

?As I see it the probability of me having the same birthday is 1/365, if I'm first in line (after the first person) thats my probability of 'winning', if I'm n+1 th in line then to win the previous n people must not have had the same birthday (364/365) therefor the probability of me winning is (364/365)^n times (1/365) - this is maximum when I'm next after the first person (n=0) - am I misreading? "What position in line gives you the greatest chance of being the First Duplicate birthday?"87.102.4.8 14:23, 19 July 2007 (UTC)

You have not misread, but you have made some calculation errors. The important error, for our purposes, is that if there are n people in front of me and they have different birthdays, my probability of having a duplicate birthday is ${\tfrac {n}{365}}$, not ${\tfrac {1}{365}}$. -- Meni Rosenfeld (talk) 20:39, 19 July 2007 (UTC)

Oh, I thought it was having the same birthday as the first person in the line, my mistake. Thanks87.102.92.83 14:43, 20 July 2007 (UTC)

Wouldn't 23rd be the place to be? Further up gives less than a 50% probability and further back makes it more and more likely that someone else will win. <disclaimer> No calculation involved, just a "gut-feeling". </disclaimer> ~ hydnjo talk 14:54, 18 July 2007 (UTC)

It's quite close to 23, yes. But I will leave finding the exact answer as a (not too difficult) exercise for the readers. -- Meni Rosenfeld (talk) 15:12, 18 July 2007 (UTC)

Suppose p(n) is the probability that among n people there are at least two with the same birthday. Then p(n) is a monotonically increasing function of n, which first goes above 50% when n=23. But the "first person" question is subtly different. The n^th person in the line can only win if there are no shared birthdays in the first n-1 people, so we are actually trying to maximise p(n)-p(n-1). This maximum occurs when n is a little lower than 23. Gandalf61 15:45, 18 July 2007 (UTC)

p(n) and p(n-1) aren't independent. When there are 366 people in front of you, they can't all have different birthdays (not counting leap year's day), but p(n)-p(n-1) will never reach zero.

Based on the first four elements, it looks like the pattern is $p(n)={\tfrac {365!n}{(365-n)!365^{n+1}}}$ where n is the number of people in front of you, and p(n) is the probability of getting a free ticket. You need to find the maximum of this equation. It can be recursively defined as $p(n)=p(n-1){\tfrac {366-n}{365}}+{\tfrac {365!}{(365-n)!365^{n+1}}}$ or $p(n)=p(n-1)({\tfrac {366-n}{365}}+{\tfrac {1}{365^{2}(n-1)}})$. I'm not certain about the second one. I got it from the first by dividing the second fraction by the calculated value of p(n-1), and putting it into the parenthesis (thus multiplying it again). If it was correct, the maximum must be the latest value where ${\tfrac {366-n}{365}}+{\tfrac {1}{365^{2}(n-1)}}>1$, because after that p(n) start decreasing. The answer is thus the floor of the zero of ${\tfrac {366-n}{365}}+{\tfrac {1}{365^{2}(n-1)}}-1$. Feel free to work this out. Just make sure to double check your answer. Remember, n is the number of people ahead of you, not the number you are in line (unless you count starting from zero). If you want a bigger challenge, try solving with leap year! — Daniel 17:28, 18 July 2007 (UTC)

It is not clear what it means that p(n) and p(n-1) are not independent. These are real numbers, not random variables.  --Lambiam 23:53, 18 July 2007 (UTC)

Plus the fact that p(n)−p(n−1) will of course reach zero. p(366) = 1 - it's certain that amongst 366 people, at least 2 will share a birthday (again discounting Feb 29th). p(n)−p(n−1) will therefore equal zero for n greater than or equal to 367. I.e. if you are the 367th in line, there is zero chance of you winning, because amongst the 366 people in front, at least 2 will share a birthday. If you are 366th in line, then p(n)−p(n−1) is very small but non-zero. The 365 people in front could potentially have everyone with a different birthday. It's very improbable (around 1:2.5×10⁷⁷⁸), but if that does turn out to be the case, then you would win as 366th in line. Richard B 00:36, 19 July 2007 (UTC)

Let me be more explicit. Let E_n be the event "one of the first n people in the line is the winner"; let p(n) be the probability of E_n and let w(n) be the probability of {E_n and not E_n-1} i.e. the probability that the n^th person in the line is the winner. Daniel is correct to say that events E_n and E_n-1 are not independent - in fact E_n-1 implies E_n. This is what exactly what leads us to conclude that w(n) = p(n)-p(n-1) as follows:

$p(n)=P(E_{n})=P(E_{n}\land (E_{n-1}\lor \lnot E_{n-1}))=P(E_{n}\land E_{n-1})+P(E_{n}\land \lnot E_{n-1})$

$P(\lnot E_{n}\land E_{n-1})=0\Rightarrow P(E_{n}\land E_{n-1})=P(E_{n-1})$

$\Rightarrow p(n)=P(E_{n-1})+P(E_{n}\land \lnot E_{n-1})=p(n-1)+w(n)$

Using the formula for p(n) derived in the birthday paradox article, we get:

$w(n)={\frac {364!}{(366-n)!}}{\frac {n-1}{365^{n-1}}}$

which is the same as the expression that Meni Rosenfeld derived from first principles above. Gandalf61 10:00, 19 July 2007 (UTC)

Where? Are you saying it matches with the first four probabilities. That appears to be what I got, only in a slightly different form, with n referring to the place you are in line instead of the number of people in front of you. You were correct about the p(n)-p(n-1) thing. In any case, I think it's generally much easier to find the zero of a function then the max, which is why I found w(n+1)/w(n) above. Had I realized you were right I probably would have looked for (p(n)-p(n-1))-(p(n-1)-p(n-2)) or p(n)-2p(n-1)+p(n-2). If you want to find the number in line you are, use the ceiling, instead of the floor, of ${\tfrac {366-n}{365}}+{\tfrac {1}{365^{2}(n-1)}}-1=0$. This is the same as ${\tfrac {-365(n^{2}-732n+1)}{365^{2}(n-1)}}=0$ which can be solved with the quadratic formula. ${\tfrac {732+-{\sqrt {732^{2}-4}}}{2}}=366+-{\sqrt {183^{2}-1}}=366+-{\sqrt {33488}}$ the first zero is the one with the minus, so it's $366-{\sqrt {33488}}$, or 182 people in front of you, 183rd in line. This is way more then the previous estimates, so I'm probably wrong. Someone see if they can find where I went wrong and fix it, or if I actually got it right and the previous estimates were way off. — Daniel 16:36, 19 July 2007 (UTC)

I got far less than 182. If you look at w(n+1)/w(n) with w(n) defined as above. If w(n+1)/w(n) is less than 1, then you are less likely to win the prize if you are standing at position (n+1) in the queue, compared with position n. So look for when w(n+1)/w(n) equals 1. I get the quadratic to look at being n^2 - n - 365 = 0. If you discount the negative root of this quadratic, then that gives you an answer just below 23, as expected. The positive root isn't an integer, so you'll have to round up to the next integer in this case, which I get to be 20, i.e. the optimum position to stand is 20th in the queue, which gives you slightly better odds than 1:31 chance of winning the free ticket. Richard B 18:55, 19 July 2007 (UTC)

A small correction to Richard: The root of $n^{2}-n-365=0$ is $1+{\sqrt {366}}\approx 20.13$. 20 is less than this value, so ${\tfrac {w(20+1)}{w(20)}}>1$, so the optimal solution is actually 21 (in other words: You need to take the ceiling of the root, not just round it). -- Meni Rosenfeld (talk) 20:26, 19 July 2007 (UTC)

${\frac {1+{\sqrt {1+4\times 365}}}{2}}\approx 19.61$ Gandalf61 20:52, 19 July 2007 (UTC)

Yes, that's what I got, but you can also see it by working out the actual probabilities for w(19), w(20) and w(21). w(20) is just slightly better odds than 1:31 as I pointed out above, w(19) and w(21) are both slightly worse than 1:31. Richard B 21:11, 19 July 2007 (UTC)

Apparently my earlier calculations, which for some unknown reason resulted in $1+{\sqrt {366}}$, have subconsciously tricked me into solving $n^{2}-n-365=0$ as if it was $n^{2}-2n-365=0$. 20 is of course correct, sorry. -- Meni Rosenfeld (talk) 10:50, 20 July 2007 (UTC)