Who discovered this number-guessing paradox?
Thanks to a helpful comment, since deleted, by user Stefanos, I was led to this (one-page) paper of Thomas M. Cover “Pick the largest number”Open Problems in Communication and Computation Springer-Verlag, 1987, p152.
Stefanos pointed out that there is an extensive discussion of related paradoxes in the Wikipedia article on the ‘Two envelope problem’. Note that the paradox I described above does not appear until late in the article, in the section "randomized solutions".
Note also that the main subject of that article involves a paradox that arises from incorrect reasoning, whereas the variation I described above is astonishing but sound.
I would still be interested to learn if this paradox predates 1987; I will award the "accepted answer" check and its 15 points to whoever posts the earliest appearance.
In his blog post, mathematical physicist John Baez considered this problem described by Thomas M. Cover as the special case $n = 2$ of what was called "the game of googol" by Martin Gardner in his column in the Feb. 1960 issue of Scientific American.
That is, John Baez accepted (the suggestion by one of his blog readers) that this is a variant of the famous secretary problem, which wiki entry actually includes this "game of googol".
If you are willing to take this point of view (Thomas M. Cover sort of did, in his closing remark), then the quest becomes the history of (this variant of) the secretary problem.
John Baez's blog post is a good expository piece with some good discussion in the comments there. However, he didn't really do the literature search that pertains to Thomas M. Cover's approach going backwards in time.
Similarly, there's no citation in that Quanta magazine article that got John Baez's notice. FWIW, the analysis there is thorough enough while being easily accessible to the general public.
My personal stance at this point is that, nobody before Thomas M. Cover looked at the secretary problem in this particular way. He passed away in 2012 so one can only learn how he encountered this problem by studying his notes or asking his collaborators, friends, etc.
I have to admit that I didn't go through all the publications (27 so far) that cited that short paper by Thomas M. Cover to see if they found anything preceding that.
For the record, if one wants to see Martin Gardner's original text, I cannot find an open access of the Feb.1960 Scientific American nor the earliest reprint of the column in his 1966 book.${}^2$ The best thing I've got is the 1994 google book. See the 2nd paragraph on p.18 for the case $n=2$. Martin Gardner certainly didn't know what he was missing.
Footnote 1:$\quad$ "New Mathematical Diversions from Scientific American". Simon and Schuster, 1966, Chapter 3, Problem 3. This is a relatively long chapter in the book, as it essentially deals with the secretary problem.