Wikipedia:Reference desk/Archives/Mathematics/2010 July 1

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 1

mathematical outcome to simple problem

I need to know if you were having a quiz with 10 participants - how many questions above 10 would you need to ask to ensure that you cannot have a draw?

mauj—Preceding unsigned comment added by 166.120.202.205 (talk) 05:35, 1 July 2010 (UTC) (email address removed. -- SGBailey (talk) 10:22, 1 July 2010 (UTC))

No matter how many questions you have, there is always a possibility of a draw. However, with some assumptions, you can choose the number of questions to make the probability of a draw small. -- Meni Rosenfeld (talk) 06:57, 1 July 2010 (UTC)

If the questions in the quiz are so easy that everybody answer correctly, then draws will occur, no matter how many questions there are in the quiz. So in order to ensure that you cannot have a draw, you need to assume that the probability p for answering correctly satisfy 0<p<1. If p depend on the participant, then there will be fewer draws than if p is the same number for all participants, so let us for the sake of the argument assume that p is the same number for all participants. Let the number of questions in the quiz be called N, and the number of correct answers from participant no i be called N_i such that 0 ≤ N₁ ≤ N₂ ≤ ··· ≤ N₁₀ ≤ N. You want to be ensured that N₁ < N₂ < ···< N₁₀. A necessary but insufficient condition for that to happen is that N≥9, (but not necessarily ≥10). As the probability for a participant to get n correct answers is $\scriptstyle {\binom {N}{n}}p^{n}(1-p)^{N-n}$, the mean number of participants getting n correct answers is $\scriptstyle \lambda =10{\binom {N}{n}}p^{n}(1-p)^{N-n}$, and the actual number is approximately poisson distributed, such that the probability that n is not a draw is $\scriptstyle e^{-\lambda }(1+\lambda )$, and the probability that none of the numbers n are draws is $\scriptstyle P=\prod _{n=0}^{N}e^{-\lambda }(1+\lambda )$. Bo Jacoby (talk) 13:30, 1 July 2010 (UTC).

Taking the logarithm of $\scriptstyle P$ gives

$\log P=\sum _{n=0}^{N}(-\lambda +\log(1+\lambda ))$.

Expanding $\scriptstyle \log(1+\lambda )=\lambda -{\frac {\lambda ^{2}}{2}}+\cdots$ gives

$\log P=\sum _{n=0}^{N}(-\lambda +\lambda -{\frac {\lambda ^{2}}{2}}+\cdots )=\sum _{n=0}^{N}(-{\frac {\lambda ^{2}}{2}}+\cdots )=-50\sum _{n=0}^{N}{\binom {N}{n}}^{2}p^{2n}(1-p)^{2(N-n)}+\cdots$.

The special case $\scriptstyle p={\frac {1}{2}}$ gives the simpler formula

$\log P\approx -50\cdot 4^{-N}\sum _{n=0}^{N}{\binom {N}{n}}^{2}$.

I do not know how to simplify this. Bo Jacoby (talk) 20:53, 1 July 2010 (UTC).

I don't know how to simplify this either (I'm sure I saw it somewhere but forgot). But thanks to my silicon master, I know what to simplify it to:

$\sum _{n=0}^{N}{\binom {N}{n}}^{2}={\binom {2N}{N}}.$

And with Stirling's formula, I believe you get something like

$4^{-N}{\binom {2N}{N}}\approx {\frac {1}{\sqrt {\pi N}}}.$

-- Meni Rosenfeld (talk) 05:03, 2 July 2010 (UTC)

That's great, Meni! (Of course you mean $\scriptstyle {\binom {2N}{N}}$ rather than $\scriptstyle {\binom {2N}{n}}$. I permitted myself to fix it). If you find the reference you should include the formula in the article on binomial coefficient. Now we should be close to answering the OP's question.

$P\approx e^{-{\frac {50}{\sqrt {\pi N}}}}$.

But there is something rotten. For big values of $\scriptstyle N$ the probability $\scriptstyle P$ approaches one rather than zero. I have made an error. Bo Jacoby (talk) 07:35, 2 July 2010 (UTC).

$\scriptstyle P$ is the probability that there are no draws. $\scriptstyle -{\frac {50}{\sqrt {\pi N}}}\approx \log(P)\approx P-1$ implies the final result:

$N\approx {\frac {2500}{\pi (1-P)^{2}}}$

If you require $\scriptstyle P$ > 0.95 you must have $\scriptstyle N$ > 318310. So the answer is that you cannot be ensured that there will be no draws. Bo Jacoby (talk) 12:14, 2 July 2010 (UTC).

A clarification. In a "winner take all" sort of contest, "no draw" is a weaker condition than a complete, non-degenerate ranking. That is, N₁ ≤ N₂ ≤ ··· ≤ N₉ < N₁₀, rather than N₁ < N₂ < ··· < N₉ < N₁₀. (Because you still have a clear winner if one person gets all the questions right, and everyone else ties with no questions right.) If you want no draws in a Olympics-style first/second/third contest, the condition would be N₁ ≤ N₂ ≤ ···≤ N₇ < N₈ < N₉ < N₁₀. The probabilities of each condition will be different. -- 174.24.195.56 (talk) 18:07, 3 July 2010 (UTC)

Only nine, if you had a knock-out tournament with quickest buzzer answers first and wrong answer means opponent wins. 92.28.245.229 (talk) 21:48, 3 July 2010 (UTC)

searching for a solution

Hello, my todays question is as follows. Let n be a natural number and [1,n] stand for the set {1,2,3...n}. Let b be a natural number and consider the equation x+y-z=b, where b is a fixed natural number > 1. Let $I_{1}=[1,\left\lceil {\frac {b}{5}}\right\rceil ],I_{2}=[\left\lfloor {\frac {b+\left\lceil {\frac {b}{5}}\right\rceil }{2}}+1\right\rfloor ,b-\left\lceil {\frac {b}{5}}\right\rceil ]$.

We need to show that it is not possible to find x,y,z such that they solve the equation and x,y is in I₂, and z in I₁. What I am trying to do is to show that the maximum value of b+z is strictly less then the minimum value of x+y. But all I can show is that $x+y>{\frac {6b}{5}}$ and $b+z<{\frac {6b}{5}}+1$. This does not solve the problem. Can someone advise me what am I doing wrong. Thanks--Shahab (talk) 18:30, 1 July 2010 (UTC)

What you wrote looks good to me; but as you see, just using the identities $x\leq \lceil x\rceil <x+1$ and $x-1<\lfloor x\rfloor \leq x$ may not be sufficient.

Try leaving the expressions unsimplified, i.e. $b+z\leq b+\left\lceil {\frac {b}{5}}\right\rceil$ and $x+y\geq 2\left\lfloor {\frac {b+\left\lceil {\frac {b}{5}}\right\rceil }{2}}+1\right\rfloor$, and then checking cases individually for b modulo 10. 98.235.80.144 (talk) 20:55, 1 July 2010 (UTC)

I do not get what you are asking me to do. Can you please elaborate a little. And from where did you get 10 in the picture. (Thanks for replying)-Shahab (talk) 02:05, 2 July 2010 (UTC)

The phrase "b modulo 10" refers to modular arithmetic or the modulo operation (used in computer programming). Those articles have a lot more detail than the basic idea you need for this problem, though.

Here's the idea: Since b is an integer, we have the following 10 cases-- b=10n+0, b=10n+1, b=10n+2, b=10n+3, ..., up to b=10n+9. We can plug each option for b into the formulas above, compute the floor and ceiling functions exactly, and then see that x+y>b+z in each case.

For example, let's look at the case b=10n+7. Then

$b+z\leq b+\left\lceil {\frac {b}{5}}\right\rceil =10n+7+\left\lceil {\frac {10n+7}{5}}\right\rceil =10n+7+\left\lceil 2n+{\frac {7}{5}}\right\rceil =10n+7+(2n+2)=12n+9$.

On the other hand,

$x+y\geq 2\left\lfloor {\frac {b+\left\lceil {\frac {b}{5}}\right\rceil }{2}}+1\right\rfloor =2\left\lfloor {\frac {10n+7+\left\lceil {\frac {10n+7}{5}}\right\rceil }{2}}+1\right\rfloor =2\left\lfloor {\frac {10n+7+\left\lceil 2n+{\frac {7}{5}}\right\rceil }{2}}+1\right\rfloor$

$=2\left\lfloor {\frac {10n+7+(2n+2)}{2}}+1\right\rfloor =2\left\lfloor {\frac {12n+9}{2}}+1\right\rfloor =2\left\lfloor 6n+{\frac {11}{2}}\right\rfloor =2(6n+5)=12n+10$

This proves that there are no solutions if b=7, 17, 27, 37, or any other positive integer ending in 7. If you check the other 9 cases yourself, you'll have the complete proof for all possible values of b. (Or maybe you'll find a counterexample-- I haven't checked them myself.) The reason to check cases of b modulo 10 is that it lets us cancel the denominators 5 and 2. If the problem had denominators of 7 and 3, then you would want to check all cases for b modulo 21 to use this method. 98.235.80.144 (talk) 02:47, 2 July 2010 (UTC)

Actually, it looks like checking b modulo 5 is sufficient. Using b=5n+0, b=5n+1, b=5n+2, b=5n+3, and b=5n+4 you will always be able to cancel the denominator 2. I should have noticed that from the start, since each expression has order 6b/5. Of course, it still works to check all choices of b modulo 10; it's just twice as much writing.98.235.80.144 (talk) 04:25, 2 July 2010 (UTC)

Thanks for all the help.---Shahab (talk) 13:40, 2 July 2010 (UTC)

No need for checking cases, just use the observation that $\lceil n/2\rceil =\lfloor (n+1)/2\rfloor$ for integer n:

${x+y\geq 2\left\lfloor {\frac {b+\lceil b/5\rceil }{2}}+1\right\rfloor =2\left\lceil {\frac {b+\lceil b/5\rceil +1}{2}}\right\rceil \geq b+\lceil b/5\rceil +1>b+\lceil b/5\rceil \geq b+z}.$

—Emil J. 13:55, 2 July 2010 (UTC)