Look for the smallest and largest elements!

A simple but powerful trick to solve problems.

Problem-solving isn’t just about raw intelligence. A lot of it comes down to knowing the right techniques.

In this issue, I’ll discuss a fundamental technique that allows you to solve a wide variety of problems.

When a problem has a collection of elements, look for the smallest and largest ones.

Let’s see it in action.

A Problem

Let B and W be finite sets of black and white points in the plane, with the property that every line segment connecting two points of the same color contains a point of the other color. Prove that all the points must lie on a single line.

Take a moment to think about it. At first glance, you might try drawing diagrams or tackling it with casework. But that approach gets complicated.

Applying our technique

We proceed by contradiction: assume the points do not all lie on a single line. Then there must be at least one triangle formed by these points. Now, let’s use our technique—focus on the triangle with the smallest area.

In this triangle, two of its vertices must share the same color. But by the problem’s conditions, there must be a point of the opposite color inside the triangle. This creates a new, smaller triangle. This contradicts our assumption that we started with the smallest possible triangle.

That’s it! By focusing on the smallest element (in this case, the smallest triangle), we solved the problem immediately. It was so easy it felt like cheating.

(This problem is from Chapter 3 of Paul Zeitz’s The Art and Craft of Problem Solving.)

Your Turn

Try solving the following problem using the above technique:

Let f(x) be a polynomial with real coefficients of degree n such that f(x) is non-negative for all real numbers x. Define the polynomial

\(g(x) := f(x) + f'(x) + f''(x) + \dots + f^{(n)}(x).\)

Show that g(x) is non-negative for all real numbers x.

If you have a solution to the above challenge problems, submit it here for a chance to be featured in the next issue of this newsletter.

Hint for the problem

This problem is quite hard, so here is a hint if you get stuck. (No peeking unless you’re stuck!)

First show that g(x) assumes a minimum value. Assume for the sake of contradiction that this minimum value is strictly negative. Study the derivative of g at this point and see if you can get a contradiction.

Solution from last week

See here for the solution to last week’s problem. (Shoutout to Oğuzhan Kaşıkçı from Istanbul whose solution is being featured this week!)

Huge thanks to Rainer Nase (Germany), David Galarza (Bogotá), Fabio Skilnik (Brazil), Aritra (Maryland), Kayra Bolat (Istanbul), Oguzhan Kasikci (Istanbul), Olivier Massicot (Champaign, IL), Subhadeep Pal, (Bangalore India), Sayan Sinha Ray, jc (New York), B Sashi Kanth (Hyderabad, India), Monbikash Gayan (Pune), Nicolas Markossian (Lebanon), and Fabio Skilnik (Brazil) for submitting solutions to last week’s challenge problem.

Thanks for reading and happy learning! Until next time,

Adithya