4
$\begingroup$

Suppose we have some permutation of the integers from $1$ to $n$. We start reading the permutation from left to right, and only select a number if it is greater than all the numbers to the left of it. For example, for $n=5$ and the permutation $41352$, we will choose the numbers $4,5$.

Over all permutations, what is the probability that the sum of the chosen numbers is even?

I believe that the answer depends on the parity of $n$, because it should be symmetrical when $n$ is even, but slightly less than $n$ when it is odd ($\frac{1}{2} - \frac{1}{2n}$).

Is there a way to formalize this argument.

New contributor
moshpit is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
5
  • 2
    $\begingroup$ I suggest: solve the problem completely for small values of $n$. $\endgroup$ Commented yesterday
  • $\begingroup$ that's how I got the answer that I stated $\endgroup$ Commented yesterday
  • $\begingroup$ Please edit your post to describe the explicit results you have obtained. I would also suggest sampling results for larger $n$. $\endgroup$ Commented yesterday
  • $\begingroup$ The stated answer ($n/2n=1/2$ for even $n$, $(n-1)/2n = 1/2 - 1/(2n)$ for odd $n$) is exactly correct at least through $n=11$. $\endgroup$ Commented yesterday
  • $\begingroup$ Err I am new to probability, what exactly is the sample space here? Like for $n=2$, no. of valid outcomes is $2$ (choosing $2$ in both permutations) and there are $2$ permutations, so the answer is $1$? $\endgroup$ Commented 20 hours ago

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.