Difference between revisions of "Without loss of generality"

(Remove vandalism: Undo revision 215816 by Marianasinta (talk))
(Tag: Undo)
 
(27 intermediate revisions by 15 users not shown)
Line 1: Line 1:
'''Without loss of generality''' is a term used in proofs to indicate that an assumption is being made that does not introduce new restrictions to the problem.  For example, in the proof of [[Schur's Inequality]], one can assume that <math>a \ge b \ge c</math> without loss of generality because the inequality is [[Symmetric property|symmetric]] in <math>a</math>, <math>b</math> and <math>c</math>.  Without loss of generality is often abbreviated '''WLOG''' or '''WOLOG'''. Be sure not to write WLOG when you mean "''with'' loss of generality"!
 
  
In simpler terms: WLOG means that it is ok to assume a value for a variable, or other such unknown, in order to solve the problem. This is often done in problems concerning ratios, or any other value that remains constant regardless of what is assumed
 
== Example Problems ==
 
=== Introductory Level ===
 
* [[2006_AMC_10B_Problems/Problem_17 | 2006 AMC 10B Problem 17]]
 
* [[2007_AMC_10A_Problems/Problem_19 | 2007 AMC 10A Problem 19]]
 
* [[2006_AMC_12A_Problems/Problem_20 | 2006 AMC 12A Problem 20]]
 
* [[2012_AMC_10A_Problems/Problem_23 | 2012 AMC 12A Problem 23]]
 
[[Category:Definition]]
 
  
=== Advanced Level ===
+
 
 +
==Definition==
 +
 
 +
Without loss of generality, often abbreviated to WLOG, is a frequently used expression in math. The term is used to indicate that the following proof emphasizes on a particular case, but doesn’t affect the validity of the proof in general.
 +
 
 +
Be careful when using WLOG in a proof. By using it, you must be certain that your statement actually DOES work for all cases!
 +
If you use WLOG in a proof and the statement is not necessarily true, points will get marked off. For example, you can't say "WLOG, let <math>a > b > c</math>." if <math>a</math> could equal <math>b</math> or <math>c</math>.
 +
 
 +
==Example==
 +
 
 +
* If three objects are each painted either red or blue, then there must be at least two objects of the same color.
 +
<math>\textbf{Proof}</math>:
 +
 
 +
Assume, '''without loss of generality''', that the first object is red. If either of the other two objects is red, then we are finished; if not, then the other two objects must both be blue and we are still finished.
 +
 
 +
The above argument works because the exact same reasoning could be applied if the first object is blue. As a result, the use of "without loss of generality" is valid in this case.
 +
(Note that this can also be proved by the [[Pigeonhole Principle]])
 +
 
 +
== Problems using WLOG ==
 
* [[2017_USAJMO_Problems/Problem_3 | 2017 USAJMO Problem 3]]
 
* [[2017_USAJMO_Problems/Problem_3 | 2017 USAJMO Problem 3]]
 +
* [[2016_AMC_12A_Problems/Problem_17 | 2016 AMC 12A Problem 17]] (See Solution 2)
 +
* [[2012_AMC_10A_Problems/Problem 23 | 2012 AMC 10A Problem 23]]
 +
* [[2018_AMC_12B_Problems/Problem 18 | 2018 AMC 10B Problem 18]]
 +
* [[2005_Austrian_Mathematical_Olympiad_Final_Round-Part 1/Problem 5]]
 +
 +
== Read more ==
 +
 +
https://en.wikipedia.org/wiki/Without_loss_of_generality
 +
 +
https://www.cl.cam.ac.uk/~jrh13/papers/wlog.pdf
 +
 +
 +
{{stub}}

Latest revision as of 15:30, 22 February 2024


Definition

Without loss of generality, often abbreviated to WLOG, is a frequently used expression in math. The term is used to indicate that the following proof emphasizes on a particular case, but doesn’t affect the validity of the proof in general.

Be careful when using WLOG in a proof. By using it, you must be certain that your statement actually DOES work for all cases! If you use WLOG in a proof and the statement is not necessarily true, points will get marked off. For example, you can't say "WLOG, let $a > b > c$." if $a$ could equal $b$ or $c$.

Example

  • If three objects are each painted either red or blue, then there must be at least two objects of the same color.

$\textbf{Proof}$:

Assume, without loss of generality, that the first object is red. If either of the other two objects is red, then we are finished; if not, then the other two objects must both be blue and we are still finished.

The above argument works because the exact same reasoning could be applied if the first object is blue. As a result, the use of "without loss of generality" is valid in this case. (Note that this can also be proved by the Pigeonhole Principle)

Problems using WLOG

Read more

https://en.wikipedia.org/wiki/Without_loss_of_generality

https://www.cl.cam.ac.uk/~jrh13/papers/wlog.pdf


This article is a stub. Help us out by expanding it.