(I don't think my answer directly answers the question, but I'm hoping it would be useful.)
I assume that when you say "problem solving" you mean mathematical "problem-solving as a skill" ("being able to obtain solutions to the problems other people give you to solve," Schoenfeld, 1992).
I was unable to find any studies that answer the question "Does taking an ordinary undergraduate mathematics course improve one's ability to solve (mathematical) problems?" (where ordinary means the instruction is not explicitly targeted at improving problem solving skills).
But there have been studies that show that undergraduates taking certain "problem-solving courses" experienced "marked shifts in [their] problem solving behavior" (e.g., Schoenfeld, 1987, p. 207).
As I understand it, researchers in mathematics education usually don't consider questions of the type "does the ordinary way of teaching improve this skill/understanding?" important (where "ordinary" is usually referred to as "traditional"). They usually consider it more valuable to ask questions of the type "what way of teaching will improve this skill/understanding?"
A good reference is
Schoenfeld, A. H. (1992). Learning to think mathematically: Problem solving, metacognition, and sense-making in mathematics. In D. Grouws (Ed.), Handbook for Research on Mathematics Teaching and Learning (pp. 334-370). New York: MacMillan.
which uses some material from
Schoenfeld, A. H. (Ed.). (1987). Cognitive Science and Mathematics Education. New Jersey: Erlbaum.
Chapter 2 (Foundations of cognitive theory and research for mathematics problem-solving, by E. A. Silver) and Chapter 8 (What's all the fuss about metacognition? by A. H. Schoenfeld) of the 1987 Schoenfeld book are particularly useful.
I realize Mathematics Education posts are often of questionable admissibility on MO. I will try to do the question here some justice by answering from within the field of Math Education, but I cannot speak to how widespread my own views on the matter are. If my response seems somewhat long, then I might suggest one consider its ratio to how broad the question title is; unless, of course, a length:breadth comparison only confuses further.
First, here is one concrete answer: James Stewart's tome on the Calculus sequence (2012) contains a section on Polya's problem solving strategies. This book is widely used in the United States at the tertiary (undergraduate) level. I cannot say Stewart has made a concerted effort to incorporate a discussion of Polya's four steps or the use of heuristics into latter parts of his text, so at least the sections on problem-solving and on Calculus are separate.
An issue of ambiguity now arises, for the question title ("Is problem solving a subject to be taught?") is somewhat different in spirit from the actual question (related to the organization of textbooks). If you restrict yourself to what appears in mathematical textbooks, then you may be doing the title-question a disservice. Probably some teachers make it a pedagogical goal to use the problem solving section as a reference that can be returned to repeatedly while teaching Calculus; probably others gloss over or completely skip the section. If you wish to explore more deeply issues related to teacher adherence to curricular materials, then the term fidelity is what should let you comb the literature.
Second, you asked a separate question that was framed as "an attempt to get an indirect answer for [this question]," and I had left an answer there with four Math Ed references some time ago. I hope that my general point about the difficulty of directly teaching heuristics was not lost, even as the question was ultimately closed, and that the relation to this post is apparent.
Third, I see elsewhere a mention of the Common Core State Standards for Mathematics (CCSSM pdf). Consider the Standards as a document, the forthcoming textbooks that will be designed to satisfy them in some quantifiable way, how teachers actually adjust (or don't) to these new texts, the corresponding professional development to implement them (nationally, I cannot say this will occur) and Standards-aligned examinations to evaluate students based on CCSSM (this will occur and already sample tests have been administered). The interplay between these components - and many others - is nontrivial, and I would be hesitant to conclude anything about how problem solving actually finds its way into the classroom, even after the next batch of textbooks is published.
From a historical perspective, the very issue you raise has been discussed and led to various curricular shifts every decade or so since at least 1980. An early document of relevance in the United States is the National Council of Teachers of Mathematics (NCTM) published piece An Agenda for Action, where the first recommendation, verbatim, is that "Problem solving be the focus of school mathematics in the 1980s." Subsequent documents of relevance include two more NCTM pieces: Curriculum and evaluation standards for school mathematics (1989) and Principles and standards for school mathematics (2000) before CCSSM was released in 2010. Plenty is written on each of these, and I'm sure a search through google scholar would be more useful than my attempt at a broad summary.
If I am to venture a guess as to the relevance of all this to your question: Assuming for a moment (perhaps unwisely) that we do not start over with a new set of standards in the near future, I expect the focus not to be on problem solving as a separate subject to be taught, but instead as a "Standard for Mathematical Practice" (CCSSM, p. 6) to be integrated with the more broadly-defined goal of sense-making in mathematics. (Not sense-making: A classic example discusses asking elementary school students, given that the farmer has 20 sheep and 10 cows, how old is the farmer? A shocking proportion of students will try to answer this question with a number: usually 30. This is no anomaly; even more extreme examples exist in which a numerical answer is given when no question at all was posed.)
I suspect that CCSSM will have a stronger effect than its predecessors, for two reasons: 1, its near nationwide acceptance by governors, which coincides not surprisingly with a shift towards a more centralized approach to education, and presages tests (hence accountability) of some sort or another; and 2, the realization that the Standards might have a long-term presence has led to some who might otherwise oppose such a document to try and make the best of the situation. I recently attended a colloquium given by Alan Schoenfeld at Teachers College, where he talked about related issues, and his work to help teachers with CCSSM despite the shortcomings it might have. (This talk has since been written up as a short article: Schoenfeld, A. Mathematical Modeling, Sense Making, and the Common Core State Standards. The Journal of Mathematics Education at Teachers College, 4(2).) Henry Pollak, who was involved in the School Mathematics Study Group (SMSG) of the 1950s and 60s behind New Math, remarked on the wonder of seeing others helping to promote and improve mathematics curricula with which they might not agree. (It is perhaps a lack of this sort of support that derailed New Math, and led to its condemnation and the following Back to the Basics movement, though its detractors would no doubt be surprised to realize the atavistic re-emergence of some wonderful materials developed around that time in "new" textbooks.)
Let me end somewhat abruptly here, for the question of how to teach problem solving or incorporate it into a curriculum is rather general, and perhaps all that was desired was a textbook reference or two.
Best Answer
The approaches in the OP already seem quite straightforward to me, and as is clear from the answer by Arthur B, doing the calculation exactly is not too complicated.
Anyway, here is my suggestion (after a bit of scribbling) for how one might have seen the solution at a glance.
All we have to do is compare the winning chances of person $k$ and person $k+1$ (provided we do it for general $k$). Edit: this is because the winning chances are first increasing and then decreasing, which of course isn't clear a priori, so perhaps the previous sentence should have started "As it turns out...".
We imagine two persons A and B who are to occupy places $k$ and $k+1$. We only have to compare the scenarios where the one who goes first wins, to the scenarios where the one who goes second wins (otherwise the order of A and B doesn't matter).
Those scenarios first of all require that persons $1,\dots, k-1$ have different birthdays.
Under that assumption, the cases where the person to go first wins are when both A and B have a birthday which is already represented among the first $k-1$ people. Counting combinatorially rather than probabilistically, there are $(k-1)^2$ ways of choosing the birthdays of A and B with that constraint.
The cases where the person to go second wins are when A and B have the same birthday, and that birthday is not shared with any of the first $k-1$ people. There are $n-(k-1)$ such ways of choosing the birthdays of A and B.
Therefore we end up comparing $(k-1)^2$ to $n-(k-1)$, or equivalently comparing $k(k-1)$ to $n$.
After having written it down, I get the feeling that this argument is more convoluted than the straightforward calculation by Arthur B, but here it is, for what it's worth.