Timeline for Separating Heavier from the Lighter Balls
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 10, 2017 at 21:04 | history | edited | Tony Huynh |
edited tags
|
|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Dec 9, 2016 at 7:55 | history | edited | Vepir | CC BY-SA 3.0 |
added 56 characters in body
|
| Dec 9, 2016 at 7:43 | vote | accept | Vepir | ||
| May 7, 2016 at 17:12 | answer | added | usul | timeline score: 7 | |
| May 7, 2016 at 14:29 | comment | added | Manfred Weis | What is the outcome of the weighting, a numerical value or a decision, which of two sets of the balls is heavier? In the classical version of the puzzle it is just a comparison of weights. If in your version the outcome is a precise weight, then the complexity might also depend on the properties of the weights, i.e. whether the heavier ones weigh an integral, rational or irrational multiple of the lighter ones. | |
| May 6, 2016 at 21:23 | answer | added | Tony Huynh | timeline score: 7 | |
| May 6, 2016 at 17:57 | comment | added | Terry Tao | You can improve this bound asymptotically by a factor of two using Shannon entropy. We can assume (for the purposes of lower bounds) that the heavy/light distribution is uniform, so the Shannon entropy is $\log_2 \binom{2n}{n} \sim 2n$. Each measurement actually has an entropy of at most $\sim \frac{1}{2} \log_2 n$ due to concentration of measure (the answer is concentrated in a region of width about $\sqrt{n}$). This gives an asymptotic lower bound of $4n/\log_2 n$. | |
| May 6, 2016 at 16:43 | comment | added | Emil Jeřábek | A simple lower bound: each weighting has at most $2n+1$ possible outcomes, hence you need at least $\left(\log\binom{2n}{n}\right)/\log(2n+1)\sim2n/\log_2n$ weightings. | |
| May 6, 2016 at 16:30 | review | First posts | |||
| May 6, 2016 at 17:00 | |||||
| May 6, 2016 at 16:27 | history | asked | Vepir | CC BY-SA 3.0 |