Skip to main content
corrected special case and added reference/motivation
Source Link
user95536
user95536

You are given $2n$ boxes that are arranged circular (you can imagine all boxes are on the edge of a circular table). Then randomly, you put $k$ balls in the boxes such that each box is containing either 0 or 1 ball.

What you have to do is to pick $n$ consecutive boxes such that the number of balls you pick is as small as possible. What is the expected number of this number (the number of balls)?

On a special case, what if $k$$k \approx\log n$?

Reference/Motivation. This is equalactually one of my work to attack this question: $O(\log n)$?Painting $n$ balls from $2n$ balls red, and guessing which ball is red, game.

You are given $2n$ boxes that are arranged circular (you can imagine all boxes are on the edge of a circular table). Then randomly, you put $k$ balls in the boxes such that each box is containing either 0 or 1 ball.

What you have to do is to pick $n$ consecutive boxes such that the number of balls you pick is as small as possible. What is the expected number of this number (the number of balls)?

On a special case, what if $k$ is equal to $O(\log n)$?

You are given $2n$ boxes that are arranged circular (you can imagine all boxes are on the edge of a circular table). Then randomly, you put $k$ balls in the boxes such that each box is containing either 0 or 1 ball.

What you have to do is to pick $n$ consecutive boxes such that the number of balls you pick is as small as possible. What is the expected number of this number (the number of balls)?

On a special case, what if $k \approx\log n$?

Reference/Motivation. This is actually one of my work to attack this question: Painting $n$ balls from $2n$ balls red, and guessing which ball is red, game.

Source Link
user95536
user95536

Randomly put $k$ balls in $2n$ circular boxes, pick $n$ consecutive boxes such that the number of balls is minimum!

You are given $2n$ boxes that are arranged circular (you can imagine all boxes are on the edge of a circular table). Then randomly, you put $k$ balls in the boxes such that each box is containing either 0 or 1 ball.

What you have to do is to pick $n$ consecutive boxes such that the number of balls you pick is as small as possible. What is the expected number of this number (the number of balls)?

On a special case, what if $k$ is equal to $O(\log n)$?