Without Loss of Generality

Without loss of generality - WLOG, for short - is a frequent stratagem in problem solving. It is incredibly powerful, although, at first sight, often appears innocuous. The essence of WLOG is in making a random selection among a number of available ones for the reason of all possible variants being equipotent, i.e., leading to exactly same procedure and result. This is akeen to the arguments by symmetry or analogy, but, perhaps, made more explicitly.

An almost classical example appeared in The Mathematical Gazette (v 98, n 543, Nov 2014, p 487):

Assume $a,b,c\ge 0.$ Prove that

$\begin{align} (b+c-a)(b-c)^{2}+(c+&a-b)(c-a)^{2}\\ &+(a+b-c)(a-b)^{2}\ge 0. \end{align}$

Proof

To avoid repetitions, denote the left-hand side of the inequality $f(a,b,c).$ Assume, without loss of generality, that $a\le b\le c.$ (Since the set $\mathbb{R}$ of all real number is totally ordered, the three numbers are bound to come in a certain order. For specific numbers the order may not be known a priori; but it does not matter: we can get one ordering from another by simply renaming the numbers.)

Assuming $a\le b\le c$ leads to a one-step solution. Note that under this assumption $(c-a)^{2}\ge (a-b)^{2}$ which implies

$f(a,b,c)\ge (b+c-a)(b-c)^{2}+2a(a-b)^{2}\ge 0.$

A similar assumption works for another problem:

Find all right triangles all of whose side lengths are Fibonacci numbers.

Solution

There are no such triangle. Indeed, take any three Fibonacci numbers, $F_m,$ $F_n,$ $F_p.$ Assume without loss of generality that $m \lt n \lt p.$ Then

$\begin{align} F_m + F_n &\le F_{n-1} + F_n\\ &= F_{n+1}\\ &\le F_p, \end{align}$

But the lengths of the sides of a triangle should satisfy the triangle inequality: $F_{m}+F_{n}\gt F_p.$

Points in the plane are each colored with one of two colors: red or blue. Prove that, for a given distance $d,$ there always exist two points of the same color at the distance $d$ from each other.

Solution

Consider the vertices of an arbitrary equilateral triangle $ABC$ of side length $d.$ Without loss of generality, we may assume that one of them, say, $A$ is red. Then one of the two: either both $B$ and $C$ are blue (and solve the problem), or one of them is red and, thus, pairs up with $A$ for a solution.

Here are additional examples; many more could be found by searching this site.

Occasionally, the WLOG reasoning may not be applicable, appearances notwithstanding. Here's one example.

|Contact| |Front page| |Contents| |What is What|

Copyright © 1996-2018 Alexander Bogomolny

72096396