In my last blog post I posed a question about finding the coeff of x^100 in a particular Taylor Series. The question and answer are given here:
The key to the problem was to recognize that it was asking how many ways you can make change of a dollar using pennies, nickels, dimes, and quarters. This can be done by hand (its 242).
1) Someone who I gave the problem to solved it by available software, but when he saw the answer was 242 he realized how to do it via making change.
2) How hard would this problem be to do completely by hand- say as a Putnam Problem? Its hard for me to say since I started with the trick and then found the problem.
3) Is this a well known trick?
If you write the polynomial as (1 – x)(1 – x^5)(1 – x^10)(1 – x^25) then this is a well-known problem; see for example Chapter 1 of Donald J. Newman's book Analytic Number Theory. If it were a Putnam problem then a good solver would reason as follows: "This type of problem is difficult to do by hand in general, but this is the Putnam, so there has to be a slick solution. So the given expression must be a nice polynomial in disguise. Let's try to factor it."
ReplyDeleteThe money changing problem is problem No. 1 in the classic Pólya, George; Szegő, Gábor (1972) [1925], Problems and theorems in analysis, 2 Vols, Springer-Verlag.
ReplyDeleteAre Putnam Problems meant to demonstrate encyclopedic knowledge of trick problems and the ability to apply them inside a weird math problem?
ReplyDelete