Median of Medians Puzzle

[@maxime_weill]

this channel always pull out the weirdest problem and i'm all here for it :). Before watching, i tried to solve this on my own, i found 9 and 17. For the smallest median m, it has to be greater than 2 other numbers in it's list, and 2 other medians, which in turn are each greater than 2 other numbers in their respective lists. So m has to be bigger than 8 other different numbers, so it has to be at least 9. It's not so hard to construct an example. I found the biggest median with similar reasoning.

[@scottmiller2591]

This sounds esoteric, but it's almost precisely John Tukey (the Tukey in the Cooley-Tukey inventors of the FFT)'s "ninther," or median of medians, method of estimating a robust central location from a large number of samples by taking 9 random samples (hence the name "ninther"), breaking into 3 groups, taking the median, then the medians of the medians. It's not as efficient as the average for a Gaussian distribution (average is the optimal estimator in this case), but works better for heavy tailed distributions. It comes from an era where a person didn't have a computer to take the median of millions of numbers, but had a pencil, paper, and a mind. It was a pretty good estimate with very little work.

[@nirajmehta6424]

fascinating, thanks for sharing

[@peterhall6656]

I vaguely recall a generalisation of this decades ago. Possibly Gian Carlo- Rota or maybe even Lazlo Lovascz. My memory fails me but this is a nice bit of work. Very interesting.

[@bigjukebox3370]

For the second example (where you'd get 9), you can just use the other example (17) to construct the "negative" of it: just take every value and substract it from 26. If you wish you can reverse the order, so they go from left to right again - and voilá! The new median will be 26-17 = 9. As I said before, in a sense this is just the "negative" version of the first solution for 17, because essentially in the domain of 1-25, the "opposite" of 25 (the largest) would be 1 (the smallest) and vise versa. And with that logic you can just "mirror" every number similarly to get a "mirrored" solution!

[@ZipplyZane]

I thought of the same thing. But the term I though of for the "negative" was the "inverse mod 26".

[@sr6424]

Really interesting. Reminds me of a book I once read - ‘ How to Lie with Statistics’! I am going to create a version of this for my next puzzle evening. I will work on something with a couple of subsets.

[@TheUglyCuckling]

That was simple but fun! I used to love puzzles of this type. I suppose I still do.

[@jay_13875]

It seems pretty straightforward to prove that for any construction resulting in a median of medians of n, you can derive another construction with a median of medians 26-n by replacing each number x in any of the sets with 26-x. From that, it follows that there can't be a median of medians smaller than 9 if there is no median of medians greater than 17, and that the smallest possible median of medians is 9.

[@DrBarker]

Yes, there is a nice symmetry about this sort of problem, that the biggest and smallest possible values should be the same distance away from the median of the whole set of numbers. In an example where the numbers aren't evenly spread out, the "distance" would be the number of spaces away from the median of the whole data set, rather than a difference between specific values.

[@pierreabbat6157]

Can you compute the persian of the persians?

[@ThePayner11]

Been trying to write a python program for this puzzle but not sure how to do it! Need a bit of help here!

[@jorgechavesfilho]

Building the algorithm itself is straightforward, but it won't be feasible in general. You will have to use the exhaustive search method (brute force). Consider that the 5 subsets (which will be exhausted) are lined up. So you will investigate 25! permutations. Some you will eliminate because you will generate unordered subsets. If instead of 25 numbers there were 50 numbers, you can imagine the complete impossibility of operating 50! attempts.

[@monkyyy0]

? I feel like it would be trivial to optimize it to do better then n!

[@jorgechavesfilho]

@@monkyyy0 I doubt it. For example, you can optimize to already generate ordered subsets. But even then, the number of attempts will be given by a numerical expression involving factorials. It's always interesting to make a Phyton application, but most of the time it will only illustrate cases of small samples. For these types of problems, there is no known way to find an answer quickly, but if an answer is provided, it can be checked quickly.

[@zathrasyes1287]

Damn, that was a cool friday-adventure!

[@armanavagyan1876]

Pretty interesting 👍

[@alipourzand6499]

Great video. Now the question is since the subsets are not unique, what is the number of solutions for the smallest and the greatest median. For me this is the beauty of the math. Every answer leads to more questions.

[@jorgechavesfilho]

Great! Just great.

[@armanavagyan1876]

Thank U😊

[@Utesfan100]

It is not hard to generalize your proof to show that for (2n+1)^2 objects the median of the median of 2n+1 partitions is between the (n-1)^2 and (2n+1)^2-(n-1)^2+1 values. n=2 is the case considered. For the median of 49 items partitioned by 7's we get the answer can be between 16 and 34.

[@silver6054]

I'm sure it's true, but the last comment, "you can get any number between 9 and 17" isn't obviously true from the proceeding. You can presumably just alter the target number included in set C, but. Quick display of the remaining cases!