Putnam Preparation Help

[ehrenfest]

I was told to move my problem solving questions here instead of cluttering up the Homework Help forums. I will use this thread to post questions related to the Putnam Exam. For all of the problems that follow, please JUST GIVE HINTS.


Problem 170 from Putnam and Beyond:
Let
$$P_n(x) = (x^n-1)(x^{n-1}-1)\cdots(x-1), \mbox{ for n \geq 1}$$.

Prove that for $\mbox{n \geq 2}, P'_n(x)$ is divisible by
$$P_{\lfloor n/2 \rfloor}(x)$$
in the ring of polynomials with integers coefficients.

We can use the division algorithm but then I don't know how to show that the remainder is 0. I'm not really sure whether it is enough to show that all the roots of $$P_{\lfloor n/2 \rfloor}(x)$$ are also roots of P'_n(x) since we are only working in the Z[x]? The roots of P'_n(x) are just the rth roots of unity for all r <= n. Anyone have a hint?

 

[morphism]

Have you tried looking at small values of n? This might suggest induction on n.

 

[uart]

My hint is to break $$P_n$$ into the product $$P_n = H_n L_n$$. Where

$$H_n(x) = (x^n - 1)...(x^{\lfloor n/2 \rfloor + 1} - 1)$$

$$L_n(x) = (x^{\lfloor n/2 \rfloor} - 1)...(x - 1)$$

Then use P' = H L' + H' L and see where that takes you.

 

[ehrenfest]

Wow its amazing how far good notation can go.

The zeroes of L_n are

$$e^{i k \theta/2 \pi m}$$

where k=0,...,m-1 and m= 1,...,floor(n/2)

Fix k and m. If e^{i k \theta/2 \pi m} is a zero of L_n, then e^{i 2k \theta/2 \pi 2m} is a zero of H_n because 2 floor(n/2) <=n. So basically this means that all the zeroes of L_n are also zeros of L_n' H_n because taking the derivative of a polynomial reduces multiplicities by 1. But we need to prove that L_n is a factor of L_n' H_n in the ring Z[x]. What I showed is NOT enough, is it?

 

[uart]

Yeah I didn't actually solve the problem before posting that hint, it just seemed like a promising way to attack it. Basically it reduces the problem to one of showing that H(x) is divisible by L(x).

I think your approach of looking at the collection of complex zeros of both H(x) and L(x) is a good way to show this. Essentually it's a "covering" type problem. You need to show that for each complex zero of L(x) there is a corresponding complex zero in H(x).

Start as you did by writing the complex zeros corresponding to each of the $x^m-1$ term, that is, $e^{i 2k \pi /m}$ for each k=0..m-1.

Consider seperately the case of k=0. Here we have one positive real zero (at x=1) for each m. Thus all that is required for H(x) to "cover" all of the x=1 zeros of L(x) is that H has at least as many "m-terms" as L which it clearly does (BTW, here by "m-term" I mean one of the $x^m-1$ factors).

Next consider m=2r, m=3r, m=4r, etc (for each m-term L). For each even "m" (m = 2r) we get a zero at $e^{i \pi}$. So just show that H has at least as many even powered terms as L and it will cover these zeros. Similarly we have to show that H has as at least many triplen powered terms as L, and at least as many multiple_of_4 powered terms and so on.

I know this is a bit messy but I think it works.

 

[PFStudent]

Hey,

The Art and Craft of Problem Solving, 2nd Edition by Paul Zeitz.

Homework Statement

1.3.13 (Putnam 1978)
Let ${A}$ be the set of ${20}$ distinct integers chosen from the arithmetic progression ${1, 4, 7,..., 100}$. Prove that there must be two distinct integers in ${A}$ whose sum is ${104}$.

Homework Equations

Familiarity with Arithmetic Progressions.

The Attempt at a Solution

Since, we're just doing hints here, I would like to know how can I start this Putnam problem?

Particularly, what is an "arthmetic progression?"

Thanks,

-PFStudent

 

[Drexas]

Try writing out all the possible sums (using two numbers from the set A) that add up to 104. What do you notice about the number of combinations?

 

[uart]

Particularly, what is an "arthmetic progression?"

It's a just a sequence in which each number differes from the previous by a constant amount. In this case each element is 3 greater than the previous.

 

[elarson89]

Let ${A}$ be the set of ${20}$ distinct integers chosen from the arithmetic progression ${1, 4, 7,..., 100}$. Prove that there must be two distinct integers in ${A}$ whose sum is ${104}$.

If you are familiar with the pigeon hole principle (PHP), this problem is pretty straight forward.

If you don't know the PHP, it's simple enough, and goes something like this. If you have n+1 pigeons but only n pigeonholes, then there is at least one pigeonhole with 2 or more pigeons.

Try assigning some groups of numbers as holes, and then placing the pigeons (numbers) into those holes.

 

[PFStudent]

Hey,

Homework Statement

Putnam 1951 A6
Determine the position of a normal chord of a parabola such that it cuts off of the parabola a segment of minimum area.

Homework Equations

Standard Form of a Parabola
$${y} = {{{a}{{x}^{2}}} + {{b}{x}} + {c}}{{\,}{\,}{\,}{\,}{\,}{\,}}{\textrm{Vertical Axis of Symmetry}}$$
$${x} = {{{d}{{y}^{2}}} + {{e}{y}} + {f}}{{\,}{\,}{\,}{\,}{\,}{\,}}{\textrm{Hortizontal Axis of Symmetry}}$$

Area Bounded Between Curves
$${A_{B}} = {\int_{a,c}^{b,d}{{\left[}{{{{f(x)}_{T}},{{f(y)}_{R}}} - {{{g(x)}_{B}},{{g(y)}_{L}}}}{\right]{{dx},{dy}}}}}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{{a}{\leq}{x}{\leq}{b}}{\,}{\,}{\,}{\,}{,}{\,}{\,}{\,}{\,}{{c}{\leq}{y}{\leq}{d}}$$

The Attempt at a Solution

From the Standard Form of a Parabola (Vertical Axis of Symmetry) let,
$${f(x)} = {{{a}{{x}^{2}}} + {{b}{x}} + {c}}$$

Since we are asked to find the position of a normal chord of a parabola, we first need to find the slope of a tangent line to a parabola for some point, ${{{P}_{1}}{{\left(}{{{x}_{1}},{{y}_{1}}}{\right)}}}$ on the parabola.
So,
$${{{f}^{\prime}}{(x)}} = {{{2}{a}{x}}+{b}}$$

Let,
$${{{f}^{\prime}}{(x)}} = {m(x)}$$

However, we need a normal line, so let,
$${p(x)} = {\frac{{-}{1}}{m(x)}}$$

$${p(x)} = {\frac{{-}{1}}{{{2}{a}{x}}+{b}}}$$

Since we need a chord normal to the parabola, we need to consider two points on the parabola: ${{{P}_{1}}{{\left(}{{{x}_{1}},{{y}_{1}}}{\right)}}}$ and ${{{P}_{2}}{{\left(}{{{x}_{2}},{{y}_{2}}}{\right)}}}$; such that a chord going through both of the points on the parabola will bound an area with only the curve of the parabola where one of the intersections will be normal to the parabola.

Let, the chord's intersection at ${{{P}_{1}}{{\left(}{{{x}_{1}},{{y}_{1}}}{\right)}}}$ be normal to the parabola.
$${p({{\left(}{{x}_{1}}{\right)}})} = {\frac{{-}{1}}{{{2}{a}{{{\left(}{{x}_{1}}{\right)}}}}+{b}}}$$

$${p{{\left(}{{x}_{1}}{\right)}}} = {\frac{{-}{1}}{{{2}{a}{{{{x}_{1}}}}}+{b}}}$$

Now consider the line,
$${y} = {{p}{x}+{c}}$$

Where ${c}$ is the y-intercept of the line.
Let ${{c} = {e}}$ to avoid confusion with ${f(x)} = {{{a}{{x}^{2}}} + {{b}{x}} + {c}}$.
$${y} = {{p}{x}+{(e)}}$$
$${y} = {{p}{x}+{e}}$$

Letting, ${{p} = {p(x)}}$ where ${{p(x)} = {p{{\left(}{{x}_{1}}{\right)}}}}$.
$${y} = {{{\left(}{{p{{\left(}{{x}_{1}}{\right)}}}}{\right)}}{x}+{e}}$$

$${y} = {{{\left(}{\frac{{-}{1}}{{{2}{a}{{{{x}_{1}}}}}+{b}}}{\right)}}{x}+{e}}$$

$${y} = {{{\frac{{-}{x}}{{{2}{a}{{{{x}_{1}}}}}+{b}}}}+{e}}$$

Now, consider the area bounded between the two curves,
$${{A}_{B}} = {{\int_{{x}_{1}}^{{x}_{2}}}{\left[}{{\left(}{{{\frac{{-}{x}}{{{2}{a}{{{{x}_{1}}}}}+{b}}}}+{e}}{\right)} - {\left(}{{{a}{{x}^{2}}} + {{b}{x}} + {c}}{\right)}}{\right]}{dx}}$$

From here is where I get kind of stuck, because once I integrate and evaluate the limits of the integral I am going to need to find a way to minimize the area. However, this is tricky since (once the integral is evaluated) the area will be given as a function of two variables, ${{A}_{B}}{{\left(}{{{x}_{1}},{{x}_{2}}}{\right)}}$.

I'm guessing the next step from there would be applying the technique of Lagrange Multipliers to find the minimum area by extracting some restrictions on the values: ${{x}_{1}}$ and ${{x}_{2}}$. Is that right? Or is there something I am missing?

Remark
I did not like the way that I started the problem from the Standard Form of a Parabola that has symmetry with respect to the vertical axis, in other words a parabola as a ${f(x)}$. I feel that had I started from the General Equation of a Conic Section where for a parabola ${{{{B}^{2}} - {{4}{A}{C}}} = {0}}$ the approach would be more rigorous, since it is the most general way to represent a parabola. Any ideas on how to approach this problem that way?

Thanks,

-PFStudent