https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Mag1c&feedformat=atom AoPS Wiki - User contributions [en] 2020-11-28T14:56:11Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=File:Temporary.png&diff=132985 File:Temporary.png 2020-09-02T00:31:15Z <p>Mag1c: </p> <hr /> <div></div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Iff&diff=130060 Iff 2020-07-31T22:21:15Z <p>Mag1c: Gödel</p> <hr /> <div>'''Iff''' is an abbreviation for the phrase &quot;if and only if.&quot;<br /> <br /> In mathematical notation, &quot;iff&quot; is expressed as &lt;math&gt;\iff&lt;/math&gt;.<br /> <br /> It is also known as a [[conditional|biconditional]] statement.<br /> <br /> An iff statement &lt;math&gt;p\iff q&lt;/math&gt; means &lt;math&gt;p\implies q&lt;/math&gt; &lt;b&gt;and&lt;/b&gt; &lt;math&gt;q\implies p&lt;/math&gt; at the same time.<br /> <br /> ==Examples==<br /> <br /> In order to prove a statement of the form &quot;&lt;math&gt;p&lt;/math&gt; iff &lt;math&gt;q&lt;/math&gt;,&quot; it is necessary to prove two distinct implications: <br /> <br /> * if &lt;math&gt;p&lt;/math&gt; then &lt;math&gt;q&lt;/math&gt;<br /> * if &lt;math&gt;q&lt;/math&gt; then &lt;math&gt;p&lt;/math&gt;<br /> <br /> ===Results===<br /> [https://artofproblemsolving.com/wiki/index.php/Godel%27s_First_Incompleteness_Theoremm Gödel's Incompleteness Theorem]<br /> <br /> ===Videos===<br /> [https://www.youtube.com/embed/MckXBKafPfw Mathematical Logic] (&quot;I am in process of making a smoother version of this&quot; -themathematicianisin).<br /> <br /> ==See Also==<br /> * [[Logic]]<br /> <br /> {{stub}}<br /> <br /> [[Category:Definition]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Godel%27s_First_Incompleteness_Theorem&diff=130059 Godel's First Incompleteness Theorem 2020-07-31T22:17:10Z <p>Mag1c: or trivial</p> <hr /> <div>Gödel's First Incompleteness Theorem is a [[theorem]] that asserts that any axiomatic theory &lt;math&gt;F&lt;/math&gt;, which can prove anything that [[Peano arithmetic]] can, is either inconsistent (i.e. it can both prove and disprove any given statement) or incomplete (i.e. there is a statement that it cannot prove nor disprove using the axioms only), or trivial (like &lt;math&gt;0=1=\infty&lt;/math&gt;).<br /> <br /> The theorem is closely related to both [[Godel's Completeness Theorem]] (that a theory is consistent iff it has a model) and [[Godel's Second Incompleteness Theorem]] (that a consistent theory cannot prove its own consistency).<br /> <br /> == Proof ==<br /> <br /> Firstly, suppose that &lt;math&gt;F&lt;/math&gt; is inconsistent; i.e. it proves a [[contradiction]]. Then, by &lt;i&gt;ex falso quodlibet&lt;/i&gt;, we can use that contradiction to prove any statement.<br /> <br /> Now suppose that &lt;math&gt;F&lt;/math&gt; is consistent (i.e. it can prove any statement using only its axioms). Then there is a [[Turing machine]] &lt;math&gt;T&lt;/math&gt; that, given (an encoding of) some Turing machine &lt;math&gt;T'&lt;/math&gt; and some input &lt;math&gt;x&lt;/math&gt;, (effectively) searches through every valid proof or disproof in &lt;math&gt;F&lt;/math&gt;, of which there are only [[countable|countably many]], until it finds a proof or disproof of (&lt;math&gt;F&lt;/math&gt;'s version of) the statement &quot;&lt;math&gt;T'&lt;/math&gt; eventually halts on input &lt;math&gt;x&lt;/math&gt;&quot;. But we know that, since the [[halting problem]] is undecidable by Turing machines, there is some valid input &lt;math&gt;(T^*, x^*)&lt;/math&gt; on which &lt;math&gt;T'&lt;/math&gt; cannot halt, and so the statement &quot;&lt;math&gt;T^*&lt;/math&gt; eventually halts on input &lt;math&gt;x^*&lt;/math&gt;&quot; is unprovable in &lt;math&gt;F&lt;/math&gt;, and we are done.<br /> <br /> == See also ==<br /> *[[Turing machine]]<br /> *[[Proof]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Iff&diff=130055 Iff 2020-07-31T21:56:00Z <p>Mag1c: /* Videos */ quotes</p> <hr /> <div>'''Iff''' is an abbreviation for the phrase &quot;if and only if.&quot;<br /> <br /> In mathematical notation, &quot;iff&quot; is expressed as &lt;math&gt;\iff&lt;/math&gt;.<br /> <br /> It is also known as a [[conditional|biconditional]] statement.<br /> <br /> An iff statement &lt;math&gt;p\iff q&lt;/math&gt; means &lt;math&gt;p\implies q&lt;/math&gt; &lt;b&gt;and&lt;/b&gt; &lt;math&gt;q\implies p&lt;/math&gt; at the same time.<br /> <br /> ==Example==<br /> In order to prove a statement of the form &quot;&lt;math&gt;p&lt;/math&gt; iff &lt;math&gt;q&lt;/math&gt;,&quot; it is necessary to prove two distinct implications: <br /> <br /> * if &lt;math&gt;p&lt;/math&gt; then &lt;math&gt;q&lt;/math&gt;<br /> * if &lt;math&gt;q&lt;/math&gt; then &lt;math&gt;p&lt;/math&gt;<br /> <br /> ===Videos===<br /> [https://www.youtube.com/embed/MckXBKafPfw Mathematical Logic] (&quot;I am in process of making a smoother version of this&quot; -themathematicianisin).<br /> <br /> ==See Also==<br /> * [[Logic]]<br /> <br /> {{stub}}<br /> <br /> [[Category:Definition]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Iff&diff=130053 Iff 2020-07-31T21:55:06Z <p>Mag1c: /* Videos */ I am in process of making a smoother version of this -themathematicianisin</p> <hr /> <div>'''Iff''' is an abbreviation for the phrase &quot;if and only if.&quot;<br /> <br /> In mathematical notation, &quot;iff&quot; is expressed as &lt;math&gt;\iff&lt;/math&gt;.<br /> <br /> It is also known as a [[conditional|biconditional]] statement.<br /> <br /> An iff statement &lt;math&gt;p\iff q&lt;/math&gt; means &lt;math&gt;p\implies q&lt;/math&gt; &lt;b&gt;and&lt;/b&gt; &lt;math&gt;q\implies p&lt;/math&gt; at the same time.<br /> <br /> ==Example==<br /> In order to prove a statement of the form &quot;&lt;math&gt;p&lt;/math&gt; iff &lt;math&gt;q&lt;/math&gt;,&quot; it is necessary to prove two distinct implications: <br /> <br /> * if &lt;math&gt;p&lt;/math&gt; then &lt;math&gt;q&lt;/math&gt;<br /> * if &lt;math&gt;q&lt;/math&gt; then &lt;math&gt;p&lt;/math&gt;<br /> <br /> ===Videos===<br /> [https://www.youtube.com/embed/MckXBKafPfw Mathematical Logic] (I am in process of making a smoother version of this -themathematicianisin).<br /> <br /> ==See Also==<br /> * [[Logic]]<br /> <br /> {{stub}}<br /> <br /> [[Category:Definition]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Iff&diff=130040 Iff 2020-07-31T21:45:37Z <p>Mag1c: </p> <hr /> <div>'''Iff''' is an abbreviation for the phrase &quot;if and only if.&quot;<br /> <br /> In mathematical notation, &quot;iff&quot; is expressed as &lt;math&gt;\iff&lt;/math&gt;.<br /> <br /> It is also known as a [[conditional|biconditional]] statement.<br /> <br /> An iff statement &lt;math&gt;p\iff q&lt;/math&gt; means &lt;math&gt;p\implies q&lt;/math&gt; &lt;b&gt;and&lt;/b&gt; &lt;math&gt;q\implies p&lt;/math&gt; at the same time.<br /> <br /> ==Example==<br /> In order to prove a statement of the form &quot;&lt;math&gt;p&lt;/math&gt; iff &lt;math&gt;q&lt;/math&gt;,&quot; it is necessary to prove two distinct implications: <br /> <br /> * if &lt;math&gt;p&lt;/math&gt; then &lt;math&gt;q&lt;/math&gt;<br /> * if &lt;math&gt;q&lt;/math&gt; then &lt;math&gt;p&lt;/math&gt;<br /> <br /> ===Videos===<br /> [https://www.youtube.com/embed/MckXBKafPfw Mathematical Logic]<br /> <br /> ==See Also==<br /> * [[Logic]]<br /> <br /> {{stub}}<br /> <br /> [[Category:Definition]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Logic&diff=130038 Logic 2020-07-31T21:22:01Z <p>Mag1c: /* Implication, Conditional */ wording</p> <hr /> <div>'''Logic''' is the systematic use of symbolic and mathematical techniques to determine the forms of valid deductive or inductive argument. <br /> <br /> ==Statements==<br /> A statement is either true or false, but it will never be both or neither. An example of a statement is &quot;A duck is a bird&quot; which is true. Another example is &quot;A pencil does not exist&quot; which is false.<br /> <br /> ===Conditional=== <br /> If &lt;math&gt;P&lt;/math&gt; then &lt;math&gt;Q&lt;/math&gt;. For example, &quot;If it is a duck then it is a bird.&quot;<br /> <br /> ===Inverse=== <br /> The inverse of the conditional statement is: If not &lt;math&gt;P&lt;/math&gt; then not &lt;math&gt;Q&lt;/math&gt;.<br /> <br /> ===Converse=== <br /> The converse of the conditional statement is: If &lt;math&gt;Q&lt;/math&gt; then &lt;math&gt;P&lt;/math&gt;. <br /> <br /> ===Contrapositive=== <br /> The contrapositive of the conditional statement is: If not &lt;math&gt;Q&lt;/math&gt; then not &lt;math&gt;P&lt;/math&gt;.<br /> <br /> &lt;br /&gt;<br /> The conditional is equivalent to the contrapositive. The inverse is equivalent to the converse. When both the conditional and the converse are true at the same time, this is equivalent to an [[Iff]] statement.<br /> <br /> ==Logical Notations==<br /> {{main|Logical notation}}<br /> <br /> A '''Logical notation''' is a special syntax that is shorthand for logical statements. <br /> <br /> ===Negations===<br /> The negation of &lt;math&gt;p&lt;/math&gt;, denoted by &lt;math&gt;\neg p&lt;/math&gt;, is the statement that is true when &lt;math&gt;p&lt;/math&gt; is false and is false when &lt;math&gt;p&lt;/math&gt; is true. This means simply &quot;it is not the case that &lt;math&gt;p&lt;/math&gt;.&quot;<br /> <br /> ===Conjunction===<br /> The conjunction of two statements basically means &quot;&lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt;&quot; and is denoted by &lt;math&gt;p \land q&lt;/math&gt;.<br /> <br /> ===Disjunction===<br /> The disjunction of two statements basically means &quot;&lt;math&gt;p&lt;/math&gt; or &lt;math&gt;q&lt;/math&gt;&quot; and is denoted by &lt;math&gt;p \vee q&lt;/math&gt;.<br /> <br /> ===Implication, Conditional===<br /> The statement &quot;If &lt;math&gt;p&lt;/math&gt; then &lt;math&gt;q&lt;/math&gt;&quot; is denoted by &lt;math&gt;p\implies q&lt;/math&gt;. For example, &lt;math&gt;x+3=5\implies x=2&lt;/math&gt; means &quot;If &lt;math&gt;x+3=5&lt;/math&gt; then &lt;math&gt;x=2&lt;/math&gt;.&quot;<br /> <br /> ===Converse===<br /> The converse of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;q \implies p&lt;/math&gt;.<br /> <br /> ===Inverse===<br /> The inverse of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;\neg p \implies \neg q&lt;/math&gt;.<br /> <br /> ===Contrapositive===<br /> The contrapositive of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;\neg q \implies \neg p&lt;/math&gt;. These statements are logically equivalent.<br /> <br /> ==Truth Tables==<br /> A truth table is the list of all possible values of a compound statement.<br /> <br /> ==Quantifiers==<br /> There are two types of quantifiers: A universal Quantifier: &quot;for all&quot; and an existential Quantifier: &quot;there exists&quot;. A universal quantifier is denoted by &lt;math&gt;\forall&lt;/math&gt; and an existential quantifier is denoted by &lt;math&gt;\exists&lt;/math&gt;.<br /> <br /> ==See Also==<br /> *[[Dual]]<br /> [[Category:Definition]]<br /> [[Category:Logic]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Logic&diff=130037 Logic 2020-07-31T21:19:26Z <p>Mag1c: grammar, notation of inverse and conditional</p> <hr /> <div>'''Logic''' is the systematic use of symbolic and mathematical techniques to determine the forms of valid deductive or inductive argument. <br /> <br /> ==Statements==<br /> A statement is either true or false, but it will never be both or neither. An example of a statement is &quot;A duck is a bird&quot; which is true. Another example is &quot;A pencil does not exist&quot; which is false.<br /> <br /> ===Conditional=== <br /> If &lt;math&gt;P&lt;/math&gt; then &lt;math&gt;Q&lt;/math&gt;. For example, &quot;If it is a duck then it is a bird.&quot;<br /> <br /> ===Inverse=== <br /> The inverse of the conditional statement is: If not &lt;math&gt;P&lt;/math&gt; then not &lt;math&gt;Q&lt;/math&gt;.<br /> <br /> ===Converse=== <br /> The converse of the conditional statement is: If &lt;math&gt;Q&lt;/math&gt; then &lt;math&gt;P&lt;/math&gt;. <br /> <br /> ===Contrapositive=== <br /> The contrapositive of the conditional statement is: If not &lt;math&gt;Q&lt;/math&gt; then not &lt;math&gt;P&lt;/math&gt;.<br /> <br /> &lt;br /&gt;<br /> The conditional is equivalent to the contrapositive. The inverse is equivalent to the converse. When both the conditional and the converse are true at the same time, this is equivalent to an [[Iff]] statement.<br /> <br /> ==Logical Notations==<br /> {{main|Logical notation}}<br /> <br /> A '''Logical notation''' is a special syntax that is shorthand for logical statements. <br /> <br /> ===Negations===<br /> The negation of &lt;math&gt;p&lt;/math&gt;, denoted by &lt;math&gt;\neg p&lt;/math&gt;, is the statement that is true when &lt;math&gt;p&lt;/math&gt; is false and is false when &lt;math&gt;p&lt;/math&gt; is true. This means simply &quot;it is not the case that &lt;math&gt;p&lt;/math&gt;.&quot;<br /> <br /> ===Conjunction===<br /> The conjunction of two statements basically means &quot;&lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt;&quot; and is denoted by &lt;math&gt;p \land q&lt;/math&gt;.<br /> <br /> ===Disjunction===<br /> The disjunction of two statements basically means &quot;&lt;math&gt;p&lt;/math&gt; or &lt;math&gt;q&lt;/math&gt;&quot; and is denoted by &lt;math&gt;p \vee q&lt;/math&gt;.<br /> <br /> ===Implication, Conditional===<br /> This operation is given by the statement &quot;If &lt;math&gt;p&lt;/math&gt;, then &lt;math&gt;q&lt;/math&gt;&quot;. It is denoted by &lt;math&gt;p\implies q&lt;/math&gt;. An example is &lt;math&gt;x+3=5\implies x=2&lt;/math&gt; which means &quot;If &lt;math&gt;x+3=5&lt;/math&gt; then &lt;math&gt;x=2&lt;/math&gt;.&quot; <br /> <br /> ===Converse===<br /> The converse of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;q \implies p&lt;/math&gt;.<br /> <br /> ===Inverse===<br /> The inverse of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;\neg p \implies \neg q&lt;/math&gt;.<br /> <br /> ===Contrapositive===<br /> The contrapositive of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;\neg q \implies \neg p&lt;/math&gt;. These statements are logically equivalent.<br /> <br /> ==Truth Tables==<br /> A truth table is the list of all possible values of a compound statement.<br /> <br /> ==Quantifiers==<br /> There are two types of quantifiers: A universal Quantifier: &quot;for all&quot; and an existential Quantifier: &quot;there exists&quot;. A universal quantifier is denoted by &lt;math&gt;\forall&lt;/math&gt; and an existential quantifier is denoted by &lt;math&gt;\exists&lt;/math&gt;.<br /> <br /> ==See Also==<br /> *[[Dual]]<br /> [[Category:Definition]]<br /> [[Category:Logic]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Logic&diff=130036 Logic 2020-07-31T21:15:35Z <p>Mag1c: /* Conditional */</p> <hr /> <div>'''Logic''' is the systematic use of symbolic and mathematical techniques to determine the forms of valid deductive or inductive argument. <br /> <br /> ==Statements==<br /> A statement is either true or false, but it will never be both or neither. An example of statement can be &quot;A duck is a bird.&quot; which is true. Another example is &quot;A pencil does not exist&quot; which is false.<br /> <br /> ===Conditional=== <br /> If &lt;math&gt;P&lt;/math&gt; then &lt;math&gt;Q&lt;/math&gt;. For example, &quot;If it is a duck then it is a bird.&quot;<br /> <br /> ===Inverse=== <br /> The inverse of the conditional statement is: If not &lt;math&gt;P&lt;/math&gt; then not &lt;math&gt;Q&lt;/math&gt;.<br /> <br /> ===Converse=== <br /> The converse of the conditional statement is: If &lt;math&gt;Q&lt;/math&gt; then &lt;math&gt;P&lt;/math&gt;. <br /> <br /> ===Contrapositive=== <br /> The contrapositive of the conditional statement is: If not &lt;math&gt;Q&lt;/math&gt; then not &lt;math&gt;P&lt;/math&gt;.<br /> <br /> &lt;br /&gt;<br /> The conditional is equivalent to the contrapositive. The inverse is equivalent to the converse. When both the conditional and the converse are true at the same time, this is equivalent to an [[Iff]] statement.<br /> <br /> ==Logical Notations==<br /> {{main|Logical notation}}<br /> <br /> A '''Logical notation''' is a special syntax that is shorthand for logical statements. <br /> <br /> ===Negations===<br /> The negation of &lt;math&gt;p&lt;/math&gt;, denoted by &lt;math&gt;\neg p&lt;/math&gt;, is the statement that is true when &lt;math&gt;p&lt;/math&gt; is false and is false when &lt;math&gt;p&lt;/math&gt; is true. This means simply &quot;it is not the case that &lt;math&gt;p&lt;/math&gt;.&quot;<br /> <br /> ===Conjunction===<br /> The conjunction of two statements basically means &quot;&lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt;&quot; and is denoted by &lt;math&gt;p \land q&lt;/math&gt;.<br /> <br /> ===Disjunction===<br /> The disjunction of two statements basically means &quot;&lt;math&gt;p&lt;/math&gt; or &lt;math&gt;q&lt;/math&gt;&quot; and is denoted by &lt;math&gt;p \vee q&lt;/math&gt;.<br /> <br /> ===Implication===<br /> This operation is given by the statement &quot;If &lt;math&gt;p&lt;/math&gt;, then &lt;math&gt;q&lt;/math&gt;&quot;. It is denoted by &lt;math&gt;p\implies q&lt;/math&gt;. An example is &quot;if &lt;math&gt;x+3=5&lt;/math&gt;, then &lt;math&gt;x=2&lt;/math&gt;.<br /> <br /> ===Converse===<br /> The converse of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;q \implies p&lt;/math&gt;.<br /> <br /> ===Contrapositive===<br /> The contrapositive of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;\neg q \implies \neg p&lt;/math&gt;. These statements are logically equivalent.<br /> <br /> ==Truth Tables==<br /> A truth table is the list of all possible values of a compound statement.<br /> <br /> ==Quantifiers==<br /> There are two types of quantifiers: A universal Quantifier: &quot;for all&quot; and an existential Quantifier: &quot;there exists&quot;. A universal quantifier is denoted by &lt;math&gt;\forall&lt;/math&gt; and an existential quantifier is denoted by &lt;math&gt;\exists&lt;/math&gt;.<br /> <br /> ==See Also==<br /> *[[Dual]]<br /> [[Category:Definition]]<br /> [[Category:Logic]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Logic&diff=130035 Logic 2020-07-31T21:11:41Z <p>Mag1c: /* Statements */ spacing</p> <hr /> <div>'''Logic''' is the systematic use of symbolic and mathematical techniques to determine the forms of valid deductive or inductive argument. <br /> <br /> ==Statements==<br /> A statement is either true or false, but it will never be both or neither. An example of statement can be &quot;A duck is a bird.&quot; which is true. Another example is &quot;A pencil does not exist&quot; which is false.<br /> <br /> ===Conditional=== <br /> If &lt;math&gt;P&lt;/math&gt; then &lt;math&gt;Q&lt;/math&gt;.<br /> <br /> ===Inverse=== <br /> The inverse of the conditional statement is: If not &lt;math&gt;P&lt;/math&gt; then not &lt;math&gt;Q&lt;/math&gt;.<br /> <br /> ===Converse=== <br /> The converse of the conditional statement is: If &lt;math&gt;Q&lt;/math&gt; then &lt;math&gt;P&lt;/math&gt;. <br /> <br /> ===Contrapositive=== <br /> The contrapositive of the conditional statement is: If not &lt;math&gt;Q&lt;/math&gt; then not &lt;math&gt;P&lt;/math&gt;.<br /> <br /> &lt;br /&gt;<br /> The conditional is equivalent to the contrapositive. The inverse is equivalent to the converse. When both the conditional and the converse are true at the same time, this is equivalent to an [[Iff]] statement.<br /> <br /> ==Logical Notations==<br /> {{main|Logical notation}}<br /> <br /> A '''Logical notation''' is a special syntax that is shorthand for logical statements. <br /> <br /> ===Negations===<br /> The negation of &lt;math&gt;p&lt;/math&gt;, denoted by &lt;math&gt;\neg p&lt;/math&gt;, is the statement that is true when &lt;math&gt;p&lt;/math&gt; is false and is false when &lt;math&gt;p&lt;/math&gt; is true. This means simply &quot;it is not the case that &lt;math&gt;p&lt;/math&gt;.&quot;<br /> <br /> ===Conjunction===<br /> The conjunction of two statements basically means &quot;&lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt;&quot; and is denoted by &lt;math&gt;p \land q&lt;/math&gt;.<br /> <br /> ===Disjunction===<br /> The disjunction of two statements basically means &quot;&lt;math&gt;p&lt;/math&gt; or &lt;math&gt;q&lt;/math&gt;&quot; and is denoted by &lt;math&gt;p \vee q&lt;/math&gt;.<br /> <br /> ===Implication===<br /> This operation is given by the statement &quot;If &lt;math&gt;p&lt;/math&gt;, then &lt;math&gt;q&lt;/math&gt;&quot;. It is denoted by &lt;math&gt;p\implies q&lt;/math&gt;. An example is &quot;if &lt;math&gt;x+3=5&lt;/math&gt;, then &lt;math&gt;x=2&lt;/math&gt;.<br /> <br /> ===Converse===<br /> The converse of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;q \implies p&lt;/math&gt;.<br /> <br /> ===Contrapositive===<br /> The contrapositive of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;\neg q \implies \neg p&lt;/math&gt;. These statements are logically equivalent.<br /> <br /> ==Truth Tables==<br /> A truth table is the list of all possible values of a compound statement.<br /> <br /> ==Quantifiers==<br /> There are two types of quantifiers: A universal Quantifier: &quot;for all&quot; and an existential Quantifier: &quot;there exists&quot;. A universal quantifier is denoted by &lt;math&gt;\forall&lt;/math&gt; and an existential quantifier is denoted by &lt;math&gt;\exists&lt;/math&gt;.<br /> <br /> ==See Also==<br /> *[[Dual]]<br /> [[Category:Definition]]<br /> [[Category:Logic]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Logic&diff=130033 Logic 2020-07-31T21:06:55Z <p>Mag1c: /* Statements */ conditional inverse converse contrapositive</p> <hr /> <div>'''Logic''' is the systematic use of symbolic and mathematical techniques to determine the forms of valid deductive or inductive argument. <br /> <br /> ==Statements==<br /> A statement is either true or false, but it will never be both or neither. An example of statement can be &quot;A duck is a bird.&quot; which is true. Another example is &quot;A pencil does not exist&quot; which is false.<br /> <br /> ===Conditional:=== If &lt;math&gt;P&lt;/math&gt; then &lt;math&gt;Q&lt;/math&gt;.<br /> <br /> ===Inverse:=== If not &lt;math&gt;P&lt;/math&gt; then not &lt;math&gt;Q&lt;/math&gt;.<br /> <br /> ===Converse:=== If &lt;math&gt;Q&lt;/math&gt; then &lt;math&gt;P&lt;/math&gt;. <br /> <br /> ===Contrapositive:=== If not &lt;math&gt;Q&lt;/math&gt; then not &lt;math&gt;P&lt;/math&gt;.<br /> <br /> &lt;br /&gt;<br /> The conditional is equivalent to the contrapositive. The inverse is equivalent to the converse. When both the conditional and the converse are true at the same time, this is equivalent to an [[Iff]] statement.<br /> <br /> ==Logical Notations==<br /> {{main|Logical notation}}<br /> <br /> A '''Logical notation''' is a special syntax that is shorthand for logical statements. <br /> <br /> ===Negations===<br /> The negation of &lt;math&gt;p&lt;/math&gt;, denoted by &lt;math&gt;\neg p&lt;/math&gt;, is the statement that is true when &lt;math&gt;p&lt;/math&gt; is false and is false when &lt;math&gt;p&lt;/math&gt; is true. This means simply &quot;it is not the case that &lt;math&gt;p&lt;/math&gt;.&quot;<br /> <br /> ===Conjunction===<br /> The conjunction of two statements basically means &quot;&lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt;&quot; and is denoted by &lt;math&gt;p \land q&lt;/math&gt;.<br /> <br /> ===Disjunction===<br /> The disjunction of two statements basically means &quot;&lt;math&gt;p&lt;/math&gt; or &lt;math&gt;q&lt;/math&gt;&quot; and is denoted by &lt;math&gt;p \vee q&lt;/math&gt;.<br /> <br /> ===Implication===<br /> This operation is given by the statement &quot;If &lt;math&gt;p&lt;/math&gt;, then &lt;math&gt;q&lt;/math&gt;&quot;. It is denoted by &lt;math&gt;p\implies q&lt;/math&gt;. An example is &quot;if &lt;math&gt;x+3=5&lt;/math&gt;, then &lt;math&gt;x=2&lt;/math&gt;.<br /> <br /> ===Converse===<br /> The converse of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;q \implies p&lt;/math&gt;.<br /> <br /> ===Contrapositive===<br /> The contrapositive of the statement &lt;math&gt;p \implies q&lt;/math&gt; is &lt;math&gt;\neg q \implies \neg p&lt;/math&gt;. These statements are logically equivalent.<br /> <br /> ==Truth Tables==<br /> A truth table is the list of all possible values of a compound statement.<br /> <br /> ==Quantifiers==<br /> There are two types of quantifiers: A universal Quantifier: &quot;for all&quot; and an existential Quantifier: &quot;there exists&quot;. A universal quantifier is denoted by &lt;math&gt;\forall&lt;/math&gt; and an existential quantifier is denoted by &lt;math&gt;\exists&lt;/math&gt;.<br /> <br /> ==See Also==<br /> *[[Dual]]<br /> [[Category:Definition]]<br /> [[Category:Logic]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Angle_bisector&diff=127332 Angle bisector 2020-07-03T03:50:38Z <p>Mag1c: </p> <hr /> <div>{{WotWAnnounce|week=June 6-12}}<br /> <br /> For an [[angle]] &lt;math&gt;\angle BAC&lt;/math&gt;, the (internal) angle bisector of &lt;math&gt;\angle BAC&lt;/math&gt; is the line from &lt;math&gt;A&lt;/math&gt; such that the angle between this line and &lt;math&gt;\overline{AB}&lt;/math&gt; is congruent to the angle between this line and &lt;math&gt;\overline{AC}&lt;/math&gt;:<br /> <br /> &lt;center&gt;[[Image:Anglebisector.png]]&lt;/center&gt;<br /> <br /> An [[angle]] &lt;math&gt;\angle BAC&lt;/math&gt; also has an external angle bisector, which bisects external angle &lt;math&gt;BAC&lt;/math&gt;: <br /> <br /> &lt;asy&gt;<br /> import markers;<br /> pair A,B,C,D,E,F;<br /> B=(0,0);<br /> C=(5,0);<br /> A=(4,2);<br /> D=(3,4);<br /> E=(10/3,0);<br /> F=rotate(-90,A)*(E);<br /> draw(A--B--C--cycle,blue);<br /> draw(C--D,blue);<br /> pen p=blue+0.15mm;<br /> draw(A--F,p);<br /> dot(A^^B^^C,red);<br /> label(&quot;$A$&quot;,A,NE);<br /> label(&quot;$B$&quot;,B,W);<br /> label(&quot;$C$&quot;,C,E);<br /> markangle(n=1,radius=20,D,A,F,green);<br /> markangle(n=1,radius=22,F,A,B,green);<br /> &lt;/asy&gt;<br /> <br /> The external angle is defined by &lt;math&gt;\angle A + \text{ external }\angle A = 180^\circ&lt;/math&gt;, and the two angle bisectors are perpendicular to each other. <br /> <br /> == Features of Angle Bisectors ==<br /> <br /> * The distances from a point on an angle bisector to both of its sides are equal.<br /> * The angle bisectors are the [[locus]] of points which are [[equidistant]] from the two sides of the angle.<br /> * A [[reflection]] about either angle bisector maps the two sides of the angle to each other.<br /> * In a triangle, the [[Angle Bisector Theorem]] gives the ratio in which the angle bisector cuts the opposite side.<br /> * In a triangle, the internal angle bisectors (which are [[cevian|cevians]]) all intersect at the [[incenter]] of the triangle. The internal angle bisector of one angle and the external angle bisectors of the other two angles all intersect at an [[excenter]] of the triangle.<br /> *A bisector of an angle can be [[Constructions|constructed]] using a compass and straightedge.<br /> <br /> {{asy image|&lt;asy&gt;<br /> size(300);<br /> import markers;<br /> pair excenter(pair A, pair B, pair C){<br /> pair X, Z;<br /> X=A+expi((angle(A-B)+angle(C-A))/2);<br /> Z=C+expi((angle(C-B)+angle(A-C))/2);<br /> return extension(X,A,Z,C);<br /> }<br /> pair X=(0,0), Y=(-10,0), Z=(-3,6);<br /> pair exX=excenter(Z,X,Y), exY=excenter(X,Y,Z), exZ=excenter(Y,Z,X);<br /> label(&quot;X&quot;,X,2*(1.5,-1));label(&quot;Y&quot;,Y,2*(-3,-1));label(&quot;Z&quot;,Z,(0.6,2));<br /> dot(X^^Y^^Z);<br /> draw(0.3*(X-Y)+X--Y+0.3*(Y-X));draw(0.3*(Y-Z)+Y--Z+0.3*(Z-Y));draw(0.3*(X-Z)+X--Z+0.3*(Z-X));<br /> draw(X+0.3*(X-exX)--exX,orange);draw(Y+0.3*(Y-exY)--exY,orange);draw(Z+0.3*(Z-exZ)--0.6*(exZ-Z)+Z,orange);<br /> draw(Y-0.5*(exX-Y)--Y+0.5*(exX-Y),green);draw(Z-0.5*(exX-Z)--Z+0.5*(exX-Z),green);draw(X-0.5*(exY-X)--X+0.5*(exY-X),green);<br /> pair I=extension(X,exX,Z,exZ);<br /> dot(&quot;I&quot;,I,(-1,2));<br /> draw(circle(I,length(I-foot(I,X,Y))),blue);<br /> markangle(n=1,3*(Z-X)+X,Z,exX,radius=22,marker(markinterval(stickframe(n=3),true)));<br /> markangle(n=1,exX,Z,Y,radius=20,marker(markinterval(stickframe(n=3),true)));<br /> markangle(n=1,3*(Y-Z)+Z,Y,exZ,radius=22,marker(markinterval(stickframe(n=2),true)));<br /> markangle(n=1,exZ,Y,X,radius=20,marker(markinterval(stickframe(n=2),true)));<br /> markangle(n=1,3*(X-Y)+Y,X,exY,radius=22,marker(markinterval(stickframe(n=1),true)));<br /> markangle(n=1,exY,X,Z,radius=20,marker(markinterval(stickframe(n=1),true)));<br /> <br /> markangle(n=3,I,Z,X,radius=20);<br /> markangle(n=3,Y,Z,I,radius=22);<br /> markangle(n=2,Z,X,I,radius=20);<br /> markangle(n=2,I,X,Y,radius=22);<br /> markangle(n=1,X,Y,I,radius=22);<br /> markangle(n=1,I,Y,Z,radius=20);<br /> &lt;/asy&gt;|center|Triangle &lt;math&gt;\triangle XYZ&lt;/math&gt; with [[incenter]] ''I'', [[incircle]] (blue), [[angle bisector]]s (orange), and [[angle bisector|external angle bisectors]] (green)}}<br /> <br /> ==See also==<br /> * [[Cevian]]<br /> * [[Geometry]]<br /> * [[Stewart's Theorem]]<br /> <br /> <br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Excircle&diff=127199 Excircle 2020-07-01T07:02:53Z <p>Mag1c: /* Properties */</p> <hr /> <div>An '''excircle''' is a [[circle]] [[Tangent line|tangent]] to the extensions of two sides of a [[triangle]] and the third side.<br /> <br /> {{asy image|&lt;asy&gt;<br /> defaultpen(fontsize(8));<br /> pair excenter(pair A, pair B, pair C){<br /> pair X, Z;<br /> X=A+expi((angle(A-B)+angle(C-A))/2);<br /> Z=C+expi((angle(C-B)+angle(A-C))/2);<br /> return extension(X,A,Z,C);<br /> }<br /> pair X=(0,0), Y=(10,0), Z=(3,6);<br /> pair exX=excenter(Z,X,Y), exY=excenter(X,Y,Z), exZ=excenter(Y,Z,X);<br /> draw(circle(exX,length(exX-foot(exX,Y,Z))));<br /> draw(circle(exY,length(exY-foot(exY,Z,X))));<br /> draw(circle(exZ,length(exZ-foot(exZ,X,Y))));<br /> draw((X-Y)+X--Y+1.5*(Y-X));draw((Y-Z)+Y--Z+(Z-Y));draw(2*(X-Z)+X--Z+2*(Z-X));<br /> label(&quot;X&quot;,X,(-1.5,-1));label(&quot;Y&quot;,Y,(2,-1));label(&quot;Z&quot;,Z,N);<br /> label(&quot;P&quot;,exX,NE);<br /> dot(X^^Y^^Z^^exX^^exY^^exZ);<br /> <br /> draw(exX--(xpart(exX),0),dashed);<br /> <br /> real slope1=(ypart(Z)-ypart(X))/(xpart(Z)-xpart(X));<br /> pair point1=exX+(1,-1/slope1);<br /> pair tangent1=extension(X,Z,point1,exX);<br /> draw(exX--tangent1,dashed);<br /> <br /> real slope2=(ypart(Y)-ypart(Z))/(xpart(Y)-xpart(Z));<br /> pair point2=exX+(1,-1/slope2);<br /> pair tangent2=extension(Y,Z,point2,exX);<br /> draw(exX--tangent2,dashed);<br /> <br /> markscalefactor=0.1;<br /> draw(rightanglemark(exX,tangent1,Z));<br /> draw(rightanglemark(exX,tangent2,Y));<br /> draw(rightanglemark(exX,(xpart(exX),0),(100,0)));<br /> &lt;/asy&gt;|right|Triangle &lt;math&gt;\triangle XYZ&lt;/math&gt; and its excircles.}}<br /> <br /> <br /> == Properties ==<br /> For any triangle, there are three unique excircles. This follows from the fact that there is one, if any, circle such that three given distinct lines are tangent to it. <br /> <br /> 1) Each excenter lies on the intersection of two [[angle bisector|external angle bisectors]].<br /> <br /> 2) The &lt;math&gt;A&lt;/math&gt;-excenter lies on the [[angle bisector]] of &lt;math&gt;\angle A&lt;/math&gt;.<br /> <br /> == Related Geometrical Objects ==<br /> *An exradius is a radius of an excircle of a triangle.<br /> *An excenter is the center of an excircle of a triangle.<br /> ==Related Formulas==<br /> If the circle is tangent to side &lt;math&gt;a&lt;/math&gt; of the triangle, the radius is &lt;math&gt;\frac{K}{s-a}&lt;/math&gt;, where &lt;math&gt;K&lt;/math&gt; is the triangle's area, and &lt;math&gt;s = \frac{a+b+c}{2}&lt;/math&gt; is the [[semiperimeter]].<br /> <br /> ==Problems==<br /> ===Introductory===<br /> *Let &lt;math&gt;E,F&lt;/math&gt; be the feet of the perpendiculars from the vertices &lt;math&gt;B,C&lt;/math&gt; of triangle &lt;math&gt;\triangle ABC&lt;/math&gt;. Let &lt;math&gt;O&lt;/math&gt; be the circumcenter &lt;math&gt;\triangle ABC&lt;/math&gt;. Prove that &lt;cmath&gt;OA \perp FE .&lt;/cmath&gt;<br /> (&lt;url&gt;https://artofproblemsolving.com/community/c4h45647 Source&lt;/url&gt;)<br /> <br /> ===Intermediate===<br /> *In triangle &lt;math&gt;ABC&lt;/math&gt;, let the &lt;math&gt;A&lt;/math&gt;-excircle touch &lt;math&gt;BC&lt;/math&gt; at &lt;math&gt;D&lt;/math&gt;. Let the &lt;math&gt;B&lt;/math&gt;-excircle of triangle &lt;math&gt;ABD&lt;/math&gt; touch &lt;math&gt;AD&lt;/math&gt; at &lt;math&gt;P&lt;/math&gt; and let the &lt;math&gt;C&lt;/math&gt;-excircle of triangle &lt;math&gt;ACD&lt;/math&gt; touch &lt;math&gt;AD&lt;/math&gt; at &lt;math&gt;Q&lt;/math&gt;. Is &lt;math&gt;\angle P\cong\angle Q&lt;/math&gt; true for all triangles &lt;math&gt;ABC&lt;/math&gt;? (&lt;url&gt;viewtopic.php?t=167688 Source&lt;/url&gt;)<br /> <br /> ===Olympiad===<br /> *Let &lt;math&gt;ABC&lt;/math&gt; be a triangle and let &lt;math&gt;\omega&lt;/math&gt; be its incircle. Denote by &lt;math&gt;D_1&lt;/math&gt; and &lt;math&gt;E_1&lt;/math&gt; the points where &lt;math&gt;\omega&lt;/math&gt; is tangent to sides &lt;math&gt;BC&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt;, respectively. Denote by &lt;math&gt;D_2&lt;/math&gt; and &lt;math&gt;E_2&lt;/math&gt; the points on sides &lt;math&gt;BC&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt;, respectively, such that &lt;math&gt;CD_2 = BD_1&lt;/math&gt; and &lt;math&gt;CE_2 = AE_1&lt;/math&gt;, and denote by &lt;math&gt;P&lt;/math&gt; the point of intersection of segments &lt;math&gt;AD_2&lt;/math&gt; and &lt;math&gt;BE_2&lt;/math&gt;. Circle &lt;math&gt;\omega&lt;/math&gt; intersects segment &lt;math&gt;AD_2&lt;/math&gt; at two points, the closer of which to the vertex &lt;math&gt;A&lt;/math&gt; is denoted by &lt;math&gt;Q&lt;/math&gt;. Prove that &lt;math&gt;AQ = D_2P&lt;/math&gt;. ([[2001 USAMO Problems/Problem 2|Source]])<br /> *Let &lt;math&gt;ABC&lt;/math&gt; be a triangle with circumcircle &lt;math&gt;\omega.&lt;/math&gt; Point &lt;math&gt;D&lt;/math&gt; lies on side &lt;math&gt;BC&lt;/math&gt; such that &lt;math&gt;\angle BAD = \angle CAD.&lt;/math&gt; Let &lt;math&gt;I_{A}&lt;/math&gt; denote the excenter of triangle &lt;math&gt;ABC&lt;/math&gt; opposite &lt;math&gt;A,&lt;/math&gt; and let &lt;math&gt;\omega_{A}&lt;/math&gt; denote the circle with &lt;math&gt;AI_{A}&lt;/math&gt; as its diameter. Circles &lt;math&gt;\omega&lt;/math&gt; and &lt;math&gt;\omega_{A}&lt;/math&gt; meet at &lt;math&gt;P&lt;/math&gt; other than &lt;math&gt;A.&lt;/math&gt; The circumcle of triangle &lt;math&gt;APD&lt;/math&gt; meet line &lt;math&gt;BC&lt;/math&gt; again at &lt;math&gt;Q\, (&lt;/math&gt;other than &lt;math&gt;D).&lt;/math&gt; Prove that &lt;math&gt;Q&lt;/math&gt; lies on the excircle of triangle &lt;math&gt;ABC&lt;/math&gt; opposite &lt;math&gt;A&lt;/math&gt;. (Source: Problem 13.2 - MOSP 2007)<br /> *Let &lt;math&gt;ABCD &lt;/math&gt; be a parallelogram. A variable line &lt;math&gt; \ell &lt;/math&gt; passing through the point &lt;math&gt;A &lt;/math&gt; intersects the rays &lt;math&gt;BC &lt;/math&gt; and &lt;math&gt;DC &lt;/math&gt; at points &lt;math&gt;X &lt;/math&gt; and &lt;math&gt;Y &lt;/math&gt;, respectively. Let &lt;math&gt;K &lt;/math&gt; and &lt;math&gt;L &lt;/math&gt; be the centres of the excircles of triangles &lt;math&gt;ABX &lt;/math&gt; and &lt;math&gt;ADY &lt;/math&gt;, touching the sides &lt;math&gt;BX &lt;/math&gt; and &lt;math&gt;DY &lt;/math&gt;, respectively. Prove that the size of angle &lt;math&gt;KCL &lt;/math&gt; does not depend on the choice of &lt;math&gt; \ell &lt;/math&gt;. ([[2005 IMO Shortlist Problems/G3|Source]])<br /> <br /> ==See also==<br /> *[[Incircle]]<br /> *[[Circumcircle]]<br /> [[Category:Definition]]<br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Angle_bisector&diff=127198 Angle bisector 2020-07-01T07:00:42Z <p>Mag1c: add external angle bisectors</p> <hr /> <div>{{WotWAnnounce|week=June 6-12}}<br /> <br /> For an [[angle]] &lt;math&gt;\angle ABC&lt;/math&gt;, the (internal) angle bisector of &lt;math&gt;\angle ABC&lt;/math&gt; is the line from B such that the angle between this line and &lt;math&gt;BC&lt;/math&gt; is congruent to the angle between this line and &lt;math&gt;AB&lt;/math&gt;:<br /> <br /> &lt;center&gt;[[Image:Anglebisector.png]]&lt;/center&gt;<br /> <br /> A given [[angle]] &lt;math&gt;\angle ABC&lt;/math&gt; also has an external angle bisector, which bisects external angle &lt;math&gt;ABC&lt;/math&gt;: <br /> <br /> &lt;asy&gt;<br /> import markers;<br /> pair A,B,C,D,E,F;<br /> B=(0,0);<br /> C=(5,0);<br /> A=(4,2);<br /> D=(3,4);<br /> E=(10/3,0);<br /> F=rotate(-90,A)*(E);<br /> draw(A--B--C--cycle,blue);<br /> draw(C--D,blue);<br /> pen p=blue+0.15mm;<br /> draw(A--F,p);<br /> dot(A^^B^^C,red);<br /> label(&quot;$A$&quot;,A,NE);<br /> label(&quot;$B$&quot;,B,W);<br /> label(&quot;$C$&quot;,C,E);<br /> markangle(n=1,radius=20,D,A,F,green);<br /> markangle(n=1,radius=22,F,A,B,green);<br /> &lt;/asy&gt;<br /> <br /> The external angle is defined by &lt;math&gt;\angle A + \text{ external }\angle A = 180^\circ&lt;/math&gt;, and the two angle bisectors are perpendicular to each other. <br /> <br /> == Features of Angle Bisectors ==<br /> <br /> * The distances from a point on an angle bisector to both of its sides are equal.<br /> * The angle bisectors are the [[locus]] of points which are [[equidistant]] from the two sides of the angle.<br /> * A [[reflection]] about either angle bisector maps the two sides of the angle to each other.<br /> * In a triangle, the [[Angle Bisector Theorem]] gives the ratio in which the angle bisector cuts the opposite side.<br /> * In a triangle, the internal angle bisectors (which are [[cevian|cevians]]) all intersect at the [[incenter]] of the triangle. The internal angle bisector of one angle and the external angle bisectors of the other two angles all intersect at an [[excenter]] of the triangle.<br /> *A bisector of an angle can be [[Constructions|constructed]] using a compass and straightedge.<br /> <br /> {{asy image|&lt;asy&gt;<br /> size(300);<br /> import markers;<br /> pair excenter(pair A, pair B, pair C){<br /> pair X, Z;<br /> X=A+expi((angle(A-B)+angle(C-A))/2);<br /> Z=C+expi((angle(C-B)+angle(A-C))/2);<br /> return extension(X,A,Z,C);<br /> }<br /> pair X=(0,0), Y=(-10,0), Z=(-3,6);<br /> pair exX=excenter(Z,X,Y), exY=excenter(X,Y,Z), exZ=excenter(Y,Z,X);<br /> label(&quot;X&quot;,X,2*(1.5,-1));label(&quot;Y&quot;,Y,2*(-3,-1));label(&quot;Z&quot;,Z,(0.6,2));<br /> dot(X^^Y^^Z);<br /> draw(0.3*(X-Y)+X--Y+0.3*(Y-X));draw(0.3*(Y-Z)+Y--Z+0.3*(Z-Y));draw(0.3*(X-Z)+X--Z+0.3*(Z-X));<br /> draw(X+0.3*(X-exX)--exX,orange);draw(Y+0.3*(Y-exY)--exY,orange);draw(Z+0.3*(Z-exZ)--0.6*(exZ-Z)+Z,orange);<br /> draw(Y-0.5*(exX-Y)--Y+0.5*(exX-Y),green);draw(Z-0.5*(exX-Z)--Z+0.5*(exX-Z),green);draw(X-0.5*(exY-X)--X+0.5*(exY-X),green);<br /> pair I=extension(X,exX,Z,exZ);<br /> dot(&quot;I&quot;,I,(-1,2));<br /> draw(circle(I,length(I-foot(I,X,Y))),blue);<br /> markangle(n=1,3*(Z-X)+X,Z,exX,radius=22,marker(markinterval(stickframe(n=3),true)));<br /> markangle(n=1,exX,Z,Y,radius=20,marker(markinterval(stickframe(n=3),true)));<br /> markangle(n=1,3*(Y-Z)+Z,Y,exZ,radius=22,marker(markinterval(stickframe(n=2),true)));<br /> markangle(n=1,exZ,Y,X,radius=20,marker(markinterval(stickframe(n=2),true)));<br /> markangle(n=1,3*(X-Y)+Y,X,exY,radius=22,marker(markinterval(stickframe(n=1),true)));<br /> markangle(n=1,exY,X,Z,radius=20,marker(markinterval(stickframe(n=1),true)));<br /> <br /> markangle(n=3,I,Z,X,radius=20);<br /> markangle(n=3,Y,Z,I,radius=22);<br /> markangle(n=2,Z,X,I,radius=20);<br /> markangle(n=2,I,X,Y,radius=22);<br /> markangle(n=1,X,Y,I,radius=22);<br /> markangle(n=1,I,Y,Z,radius=20);<br /> &lt;/asy&gt;|center|Triangle &lt;math&gt;\triangle XYZ&lt;/math&gt; with [[incenter]] ''I'', [[incircle]] (blue), [[angle bisector]]s (orange), and [[angle bisector|external angle bisectors]] (green)}}<br /> <br /> ==See also==<br /> * [[Cevian]]<br /> * [[Geometry]]<br /> * [[Stewart's Theorem]]<br /> <br /> <br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Angle_bisector&diff=127197 Angle bisector 2020-07-01T06:33:49Z <p>Mag1c: </p> <hr /> <div>{{WotWAnnounce|week=June 6-12}}<br /> <br /> For an [[angle]] &lt;math&gt;\angle ABC&lt;/math&gt;, the (internal) angle bisector of &lt;math&gt;\angle ABC&lt;/math&gt; is the line from B such that the angle between this line and &lt;math&gt;BC&lt;/math&gt; is congruent to the angle between this line and &lt;math&gt;AB&lt;/math&gt;:<br /> <br /> &lt;center&gt;[[Image:Anglebisector.png]]&lt;/center&gt;<br /> <br /> A given [[angle]] &lt;math&gt;\angle ABC&lt;/math&gt; also has an external angle bisector, which bisects external angle &lt;math&gt;ABC&lt;/math&gt;: <br /> <br /> &lt;asy&gt;<br /> import markers;<br /> pair A,B,C,D,E,F;<br /> B=(0,0);<br /> C=(5,0);<br /> A=(4,2);<br /> D=(3,4);<br /> E=(10/3,0);<br /> F=rotate(-90,A)*(E);<br /> draw(A--B--C--cycle,blue);<br /> draw(C--D,blue);<br /> pen p=blue+0.15mm;<br /> draw(A--F,p);<br /> dot(A^^B^^C,red);<br /> label(&quot;$A$&quot;,A,NE);<br /> label(&quot;$B$&quot;,B,W);<br /> label(&quot;$C$&quot;,C,E);<br /> markangle(n=1,radius=20,D,A,F,green);<br /> markangle(n=1,radius=22,F,A,B,green);<br /> &lt;/asy&gt;<br /> <br /> The external angle is defined by &lt;math&gt;\angle A + \text{ external }\angle A = 180^\circ&lt;/math&gt;, and the two angle bisectors are perpendicular to each other. <br /> <br /> == Features of Angle Bisectors ==<br /> <br /> * The distances from a point on an angle bisector to both of its sides are equal.<br /> * The angle bisectors are the [[locus]] of points which are [[equidistant]] from the two sides of the angle.<br /> * A [[reflection]] about either angle bisector maps the two sides of the angle to each other.<br /> * In a triangle, the [[Angle Bisector Theorem]] gives the ratio in which the angle bisector cuts the opposite side.<br /> * In a triangle, the internal angle bisectors (which are [[cevian|cevians]]) all intersect at the [[incenter]] of the triangle. The internal angle bisector of one angle and the external angle bisectors of the other two angles all intersect at an [[excenter]] of the triangle.<br /> *A bisector of an angle can be [[Constructions|constructed]] using a compass and straightedge.<br /> <br /> {{asy image|&lt;asy&gt;<br /> size(300);<br /> import markers;<br /> pair excenter(pair A, pair B, pair C){<br /> pair X, Z;<br /> X=A+expi((angle(A-B)+angle(C-A))/2);<br /> Z=C+expi((angle(C-B)+angle(A-C))/2);<br /> return extension(X,A,Z,C);<br /> }<br /> pair X=(0,0), Y=(-10,0), Z=(-3,6);<br /> pair exX=excenter(Z,X,Y), exY=excenter(X,Y,Z), exZ=excenter(Y,Z,X);<br /> label(&quot;X&quot;,X,2*(1.5,-1));label(&quot;Y&quot;,Y,2*(-3,-1));label(&quot;Z&quot;,Z,(0.6,2));<br /> dot(X^^Y^^Z);<br /> draw(0.3*(X-Y)+X--Y+0.3*(Y-X));draw(0.3*(Y-Z)+Y--Z+0.3*(Z-Y));draw(0.3*(X-Z)+X--Z+0.3*(Z-X));<br /> draw(X+0.3*(X-exX)--exX,orange);draw(Y+0.3*(Y-exY)--exY,orange);draw(Z+0.3*(Z-exZ)--0.6*(exZ-Z)+Z,orange);<br /> draw(Y-0.5*(exX-Y)--Y+0.5*(exX-Y),green);draw(Z-0.5*(exX-Z)--Z+0.5*(exX-Z),green);draw(X-0.5*(exY-X)--X+0.5*(exY-X),green);<br /> pair I=extension(X,exX,Z,exZ);<br /> dot(&quot;I&quot;,I,(-1,2));<br /> draw(circle(I,length(I-foot(I,X,Y))),blue);<br /> markangle(n=1,I,Z,X,radius=20,marker(markinterval(stickframe(n=2),true)));<br /> &lt;/asy&gt;|center|Triangle &lt;math&gt;\triangle XYZ&lt;/math&gt; with [[incenter]] ''I'', with [[angle bisector]]s (orange), [[incircle]] (blue), and [[inradius|inradii]] (green)}}<br /> <br /> [[Image:Incenter.PNG|left|thumb|300px|Triangle ''XYZ'' with [[incenter]] ''I'', with [[angle bisector]]s (orange), [[incircle]] (blue), and [[external angle bisector]]s (green)]]<br /> <br /> ==See also==<br /> * [[Cevian]]<br /> * [[Geometry]]<br /> * [[Stewart's Theorem]]<br /> <br /> {{stub}}<br /> <br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Angle_bisector&diff=127196 Angle bisector 2020-07-01T06:19:17Z <p>Mag1c: diagram</p> <hr /> <div>{{WotWAnnounce|week=June 6-12}}<br /> <br /> For an [[angle]] &lt;math&gt;\angle ABC&lt;/math&gt;, the (internal) angle bisector of &lt;math&gt;\angle ABC&lt;/math&gt; is the line from B such that the angle between this line and &lt;math&gt;BC&lt;/math&gt; is congruent to the angle between this line and &lt;math&gt;AB&lt;/math&gt;:<br /> <br /> &lt;center&gt;[[Image:Anglebisector.png]]&lt;/center&gt;<br /> <br /> A given [[angle]] &lt;math&gt;\angle ABC&lt;/math&gt; also has an external angle bisector, which bisects external angle &lt;math&gt;ABC&lt;/math&gt;: <br /> <br /> &lt;asy&gt;<br /> import markers;<br /> pair A,B,C,D,E,F;<br /> B=(0,0);<br /> C=(5,0);<br /> A=(4,2);<br /> D=(3,4);<br /> E=(10/3,0);<br /> F=rotate(-90,A)*(E);<br /> draw(A--B--C--cycle,blue);<br /> draw(C--D,blue);<br /> pen p=blue+0.15mm;<br /> draw(A--F,p);<br /> dot(A^^B^^C,red);<br /> label(&quot;$A$&quot;,A,NE);<br /> label(&quot;$B$&quot;,B,W);<br /> label(&quot;$C$&quot;,C,E);<br /> markangle(n=1,radius=20,D,A,F,green);<br /> markangle(n=1,radius=22,F,A,B,green);<br /> &lt;/asy&gt;<br /> <br /> The external angle is defined by &lt;math&gt;\angle A + \text{ external }\angle A = 180^\circ&lt;/math&gt;, and the two angle bisectors are perpendicular to each other. <br /> <br /> == Features of Angle Bisectors ==<br /> <br /> * The distances from a point on an angle bisector to both of its sides are equal.<br /> * The angle bisectors are the [[locus]] of points which are [[equidistant]] from the two sides of the angle.<br /> * A [[reflection]] about either angle bisector maps the two sides of the angle to each other.<br /> * In a triangle, the [[Angle Bisector Theorem]] gives the ratio in which the angle bisector cuts the opposite side.<br /> * In a triangle, the internal angle bisectors (which are [[cevian|cevians]]) all intersect at the [[incenter]] of the triangle. The internal angle bisector of one angle and the external angle bisectors of the other two angles all intersect at an [[excenter]] of the triangle.<br /> *A bisector of an angle can be [[Constructions|constructed]] using a compass and straightedge.<br /> <br /> {{asy image|&lt;asy&gt;<br /> size(300);<br /> pair excenter(pair A, pair B, pair C){<br /> pair X, Z;<br /> X=A+expi((angle(A-B)+angle(C-A))/2);<br /> Z=C+expi((angle(C-B)+angle(A-C))/2);<br /> return extension(X,A,Z,C);<br /> }<br /> pair X=(0,0), Y=(-10,0), Z=(-3,6);<br /> pair exX=excenter(Z,X,Y), exY=excenter(X,Y,Z), exZ=excenter(Y,Z,X);<br /> label(&quot;X&quot;,X,2*(1.5,-1));label(&quot;Y&quot;,Y,2*(-3,-1));label(&quot;Z&quot;,Z,(0.6,2));<br /> dot(X^^Y^^Z);<br /> draw(0.3*(X-Y)+X--Y+0.3*(Y-X));draw(0.3*(Y-Z)+Y--Z+0.3*(Z-Y));draw(0.3*(X-Z)+X--Z+0.3*(Z-X));<br /> draw(X+0.3*(X-exX)--exX,orange);draw(Y+0.3*(Y-exY)--exY,orange);draw(Z+0.3*(Z-exZ)--0.6*(exZ-Z)+Z,orange);<br /> pair I=extension(X,exX,Z,exZ);<br /> dot(&quot;I&quot;,I,(-1,2));<br /> draw(circle(I,length(I-foot(I,X,Y))),blue);<br /> &lt;/asy&gt;|center|Triangle &lt;math&gt;\triangle XYZ&lt;/math&gt; with [[incenter]] ''I'', with [[angle bisector]]s (red), [[incircle]] (blue), and [[inradius|inradii]] (green)}}<br /> <br /> [[Image:Incenter.PNG|left|thumb|300px|Triangle ''XYZ'' with [[incenter]] ''I'', with [[angle bisector]]s (orange), [[incircle]] (blue), and [[external angle bisector]]s (green)]]<br /> <br /> ==See also==<br /> * [[Cevian]]<br /> * [[Geometry]]<br /> * [[Stewart's Theorem]]<br /> <br /> {{stub}}<br /> <br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Angle_bisector&diff=127195 Angle bisector 2020-07-01T05:18:49Z <p>Mag1c: </p> <hr /> <div>{{WotWAnnounce|week=June 6-12}}<br /> <br /> For an [[angle]] &lt;math&gt;\angle ABC&lt;/math&gt;, the (internal) angle bisector of &lt;math&gt;\angle ABC&lt;/math&gt; is the line from B such that the angle between this line and &lt;math&gt;BC&lt;/math&gt; is congruent to the angle between this line and &lt;math&gt;AB&lt;/math&gt;:<br /> <br /> &lt;center&gt;[[Image:Anglebisector.png]]&lt;/center&gt;<br /> <br /> A given [[angle]] &lt;math&gt;\angle ABC&lt;/math&gt; also has an external angle bisector, which bisects external angle &lt;math&gt;ABC&lt;/math&gt;: <br /> <br /> &lt;asy&gt;<br /> pair A,B,C,D;<br /> B=(0,0);<br /> C=(5,0);<br /> A=(4,2);<br /> D=(3,4);<br /> draw(A--B--C--cycle,blue);<br /> draw(C--D,blue);<br /> dot(A^^B^^C,red);<br /> label(&quot;$A$&quot;,A,NE);<br /> label(&quot;$B$&quot;,B,W);<br /> label(&quot;$C$&quot;,C,E);<br /> &lt;/asy&gt;<br /> <br /> The two angle bisectors are perpendicular to each other and &lt;math&gt;\text{internal angle }A + \text{ external angle }A = 180^\circ.&lt;/math&gt;<br /> <br /> == Features of Angle Bisectors ==<br /> <br /> * The distances from a point on an angle bisector to both of its sides are equal.<br /> * The angle bisectors are the [[locus]] of points which are [[equidistant]] from the two sides of the angle.<br /> * A [[reflection]] about either angle bisector maps the two sides of the angle to each other.<br /> * In a triangle, the [[Angle Bisector Theorem]] gives the ratio in which the angle bisector cuts the opposite side.<br /> * In a triangle, the internal angle bisectors (which are [[cevian|cevians]]) all intersect at the [[incenter]] of the triangle. The internal angle bisector of one angle and the external angle bisectors of the other two angles all intersect at an [[excenter]] of the triangle.<br /> *A bisector of an angle can be [[Constructions|constructed]] using a compass and straightedge.<br /> <br /> {{asy image|&lt;asy&gt;<br /> defaultpen(fontsize(8));<br /> pair excenter(pair A, pair B, pair C){<br /> pair X, Z;<br /> X=A+expi((angle(A-B)+angle(C-A))/2);<br /> Z=C+expi((angle(C-B)+angle(A-C))/2);<br /> return extension(X,A,Z,C);<br /> }<br /> pair X=(0,0), Y=(10,0), Z=(3,6);<br /> pair exX=excenter(Z,X,Y), exY=excenter(X,Y,Z), exZ=excenter(Y,Z,X);<br /> draw(circle(exX,length(exX-foot(exX,Y,Z))));<br /> draw(circle(exY,length(exY-foot(exY,Z,X))));<br /> draw(circle(exZ,length(exZ-foot(exZ,X,Y))));<br /> draw((X-Y)+X--Y+1.5*(Y-X));draw((Y-Z)+Y--Z+(Z-Y));draw(2*(X-Z)+X--Z+2*(Z-X));<br /> label(&quot;X&quot;,X,(-1.5,-1));label(&quot;Y&quot;,Y,(2,-1));label(&quot;Z&quot;,Z,N);<br /> label(&quot;P&quot;,exX,NE);<br /> dot(X^^Y^^Z^^exX^^exY^^exZ);<br /> <br /> draw(exX--(xpart(exX),0),dashed);<br /> <br /> real slope1=(ypart(Z)-ypart(X))/(xpart(Z)-xpart(X));<br /> pair point1=exX+(1,-1/slope1);<br /> pair tangent1=extension(X,Z,point1,exX);<br /> draw(exX--tangent1,dashed);<br /> <br /> real slope2=(ypart(Y)-ypart(Z))/(xpart(Y)-xpart(Z));<br /> pair point2=exX+(1,-1/slope2);<br /> pair tangent2=extension(Y,Z,point2,exX);<br /> draw(exX--tangent2,dashed);<br /> <br /> markscalefactor=0.1;<br /> draw(rightanglemark(exX,tangent1,Z));<br /> draw(rightanglemark(exX,tangent2,Y));<br /> draw(rightanglemark(exX,(xpart(exX),0),(100,0)));<br /> &lt;/asy&gt;|center|Triangle &lt;math&gt;\triangle XYZ&lt;/math&gt; with [[incenter]] ''I'', with [[angle bisector]]s (red), [[incircle]] (blue), and [[inradius|inradii]] (green)}}<br /> <br /> [[Image:Incenter.PNG|left|thumb|300px|Triangle ''ABC'' with [[incenter]] ''I'', with [[angle bisector]]s (red), [[external angle bisector[[incircle]] (blue), and [[inradius|inradii]] (green)]]<br /> <br /> ==See also==<br /> * [[Cevian]]<br /> * [[Geometry]]<br /> * [[Stewart's Theorem]]<br /> <br /> {{stub}}<br /> <br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Angle_bisector&diff=127194 Angle bisector 2020-07-01T05:13:53Z <p>Mag1c: </p> <hr /> <div>{{WotWAnnounce|week=June 6-12}}<br /> <br /> For an [[angle]] &lt;math&gt;\angle ABC&lt;/math&gt;, the (internal) angle bisector of &lt;math&gt;\angle ABC&lt;/math&gt; is the line from B such that the angle between this line and &lt;math&gt;BC&lt;/math&gt; is congruent to the angle between this line and &lt;math&gt;AB&lt;/math&gt;:<br /> <br /> &lt;center&gt;[[Image:Anglebisector.png]]&lt;/center&gt;<br /> <br /> A given [[angle]] &lt;math&gt;\angle ABC&lt;/math&gt; also has an external angle bisector, which bisects external angle &lt;math&gt;ABC&lt;/math&gt; where &lt;math&gt;\text{internal angle }A + \text{ external angle }A = 180^\circ&lt;/math&gt;:<br /> <br /> {{asy image |&lt;asy&gt;<br /> pair A,B,C,D;<br /> B=(0,0);<br /> C=(5,0);<br /> A=(4,2);<br /> D=(3,4);<br /> draw(A--B--C--cycle,blue);<br /> draw(C--D,blue);<br /> &lt;/asy&gt;|center|}}<br /> <br /> The two angle bisectors are perpendicular to each other.<br /> <br /> == Features of Angle Bisectors ==<br /> <br /> * The distances from a point on an angle bisector to both of its sides are equal.<br /> * The angle bisectors are the [[locus]] of points which are [[equidistant]] from the two sides of the angle.<br /> * A [[reflection]] about either angle bisector maps the two sides of the angle to each other.<br /> * In a triangle, the [[Angle Bisector Theorem]] gives the ratio in which the angle bisector cuts the opposite side.<br /> * In a triangle, the internal angle bisectors (which are [[cevian|cevians]]) all intersect at the [[incenter]] of the triangle. The internal angle bisector of one angle and the external angle bisectors of the other two angles all intersect at an [[excenter]] of the triangle.<br /> *A bisector of an angle can be [[Constructions|constructed]] using a compass and straightedge.<br /> <br /> {{asy image|&lt;asy&gt;<br /> defaultpen(fontsize(8));<br /> pair excenter(pair A, pair B, pair C){<br /> pair X, Z;<br /> X=A+expi((angle(A-B)+angle(C-A))/2);<br /> Z=C+expi((angle(C-B)+angle(A-C))/2);<br /> return extension(X,A,Z,C);<br /> }<br /> pair X=(0,0), Y=(10,0), Z=(3,6);<br /> pair exX=excenter(Z,X,Y), exY=excenter(X,Y,Z), exZ=excenter(Y,Z,X);<br /> draw(circle(exX,length(exX-foot(exX,Y,Z))));<br /> draw(circle(exY,length(exY-foot(exY,Z,X))));<br /> draw(circle(exZ,length(exZ-foot(exZ,X,Y))));<br /> draw((X-Y)+X--Y+1.5*(Y-X));draw((Y-Z)+Y--Z+(Z-Y));draw(2*(X-Z)+X--Z+2*(Z-X));<br /> label(&quot;X&quot;,X,(-1.5,-1));label(&quot;Y&quot;,Y,(2,-1));label(&quot;Z&quot;,Z,N);<br /> label(&quot;P&quot;,exX,NE);<br /> dot(X^^Y^^Z^^exX^^exY^^exZ);<br /> <br /> draw(exX--(xpart(exX),0),dashed);<br /> <br /> real slope1=(ypart(Z)-ypart(X))/(xpart(Z)-xpart(X));<br /> pair point1=exX+(1,-1/slope1);<br /> pair tangent1=extension(X,Z,point1,exX);<br /> draw(exX--tangent1,dashed);<br /> <br /> real slope2=(ypart(Y)-ypart(Z))/(xpart(Y)-xpart(Z));<br /> pair point2=exX+(1,-1/slope2);<br /> pair tangent2=extension(Y,Z,point2,exX);<br /> draw(exX--tangent2,dashed);<br /> <br /> markscalefactor=0.1;<br /> draw(rightanglemark(exX,tangent1,Z));<br /> draw(rightanglemark(exX,tangent2,Y));<br /> draw(rightanglemark(exX,(xpart(exX),0),(100,0)));<br /> &lt;/asy&gt;|center|Triangle &lt;math&gt;\triangle XYZ&lt;/math&gt; with [[incenter]] ''I'', with [[angle bisector]]s (red), [[incircle]] (blue), and [[inradius|inradii]] (green)}}<br /> <br /> [[Image:Incenter.PNG|left|thumb|300px|Triangle ''ABC'' with [[incenter]] ''I'', with [[angle bisector]]s (red), [[external angle bisector[[incircle]] (blue), and [[inradius|inradii]] (green)]]<br /> <br /> ==See also==<br /> * [[Cevian]]<br /> * [[Geometry]]<br /> * [[Stewart's Theorem]]<br /> <br /> {{stub}}<br /> <br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Excircle&diff=127193 Excircle 2020-07-01T04:43:05Z <p>Mag1c: /* Properties */</p> <hr /> <div>An '''excircle''' is a [[circle]] [[Tangent line|tangent]] to the extensions of two sides of a [[triangle]] and the third side.<br /> <br /> {{asy image|&lt;asy&gt;<br /> defaultpen(fontsize(8));<br /> pair excenter(pair A, pair B, pair C){<br /> pair X, Z;<br /> X=A+expi((angle(A-B)+angle(C-A))/2);<br /> Z=C+expi((angle(C-B)+angle(A-C))/2);<br /> return extension(X,A,Z,C);<br /> }<br /> pair X=(0,0), Y=(10,0), Z=(3,6);<br /> pair exX=excenter(Z,X,Y), exY=excenter(X,Y,Z), exZ=excenter(Y,Z,X);<br /> draw(circle(exX,length(exX-foot(exX,Y,Z))));<br /> draw(circle(exY,length(exY-foot(exY,Z,X))));<br /> draw(circle(exZ,length(exZ-foot(exZ,X,Y))));<br /> draw((X-Y)+X--Y+1.5*(Y-X));draw((Y-Z)+Y--Z+(Z-Y));draw(2*(X-Z)+X--Z+2*(Z-X));<br /> label(&quot;X&quot;,X,(-1.5,-1));label(&quot;Y&quot;,Y,(2,-1));label(&quot;Z&quot;,Z,N);<br /> label(&quot;P&quot;,exX,NE);<br /> dot(X^^Y^^Z^^exX^^exY^^exZ);<br /> <br /> draw(exX--(xpart(exX),0),dashed);<br /> <br /> real slope1=(ypart(Z)-ypart(X))/(xpart(Z)-xpart(X));<br /> pair point1=exX+(1,-1/slope1);<br /> pair tangent1=extension(X,Z,point1,exX);<br /> draw(exX--tangent1,dashed);<br /> <br /> real slope2=(ypart(Y)-ypart(Z))/(xpart(Y)-xpart(Z));<br /> pair point2=exX+(1,-1/slope2);<br /> pair tangent2=extension(Y,Z,point2,exX);<br /> draw(exX--tangent2,dashed);<br /> <br /> markscalefactor=0.1;<br /> draw(rightanglemark(exX,tangent1,Z));<br /> draw(rightanglemark(exX,tangent2,Y));<br /> draw(rightanglemark(exX,(xpart(exX),0),(100,0)));<br /> &lt;/asy&gt;|right|Triangle &lt;math&gt;\triangle XYZ&lt;/math&gt; and its excircles.}}<br /> <br /> <br /> == Properties ==<br /> For any triangle, there are three unique excircles. This follows from the fact that there is one, if any, circle such that three given distinct lines are tangent to it. <br /> <br /> 1) Each excenter lies on the intersection of two external angle bisectors.<br /> <br /> 2) The &lt;math&gt;A&lt;/math&gt;-excenter lies on the angle bisector of &lt;math&gt;\angle A&lt;/math&gt;.<br /> <br /> == Related Geometrical Objects ==<br /> *An exradius is a radius of an excircle of a triangle.<br /> *An excenter is the center of an excircle of a triangle.<br /> ==Related Formulas==<br /> If the circle is tangent to side &lt;math&gt;a&lt;/math&gt; of the triangle, the radius is &lt;math&gt;\frac{K}{s-a}&lt;/math&gt;, where &lt;math&gt;K&lt;/math&gt; is the triangle's area, and &lt;math&gt;s = \frac{a+b+c}{2}&lt;/math&gt; is the [[semiperimeter]].<br /> <br /> ==Problems==<br /> ===Introductory===<br /> *Let &lt;math&gt;E,F&lt;/math&gt; be the feet of the perpendiculars from the vertices &lt;math&gt;B,C&lt;/math&gt; of triangle &lt;math&gt;\triangle ABC&lt;/math&gt;. Let &lt;math&gt;O&lt;/math&gt; be the circumcenter &lt;math&gt;\triangle ABC&lt;/math&gt;. Prove that &lt;cmath&gt;OA \perp FE .&lt;/cmath&gt;<br /> (&lt;url&gt;https://artofproblemsolving.com/community/c4h45647 Source&lt;/url&gt;)<br /> <br /> ===Intermediate===<br /> *In triangle &lt;math&gt;ABC&lt;/math&gt;, let the &lt;math&gt;A&lt;/math&gt;-excircle touch &lt;math&gt;BC&lt;/math&gt; at &lt;math&gt;D&lt;/math&gt;. Let the &lt;math&gt;B&lt;/math&gt;-excircle of triangle &lt;math&gt;ABD&lt;/math&gt; touch &lt;math&gt;AD&lt;/math&gt; at &lt;math&gt;P&lt;/math&gt; and let the &lt;math&gt;C&lt;/math&gt;-excircle of triangle &lt;math&gt;ACD&lt;/math&gt; touch &lt;math&gt;AD&lt;/math&gt; at &lt;math&gt;Q&lt;/math&gt;. Is &lt;math&gt;\angle P\cong\angle Q&lt;/math&gt; true for all triangles &lt;math&gt;ABC&lt;/math&gt;? (&lt;url&gt;viewtopic.php?t=167688 Source&lt;/url&gt;)<br /> <br /> ===Olympiad===<br /> *Let &lt;math&gt;ABC&lt;/math&gt; be a triangle and let &lt;math&gt;\omega&lt;/math&gt; be its incircle. Denote by &lt;math&gt;D_1&lt;/math&gt; and &lt;math&gt;E_1&lt;/math&gt; the points where &lt;math&gt;\omega&lt;/math&gt; is tangent to sides &lt;math&gt;BC&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt;, respectively. Denote by &lt;math&gt;D_2&lt;/math&gt; and &lt;math&gt;E_2&lt;/math&gt; the points on sides &lt;math&gt;BC&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt;, respectively, such that &lt;math&gt;CD_2 = BD_1&lt;/math&gt; and &lt;math&gt;CE_2 = AE_1&lt;/math&gt;, and denote by &lt;math&gt;P&lt;/math&gt; the point of intersection of segments &lt;math&gt;AD_2&lt;/math&gt; and &lt;math&gt;BE_2&lt;/math&gt;. Circle &lt;math&gt;\omega&lt;/math&gt; intersects segment &lt;math&gt;AD_2&lt;/math&gt; at two points, the closer of which to the vertex &lt;math&gt;A&lt;/math&gt; is denoted by &lt;math&gt;Q&lt;/math&gt;. Prove that &lt;math&gt;AQ = D_2P&lt;/math&gt;. ([[2001 USAMO Problems/Problem 2|Source]])<br /> *Let &lt;math&gt;ABC&lt;/math&gt; be a triangle with circumcircle &lt;math&gt;\omega.&lt;/math&gt; Point &lt;math&gt;D&lt;/math&gt; lies on side &lt;math&gt;BC&lt;/math&gt; such that &lt;math&gt;\angle BAD = \angle CAD.&lt;/math&gt; Let &lt;math&gt;I_{A}&lt;/math&gt; denote the excenter of triangle &lt;math&gt;ABC&lt;/math&gt; opposite &lt;math&gt;A,&lt;/math&gt; and let &lt;math&gt;\omega_{A}&lt;/math&gt; denote the circle with &lt;math&gt;AI_{A}&lt;/math&gt; as its diameter. Circles &lt;math&gt;\omega&lt;/math&gt; and &lt;math&gt;\omega_{A}&lt;/math&gt; meet at &lt;math&gt;P&lt;/math&gt; other than &lt;math&gt;A.&lt;/math&gt; The circumcle of triangle &lt;math&gt;APD&lt;/math&gt; meet line &lt;math&gt;BC&lt;/math&gt; again at &lt;math&gt;Q\, (&lt;/math&gt;other than &lt;math&gt;D).&lt;/math&gt; Prove that &lt;math&gt;Q&lt;/math&gt; lies on the excircle of triangle &lt;math&gt;ABC&lt;/math&gt; opposite &lt;math&gt;A&lt;/math&gt;. (Source: Problem 13.2 - MOSP 2007)<br /> *Let &lt;math&gt;ABCD &lt;/math&gt; be a parallelogram. A variable line &lt;math&gt; \ell &lt;/math&gt; passing through the point &lt;math&gt;A &lt;/math&gt; intersects the rays &lt;math&gt;BC &lt;/math&gt; and &lt;math&gt;DC &lt;/math&gt; at points &lt;math&gt;X &lt;/math&gt; and &lt;math&gt;Y &lt;/math&gt;, respectively. Let &lt;math&gt;K &lt;/math&gt; and &lt;math&gt;L &lt;/math&gt; be the centres of the excircles of triangles &lt;math&gt;ABX &lt;/math&gt; and &lt;math&gt;ADY &lt;/math&gt;, touching the sides &lt;math&gt;BX &lt;/math&gt; and &lt;math&gt;DY &lt;/math&gt;, respectively. Prove that the size of angle &lt;math&gt;KCL &lt;/math&gt; does not depend on the choice of &lt;math&gt; \ell &lt;/math&gt;. ([[2005 IMO Shortlist Problems/G3|Source]])<br /> <br /> ==See also==<br /> *[[Incircle]]<br /> *[[Circumcircle]]<br /> [[Category:Definition]]<br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Excircle&diff=127191 Excircle 2020-07-01T04:01:12Z <p>Mag1c: mark angles</p> <hr /> <div>An '''excircle''' is a [[circle]] [[Tangent line|tangent]] to the extensions of two sides of a [[triangle]] and the third side.<br /> <br /> {{asy image|&lt;asy&gt;<br /> defaultpen(fontsize(8));<br /> pair excenter(pair A, pair B, pair C){<br /> pair X, Z;<br /> X=A+expi((angle(A-B)+angle(C-A))/2);<br /> Z=C+expi((angle(C-B)+angle(A-C))/2);<br /> return extension(X,A,Z,C);<br /> }<br /> pair X=(0,0), Y=(10,0), Z=(3,6);<br /> pair exX=excenter(Z,X,Y), exY=excenter(X,Y,Z), exZ=excenter(Y,Z,X);<br /> draw(circle(exX,length(exX-foot(exX,Y,Z))));<br /> draw(circle(exY,length(exY-foot(exY,Z,X))));<br /> draw(circle(exZ,length(exZ-foot(exZ,X,Y))));<br /> draw((X-Y)+X--Y+1.5*(Y-X));draw((Y-Z)+Y--Z+(Z-Y));draw(2*(X-Z)+X--Z+2*(Z-X));<br /> label(&quot;X&quot;,X,(-1.5,-1));label(&quot;Y&quot;,Y,(2,-1));label(&quot;Z&quot;,Z,N);<br /> label(&quot;P&quot;,exX,NE);<br /> dot(X^^Y^^Z^^exX^^exY^^exZ);<br /> <br /> draw(exX--(xpart(exX),0),dashed);<br /> <br /> real slope1=(ypart(Z)-ypart(X))/(xpart(Z)-xpart(X));<br /> pair point1=exX+(1,-1/slope1);<br /> pair tangent1=extension(X,Z,point1,exX);<br /> draw(exX--tangent1,dashed);<br /> <br /> real slope2=(ypart(Y)-ypart(Z))/(xpart(Y)-xpart(Z));<br /> pair point2=exX+(1,-1/slope2);<br /> pair tangent2=extension(Y,Z,point2,exX);<br /> draw(exX--tangent2,dashed);<br /> <br /> markscalefactor=0.1;<br /> draw(rightanglemark(exX,tangent1,Z));<br /> draw(rightanglemark(exX,tangent2,Y));<br /> draw(rightanglemark(exX,(xpart(exX),0),(100,0)));<br /> &lt;/asy&gt;|right|Triangle &lt;math&gt;\triangle XYZ&lt;/math&gt; and its excircles.}}<br /> <br /> <br /> == Properties ==<br /> For any triangle, there are three unique excircles. This follows from the fact that there is one, if any, circle such that three given distinct lines are tangent to it. Any of the three excenters lies on the intersection of two external angle bisectors.<br /> <br /> == Related Geometrical Objects ==<br /> *An exradius is a radius of an excircle of a triangle.<br /> *An excenter is the center of an excircle of a triangle.<br /> ==Related Formulas==<br /> If the circle is tangent to side &lt;math&gt;a&lt;/math&gt; of the triangle, the radius is &lt;math&gt;\frac{K}{s-a}&lt;/math&gt;, where &lt;math&gt;K&lt;/math&gt; is the triangle's area, and &lt;math&gt;s = \frac{a+b+c}{2}&lt;/math&gt; is the [[semiperimeter]].<br /> <br /> ==Problems==<br /> ===Introductory===<br /> *Let &lt;math&gt;E,F&lt;/math&gt; be the feet of the perpendiculars from the vertices &lt;math&gt;B,C&lt;/math&gt; of triangle &lt;math&gt;\triangle ABC&lt;/math&gt;. Let &lt;math&gt;O&lt;/math&gt; be the circumcenter &lt;math&gt;\triangle ABC&lt;/math&gt;. Prove that &lt;cmath&gt;OA \perp FE .&lt;/cmath&gt;<br /> (&lt;url&gt;https://artofproblemsolving.com/community/c4h45647 Source&lt;/url&gt;)<br /> <br /> ===Intermediate===<br /> *In triangle &lt;math&gt;ABC&lt;/math&gt;, let the &lt;math&gt;A&lt;/math&gt;-excircle touch &lt;math&gt;BC&lt;/math&gt; at &lt;math&gt;D&lt;/math&gt;. Let the &lt;math&gt;B&lt;/math&gt;-excircle of triangle &lt;math&gt;ABD&lt;/math&gt; touch &lt;math&gt;AD&lt;/math&gt; at &lt;math&gt;P&lt;/math&gt; and let the &lt;math&gt;C&lt;/math&gt;-excircle of triangle &lt;math&gt;ACD&lt;/math&gt; touch &lt;math&gt;AD&lt;/math&gt; at &lt;math&gt;Q&lt;/math&gt;. Is &lt;math&gt;\angle P\cong\angle Q&lt;/math&gt; true for all triangles &lt;math&gt;ABC&lt;/math&gt;? (&lt;url&gt;viewtopic.php?t=167688 Source&lt;/url&gt;)<br /> <br /> ===Olympiad===<br /> *Let &lt;math&gt;ABC&lt;/math&gt; be a triangle and let &lt;math&gt;\omega&lt;/math&gt; be its incircle. Denote by &lt;math&gt;D_1&lt;/math&gt; and &lt;math&gt;E_1&lt;/math&gt; the points where &lt;math&gt;\omega&lt;/math&gt; is tangent to sides &lt;math&gt;BC&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt;, respectively. Denote by &lt;math&gt;D_2&lt;/math&gt; and &lt;math&gt;E_2&lt;/math&gt; the points on sides &lt;math&gt;BC&lt;/math&gt; and &lt;math&gt;AC&lt;/math&gt;, respectively, such that &lt;math&gt;CD_2 = BD_1&lt;/math&gt; and &lt;math&gt;CE_2 = AE_1&lt;/math&gt;, and denote by &lt;math&gt;P&lt;/math&gt; the point of intersection of segments &lt;math&gt;AD_2&lt;/math&gt; and &lt;math&gt;BE_2&lt;/math&gt;. Circle &lt;math&gt;\omega&lt;/math&gt; intersects segment &lt;math&gt;AD_2&lt;/math&gt; at two points, the closer of which to the vertex &lt;math&gt;A&lt;/math&gt; is denoted by &lt;math&gt;Q&lt;/math&gt;. Prove that &lt;math&gt;AQ = D_2P&lt;/math&gt;. ([[2001 USAMO Problems/Problem 2|Source]])<br /> *Let &lt;math&gt;ABC&lt;/math&gt; be a triangle with circumcircle &lt;math&gt;\omega.&lt;/math&gt; Point &lt;math&gt;D&lt;/math&gt; lies on side &lt;math&gt;BC&lt;/math&gt; such that &lt;math&gt;\angle BAD = \angle CAD.&lt;/math&gt; Let &lt;math&gt;I_{A}&lt;/math&gt; denote the excenter of triangle &lt;math&gt;ABC&lt;/math&gt; opposite &lt;math&gt;A,&lt;/math&gt; and let &lt;math&gt;\omega_{A}&lt;/math&gt; denote the circle with &lt;math&gt;AI_{A}&lt;/math&gt; as its diameter. Circles &lt;math&gt;\omega&lt;/math&gt; and &lt;math&gt;\omega_{A}&lt;/math&gt; meet at &lt;math&gt;P&lt;/math&gt; other than &lt;math&gt;A.&lt;/math&gt; The circumcle of triangle &lt;math&gt;APD&lt;/math&gt; meet line &lt;math&gt;BC&lt;/math&gt; again at &lt;math&gt;Q\, (&lt;/math&gt;other than &lt;math&gt;D).&lt;/math&gt; Prove that &lt;math&gt;Q&lt;/math&gt; lies on the excircle of triangle &lt;math&gt;ABC&lt;/math&gt; opposite &lt;math&gt;A&lt;/math&gt;. (Source: Problem 13.2 - MOSP 2007)<br /> *Let &lt;math&gt;ABCD &lt;/math&gt; be a parallelogram. A variable line &lt;math&gt; \ell &lt;/math&gt; passing through the point &lt;math&gt;A &lt;/math&gt; intersects the rays &lt;math&gt;BC &lt;/math&gt; and &lt;math&gt;DC &lt;/math&gt; at points &lt;math&gt;X &lt;/math&gt; and &lt;math&gt;Y &lt;/math&gt;, respectively. Let &lt;math&gt;K &lt;/math&gt; and &lt;math&gt;L &lt;/math&gt; be the centres of the excircles of triangles &lt;math&gt;ABX &lt;/math&gt; and &lt;math&gt;ADY &lt;/math&gt;, touching the sides &lt;math&gt;BX &lt;/math&gt; and &lt;math&gt;DY &lt;/math&gt;, respectively. Prove that the size of angle &lt;math&gt;KCL &lt;/math&gt; does not depend on the choice of &lt;math&gt; \ell &lt;/math&gt;. ([[2005 IMO Shortlist Problems/G3|Source]])<br /> <br /> ==See also==<br /> *[[Incircle]]<br /> *[[Circumcircle]]<br /> [[Category:Definition]]<br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Dissection&diff=127151 Dissection 2020-06-30T22:13:08Z <p>Mag1c: create page</p> <hr /> <div>==Definition==<br /> <br /> According to [https://en.wikipedia.org/wiki/Equidissection https://en.wikipedia.org/wiki/Equidissection]: &quot;A dissection of a polygon P is a finite set of triangles that do not overlap and whose union is all of P.&quot;<br /> <br /> ==Example==<br /> <br /> Here is an example of a dissection (of the bottom square):<br /> &lt;asy&gt;<br /> import graph; defaultpen(linewidth(0.7)); unitsize(15); pen ds=black, ls = linetype(&quot;2 2&quot;); <br /> pen fueaev=rgb(1,0.4,0.4), ffffea=rgb(1,1,0.4), evfuea=rgb(0.4,1,0.4), fffuev=rgb(1,0.5,0.3), fzfzfz=rgb(0.8,0.8,0.8), evevfz=rgb(0.4,0.4,1); <br /> <br /> fill((0,0)--(1.5,2)--(-0.5,3.5)--(-2,1.5)--cycle,fueaev); fill((1.5,2)--(4.17,0)--(6.17,2.67)--(3.5,4.67)--cycle,fueaev); fill((4.17,0)--(0,0)--(0,-4.17)--(4.17,-4.17)--cycle,fueaev); fill((1.5,2)--(2,2.67)--(2,1.63)--cycle,ffffea); fill((2,2.67)--(2,1.63)--(4.17,0)--(6.17,2.67)--cycle,evfuea); fill((0,3.13)--(0,0)--(1.5,2)--cycle,fffuev); fill((-0.5,3.5)--(0,3.13)--(0,0)--(-2,1.5)--cycle,fueaev); fill((0,0)--(1.5,2)--(4.17,0)--cycle,fzfzfz); fill((2,2.67)--(3.5,4.67)--(6.17,2.67)--cycle,evevfz); fill((0,-4.17)--(1.5,-2.17)--(0,-1.04)--cycle,fffuev); fill((1.5,-2.17)--(0,-4.17)--(4.17,-4.17)--cycle,evevfz); fill((4.17,0)--(3.67,-0.67)--(4.17,-1.04)--cycle,white); fill((3.67,-0.67)--(2.17,-2.67)--(4.17,-4.17)--(4.17,-1.04)--cycle,fueaev); fill((0,0)--(0,-1.04)--(2.17,-2.67)--(4.17,0)--cycle,evfuea); fill((4.17,0)--(3.67,-0.67)--(4.17,-1.04)--cycle, ffffea);<br /> <br /> draw((0,0)--(1.5,2)); draw((0,0)--(4.17,0)); draw((1.5,2)--(4.17,0)); draw((0,0)--(1.5,2)); draw((1.5,2)--(-0.5,3.5)); draw((-0.5,3.5)--(-2,1.5)); draw((-2,1.5)--(0,0)); draw((1.5,2)--(4.17,0)); draw((4.17,0)--(6.17,2.67)); draw((6.17,2.67)--(3.5,4.67)); draw((3.5,4.67)--(1.5,2)); draw((4.17,0)--(0,0)); draw((0,0)--(0,-4.17)); draw((0,-4.17)--(4.17,-4.17)); draw((4.17,-4.17)--(4.17,0)); draw((0,0)--(-2,1.5)); draw((-2,1.5)--(-0.5,3.5)); draw((-0.5,3.5)--(1.5,2)); draw((0,0)--(0,-4.17)); draw((0,-4.17)--(4.17,-4.17)); draw((4.17,-4.17)--(4.17,0)); draw((4.17,0)--(6.17,2.67)); draw((6.17,2.67)--(3.5,4.67)); draw((3.5,4.67)--(1.5,2)); draw((0,-4.17)--(0,0)); draw((0,0)--(0,3.13)); draw((1.5,2)--(2,2.67)); draw((2,2.67)--(2,1.63)); draw((2,1.63)--(1.5,2)); draw((2,2.67)--(2,1.63)); draw((2,1.63)--(4.17,0)); draw((4.17,0)--(6.17,2.67)); draw((6.17,2.67)--(2,2.67)); draw((0,3.13)--(0,0)); draw((0,0)--(1.5,2)); draw((1.5,2)--(0,3.13)); draw((-0.5,3.5)--(0,3.13)); draw((0,3.13)--(0,0)); draw((0,0)--(-2,1.5)); draw((-2,1.5)--(-0.5,3.5)); draw((0,0)--(1.5,2)); draw((1.5,2)--(4.17,0)); draw((4.17,0)--(0,0)); draw((2,2.67)--(3.5,4.67)); draw((3.5,4.67)--(6.17,2.67)); draw((6.17,2.67)--(2,2.67)); draw((0,-1.04)--(4.17,-4.17)); draw((0,-4.17)--(1.5,-2.17)); draw((1.5,-2.17)--(0,-1.04)); draw((0,-1.04)--(0,-4.17)); draw((1.5,-2.17)--(0,-4.17)); draw((0,-4.17)--(4.17,-4.17)); draw((4.17,-4.17)--(1.5,-2.17)); draw((4.17,0)--(3.67,-0.67)); draw((3.67,-0.67)--(4.17,-1.04)); draw((4.17,-1.04)--(4.17,0)); draw((3.67,-0.67)--(2.17,-2.67)); draw((2.17,-2.67)--(4.17,-4.17)); draw((4.17,-4.17)--(4.17,-1.04)); draw((4.17,-1.04)--(3.67,-0.67)); draw((0,0)--(0,-1.04)); draw((0,-1.04)--(2.17,-2.67)); draw((2.17,-2.67)--(4.17,0)); draw((4.17,0)--(0,0)); <br /> <br /> draw((-0.5,3.5)--(1.5,6.17),ls); <br /> draw((1.5,6.17)--(3.5,4.67),ls); <br /> draw((0,3.13)--(0,4.17),ls); <br /> draw((1.5,6.17)--(1.5,2),ls); <br /> draw((2,5.79)--(2,2.67),ls); <br /> draw(rightanglemark((0,0),(1.5,2),(4.17,0)));<br /> &lt;/asy&gt;<br /> &lt;center&gt;<br /> ([http://www.cut-the-knot.org/pythagoras/PythLoomis25G.shtml Cut-the-knot], [https://artofproblemsolving.com/wiki/index.php/Proofs_without_words Proofs without words])&lt;/center&gt;</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Triangle_numbers&diff=123336 Triangle numbers 2020-05-31T00:51:52Z <p>Mag1c: Redirect to Triangular numbers page</p> <hr /> <div>#REDIRECT[[Triangular_number]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Determinant&diff=122196 Determinant 2020-05-09T04:31:14Z <p>Mag1c: determinants in terms of simpler determinants</p> <hr /> <div>The '''determinant''' is an important notion in [[linear algebra]].<br /> <br /> For an &lt;math&gt;n\times n&lt;/math&gt; matrix &lt;math&gt;a = (a_{ij})&lt;/math&gt;, the determinant is defined by<br /> the sum<br /> &lt;cmath&gt; \begin{align*}<br /> \det a &amp;= \sum_{\sigma \in S_n} \text{sign} (\sigma) a_{1\sigma(1)}<br /> a_{2\sigma(2)} \dotsc a_{n\sigma(n)} \\<br /> &amp;= \sum_{\sigma \in S_n} \text{sign}(\sigma) \prod_{i=1}^n a_{i\sigma(i)} ,<br /> \end{align*} &lt;/cmath&gt;<br /> where &lt;math&gt;S_n&lt;/math&gt; is the set of all [[permutation]]s on the set<br /> &lt;math&gt;\{ 1, \dotsc, n\}&lt;/math&gt;, and &lt;math&gt;\text{sign}(\sigma)&lt;/math&gt; is the<br /> [[Symmetric_group#Even_and_Odd_Permutations.3B_Alternating_Groups |parity]]<br /> of the permutation &lt;math&gt;\sigma&lt;/math&gt;.<br /> <br /> For example, the determinant of a &lt;math&gt;2\times 2&lt;/math&gt; matrix<br /> &lt;math&gt;\begin{pmatrix} a&amp;b \\c&amp;d \end{pmatrix}&lt;/math&gt; is &lt;math&gt;ad - bc&lt;/math&gt;.<br /> <br /> This quantity may seem unwieldy, but surprisingly, it is multiplicative.<br /> That is, for any &lt;math&gt;n \times n&lt;/math&gt; matrices &lt;math&gt;a,b&lt;/math&gt; (over the same commutative<br /> [[field]]),<br /> &lt;cmath&gt; \det (ab) = \det (a) \cdot \det (b) . &lt;/cmath&gt;<br /> <br /> More generally, if &lt;math&gt;F&lt;/math&gt; is a [[commutative]] [[field]] and &lt;math&gt;a&lt;/math&gt;<br /> is an element of a (strictly [[power associative]]) &lt;math&gt;n&lt;/math&gt;-dimensional<br /> &lt;math&gt;F&lt;/math&gt;-[[algebra (structure) |algebra]] &lt;math&gt;A&lt;/math&gt;, then the determinant of &lt;math&gt;a&lt;/math&gt;<br /> is &lt;math&gt;(-1)^n&lt;/math&gt; times the constant term of the [[characteristic polynomial]]<br /> of &lt;math&gt;a&lt;/math&gt;.<br /> <br /> Our generalized determinants also satisfy the multiplicative property<br /> when &lt;math&gt;A&lt;/math&gt; is [[associative]].<br /> <br /> == Determinants in Terms of Simpler Determinants ==<br /> <br /> An &lt;math&gt;n\times n&lt;/math&gt; determinant can be written in terms of &lt;math&gt;(n-1)\times(n-1)&lt;/math&gt; determinants:<br /> &lt;cmath&gt;\det(a_{n\times n})=\sum_{i=1}^n(-1)^{i+1}\det(m_i)&lt;/cmath&gt;<br /> where &lt;math&gt;m_i&lt;/math&gt; is the &lt;math&gt;(n-1)\times(n-1)&lt;/math&gt; matrix formed by removing the &lt;math&gt;1&lt;/math&gt;st row and &lt;math&gt;i&lt;/math&gt;th column from &lt;math&gt;a&lt;/math&gt;:<br /> &lt;cmath&gt;m_i=\begin{pmatrix}<br /> \blacksquare &amp; \blacksquare &amp; ... &amp; \blacksquare &amp; \blacksquare &amp; \blacksquare &amp; ... &amp; \blacksquare &amp; \blacksquare\\<br /> a_{21} &amp; a_{22} &amp; ... &amp; a_{2,i-1} &amp; \blacksquare &amp; a_{2,i+1} &amp; ... &amp; a_{2,n-1} &amp; a_{2n}\\<br /> a_{31} &amp; a_{32} &amp; ... &amp; a_{3,i-1} &amp; \blacksquare &amp; a_{3,i+1} &amp; ... &amp; a_{3,n-1} &amp; a_{3n}\\<br /> &amp;&amp;&amp;&amp;\vdots&amp;&amp;&amp;&amp;\\<br /> a_{n1} &amp; a_{n2} &amp; ... &amp; a_{n,i-1} &amp; \blacksquare &amp; a_{n,i+1} &amp; ... &amp; a_{n,n-1} &amp; a_{nn}<br /> \end{pmatrix}=\begin{pmatrix}<br /> a_{21} &amp; ... &amp; a_{2,i-1} &amp; a_{2,i+1} &amp; ... &amp; a_{2n}\\<br /> a_{31} &amp; ... &amp; a_{3,i-1} &amp; a_{3,i+1} &amp; ... &amp; a_{3n}\\<br /> &amp;&amp;\vdots&amp;\vdots&amp;&amp;&amp;\\<br /> a_{n1} &amp; ... &amp; a_{n,i-1} &amp; a_{n,i+1} &amp; ... &amp; a_{nn}<br /> \end{pmatrix}&lt;/cmath&gt;<br /> <br /> This makes it easy to see why the determinant of an &lt;math&gt;n\times n&lt;/math&gt; matrix &lt;math&gt;a&lt;/math&gt; is the sum of the diagonals labeled &lt;math&gt;+&lt;/math&gt;, minus the sum of the diagonals labeled &lt;math&gt;-&lt;/math&gt;, where &quot;diagonal&quot; means the product of the terms along it:<br /> &lt;center&gt;&lt;asy&gt;<br /> size(300);<br /> draw(arc((3.3,-1.5), 4, 155, 205));<br /> draw(arc((-0.3,-1.5), 4, -25, 25));<br /> label(&quot;$a_{11}$&quot;,(0,0));<br /> label(&quot;$a_{12}$&quot;,(1,0));<br /> label(&quot;$...$&quot;,(2,0));<br /> label(&quot;$a_{1n}$&quot;,(3,0));<br /> <br /> label(&quot;$a_{21}$&quot;,(0,-1));<br /> label(&quot;$a_{22}$&quot;,(1,-1));<br /> label(&quot;$...$&quot;,(2,-1));<br /> label(&quot;$a_{2n}$&quot;,(3,-1));<br /> <br /> label(&quot;$\vdots$&quot;,(0,-2));<br /> label(&quot;$\ddots$&quot;,(2,-2));<br /> <br /> label(&quot;$a_{n1}$&quot;,(0,-3));<br /> label(&quot;$a_{n2}$&quot;,(1,-3));<br /> label(&quot;$...$&quot;,(2,-3));<br /> label(&quot;$a_{nn}$&quot;,(3,-3));<br /> label(&quot;$a_{11}$&quot;,(0,0));<br /> label(&quot;$a_{12}$&quot;,(1,0));<br /> label(&quot;$...$&quot;,(2,0));<br /> label(&quot;$a_{1n}$&quot;,(3,0));<br /> <br /> <br /> label(&quot;$a_{11}$&quot;,(4,0));<br /> label(&quot;$a_{12}$&quot;,(5,0));<br /> label(&quot;$...$&quot;,(6,0));<br /> label(&quot;$a_{1n}$&quot;,(7,0));<br /> <br /> label(&quot;$a_{21}$&quot;,(4,-1));<br /> label(&quot;$a_{22}$&quot;,(5,-1));<br /> label(&quot;$...$&quot;,(6,-1));<br /> label(&quot;$a_{2n}$&quot;,(7,-1));<br /> <br /> label(&quot;$\vdots$&quot;,(4,-2));<br /> label(&quot;$\ddots$&quot;,(6,-2));<br /> <br /> label(&quot;$a_{n1}$&quot;,(4,-3));<br /> label(&quot;$a_{n2}$&quot;,(5,-3));<br /> label(&quot;$...$&quot;,(6,-3));<br /> label(&quot;$a_{nn}$&quot;,(7,-3));<br /> <br /> for (int i=0; i&lt;4; ++i)<br /> {<br /> draw((i-0.2,0.2)--(i+3-0.2,-3+0.2));<br /> label(&quot;$+$&quot;,(i-0.4,0.4));<br /> }<br /> for (int i=0; i&lt;4; ++i)<br /> {<br /> draw((i+0.2+4,0.2)--(i-3+4+0.2,-3+0.2));<br /> label(&quot;$-$&quot;,(i+0.4+4,0.4));<br /> }<br /> &lt;/asy&gt;&lt;/center&gt;<br /> <br /> == Matrix Determinants are Multiplicative ==<br /> <br /> In this section we prove that the determinant as defined for<br /> &lt;math&gt;n\times n&lt;/math&gt; matrices is multiplicative.<br /> <br /> We first note that<br /> &lt;cmath&gt; \begin{align*}<br /> \det a \det b &amp;= \sum_{\sigma \in S_n} (-1)^{\sigma}<br /> \prod_{i=1}^n a_{i\sigma(i)}<br /> \sum_{\tau \in S_n} (-1)^{\tau} \prod_{j=1}^n b_{j\tau(j)} \\<br /> &amp;= \sum_{\sigma, \tau \in S_n} (-1)^{\tau \sigma}<br /> \prod_{i=1}^n a_{i\sigma(i)} \cdot \prod_{j=1}^n b_{\sigma(j)<br /> \tau (\sigma(j))} \\<br /> &amp;= \sum_{\sigma, \tau \in S_n} (-1)^{\tau \sigma}<br /> \prod_{i=1}^n a_{i \sigma(i)} b_{\sigma(i) \tau\circ \sigma(i)}<br /> ,<br /> \end{align*} &lt;/cmath&gt;<br /> from rearrangements of terms. If we let &lt;math&gt;\upsilon = \tau \circ \sigma&lt;/math&gt;,<br /> we then have<br /> &lt;cmath&gt; \begin{align}<br /> \nonumber<br /> \det a \det b &amp;= \sum_{\upsilon \in S_n} (-1)^\upsilon<br /> \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i\sigma(i)} b_{\sigma(i)<br /> \upsilon(i)} \\<br /> &amp;= \sum_{\sigma \in S_n} \sum_{\upsilon \in S_n} (-1)^\upsilon<br /> \prod_{i=1}^n a_{i\sigma(i)} b_{\sigma(i) \upsilon(i)} .<br /> \end{align} &lt;/cmath&gt;<br /> <br /> On the other hand,<br /> &lt;cmath&gt; \begin{align*}<br /> \det ab &amp;= \sum_{\upsilon \in S_n} (-1)^\upsilon \prod_{i=1}^n (ab)_{i<br /> \upsilon(i)} \\<br /> &amp;= \sum_{\upsilon \in S_n} (-1)^\upsilon \prod_{i=1}^n \sum_{j=1}^n<br /> a_{ij} b_{j \upsilon(i)} \\<br /> &amp;= \sum_{\upsilon \in S_n} (-1)^\upsilon \sum_{\phi \in [n]^{[n]}}<br /> \prod_{i=1}^n a_{i \phi(i)} b_{\phi(i) \upsilon(i)} \\<br /> &amp;= \sum_{\phi \in [n]^{[n]}} \sum_{\upsilon \in S_n} (-1)^\upsilon<br /> \prod_{i=1}^n a_{i \phi(i)} b_{\phi(i) \upsilon(i)} ,<br /> \end{align*} &lt;/cmath&gt;<br /> where &lt;math&gt;[n]&lt;/math&gt; is the set &lt;math&gt;\{1, \dotsc, n\}&lt;/math&gt;, and &lt;math&gt;[n]^{[n]}&lt;/math&gt; is the<br /> set of [[function]]s mapping &lt;math&gt;[n]&lt;/math&gt; into itself.<br /> <br /> From equation (1), it thus suffices to show that if<br /> &lt;math&gt;\phi \in [n]^{[n]}&lt;/math&gt; is not a permutation on &lt;math&gt;[n]&lt;/math&gt;, then<br /> &lt;cmath&gt; \sum_{\upsilon \in S_n} (-1)^\upsilon \prod_{i=1}^n<br /> a_{i\phi(i)} b_{\phi(i) \upsilon(i)} = 0 . \qquad (2) &lt;/cmath&gt;<br /> <br /> To this end, suppose that &lt;math&gt;\phi&lt;/math&gt; is not a permutation. Then<br /> there exist distinct [[integer]]s &lt;math&gt;a,b \in [n]&lt;/math&gt; such that<br /> &lt;math&gt;\phi(a) = \phi(b)&lt;/math&gt;. Let &lt;math&gt;\psi&lt;/math&gt; be the permutation on &lt;math&gt;[n]&lt;/math&gt;<br /> that transposes &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; while fixing everything else. Then<br /> &lt;cmath&gt; \prod_{i=1}^n a_{i \phi(i)} b_{\phi(i) \upsilon(i)}<br /> = \prod_{i=1}^n a_{i\phi(i)} b_{\phi(i) \upsilon(\psi(i))} , &lt;/cmath&gt;<br /> as the latter product is the same as the former, with two terms<br /> switched. On the other hand &lt;math&gt;\psi&lt;/math&gt; is an odd permutation, so<br /> &lt;cmath&gt; (-1)^\upsilon \prod_{i=1}^n a_{i \phi(i)} b_{\phi(i) \upsilon(i)}<br /> + (-1)^{\upsilon \psi} \prod_{i=1}^n a_{i \phi(i)}<br /> b_{\phi(i) \upsilon(\psi(i))} =0 . &lt;/cmath&gt;<br /> Since &lt;math&gt;\psi = \psi^{-1}&lt;/math&gt;, we can partition the elements of &lt;math&gt;S_n&lt;/math&gt;<br /> into pairs &lt;math&gt;\{ \sigma, \sigma \circ \tau\}&lt;/math&gt; for which the equation<br /> above holds. Equation 2 then follows, and we are done. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> == Equivalence of Definitions ==<br /> <br /> We now prove that our two definitions are equivalent. We first<br /> note that the definitions coincide in the case of<br /> [[upper_triangular matrix | upper-triangular matrices]], as<br /> each entry in the diagonal of an upper-triangular matrix corresponds<br /> to a (generalized) [[eigenvalue]] of the matrix.<br /> <br /> We now use the fact that every element &lt;math&gt;a&lt;/math&gt; of &lt;math&gt;M_n(F)&lt;/math&gt; is similar to<br /> an upper triangular matrix; that is, there exists an upper triangular<br /> matrix &lt;math&gt;b&lt;/math&gt; and an invertible matrix &lt;math&gt;c&lt;/math&gt; such that<br /> &lt;cmath&gt; a = c b c^{-1} . &lt;/cmath&gt;<br /> Writing &lt;math&gt;\det\nolimits'&lt;/math&gt; for our specialized determinant for matrices and<br /> &lt;math&gt;\det&lt;/math&gt; for our generalized definition<br /> with the characteristic polynomial, we have<br /> &lt;cmath&gt; \begin{align*}<br /> \det\nolimits'(a) = \det\nolimits'(cbc^{-1})<br /> &amp;= \det\nolimits'(c) \cdot \det\nolimits'(bc^{-1}) \\<br /> &amp;= \det\nolimits'(bc^{-1}) \det\nolimits'(c) \\<br /> &amp;= \det\nolimits'(b) = \det b = \det a ,<br /> \end{align*} &lt;/cmath&gt;<br /> as the characteristic polynomial does not change under<br /> [[automorphism]]s of &lt;math&gt;A&lt;/math&gt; that fix &lt;math&gt;F&lt;/math&gt;. Our two definitions<br /> are therefore equivalent. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> == References ==<br /> <br /> * Garibaldi, Skip, &quot;The Characteristic Polynomial and Determinant Are Not Ad Hoc Constructions&quot;. ''American Mathematical Monthly'' '''111''' (2004), no. 9, p. 761, Nov. 2004. [http://www.mathcs.emory.edu/~skip/dets/dets.pdf Preprint]<br /> <br /> == See also ==<br /> <br /> * [[Characteristic polynomial]]<br /> * [[Upper triangular matrix]]<br /> <br /> [[Category:Linear algebra]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=File:Slantasymptote.png&diff=122171 File:Slantasymptote.png 2020-05-08T08:54:33Z <p>Mag1c: Mag1c uploaded a new version of File:Slantasymptote.png</p> <hr /> <div>== Summary ==<br /> slant asymptote</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Asymptote_(geometry)&diff=122170 Asymptote (geometry) 2020-05-08T08:05:17Z <p>Mag1c: move picture</p> <hr /> <div>:''For the vector graphics language, see [[Asymptote (Vector Graphics Language)]].''<br /> <br /> An '''asymptote''' is a [[line]] or [[curve]] that a certain [[function]] approaches.<br /> [[File:Asymptote_graph.png|thumb|300px|The function &lt;math&gt;y=\tfrac{2x}{x-2}&lt;/math&gt; has a vertical asymptote at x=2 and a horizontal asymptote at y=2]]<br /> <br /> Linear asymptotes can be of three different kinds: horizontal, vertical or slant (oblique). <br /> <br /> <br /> == Vertical Asymptotes ==<br /> The vertical asymptote can be found by finding values of &lt;math&gt;x&lt;/math&gt; that make the function undefined. Generally, it is found by setting the denominator of a rational function to zero.<br /> <br /> If the numerator and denominator of a rational function share a factor, this factor is not a vertical asymptote. Instead, it appears as a hole in the graph.<br /> <br /> A rational function may have more than one vertical asymptote.<br /> <br /> ===Example Problems===<br /> Find the vertical asymptotes of 1) &lt;math&gt;y = \frac{1}{x^2-5x}&lt;/math&gt; 2) &lt;math&gt;\tan 3x&lt;/math&gt;.<br /> <br /> ====Solution====<br /> 1) To find the vertical asymptotes, let &lt;math&gt;x^2-5x=0&lt;/math&gt;. Solving the equation:<br /> <br /> &lt;cmath&gt;\begin{eqnarray*}x^2-5x&amp;=&amp;0\\x&amp;=&amp;\boxed{0,5}\end{eqnarray*}&lt;/cmath&gt;<br /> <br /> So the vertical asymptotes are &lt;math&gt;x=0,x=5&lt;/math&gt;.<br /> <br /> 2) Since &lt;math&gt;\tan 3x = \frac{\sin 3x}{\cos 3x}&lt;/math&gt;, we need to find where &lt;math&gt;\cos 3x = 0&lt;/math&gt;. The cosine function is zero at &lt;math&gt;\frac{\pi}{2} + n\pi&lt;/math&gt; for all [[integer]]s &lt;math&gt;n&lt;/math&gt;; thus the functions is undefined at &lt;math&gt;x=\frac{\pi}{6} + \frac{n\pi}{3}&lt;/math&gt;.<br /> <br /> == Horizontal Asymptotes ==<br /> For rational functions in the form of &lt;math&gt;\frac{P(x)}{Q(x)}&lt;/math&gt; where &lt;math&gt;P(x), Q(x)&lt;/math&gt; are both [[polynomial]]s:<br /> <br /> 1. If the [[Degree of a polynomial | degree ]] of &lt;math&gt;Q(x)&lt;/math&gt; is greater than that of the degree of &lt;math&gt;P(x)&lt;/math&gt;, then the horizontal asymptote is at &lt;math&gt;y = 0&lt;/math&gt;. This can be seen by noting that as &lt;math&gt;x&lt;/math&gt; increases, &lt;math&gt;Q(x)&lt;/math&gt; increases much faster than &lt;math&gt;P(x)&lt;/math&gt; does. Since the denominator increases faster than the numerator, as x approaches infinity, y gets smaller until it approaches zero. A similar trend can be seen as x decreases.<br /> <br /> 2. If the degree of &lt;math&gt;Q(x)&lt;/math&gt; is equal to that of the degree of &lt;math&gt;P(x)&lt;/math&gt;, then the horizontal asymptote is at the quotient of the leading coefficient of &lt;math&gt;P(x)&lt;/math&gt; over the leading coefficient of &lt;math&gt;Q(x)&lt;/math&gt;. <br /> <br /> 3. If the degree of &lt;math&gt;Q(x)&lt;/math&gt; is less than the degree of &lt;math&gt;P(x)&lt;/math&gt;, see below (slanted asymptotes)<br /> <br /> A function may not have more than one horizontal asymptote. Functions with a &quot;middle section&quot; may cross the horizontal asymptote at one point. To find this point, set y=horizontal asymptote and solve.<br /> <br /> ===Example Problem===<br /> Find the horizontal asymptote of &lt;math&gt;f(x) = \frac{x^2 - 3x + 2}{-2x^2 + 15x + 10000}&lt;/math&gt;.<br /> <br /> ====Solution====<br /> The numerator has the same degree as the denominator, so the horizontal asymptote is the quotient of the leading coefficients:<br /> &lt;math&gt;y= \frac {1} {-2}&lt;/math&gt;<br /> <br /> == Slant Asymptotes ==<br /> <br /> [[File:Slantasymptote.png|thumb|500px|The function &lt;math&gt;y=\tfrac{x^2+2x+4} {x+1}&lt;/math&gt; has a slant asymptote at y=x+1 ]]<br /> <br /> For rational functions &lt;math&gt;\frac{P(x)}{Q(x)}&lt;/math&gt;, a slant asymptote occurs when the degree of &lt;math&gt;P(x)&lt;/math&gt; is one greater than the degree of &lt;math&gt;Q(x)&lt;/math&gt;. If the degree of &lt;math&gt;P(x)&lt;/math&gt; is two or more greater than the degree of &lt;math&gt;Q(x)&lt;/math&gt;, then we get a curved asymptote. Again, like horizontal asymptotes, it is possible to get crossing points of slant asymptotes.<br /> <br /> For rational functions, we can find the slant asymptote simply by long division, omitting the remainder and setting y=quotient.<br /> <br /> ===Example Problem===<br /> <br /> Find the slant asymptote of &lt;math&gt;y= \frac{x^2+2x+4} {x+1}&lt;/math&gt;<br /> <br /> '''Solution'''<br /> <br /> &lt;math&gt;\frac{x^2+2x+4}{x+1}= x+1+\frac{3} {x+1}&lt;/math&gt;<br /> <br /> <br /> The slant asymptote is &lt;math&gt;y=x+1&lt;/math&gt;<br /> <br /> ==External Links==<br /> 3 minute asymptote lesson: [http://www.youtube.com/watch?v=4Cqm07W2teM&amp;feature=plcp]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Asymptote_(geometry)&diff=122169 Asymptote (geometry) 2020-05-08T08:04:11Z <p>Mag1c: resize picture</p> <hr /> <div>:''For the vector graphics language, see [[Asymptote (Vector Graphics Language)]].''<br /> <br /> An '''asymptote''' is a [[line]] or [[curve]] that a certain [[function]] approaches.<br /> [[File:Asymptote_graph.png|thumb|300px|The function &lt;math&gt;y=\tfrac{2x}{x-2}&lt;/math&gt; has a vertical asymptote at x=2 and a horizontal asymptote at y=2]]<br /> <br /> Linear asymptotes can be of three different kinds: horizontal, vertical or slant (oblique). <br /> <br /> <br /> == Vertical Asymptotes ==<br /> The vertical asymptote can be found by finding values of &lt;math&gt;x&lt;/math&gt; that make the function undefined. Generally, it is found by setting the denominator of a rational function to zero.<br /> <br /> If the numerator and denominator of a rational function share a factor, this factor is not a vertical asymptote. Instead, it appears as a hole in the graph.<br /> <br /> A rational function may have more than one vertical asymptote.<br /> <br /> ===Example Problems===<br /> Find the vertical asymptotes of 1) &lt;math&gt;y = \frac{1}{x^2-5x}&lt;/math&gt; 2) &lt;math&gt;\tan 3x&lt;/math&gt;.<br /> <br /> ====Solution====<br /> 1) To find the vertical asymptotes, let &lt;math&gt;x^2-5x=0&lt;/math&gt;. Solving the equation:<br /> <br /> &lt;cmath&gt;\begin{eqnarray*}x^2-5x&amp;=&amp;0\\x&amp;=&amp;\boxed{0,5}\end{eqnarray*}&lt;/cmath&gt;<br /> <br /> So the vertical asymptotes are &lt;math&gt;x=0,x=5&lt;/math&gt;.<br /> <br /> 2) Since &lt;math&gt;\tan 3x = \frac{\sin 3x}{\cos 3x}&lt;/math&gt;, we need to find where &lt;math&gt;\cos 3x = 0&lt;/math&gt;. The cosine function is zero at &lt;math&gt;\frac{\pi}{2} + n\pi&lt;/math&gt; for all [[integer]]s &lt;math&gt;n&lt;/math&gt;; thus the functions is undefined at &lt;math&gt;x=\frac{\pi}{6} + \frac{n\pi}{3}&lt;/math&gt;.<br /> <br /> == Horizontal Asymptotes ==<br /> For rational functions in the form of &lt;math&gt;\frac{P(x)}{Q(x)}&lt;/math&gt; where &lt;math&gt;P(x), Q(x)&lt;/math&gt; are both [[polynomial]]s:<br /> <br /> 1. If the [[Degree of a polynomial | degree ]] of &lt;math&gt;Q(x)&lt;/math&gt; is greater than that of the degree of &lt;math&gt;P(x)&lt;/math&gt;, then the horizontal asymptote is at &lt;math&gt;y = 0&lt;/math&gt;. This can be seen by noting that as &lt;math&gt;x&lt;/math&gt; increases, &lt;math&gt;Q(x)&lt;/math&gt; increases much faster than &lt;math&gt;P(x)&lt;/math&gt; does. Since the denominator increases faster than the numerator, as x approaches infinity, y gets smaller until it approaches zero. A similar trend can be seen as x decreases.<br /> <br /> 2. If the degree of &lt;math&gt;Q(x)&lt;/math&gt; is equal to that of the degree of &lt;math&gt;P(x)&lt;/math&gt;, then the horizontal asymptote is at the quotient of the leading coefficient of &lt;math&gt;P(x)&lt;/math&gt; over the leading coefficient of &lt;math&gt;Q(x)&lt;/math&gt;. <br /> <br /> 3. If the degree of &lt;math&gt;Q(x)&lt;/math&gt; is less than the degree of &lt;math&gt;P(x)&lt;/math&gt;, see below (slanted asymptotes)<br /> <br /> A function may not have more than one horizontal asymptote. Functions with a &quot;middle section&quot; may cross the horizontal asymptote at one point. To find this point, set y=horizontal asymptote and solve.<br /> <br /> ===Example Problem===<br /> Find the horizontal asymptote of &lt;math&gt;f(x) = \frac{x^2 - 3x + 2}{-2x^2 + 15x + 10000}&lt;/math&gt;.<br /> <br /> ====Solution====<br /> The numerator has the same degree as the denominator, so the horizontal asymptote is the quotient of the leading coefficients:<br /> &lt;math&gt;y= \frac {1} {-2}&lt;/math&gt;<br /> <br /> == Slant Asymptotes ==<br /> For rational functions &lt;math&gt;\frac{P(x)}{Q(x)}&lt;/math&gt;, a slant asymptote occurs when the degree of &lt;math&gt;P(x)&lt;/math&gt; is one greater than the degree of &lt;math&gt;Q(x)&lt;/math&gt;. If the degree of &lt;math&gt;P(x)&lt;/math&gt; is two or more greater than the degree of &lt;math&gt;Q(x)&lt;/math&gt;, then we get a curved asymptote. Again, like horizontal asymptotes, it is possible to get crossing points of slant asymptotes.<br /> <br /> For rational functions, we can find the slant asymptote simply by long division, omitting the remainder and setting y=quotient.<br /> <br /> ===Example Problem===<br /> [[File:Slantasymptote.png|thumb|500px|The function &lt;math&gt;y=\tfrac{x^2+2x+4} {x+1}&lt;/math&gt; has a slant asymptote at y=x+1 ]]<br /> <br /> Find the slant asymptote of &lt;math&gt;y= \frac{x^2+2x+4} {x+1}&lt;/math&gt;<br /> <br /> '''Solution'''<br /> <br /> &lt;math&gt;\frac{x^2+2x+4}{x+1}= x+1+\frac{3} {x+1}&lt;/math&gt;<br /> <br /> <br /> The slant asymptote is &lt;math&gt;y=x+1&lt;/math&gt;<br /> <br /> ==External Links==<br /> 3 minute asymptote lesson: [http://www.youtube.com/watch?v=4Cqm07W2teM&amp;feature=plcp]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Asymptote_(geometry)&diff=122168 Asymptote (geometry) 2020-05-08T08:02:20Z <p>Mag1c: move picture</p> <hr /> <div>:''For the vector graphics language, see [[Asymptote (Vector Graphics Language)]].''<br /> <br /> An '''asymptote''' is a [[line]] or [[curve]] that a certain [[function]] approaches.<br /> [[File:Asymptote_graph.png|thumb|300px|The function &lt;math&gt;y=\tfrac{2x}{x-2}&lt;/math&gt; has a vertical asymptote at x=2 and a horizontal asymptote at y=2]]<br /> <br /> Linear asymptotes can be of three different kinds: horizontal, vertical or slanted (oblique). <br /> <br /> <br /> == Vertical Asymptotes ==<br /> The vertical asymptote can be found by finding values of &lt;math&gt;x&lt;/math&gt; that make the function undefined. Generally, it is found by setting the denominator of a rational function to zero.<br /> <br /> If the numerator and denominator of a rational function share a factor, this factor is not a vertical asymptote. Instead, it appears as a hole in the graph.<br /> <br /> A rational function may have more than one vertical asymptote.<br /> <br /> ===Example Problems===<br /> Find the vertical asymptotes of 1) &lt;math&gt;y = \frac{1}{x^2-5x}&lt;/math&gt; 2) &lt;math&gt;\tan 3x&lt;/math&gt;.<br /> <br /> ====Solution====<br /> 1) To find the vertical asymptotes, let &lt;math&gt;x^2-5x=0&lt;/math&gt;. Solving the equation:<br /> <br /> &lt;cmath&gt;\begin{eqnarray*}x^2-5x&amp;=&amp;0\\x&amp;=&amp;\boxed{0,5}\end{eqnarray*}&lt;/cmath&gt;<br /> <br /> So the vertical asymptotes are &lt;math&gt;x=0,x=5&lt;/math&gt;.<br /> <br /> 2) Since &lt;math&gt;\tan 3x = \frac{\sin 3x}{\cos 3x}&lt;/math&gt;, we need to find where &lt;math&gt;\cos 3x = 0&lt;/math&gt;. The cosine function is zero at &lt;math&gt;\frac{\pi}{2} + n\pi&lt;/math&gt; for all [[integer]]s &lt;math&gt;n&lt;/math&gt;; thus the functions is undefined at &lt;math&gt;x=\frac{\pi}{6} + \frac{n\pi}{3}&lt;/math&gt;.<br /> <br /> == Horizontal Asymptotes ==<br /> For rational functions in the form of &lt;math&gt;\frac{P(x)}{Q(x)}&lt;/math&gt; where &lt;math&gt;P(x), Q(x)&lt;/math&gt; are both [[polynomial]]s:<br /> <br /> 1. If the [[Degree of a polynomial | degree ]] of &lt;math&gt;Q(x)&lt;/math&gt; is greater than that of the degree of &lt;math&gt;P(x)&lt;/math&gt;, then the horizontal asymptote is at &lt;math&gt;y = 0&lt;/math&gt;. This can be seen by noting that as &lt;math&gt;x&lt;/math&gt; increases, &lt;math&gt;Q(x)&lt;/math&gt; increases much faster than &lt;math&gt;P(x)&lt;/math&gt; does. Since the denominator increases faster than the numerator, as x approaches infinity, y gets smaller until it approaches zero. A similar trend can be seen as x decreases.<br /> <br /> 2. If the degree of &lt;math&gt;Q(x)&lt;/math&gt; is equal to that of the degree of &lt;math&gt;P(x)&lt;/math&gt;, then the horizontal asymptote is at the quotient of the leading coefficient of &lt;math&gt;P(x)&lt;/math&gt; over the leading coefficient of &lt;math&gt;Q(x)&lt;/math&gt;. <br /> <br /> 3. If the degree of &lt;math&gt;Q(x)&lt;/math&gt; is less than the degree of &lt;math&gt;P(x)&lt;/math&gt;, see below (slanted asymptotes)<br /> <br /> A function may not have more than one horizontal asymptote. Functions with a &quot;middle section&quot; may cross the horizontal asymptote at one point. To find this point, set y=horizontal asymptote and solve.<br /> <br /> ===Example Problem===<br /> Find the horizontal asymptote of &lt;math&gt;f(x) = \frac{x^2 - 3x + 2}{-2x^2 + 15x + 10000}&lt;/math&gt;.<br /> <br /> ====Solution====<br /> The numerator has the same degree as the denominator, so the horizontal asymptote is the quotient of the leading coefficients:<br /> &lt;math&gt;y= \frac {1} {-2}&lt;/math&gt;<br /> <br /> == Slant (Oblique) Asymptotes ==<br /> For rational functions &lt;math&gt;\frac{P(x)}{Q(x)}&lt;/math&gt;, a slant asymptote occurs when the degree of &lt;math&gt;P(x)&lt;/math&gt; is one greater than the degree of &lt;math&gt;Q(x)&lt;/math&gt;. If the degree of &lt;math&gt;P(x)&lt;/math&gt; is two or more greater than the degree of &lt;math&gt;Q(x)&lt;/math&gt;, then we get a curved asymptote. Again, like horizontal asymptotes, it is possible to get crossing points of slant asymptotes.<br /> <br /> For rational functions, we can find the slant asymptote simply by long division, omitting the remainder and setting y=quotient.<br /> <br /> ===Example Problem===<br /> [[File:Slantasymptote.png|thumb|300px|The function &lt;math&gt;y=\tfrac{x^2+2x+4} {x+1}&lt;/math&gt; has a slant asymptote at y=x+1 ]]<br /> <br /> Find the slant asymptote of &lt;math&gt;y= \frac{x^2+2x+4} {x+1}&lt;/math&gt;<br /> <br /> '''Solution'''<br /> <br /> &lt;math&gt;\frac{x^2+2x+4}{x+1}= x+1+\frac{3} {x+1}&lt;/math&gt;<br /> <br /> <br /> The slant asymptote is &lt;math&gt;y=x+1&lt;/math&gt;<br /> <br /> ==External Links==<br /> 3 minute asymptote lesson: [http://www.youtube.com/watch?v=4Cqm07W2teM&amp;feature=plcp]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Asymptote_(geometry)&diff=122167 Asymptote (geometry) 2020-05-08T08:00:49Z <p>Mag1c: graph of slant asymptote</p> <hr /> <div>:''For the vector graphics language, see [[Asymptote (Vector Graphics Language)]].''<br /> <br /> An '''asymptote''' is a [[line]] or [[curve]] that a certain [[function]] approaches.<br /> [[File:Asymptote_graph.png|thumb|300px|The function &lt;math&gt;y=\tfrac{2x}{x-2}&lt;/math&gt; has a vertical asymptote at x=2 and a horizontal asymptote at y=2]]<br /> <br /> Linear asymptotes can be of three different kinds: horizontal, vertical or slanted (oblique). <br /> <br /> <br /> == Vertical Asymptotes ==<br /> The vertical asymptote can be found by finding values of &lt;math&gt;x&lt;/math&gt; that make the function undefined. Generally, it is found by setting the denominator of a rational function to zero.<br /> <br /> If the numerator and denominator of a rational function share a factor, this factor is not a vertical asymptote. Instead, it appears as a hole in the graph.<br /> <br /> A rational function may have more than one vertical asymptote.<br /> <br /> ===Example Problems===<br /> Find the vertical asymptotes of 1) &lt;math&gt;y = \frac{1}{x^2-5x}&lt;/math&gt; 2) &lt;math&gt;\tan 3x&lt;/math&gt;.<br /> <br /> ====Solution====<br /> 1) To find the vertical asymptotes, let &lt;math&gt;x^2-5x=0&lt;/math&gt;. Solving the equation:<br /> <br /> &lt;cmath&gt;\begin{eqnarray*}x^2-5x&amp;=&amp;0\\x&amp;=&amp;\boxed{0,5}\end{eqnarray*}&lt;/cmath&gt;<br /> <br /> So the vertical asymptotes are &lt;math&gt;x=0,x=5&lt;/math&gt;.<br /> <br /> 2) Since &lt;math&gt;\tan 3x = \frac{\sin 3x}{\cos 3x}&lt;/math&gt;, we need to find where &lt;math&gt;\cos 3x = 0&lt;/math&gt;. The cosine function is zero at &lt;math&gt;\frac{\pi}{2} + n\pi&lt;/math&gt; for all [[integer]]s &lt;math&gt;n&lt;/math&gt;; thus the functions is undefined at &lt;math&gt;x=\frac{\pi}{6} + \frac{n\pi}{3}&lt;/math&gt;.<br /> <br /> == Horizontal Asymptotes ==<br /> For rational functions in the form of &lt;math&gt;\frac{P(x)}{Q(x)}&lt;/math&gt; where &lt;math&gt;P(x), Q(x)&lt;/math&gt; are both [[polynomial]]s:<br /> <br /> 1. If the [[Degree of a polynomial | degree ]] of &lt;math&gt;Q(x)&lt;/math&gt; is greater than that of the degree of &lt;math&gt;P(x)&lt;/math&gt;, then the horizontal asymptote is at &lt;math&gt;y = 0&lt;/math&gt;. This can be seen by noting that as &lt;math&gt;x&lt;/math&gt; increases, &lt;math&gt;Q(x)&lt;/math&gt; increases much faster than &lt;math&gt;P(x)&lt;/math&gt; does. Since the denominator increases faster than the numerator, as x approaches infinity, y gets smaller until it approaches zero. A similar trend can be seen as x decreases.<br /> <br /> 2. If the degree of &lt;math&gt;Q(x)&lt;/math&gt; is equal to that of the degree of &lt;math&gt;P(x)&lt;/math&gt;, then the horizontal asymptote is at the quotient of the leading coefficient of &lt;math&gt;P(x)&lt;/math&gt; over the leading coefficient of &lt;math&gt;Q(x)&lt;/math&gt;. <br /> <br /> 3. If the degree of &lt;math&gt;Q(x)&lt;/math&gt; is less than the degree of &lt;math&gt;P(x)&lt;/math&gt;, see below (slanted asymptotes)<br /> <br /> A function may not have more than one horizontal asymptote. Functions with a &quot;middle section&quot; may cross the horizontal asymptote at one point. To find this point, set y=horizontal asymptote and solve.<br /> <br /> ===Example Problem===<br /> Find the horizontal asymptote of &lt;math&gt;f(x) = \frac{x^2 - 3x + 2}{-2x^2 + 15x + 10000}&lt;/math&gt;.<br /> <br /> ====Solution====<br /> The numerator has the same degree as the denominator, so the horizontal asymptote is the quotient of the leading coefficients:<br /> &lt;math&gt;y= \frac {1} {-2}&lt;/math&gt;<br /> <br /> == Slant (Oblique) Asymptotes ==<br /> For rational functions &lt;math&gt;\frac{P(x)}{Q(x)}&lt;/math&gt;, a slant asymptote occurs when the degree of &lt;math&gt;P(x)&lt;/math&gt; is one greater than the degree of &lt;math&gt;Q(x)&lt;/math&gt;. If the degree of &lt;math&gt;P(x)&lt;/math&gt; is two or more greater than the degree of &lt;math&gt;Q(x)&lt;/math&gt;, then we get a curved asymptote. Again, like horizontal asymptotes, it is possible to get crossing points of slant asymptotes.<br /> <br /> For rational functions, we can find the slant asymptote simply by long division, omitting the remainder and setting y=quotient.<br /> <br /> ===Example Problem===<br /> Find the slant asymptote of &lt;math&gt;y= \frac{x^2+2x+4} {x+1}&lt;/math&gt;<br /> <br /> '''Solution'''<br /> <br /> &lt;math&gt;\frac{x^2+2x+4}{x+1}= x+1+\frac{3} {x+1}&lt;/math&gt;<br /> <br /> <br /> The slant asymptote is &lt;math&gt;y=x+1&lt;/math&gt;<br /> <br /> [[File:Slantasymptote.png|thumb|300px|The function &lt;math&gt;y=\tfrac{x^2+2x+4} {x+1}&lt;/math&gt; has a slant asymptote at y=x+1 ]]<br /> <br /> ==External Links==<br /> 3 minute asymptote lesson: [http://www.youtube.com/watch?v=4Cqm07W2teM&amp;feature=plcp]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=File:Slantasymptote.png&diff=122166 File:Slantasymptote.png 2020-05-08T07:54:23Z <p>Mag1c: slant asymptote</p> <hr /> <div>== Summary ==<br /> slant asymptote</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Ball-and-urn&diff=114528 Ball-and-urn 2020-01-09T03:28:56Z <p>Mag1c: /* Reasoning (One of Several) */</p> <hr /> <div>The '''ball-and-urn''' technique, also known as '''stars-and-bars''', is a commonly used technique in [[combinatorics]].<br /> <br /> It is used to solve problems of the form: how many ways can one distribute &lt;math&gt;k&lt;/math&gt; indistinguishable objects into &lt;math&gt;n&lt;/math&gt; distinguishable bins? We can imagine this as finding the number of ways to drop &lt;math&gt;k&lt;/math&gt; balls into &lt;math&gt;n&lt;/math&gt; urns, or equivalently to arrange &lt;math&gt;k&lt;/math&gt; balls and &lt;math&gt;n-1&lt;/math&gt; dividers. For example, &lt;cmath&gt;****||&lt;/cmath&gt;&lt;cmath&gt;***|*|&lt;/cmath&gt;&lt;cmath&gt;*|**|*&lt;/cmath&gt;&lt;cmath&gt;...&lt;/cmath&gt; represent the ways to put &lt;math&gt;k=4&lt;/math&gt; objects in &lt;math&gt;n=3&lt;/math&gt; bins. The number of ways to do such is &lt;math&gt;{n+k-1 \choose k}&lt;/math&gt;.<br /> <br /> <br /> == Reasoning (One of Several) ==<br /> <br /> Arranging &lt;math&gt;k&lt;/math&gt; *'s and &lt;math&gt;n-1&lt;/math&gt; |'s is the same as saying there are &lt;math&gt;k+n-1&lt;/math&gt; positions: &lt;cmath&gt;\underbrace{\_~~ \_~~ \_~~ \_~~ \_~~ \_~~}_{k+n-1}&lt;/cmath&gt; and you want to fill &lt;math&gt;k&lt;/math&gt; of them with *'s and the rest of them with |'s. Thus you are choosing &lt;math&gt;k&lt;/math&gt; positions out of &lt;math&gt;n+k-1&lt;/math&gt; total positions, resulting in a total of &lt;math&gt;{n+k-1\choose k}&lt;/math&gt; ways.<br /> <br /> == Reasoning (One of Several) ==<br /> If you could only put one ball in each urn, then there would be &lt;math&gt;{n \choose k}&lt;/math&gt; possibilities; the problem is that you can repeat urns, so this does not work. You can, however, reframe the problem as so: imagine that you have the &lt;math&gt;n&lt;/math&gt; urns (numbered 1 through &lt;math&gt;n&lt;/math&gt;) and then you also have &lt;math&gt;k-1&lt;/math&gt; urns labeled &quot;repeat 1st&quot;, &quot;repeat 2nd&quot;, ..., and &quot;repeat &lt;math&gt;k-1&lt;/math&gt;-th&quot;. After the balls are in urns you can imagine that any balls in the &quot;repeat&quot; urns are moved on top of the correct balls in the first &lt;math&gt;n&lt;/math&gt; urns, moving from left to right. There is a one-to-one correspondence between the non-repeating arrangements in these new urns and the repeats-allowed arrangements in the original urns. <br /> <br /> For a simple example, consider &lt;math&gt;4&lt;/math&gt; balls and &lt;math&gt;5&lt;/math&gt; urns. The one to one correspondence between several of the possibilities and the &quot;repeated urns&quot; version is shown. Since there are 4 balls, these examples will have three possible &quot;repeat&quot; urns. For simplicity, I am listing the numbers of the urns with balls in them, so &quot;1,1,2,4&quot; means &lt;math&gt;2&lt;/math&gt; balls in urn &lt;math&gt;1, 1&lt;/math&gt; in urn &lt;math&gt;2,&lt;/math&gt; and &lt;math&gt;1&lt;/math&gt; in urn &lt;math&gt;4.&lt;/math&gt; The same is true for the &quot;repeat&quot; urns options but I use the notation &lt;math&gt;r_1&lt;/math&gt; etc.<br /> <br /> *&lt;math&gt;1,2,3,4 \leftrightarrow 1,2,3,4&lt;/math&gt; (no repeats).<br /> *&lt;math&gt;1,1,2,4 \leftrightarrow 1,2,4,&lt;/math&gt; &lt;math&gt;r_1&lt;/math&gt;.<br /> *&lt;math&gt;1,2,2,2 \leftrightarrow 1,2,&lt;/math&gt; &lt;math&gt;r_2&lt;/math&gt;, &lt;math&gt;r_3&lt;/math&gt;.<br /> *&lt;math&gt;4,4,5,5 \leftrightarrow 4,5,&lt;/math&gt; &lt;math&gt;r_1&lt;/math&gt;, &lt;math&gt;r_2&lt;/math&gt;.<br /> <br /> Since the re-framed version of the problem has &lt;math&gt;n+k-1&lt;/math&gt; urns, and &lt;math&gt;k&lt;/math&gt; balls that can each only go in one urn, the number of possible scenarios is simply &lt;math&gt;{n+k-1 <br /> \choose k}.&lt;/math&gt; Note: Due to the principle that &lt;math&gt;{a \choose b}={a \choose a-b}&lt;/math&gt;, we can say that &lt;math&gt;{n+k-1 \choose k}={n+k-1 \choose n-1}&lt;/math&gt;.<br /> <br /> == Problems ==<br /> *[[2003 AMC 10A Problems/Problem 21]]<br /> *[[Mock AIME 3 Pre 2005 Problems/Problem 2]]<br /> *[[2007 AIME I Problems/Problem 10]]<br /> *[[1986 AIME Problems/Problem 13]]<br /> *[[2018 AMC 10A Problems/Problem 11]]<br /> *[[2019 AMC 8 Problems/Problem 25]]<br /> [[Category:Combinatorics]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Ball-and-urn&diff=114527 Ball-and-urn 2020-01-09T03:13:46Z <p>Mag1c: visual</p> <hr /> <div>The '''ball-and-urn''' technique, also known as '''stars-and-bars''', is a commonly used technique in [[combinatorics]].<br /> <br /> It is used to solve problems of the form: how many ways can one distribute &lt;math&gt;k&lt;/math&gt; indistinguishable objects into &lt;math&gt;n&lt;/math&gt; distinguishable bins? We can imagine this as finding the number of ways to drop &lt;math&gt;k&lt;/math&gt; balls into &lt;math&gt;n&lt;/math&gt; urns, or equivalently to arrange &lt;math&gt;k&lt;/math&gt; balls and &lt;math&gt;n-1&lt;/math&gt; dividers. For example, &lt;cmath&gt;****||&lt;/cmath&gt;&lt;cmath&gt;***|*|&lt;/cmath&gt;&lt;cmath&gt;*|**|*&lt;/cmath&gt;&lt;cmath&gt;...&lt;/cmath&gt; represent the ways to put &lt;math&gt;k=4&lt;/math&gt; objects in &lt;math&gt;n=3&lt;/math&gt; bins. The number of ways to do such is &lt;math&gt;{n+k-1 \choose k}&lt;/math&gt;.<br /> <br /> <br /> == Reasoning (One of Several) ==<br /> If you could only put one ball in each urn, then there would be &lt;math&gt;{n \choose k}&lt;/math&gt; possibilities; the problem is that you can repeat urns, so this does not work. You can, however, reframe the problem as so: imagine that you have the &lt;math&gt;n&lt;/math&gt; urns (numbered 1 through &lt;math&gt;n&lt;/math&gt;) and then you also have &lt;math&gt;k-1&lt;/math&gt; urns labeled &quot;repeat 1st&quot;, &quot;repeat 2nd&quot;, ..., and &quot;repeat &lt;math&gt;k-1&lt;/math&gt;-th&quot;. After the balls are in urns you can imagine that any balls in the &quot;repeat&quot; urns are moved on top of the correct balls in the first &lt;math&gt;n&lt;/math&gt; urns, moving from left to right. There is a one-to-one correspondence between the non-repeating arrangements in these new urns and the repeats-allowed arrangements in the original urns. <br /> <br /> For a simple example, consider &lt;math&gt;4&lt;/math&gt; balls and &lt;math&gt;5&lt;/math&gt; urns. The one to one correspondence between several of the possibilities and the &quot;repeated urns&quot; version is shown. Since there are 4 balls, these examples will have three possible &quot;repeat&quot; urns. For simplicity, I am listing the numbers of the urns with balls in them, so &quot;1,1,2,4&quot; means &lt;math&gt;2&lt;/math&gt; balls in urn &lt;math&gt;1, 1&lt;/math&gt; in urn &lt;math&gt;2,&lt;/math&gt; and &lt;math&gt;1&lt;/math&gt; in urn &lt;math&gt;4.&lt;/math&gt; The same is true for the &quot;repeat&quot; urns options but I use the notation &lt;math&gt;r_1&lt;/math&gt; etc.<br /> <br /> *&lt;math&gt;1,2,3,4 \leftrightarrow 1,2,3,4&lt;/math&gt; (no repeats).<br /> *&lt;math&gt;1,1,2,4 \leftrightarrow 1,2,4,&lt;/math&gt; &lt;math&gt;r_1&lt;/math&gt;.<br /> *&lt;math&gt;1,2,2,2 \leftrightarrow 1,2,&lt;/math&gt; &lt;math&gt;r_2&lt;/math&gt;, &lt;math&gt;r_3&lt;/math&gt;.<br /> *&lt;math&gt;4,4,5,5 \leftrightarrow 4,5,&lt;/math&gt; &lt;math&gt;r_1&lt;/math&gt;, &lt;math&gt;r_2&lt;/math&gt;.<br /> <br /> Since the re-framed version of the problem has &lt;math&gt;n+k-1&lt;/math&gt; urns, and &lt;math&gt;k&lt;/math&gt; balls that can each only go in one urn, the number of possible scenarios is simply &lt;math&gt;{n+k-1 <br /> \choose k}.&lt;/math&gt; Note: Due to the principle that &lt;math&gt;{a \choose b}={a \choose a-b}&lt;/math&gt;, we can say that &lt;math&gt;{n+k-1 \choose k}={n+k-1 \choose n-1}&lt;/math&gt;.<br /> <br /> == Problems ==<br /> *[[2003 AMC 10A Problems/Problem 21]]<br /> *[[Mock AIME 3 Pre 2005 Problems/Problem 2]]<br /> *[[2007 AIME I Problems/Problem 10]]<br /> *[[1986 AIME Problems/Problem 13]]<br /> *[[2018 AMC 10A Problems/Problem 11]]<br /> *[[2019 AMC 8 Problems/Problem 25]]<br /> [[Category:Combinatorics]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Molar_heat_capacity&diff=112227 Molar heat capacity 2019-11-27T09:35:05Z <p>Mag1c: url</p> <hr /> <div>Adding heat to a substance changes its temperature in accordance to &lt;cmath&gt;\Delta Q=nc_M\Delta T&lt;/cmath&gt;<br /> &lt;math&gt;\Delta Q=&lt;/math&gt; change in heat<br /> &lt;br /&gt;<br /> &lt;math&gt;n=&lt;/math&gt; moles of substance<br /> &lt;br /&gt;<br /> &lt;math&gt;c_M=&lt;/math&gt; molar heat capacity<br /> &lt;br /&gt;<br /> &lt;math&gt;\Delta T=&lt;/math&gt; change in temperature<br /> &lt;br /&gt;<br /> &lt;br /&gt;<br /> At constant volume, &lt;math&gt;c_M=c_V&lt;/math&gt;.<br /> &lt;br /&gt;<br /> At constant pressure, &lt;math&gt;c_M=c_P&lt;/math&gt;.<br /> &lt;br /&gt;<br /> &lt;br /&gt;<br /> For an ideal gas, &lt;math&gt;c_P=c_V+R&lt;/math&gt; where &lt;math&gt;R=&lt;/math&gt; the ideal gas constant.<br /> &lt;br /&gt;<br /> For an incompressible substance, &lt;math&gt;c_P=c_V&lt;/math&gt;.<br /> &lt;br /&gt;<br /> &lt;br /&gt;<br /> In adiabatic compression (&lt;math&gt;\Delta Q=0&lt;/math&gt;) of an ideal gas, &lt;math&gt;PV^\gamma&lt;/math&gt; stays constant, where &lt;math&gt;\gamma=\frac{c_V+R}{c_V}&lt;/math&gt;. An excellent derivation of this can be found [https://www.animations.physics.unsw.edu.au/jw/Adiabatic-expansion-compression.htm here].</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Molar_heat_capacity&diff=112226 Molar heat capacity 2019-11-27T09:30:11Z <p>Mag1c: spacing</p> <hr /> <div>Adding heat to a substance changes its temperature in accordance to &lt;cmath&gt;\Delta Q=nc_M\Delta T&lt;/cmath&gt;<br /> &lt;math&gt;\Delta Q=&lt;/math&gt; change in heat<br /> &lt;br /&gt;<br /> &lt;math&gt;n=&lt;/math&gt; moles of substance<br /> &lt;br /&gt;<br /> &lt;math&gt;c_M=&lt;/math&gt; molar heat capacity<br /> &lt;br /&gt;<br /> &lt;math&gt;\Delta T=&lt;/math&gt; change in temperature<br /> &lt;br /&gt;<br /> &lt;br /&gt;<br /> At constant volume, &lt;math&gt;c_M=c_V&lt;/math&gt;.<br /> &lt;br /&gt;<br /> At constant pressure, &lt;math&gt;c_M=c_P&lt;/math&gt;.<br /> &lt;br /&gt;<br /> &lt;br /&gt;<br /> For an ideal gas, &lt;math&gt;c_P=c_V+R&lt;/math&gt; where &lt;math&gt;R=&lt;/math&gt; the ideal gas constant.<br /> &lt;br /&gt;<br /> For an incompressible substance, &lt;math&gt;c_P=c_V&lt;/math&gt;.<br /> &lt;br /&gt;<br /> &lt;br /&gt;<br /> In adiabatic compression (&lt;math&gt;\Delta Q=0&lt;/math&gt;) of an ideal gas, &lt;math&gt;PV^\gamma&lt;/math&gt; stays constant, where &lt;math&gt;\gamma=\frac{c_V+R}{c_V}&lt;/math&gt;.</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Molar_heat_capacity&diff=112225 Molar heat capacity 2019-11-27T09:23:50Z <p>Mag1c: create article</p> <hr /> <div>Adding heat to a substance changes its temperature in accordance to &lt;cmath&gt;\Delta Q=nc_M\Delta T&lt;/cmath&gt;<br /> &lt;math&gt;\Delta Q=&lt;/math&gt; change in heat<br /> &lt;math&gt;n=&lt;/math&gt; moles of substance<br /> &lt;math&gt;c_M=&lt;/math&gt; molar heat capacity<br /> &lt;math&gt;\Delta T=&lt;/math&gt; change in temperature<br /> <br /> At constant volume, &lt;math&gt;c_M=c_V&lt;/math&gt;.<br /> At constant pressure, &lt;math&gt;c_M=c_P&lt;/math&gt;.<br /> <br /> For an ideal gas, &lt;math&gt;c_P=c_V+R&lt;/math&gt;.<br /> For an incompressible substance, &lt;math&gt;c_P=c_V&lt;/math&gt;.<br /> <br /> In adiabatic compression (&lt;math&gt;\Delta Q=0&lt;/math&gt;) of an ideal gas, &lt;math&gt;PV^\gamma&lt;/math&gt; stays constant, where &lt;math&gt;\gamma=\frac{c_V+R}{c_V}&lt;/math&gt;.</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=2001_AIME_I_Problems/Problem_5&diff=111429 2001 AIME I Problems/Problem 5 2019-11-15T02:13:22Z <p>Mag1c: /* Solution 1 */</p> <hr /> <div>== Problem ==<br /> An [[equilateral triangle]] is inscribed in the [[ellipse]] whose equation is &lt;math&gt;x^2+4y^2=4&lt;/math&gt;. One vertex of the triangle is &lt;math&gt;(0,1)&lt;/math&gt;, one altitude is contained in the y-axis, and the length of each side is &lt;math&gt;\sqrt{\frac mn}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m+n&lt;/math&gt;.<br /> <br /> __TOC__<br /> == Solution ==<br /> &lt;center&gt;&lt;asy&gt;<br /> pointpen = black; pathpen = black + linewidth(0.7);<br /> path e = xscale(2)*unitcircle; real x = -8/13*3^.5;<br /> D((-3,0)--(3,0)); D((0,-2)--(0,2)); /* axes */<br /> D(e); D(D((0,1))--(x,x*3^.5+1)--(-x,x*3^.5+1)--cycle);<br /> &lt;/asy&gt;&lt;/center&gt;<br /> === Solution 1 ===<br /> Denote the vertices of the triangle &lt;math&gt;A,B,&lt;/math&gt; and &lt;math&gt;C,&lt;/math&gt; where &lt;math&gt;B&lt;/math&gt; is in [[quadrant]] 4 and &lt;math&gt;C&lt;/math&gt; is in quadrant &lt;math&gt;3.&lt;/math&gt;<br /> <br /> Note that the slope of &lt;math&gt;\overline{AC}&lt;/math&gt; is &lt;math&gt;\tan 60^\circ = \sqrt {3}.&lt;/math&gt; Hence, the equation of the line containing &lt;math&gt;\overline{AC}&lt;/math&gt; is<br /> &lt;cmath&gt;<br /> y = x\sqrt {3} + 1.<br /> &lt;/cmath&gt;<br /> This will intersect the ellipse when<br /> &lt;cmath&gt;<br /> \begin{eqnarray*}4 = x^{2} + 4y^{2} &amp; = &amp; x^{2} + 4(x\sqrt {3} + 1)^{2} \\<br /> &amp; = &amp; x^{2} + 4(3x^{2} + 2x\sqrt {3} + 1) \implies x(13x+8\sqrt 3)=0\implies x = \frac { - 8\sqrt {3}}{13}. \end{eqnarray*}<br /> &lt;/cmath&gt;<br /> We ignore the &lt;math&gt;x=0&lt;/math&gt; solution because it is not in quadrant 3.<br /> <br /> Since the triangle is symmetric with respect to the y-axis, the coordinates of &lt;math&gt;B&lt;/math&gt; and &lt;math&gt;C&lt;/math&gt; are now &lt;math&gt;\left(\frac {8\sqrt {3}}{13},y_{0}\right)&lt;/math&gt; and &lt;math&gt;\left(\frac { - 8\sqrt {3}}{13},y_{0}\right),&lt;/math&gt; respectively, for some value of &lt;math&gt;y_{0}.&lt;/math&gt;<br /> <br /> It is clear that the value of &lt;math&gt;y_{0}&lt;/math&gt; is irrelevant to the length of &lt;math&gt;BC&lt;/math&gt;. Our answer is<br /> &lt;cmath&gt;<br /> BC = 2*\frac {8\sqrt {3}}{13}=\sqrt {4\left(\frac {8\sqrt {3}}{13}\right)^{2}} = \sqrt {\frac {768}{169}}\implies m + n = \boxed{937}.<br /> &lt;/cmath&gt;<br /> <br /> === Solution 2 ===<br /> Solving for &lt;math&gt;y&lt;/math&gt; in terms of &lt;math&gt;x&lt;/math&gt; gives &lt;math&gt;y=\sqrt{4-x^2}/2&lt;/math&gt;, so the two other points of the triangle are &lt;math&gt;(x,\sqrt{4-x^2}/2)&lt;/math&gt; and &lt;math&gt;(-x,\sqrt{4-x^2}/2)&lt;/math&gt;, which are a distance of &lt;math&gt;2x&lt;/math&gt; apart. Thus &lt;math&gt;2x&lt;/math&gt; equals the distance between &lt;math&gt;(x,\sqrt{4-x^2}/2)&lt;/math&gt; and &lt;math&gt;(0,1)&lt;/math&gt;, so by the distance formula we have <br /> <br /> &lt;cmath&gt;2x=\sqrt{x^2+(1-\sqrt{4-x^2}/2)^2}.&lt;/cmath&gt; <br /> <br /> Squaring both sides and simplifying through algebra yields &lt;math&gt;x^2=192/169&lt;/math&gt;, so &lt;math&gt;2x=\sqrt{768/169}&lt;/math&gt; and the answer is &lt;math&gt;\boxed{937}&lt;/math&gt;.<br /> <br /> === Solution 3 ===<br /> Since the altitude goes along the &lt;math&gt;y&lt;/math&gt; axis, this means that the base is a horizontal line, which means that the endpoints of the base are &lt;math&gt;(x,y)&lt;/math&gt; and &lt;math&gt;(-x,y)&lt;/math&gt;, and WLOG, we can say that &lt;math&gt;x&lt;/math&gt; is positive.<br /> <br /> Now, since all sides of an equilateral triangle are the same, we can do this (distance from one of the endpoints of the base to the vertex and the length of the base):<br /> <br /> &lt;math&gt;\sqrt{x^2 + (y-1)^2} = 2x&lt;/math&gt;<br /> <br /> Square both sides,<br /> <br /> &lt;math&gt;x^2 + (y-1)^2 = 4x^2\implies (y-1)^2 = 3x^2&lt;/math&gt;<br /> <br /> Now, with the equation of the ellipse:<br /> &lt;math&gt;x^2 + 4y^2 = 4&lt;/math&gt;<br /> <br /> &lt;math&gt;x^2 = 4-4y^2&lt;/math&gt;<br /> <br /> &lt;math&gt;3x^2 = 12-12y^2&lt;/math&gt;<br /> <br /> Substituting, <br /> <br /> &lt;math&gt;12-12y^2 = y^2 - 2y +1&lt;/math&gt;<br /> <br /> Moving stuff around and solving:<br /> <br /> &lt;math&gt;y = \frac{-11}{3}, 1&lt;/math&gt;<br /> <br /> The second is found to be extraneous, so, when we go back and figure out &lt;math&gt;x&lt;/math&gt; and then &lt;math&gt;2x&lt;/math&gt; (which is the side length), we find it to be:<br /> <br /> &lt;math&gt;\sqrt{\frac{768}{169}}&lt;/math&gt; <br /> <br /> and so we get the desired answer of &lt;math&gt;\boxed{937}&lt;/math&gt;.<br /> <br /> == See also ==<br /> {{AIME box|year=2001|n=I|num-b=4|num-a=6}}<br /> <br /> [[Category:Intermediate Geometry Problems]]<br /> {{MAA Notice}}</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Conic_section&diff=111427 Conic section 2019-11-15T01:58:28Z <p>Mag1c: images: standard equations</p> <hr /> <div>A '''conic section''' is any of the geometric figures that can arise when a [[plane]] [[intersect]]s a [[cone]]. (In fact, one usually considers a &quot;two-ended cone,&quot; that is, two [[congruent]] right circular cones placed tip to tip so that their axes align.) As is clear from their definition, the conic sections are all [[plane curve]]s, and every conic section can be described in [[Cartesian coordinates]] by a [[polynomial]] [[equation]] of degree two or less. <br /> <br /> == Classification of conic sections ==<br /> All conic sections fall into the following categories:<br /> <br /> === Nondegenerate conic sections ===<br /> <br /> * A [[circle]] is the conic section formed when the cutting plane is [[parallel]] to the [[base (geometry) | base]] of the cone or equivalently [[perpendicular]] to the axis. (This is really just a special case of the ellipse -- see the next bullet point.)<br /> <br /> * An [[ellipse]] is formed if the cutting plane makes an [[angle]] with the axis that is larger than the angle between the [[cone element | element of the cone]] and the axis.<br /> [[Image:Ellipse.png|alt=Ellipse]]By Klaas van Aarsen - Created as a latex tikzpicturePreviously published: Not published before, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=25261046<br /> <br /> * A [[parabola]] is formed when the cutting plane makes an angle with the axis that is equal to the angle between the element of the cone and the axis.<br /> [[Image:Parabola2.png|alt=Parabola]]By Klaas van Aarsen - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=25261094<br /> <br /> * An [[hyperbola]] is formed when the cutting plane makes an angle with the axis that is smaller than the angle between the element of the cone and the axis.<br /> [[Image:Hyperbola.png|alt=Hyperbola]]By Klaas van Aarsen - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=25261095<br /> <br /> === Degenerate conic sections ===<br /> <br /> If the cutting plane passes through the vertex of the cone, the result is a degenerate conic section. Degenerate conics fall into three categories:<br /> <br /> * If the cutting plane makes an angle with the axis that is larger than the angle between the element of the cone and the axis then the plane intersects the cone only in the vertex, i.e. the resulting section is a single [[point]]. This is a degenerate ellipse.<br /> <br /> * If the cutting plane makes an angle with the axis equal to the angle between the element of the cone and the axis then the plane is tangent to the cone and the resulting section is a [[line]]. This is a degenerate parabola.<br /> <br /> * If the cutting plane makes an angle with the axis that is smaller than then angle between the element of the cone and the axis then the resulting section is two intersecting lines. This is a degenerate hyperbola.<br /> <br /> <br /> {{image}}<br /> <br /> <br /> There are alternate (but equivalent) definitions of every conic section. We present them here:<br /> <br /> == Definitions of conic sections in terms of foci and directrices ==<br /> {{stub}}<br /> <br /> == Definitions of conic sections in terms of Cartesian coordinates ==<br /> {{stub}}<br /> <br /> == See Also ==<br /> * [[Parabola]]<br /> * [[Hyperbola]]<br /> * [[Circle]]<br /> * [[Ellipse]]<br /> <br /> [[Category:Definition]]<br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=File:Parabola2.png&diff=111426 File:Parabola2.png 2019-11-15T01:53:05Z <p>Mag1c: standard equations By Klaas van Aarsen - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=25261094</p> <hr /> <div>== Summary ==<br /> standard equations<br /> <br /> By Klaas van Aarsen - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=25261094</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=File:Hyperbola.png&diff=111425 File:Hyperbola.png 2019-11-15T01:52:18Z <p>Mag1c: standard equations By Klaas van Aarsen - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=25261095</p> <hr /> <div>== Summary ==<br /> standard equations<br /> <br /> By Klaas van Aarsen - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=25261095</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=File:Ellipse.png&diff=111424 File:Ellipse.png 2019-11-15T01:51:41Z <p>Mag1c: standard equations By Klaas van Aarsen - Created as a latex tikzpicturePreviously published: Not published before, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=25261046</p> <hr /> <div>== Summary ==<br /> standard equations<br /> <br /> By Klaas van Aarsen - Created as a latex tikzpicturePreviously published: Not published before, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=25261046</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Circumradius&diff=110972 Circumradius 2019-11-08T02:04:33Z <p>Mag1c: /* Right triangles */</p> <hr /> <div>The '''circumradius''' of a [[cyclic]] [[polygon]] is the radius of the circumscribed circle of that polygon. For a triangle, it is the measure of the [[radius]] of the [[circle]] that [[circumscribe]]s the triangle. Since every triangle is [[cyclic]], every triangle has a circumscribed circle, or a [[circumcircle]].<br /> <br /> ==Formula for a Triangle==<br /> Let &lt;math&gt;a, b&lt;/math&gt; and &lt;math&gt;c&lt;/math&gt; denote the triangle's three sides and let &lt;math&gt;A&lt;/math&gt; denote the area of the triangle. Then, the measure of the circumradius of the triangle is simply &lt;math&gt;R=\frac{abc}{4A}&lt;/math&gt;. This can be rewritten as &lt;math&gt;A=\frac{abc}{4R}&lt;/math&gt;.<br /> <br /> == Proof ==<br /> &lt;asy&gt;<br /> pair O, A, B, C, D;<br /> O=(0,0);<br /> A=(-5,1);<br /> B=(1,5);<br /> C=(5,1);<br /> dot(O); dot (A); dot (B); dot (C);<br /> draw(circle(O, sqrt(26)));<br /> draw(A--B--C--cycle);<br /> D=-B; dot (D);<br /> draw(B--D--A);<br /> label(&quot;$A$&quot;, A, W);<br /> label(&quot;$B$&quot;, B, N);<br /> label(&quot;$C$&quot;, C, E);<br /> label(&quot;$D$&quot;, D, S);<br /> label(&quot;$O$&quot;, O, W);<br /> pair E;<br /> E=foot(B,A,C);<br /> draw(B--E);<br /> dot(E);<br /> label(&quot;$E$&quot;, E, S);<br /> draw(rightanglemark(B,A,D,20));<br /> draw(rightanglemark(B,E,C,20));<br /> &lt;/asy&gt;<br /> <br /> <br /> We let &lt;math&gt;AB=c&lt;/math&gt;, &lt;math&gt;BC=a&lt;/math&gt;, &lt;math&gt;AC=b&lt;/math&gt;, &lt;math&gt;BE=h&lt;/math&gt;, and &lt;math&gt;BO=R&lt;/math&gt;. We know that &lt;math&gt;\angle BAD&lt;/math&gt; is a right angle because &lt;math&gt;BD&lt;/math&gt; is the diameter. Also, &lt;math&gt;\angle ADB = \angle BCA&lt;/math&gt; because they both subtend arc &lt;math&gt;AB&lt;/math&gt;. Therefore, &lt;math&gt;\triangle BAD \sim \triangle BEC&lt;/math&gt; by AA similarity, so we have<br /> &lt;cmath&gt;\frac{BD}{BA} = \frac{BC}{BE},&lt;/cmath&gt; or &lt;cmath&gt; \frac {2R} c = \frac ah.&lt;/cmath&gt;<br /> However, remember that &lt;math&gt;[ABC] = \frac {bh} 2\implies h=\frac{2 \times [ABC]}b&lt;/math&gt;. Substituting this in gives us<br /> &lt;cmath&gt; \frac {2R} c = \frac a{\frac{2 \times [ABC]}b},&lt;/cmath&gt; and then bash through the algebra to get<br /> &lt;cmath&gt; R=\frac{abc}{4\times [ABC]}\text{ or }[ABC]=\frac{abc}{4R}&lt;/cmath&gt;<br /> and we are done.<br /> <br /> ==Formula for Circumradius==<br /> &lt;math&gt;R = \frac{abc}{4rs}&lt;/math&gt;<br /> Where &lt;math&gt;R&lt;/math&gt; is the circumradius, &lt;math&gt;r&lt;/math&gt; is the inradius, and &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, and &lt;math&gt;c&lt;/math&gt; are the respective sides of the triangle and &lt;math&gt;s = (a+b+c)/2&lt;/math&gt; is the semiperimeter. Note that this is similar to the previously mentioned formula; the reason being that &lt;math&gt;A = rs&lt;/math&gt;.<br /> <br /> But, if you don't know the inradius, you can find the area of the triangle by Heron's Formula:<br /> <br /> &lt;math&gt;A=\sqrt{s(s-a)(s-b)(s-c)}&lt;/math&gt;<br /> <br /> ==Euler's Theorem for a Triangle==<br /> Let &lt;math&gt;\triangle ABC&lt;/math&gt; have circumcenter &lt;math&gt;O&lt;/math&gt; and incenter &lt;math&gt;I&lt;/math&gt;.Then &lt;cmath&gt;OI^2=R(R-2r) \implies R \geq 2r&lt;/cmath&gt;<br /> <br /> ==Proof==<br /> <br /> == Right triangles ==<br /> The hypotenuse of the triangle is the diameter of its circumcircle, and the circumcenter is its midpoint, so the circumradius is equal to half of the hypotenuse of the right triangle.<br /> <br /> &lt;asy&gt;<br /> pair A,B,C,I;<br /> A=(0,0);<br /> B=(0,3);<br /> C=(4,0);<br /> draw(A--B--C--cycle);<br /> I=circumcenter(A,B,C);<br /> draw(I--A,gray);<br /> label(&quot;$r$&quot;,(I+A)/2,NW,gray);<br /> draw(circumcircle(A,B,C));<br /> label(&quot;$C$&quot;,I,N);<br /> dot(I);<br /> draw(rightanglemark(B,A,C,10));<br /> &lt;/asy&gt;<br /> <br /> This results in a well-known theorem:<br /> ===Theorem===<br /> The midpoint of the hypotenuse is equidistant from the vertices of the right triangle.<br /> <br /> == Equilateral triangles ==<br /> <br /> &lt;math&gt;R=\frac{s}{\sqrt3}&lt;/math&gt;<br /> <br /> where &lt;math&gt;s&lt;/math&gt; is the length of a side of the triangle.<br /> <br /> &lt;asy&gt;<br /> pair A,B,C,I;<br /> A=(0,0);<br /> B=(1,0);<br /> C=intersectionpoint(arc(A,1,0,90),arc(B,1,90,180));<br /> draw(A--B--C--cycle);<br /> I=circumcenter(A,B,C);<br /> draw(circumcircle(A,B,C));<br /> label(&quot;$C$&quot;,I,E);<br /> dot(I);<br /> label(&quot;$s$&quot;,A--B,S);<br /> label(&quot;$s$&quot;,A--C,N);<br /> label(&quot;$s$&quot;,B--C,N);<br /> &lt;/asy&gt;<br /> <br /> == If all three sides are known ==<br /> <br /> &lt;math&gt;R=\frac{abc}{\sqrt{(a+b+c)(-a+b+c)(a-b+c)(a+b-c)}}&lt;/math&gt;<br /> <br /> And this formula comes from the area of Heron and &lt;math&gt;R=\frac{abc}{4A}&lt;/math&gt;.<br /> <br /> == If you know just one side and its opposite angle ==<br /> <br /> &lt;math&gt;2R=\frac{a}{\sin{A}}&lt;/math&gt; which is just extension of law of sines<br /> <br /> (Extended Law of Sines)<br /> <br /> ==See also==<br /> * [[Inradius]]<br /> * [[Semiperimeter]]<br /> <br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Circumradius&diff=110970 Circumradius 2019-11-08T02:03:26Z <p>Mag1c: /* Right triangles */</p> <hr /> <div>The '''circumradius''' of a [[cyclic]] [[polygon]] is the radius of the circumscribed circle of that polygon. For a triangle, it is the measure of the [[radius]] of the [[circle]] that [[circumscribe]]s the triangle. Since every triangle is [[cyclic]], every triangle has a circumscribed circle, or a [[circumcircle]].<br /> <br /> ==Formula for a Triangle==<br /> Let &lt;math&gt;a, b&lt;/math&gt; and &lt;math&gt;c&lt;/math&gt; denote the triangle's three sides and let &lt;math&gt;A&lt;/math&gt; denote the area of the triangle. Then, the measure of the circumradius of the triangle is simply &lt;math&gt;R=\frac{abc}{4A}&lt;/math&gt;. This can be rewritten as &lt;math&gt;A=\frac{abc}{4R}&lt;/math&gt;.<br /> <br /> == Proof ==<br /> &lt;asy&gt;<br /> pair O, A, B, C, D;<br /> O=(0,0);<br /> A=(-5,1);<br /> B=(1,5);<br /> C=(5,1);<br /> dot(O); dot (A); dot (B); dot (C);<br /> draw(circle(O, sqrt(26)));<br /> draw(A--B--C--cycle);<br /> D=-B; dot (D);<br /> draw(B--D--A);<br /> label(&quot;$A$&quot;, A, W);<br /> label(&quot;$B$&quot;, B, N);<br /> label(&quot;$C$&quot;, C, E);<br /> label(&quot;$D$&quot;, D, S);<br /> label(&quot;$O$&quot;, O, W);<br /> pair E;<br /> E=foot(B,A,C);<br /> draw(B--E);<br /> dot(E);<br /> label(&quot;$E$&quot;, E, S);<br /> draw(rightanglemark(B,A,D,20));<br /> draw(rightanglemark(B,E,C,20));<br /> &lt;/asy&gt;<br /> <br /> <br /> We let &lt;math&gt;AB=c&lt;/math&gt;, &lt;math&gt;BC=a&lt;/math&gt;, &lt;math&gt;AC=b&lt;/math&gt;, &lt;math&gt;BE=h&lt;/math&gt;, and &lt;math&gt;BO=R&lt;/math&gt;. We know that &lt;math&gt;\angle BAD&lt;/math&gt; is a right angle because &lt;math&gt;BD&lt;/math&gt; is the diameter. Also, &lt;math&gt;\angle ADB = \angle BCA&lt;/math&gt; because they both subtend arc &lt;math&gt;AB&lt;/math&gt;. Therefore, &lt;math&gt;\triangle BAD \sim \triangle BEC&lt;/math&gt; by AA similarity, so we have<br /> &lt;cmath&gt;\frac{BD}{BA} = \frac{BC}{BE},&lt;/cmath&gt; or &lt;cmath&gt; \frac {2R} c = \frac ah.&lt;/cmath&gt;<br /> However, remember that &lt;math&gt;[ABC] = \frac {bh} 2\implies h=\frac{2 \times [ABC]}b&lt;/math&gt;. Substituting this in gives us<br /> &lt;cmath&gt; \frac {2R} c = \frac a{\frac{2 \times [ABC]}b},&lt;/cmath&gt; and then bash through the algebra to get<br /> &lt;cmath&gt; R=\frac{abc}{4\times [ABC]}\text{ or }[ABC]=\frac{abc}{4R}&lt;/cmath&gt;<br /> and we are done.<br /> <br /> ==Formula for Circumradius==<br /> &lt;math&gt;R = \frac{abc}{4rs}&lt;/math&gt;<br /> Where &lt;math&gt;R&lt;/math&gt; is the circumradius, &lt;math&gt;r&lt;/math&gt; is the inradius, and &lt;math&gt;a&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt;, and &lt;math&gt;c&lt;/math&gt; are the respective sides of the triangle and &lt;math&gt;s = (a+b+c)/2&lt;/math&gt; is the semiperimeter. Note that this is similar to the previously mentioned formula; the reason being that &lt;math&gt;A = rs&lt;/math&gt;.<br /> <br /> But, if you don't know the inradius, you can find the area of the triangle by Heron's Formula:<br /> <br /> &lt;math&gt;A=\sqrt{s(s-a)(s-b)(s-c)}&lt;/math&gt;<br /> <br /> ==Euler's Theorem for a Triangle==<br /> Let &lt;math&gt;\triangle ABC&lt;/math&gt; have circumcenter &lt;math&gt;O&lt;/math&gt; and incenter &lt;math&gt;I&lt;/math&gt;.Then &lt;cmath&gt;OI^2=R(R-2r) \implies R \geq 2r&lt;/cmath&gt;<br /> <br /> ==Proof==<br /> <br /> == Right triangles ==<br /> The hypotenuse of the triangle is the diameter of its circumcircle, and the circumcenter is its midpoint, so the circumradius is equal to half of the hypotenuse of the right triangle.<br /> <br /> &lt;asy&gt;<br /> pair A,B,C,I;<br /> A=(0,0);<br /> B=(0,3);<br /> C=(4,0);<br /> draw(A--B--C--cycle);<br /> I=circumcenter(A,B,C);<br /> draw(I--A,gray);<br /> label(&quot;$r$&quot;,(I+A)/2,gray,NW);<br /> draw(circumcircle(A,B,C));<br /> label(&quot;$C$&quot;,I,N);<br /> dot(I);<br /> draw(rightanglemark(B,A,C,10));<br /> &lt;/asy&gt;<br /> <br /> This results in a well-known theorem:<br /> ===Theorem===<br /> The midpoint of the hypotenuse is equidistant from the vertices of the right triangle.<br /> <br /> == Equilateral triangles ==<br /> <br /> &lt;math&gt;R=\frac{s}{\sqrt3}&lt;/math&gt;<br /> <br /> where &lt;math&gt;s&lt;/math&gt; is the length of a side of the triangle.<br /> <br /> &lt;asy&gt;<br /> pair A,B,C,I;<br /> A=(0,0);<br /> B=(1,0);<br /> C=intersectionpoint(arc(A,1,0,90),arc(B,1,90,180));<br /> draw(A--B--C--cycle);<br /> I=circumcenter(A,B,C);<br /> draw(circumcircle(A,B,C));<br /> label(&quot;$C$&quot;,I,E);<br /> dot(I);<br /> label(&quot;$s$&quot;,A--B,S);<br /> label(&quot;$s$&quot;,A--C,N);<br /> label(&quot;$s$&quot;,B--C,N);<br /> &lt;/asy&gt;<br /> <br /> == If all three sides are known ==<br /> <br /> &lt;math&gt;R=\frac{abc}{\sqrt{(a+b+c)(-a+b+c)(a-b+c)(a+b-c)}}&lt;/math&gt;<br /> <br /> And this formula comes from the area of Heron and &lt;math&gt;R=\frac{abc}{4A}&lt;/math&gt;.<br /> <br /> == If you know just one side and its opposite angle ==<br /> <br /> &lt;math&gt;2R=\frac{a}{\sin{A}}&lt;/math&gt; which is just extension of law of sines<br /> <br /> (Extended Law of Sines)<br /> <br /> ==See also==<br /> * [[Inradius]]<br /> * [[Semiperimeter]]<br /> <br /> [[Category:Geometry]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=User:Mag1c&diff=110498 User:Mag1c 2019-10-21T06:26:23Z <p>Mag1c: fix link</p> <hr /> <div>==Python and Jupyter Notebook Tutorial and Demo==<br /> <br /> In progress, feel free to fill in stuff and otherwise contribute!<br /> <br /> &lt;br /&gt;<br /> <br /> ===Linux===<br /> <br /> ===Mac===<br /> <br /> [[File:Doodle.jpg]]<br /> <br /> https://youtu.be/0CErj2nTwrI<br /> <br /> ===Windows===<br /> <br /> &lt;br /&gt;<br /> <br /> ==Tips for Succeeding at Math, Life (Maybe), and Beyond (Maaaybe)==<br /> <br /> <br /> A teacher once taught me that grades are for comparing yourself with yourself, not others. It has been one of the most useful pieces of advice in my life.<br /> <br /> &lt;br /&gt;<br /> <br /> I know it is easy to get ''bogged down'' by bureaucracy and competition, so let me offer some similar advice to help you navigate that:<br /> <br /> &lt;br /&gt;<br /> <br /> # Have a spiritual life. There are many interpretations of what this means, but the general consensus is that it is beyond words.&lt;sup&gt;[[#Footnotes|]][[#Footnotes|]][[#Footnotes|]][[#Footnotes|]][[#Footnotes|]]&lt;/sup&gt;<br /> # Homework (grades) are for comparing with yourself not others<br /> # Same thing with Quizzes (questions)<br /> # conTests are for fun<br /> # Math is something you play!<br /> <br /> ==What tips do you have? Feel free to share in an article and link it above!==<br /> <br /> ==&lt;small&gt;Notes&lt;/small&gt;==<br /> &lt;small&gt; &quot;Be your own guide.&quot; -Buddha<br /> <br />  &quot;The Dao that is spoken is not the true Dao. The name that is named is not the true name.&quot; -Tao Te Ching<br /> <br />  &quot;This is why I speak to them in parables: 'Though seeing, they do not see; though hearing, they do not hear or understand.'&quot; -Jesus<br /> <br />  &lt;u&gt;[https://www.worldcat.org/title/beyond-words/oclc/769188130 Beyond Words]&lt;/u&gt; by Sri Swami Satchidananda<br /> <br />  [https://www.youtube.com/user/AwakenTheWorldFilm/playlists?view=50&amp;sort=dd&amp;shelf_id=23 Samadhi the Film] by Awaken The World Initiative&lt;/small&gt;</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=User:Mag1c&diff=110497 User:Mag1c 2019-10-21T06:25:28Z <p>Mag1c: /* Mac */</p> <hr /> <div>==Python and Jupyter Notebook Tutorial and Demo==<br /> <br /> In progress, feel free to fill in stuff and otherwise contribute!<br /> <br /> &lt;br /&gt;<br /> <br /> ===Linux===<br /> <br /> ===Mac===<br /> <br /> [[File:Doodle.jpg]]<br /> https://youtu.be/0CErj2nTwrI<br /> <br /> ===Windows===<br /> <br /> &lt;br /&gt;<br /> <br /> ==Tips for Succeeding at Math, Life (Maybe), and Beyond (Maaaybe)==<br /> <br /> <br /> A teacher once taught me that grades are for comparing yourself with yourself, not others. It has been one of the most useful pieces of advice in my life.<br /> <br /> &lt;br /&gt;<br /> <br /> I know it is easy to get ''bogged down'' by bureaucracy and competition, so let me offer some similar advice to help you navigate that:<br /> <br /> &lt;br /&gt;<br /> <br /> # Have a spiritual life. There are many interpretations of what this means, but the general consensus is that it is beyond words.&lt;sup&gt;[[#Footnotes|]][[#Footnotes|]][[#Footnotes|]][[#Footnotes|]][[#Footnotes|]]&lt;/sup&gt;<br /> # Homework (grades) are for comparing with yourself not others<br /> # Same thing with Quizzes (questions)<br /> # conTests are for fun<br /> # Math is something you play!<br /> <br /> ==What tips do you have? Feel free to share in an article and link it above!==<br /> <br /> ==&lt;small&gt;Notes&lt;/small&gt;==<br /> &lt;small&gt; &quot;Be your own guide.&quot; -Buddha<br /> <br />  &quot;The Dao that is spoken is not the true Dao. The name that is named is not the true name.&quot; -Tao Te Ching<br /> <br />  &quot;This is why I speak to them in parables: 'Though seeing, they do not see; though hearing, they do not hear or understand.'&quot; -Jesus<br /> <br />  &lt;u&gt;[https://www.worldcat.org/title/beyond-words/oclc/769188130 Beyond Words]&lt;/u&gt; by Sri Swami Satchidananda<br /> <br />  [https://www.youtube.com/user/AwakenTheWorldFilm/playlists?view=50&amp;sort=dd&amp;shelf_id=23 Samadhi the Film] by Awaken The World Initiative&lt;/small&gt;</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=User:Mag1c&diff=110496 User:Mag1c 2019-10-21T06:23:58Z <p>Mag1c: python + jupyter tutorial + demo</p> <hr /> <div>==Python and Jupyter Notebook Tutorial and Demo==<br /> <br /> In progress, feel free to fill in stuff and otherwise contribute!<br /> <br /> &lt;br /&gt;<br /> <br /> ===Linux===<br /> <br /> ===Mac===<br /> <br /> [[File:Doodle.jpg]]<br /> [url]https://youtu.be/0CErj2nTwrI[/url]<br /> <br /> ===Windows===<br /> <br /> &lt;br /&gt;<br /> <br /> ==Tips for Succeeding at Math, Life (Maybe), and Beyond (Maaaybe)==<br /> <br /> <br /> A teacher once taught me that grades are for comparing yourself with yourself, not others. It has been one of the most useful pieces of advice in my life.<br /> <br /> &lt;br /&gt;<br /> <br /> I know it is easy to get ''bogged down'' by bureaucracy and competition, so let me offer some similar advice to help you navigate that:<br /> <br /> &lt;br /&gt;<br /> <br /> # Have a spiritual life. There are many interpretations of what this means, but the general consensus is that it is beyond words.&lt;sup&gt;[[#Footnotes|]][[#Footnotes|]][[#Footnotes|]][[#Footnotes|]][[#Footnotes|]]&lt;/sup&gt;<br /> # Homework (grades) are for comparing with yourself not others<br /> # Same thing with Quizzes (questions)<br /> # conTests are for fun<br /> # Math is something you play!<br /> <br /> ==What tips do you have? Feel free to share in an article and link it above!==<br /> <br /> ==&lt;small&gt;Notes&lt;/small&gt;==<br /> &lt;small&gt; &quot;Be your own guide.&quot; -Buddha<br /> <br />  &quot;The Dao that is spoken is not the true Dao. The name that is named is not the true name.&quot; -Tao Te Ching<br /> <br />  &quot;This is why I speak to them in parables: 'Though seeing, they do not see; though hearing, they do not hear or understand.'&quot; -Jesus<br /> <br />  &lt;u&gt;[https://www.worldcat.org/title/beyond-words/oclc/769188130 Beyond Words]&lt;/u&gt; by Sri Swami Satchidananda<br /> <br />  [https://www.youtube.com/user/AwakenTheWorldFilm/playlists?view=50&amp;sort=dd&amp;shelf_id=23 Samadhi the Film] by Awaken The World Initiative&lt;/small&gt;</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=File:Doodle.jpg&diff=110495 File:Doodle.jpg 2019-10-21T06:22:40Z <p>Mag1c: </p> <hr /> <div></div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=2016_AIME_I_Problems/Problem_6&diff=109971 2016 AIME I Problems/Problem 6 2019-09-26T04:17:24Z <p>Mag1c: /* Solution 6 */ alternate solution</p> <hr /> <div>==Problem==<br /> In &lt;math&gt;\triangle ABC&lt;/math&gt; let &lt;math&gt;I&lt;/math&gt; be the center of the inscribed circle, and let the bisector of &lt;math&gt;\angle ACB&lt;/math&gt; intersect &lt;math&gt;AB&lt;/math&gt; at &lt;math&gt;L&lt;/math&gt;. The line through &lt;math&gt;C&lt;/math&gt; and &lt;math&gt;L&lt;/math&gt; intersects the circumscribed circle of &lt;math&gt;\triangle ABC&lt;/math&gt; at the two points &lt;math&gt;C&lt;/math&gt; and &lt;math&gt;D&lt;/math&gt;. If &lt;math&gt;LI=2&lt;/math&gt; and &lt;math&gt;LD=3&lt;/math&gt;, then &lt;math&gt;IC=\tfrac{p}{q}&lt;/math&gt;, where &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;p+q&lt;/math&gt;.<br /> <br /> =Solution=<br /> ==Solution 1==<br /> Suppose we label the angles as shown below.<br /> &lt;asy&gt;<br /> size(150);<br /> import olympiad;<br /> real c=8.1,a=5*(c+sqrt(c^2-64))/6,b=5*(c-sqrt(c^2-64))/6;<br /> pair A=(0,0),B=(c,0),D=(c/2,-sqrt(25-(c/2)^2));<br /> pair C=intersectionpoints(circle(A,b),circle(B,a));<br /> pair I=incenter(A,B,C);<br /> pair L=extension(C,D,A,B);<br /> dot(I^^A^^B^^C^^D);<br /> draw(C--D);<br /> path midangle(pair d,pair e,pair f) {return e--e+((f-e)/length(f-e)+(d-e)/length(d-e))/2;}<br /> draw(A--B--D--cycle);<br /> draw(circumcircle(A,B,D));<br /> draw(A--C--B);<br /> draw(A--I--B^^C--I);<br /> draw(incircle(A,B,C));<br /> label(&quot;$A$&quot;,A,SW,fontsize(8));<br /> label(&quot;$B$&quot;,B,SE,fontsize(8));<br /> label(&quot;$C$&quot;,C,N,fontsize(8));<br /> label(&quot;$D$&quot;,D,S,fontsize(8));<br /> label(&quot;$I$&quot;,I,NE,fontsize(8));<br /> label(&quot;$L$&quot;,L,SW,fontsize(8));<br /> label(&quot;$\alpha$&quot;,A,5*dir(midangle(C,A,I)),fontsize(8));<br /> label(&quot;$\alpha$&quot;,A,5*dir(midangle(I,A,B)),fontsize(8));<br /> label(&quot;$\beta$&quot;,B,12*dir(midangle(A,B,I)),fontsize(8));<br /> label(&quot;$\beta$&quot;,B,12*dir(midangle(I,B,C)),fontsize(8));<br /> label(&quot;$\gamma$&quot;,C,5*dir(midangle(A,C,I)),fontsize(8));<br /> label(&quot;$\gamma$&quot;,C,5*dir(midangle(I,C,B)),fontsize(8));<br /> &lt;/asy&gt;<br /> As &lt;math&gt;\angle BCD&lt;/math&gt; and &lt;math&gt;\angle BAD&lt;/math&gt; intercept the same arc, we know that &lt;math&gt;\angle BAD=\gamma&lt;/math&gt;. Similarly, &lt;math&gt;\angle ABD=\gamma&lt;/math&gt;. Also, using &lt;math&gt;\triangle ICA&lt;/math&gt;, we find &lt;math&gt;\angle CIA=180-\alpha-\gamma&lt;/math&gt;. Therefore, &lt;math&gt;\angle AID=\alpha+\gamma&lt;/math&gt;. Therefore, &lt;math&gt;\angle DAI=\angle AID=\alpha+\gamma&lt;/math&gt;, so &lt;math&gt;\triangle AID&lt;/math&gt; must be isosceles with &lt;math&gt;AD=ID=5&lt;/math&gt;. Similarly, &lt;math&gt;BD=ID=5&lt;/math&gt;. Then &lt;math&gt;\triangle DLB \sim \triangle ALC&lt;/math&gt;, hence &lt;math&gt;\frac{AL}{AC} = \frac{3}{5}&lt;/math&gt;. Also, &lt;math&gt;AI&lt;/math&gt; bisects &lt;math&gt;\angle LAC&lt;/math&gt;, so by the Angle Bisector Theorem &lt;math&gt;\frac{CI}{IL} =\frac{AC}{AL}= \frac{5}{3}&lt;/math&gt;. Thus &lt;math&gt;CI = \frac{10}{3}&lt;/math&gt;, and the answer is &lt;math&gt;\boxed{013}&lt;/math&gt;.<br /> <br /> ==Solution 2==<br /> <br /> WLOG assume &lt;math&gt;\triangle ABC&lt;/math&gt; is isosceles. Then, &lt;math&gt;L&lt;/math&gt; is the midpoint of &lt;math&gt;AB&lt;/math&gt;, and &lt;math&gt;\angle CLB=\angle CLA=90^\circ&lt;/math&gt;. Draw the perpendicular from &lt;math&gt;I&lt;/math&gt; to &lt;math&gt;CB&lt;/math&gt;, and let it meet &lt;math&gt;CB&lt;/math&gt; at &lt;math&gt;E&lt;/math&gt;. Since &lt;math&gt;IL=2&lt;/math&gt;, &lt;math&gt;IE&lt;/math&gt; is also &lt;math&gt;2&lt;/math&gt; (they are both inradii). Set &lt;math&gt;BD&lt;/math&gt; as &lt;math&gt;x&lt;/math&gt;. Then, triangles &lt;math&gt;BLD&lt;/math&gt; and &lt;math&gt;CEI&lt;/math&gt; are similar, and &lt;math&gt;\tfrac{2}{3}=\tfrac{CI}{x}&lt;/math&gt;. Thus, &lt;math&gt;CI=\tfrac{2x}{3}&lt;/math&gt;. &lt;math&gt;\triangle CBD \sim \triangle CEI&lt;/math&gt;, so &lt;math&gt;\tfrac{IE}{DB}=\tfrac{CI}{CD}&lt;/math&gt;. Thus &lt;math&gt;\tfrac{2}{x}=\tfrac{(2x/3)}{(2x/3+5)}&lt;/math&gt;. Solving for &lt;math&gt;x&lt;/math&gt;, we have:<br /> &lt;math&gt;x^2-2x-15=0&lt;/math&gt;, or &lt;math&gt;x=5, -3&lt;/math&gt;. &lt;math&gt;x&lt;/math&gt; is positive, so &lt;math&gt;x=5&lt;/math&gt;. As a result, &lt;math&gt;CI=\tfrac{2x}{3}=\tfrac{10}{3}&lt;/math&gt; and the answer is &lt;math&gt;\boxed{013}&lt;/math&gt;<br /> <br /> ==Solution 3==<br /> <br /> WLOG assume &lt;math&gt;\triangle ABC&lt;/math&gt; is isosceles (with vertex &lt;math&gt;C&lt;/math&gt;). Let &lt;math&gt;O&lt;/math&gt; be the center of the circumcircle, &lt;math&gt;R&lt;/math&gt; the circumradius, and &lt;math&gt;r&lt;/math&gt; the inradius. A simple sketch will reveal that &lt;math&gt;\triangle ABC&lt;/math&gt; must be obtuse (as an acute triangle will result in &lt;math&gt;LI&lt;/math&gt; being greater than &lt;math&gt;DL&lt;/math&gt;) and that &lt;math&gt;O&lt;/math&gt; and &lt;math&gt;I&lt;/math&gt; are collinear. Next, if &lt;math&gt;OI=d&lt;/math&gt;, &lt;math&gt;DO+OI=R+d&lt;/math&gt; and &lt;math&gt;R+d=DL+LI=5&lt;/math&gt;. Euler gives us that &lt;math&gt;d^{2}=R(R-2r)&lt;/math&gt;, and in this case, &lt;math&gt;r=LI=2&lt;/math&gt;. Thus, &lt;math&gt;d=\sqrt{R^{2}-4R}&lt;/math&gt;. Solving for &lt;math&gt;d&lt;/math&gt;, we have &lt;math&gt;R+\sqrt{R^{2}-4R}=5&lt;/math&gt;, then &lt;math&gt;R^{2}-4R=25-10R+R^{2}&lt;/math&gt;, yielding &lt;math&gt;R=\frac{25}{6}&lt;/math&gt;. Next, &lt;math&gt;R+d=5&lt;/math&gt; so &lt;math&gt;d=\frac{5}{6}&lt;/math&gt;. Finally, &lt;math&gt;OC=OI+IC&lt;/math&gt; gives us &lt;math&gt;R=d+IC&lt;/math&gt;, and &lt;math&gt;IC=\frac{25}{6}-\frac{5}{6}=\frac{10}{3}&lt;/math&gt;. Our answer is then &lt;math&gt;\boxed{013}&lt;/math&gt;.<br /> <br /> ==Solution 4==<br /> <br /> Since &lt;math&gt;\angle{LAD} = \angle{BDC}&lt;/math&gt; and &lt;math&gt;\angle{DLA}=\angle{DBC}&lt;/math&gt;, &lt;math&gt;\triangle{DLA}\sim\triangle{DBC}&lt;/math&gt;. Also, &lt;math&gt;\angle{DAC}=\angle{BLC}&lt;/math&gt; and &lt;math&gt;\angle{ACD}=\angle{LCB}&lt;/math&gt; so &lt;math&gt;\triangle{DAC}\sim\triangle{BLC}&lt;/math&gt;. Now we can call &lt;math&gt;AC&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;BC&lt;/math&gt;, &lt;math&gt;a&lt;/math&gt;. By angle bisector theorem, &lt;math&gt;\frac{AD}{DB}=\frac{AC}{BC}&lt;/math&gt;. So let &lt;math&gt;AD=bk&lt;/math&gt; and &lt;math&gt;DB=ak&lt;/math&gt; for some value of &lt;math&gt;k&lt;/math&gt;. Now call &lt;math&gt;IC=x&lt;/math&gt;. By the similar triangles we found earlier, &lt;math&gt;\frac{3}{ak}=\frac{bk}{x+2}&lt;/math&gt; and &lt;math&gt;\frac{b}{x+5}=\frac{x+2}{a}&lt;/math&gt;. We can simplify this to &lt;math&gt;abk^2=3x+6&lt;/math&gt; and &lt;math&gt;ab=(x+5)(x+2)&lt;/math&gt;. So we can plug the &lt;math&gt;ab&lt;/math&gt; into the first equation and get &lt;math&gt;(x+5)(x+2)k^2=3(x+2) \rightarrow k^2(x+5)=3&lt;/math&gt;. We can now draw a line through &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;I&lt;/math&gt; that intersects &lt;math&gt;BC&lt;/math&gt; at &lt;math&gt;E&lt;/math&gt;. By mass points, we can assign a mass of &lt;math&gt;a&lt;/math&gt; to &lt;math&gt;A&lt;/math&gt;, &lt;math&gt;b&lt;/math&gt; to &lt;math&gt;B&lt;/math&gt;, and &lt;math&gt;a+b&lt;/math&gt; to &lt;math&gt;D&lt;/math&gt;. We can also assign a mass of &lt;math&gt;(a+b)k&lt;/math&gt; to &lt;math&gt;C&lt;/math&gt; by angle bisector theorem. So the ratio of &lt;math&gt;\frac{DI}{IC}=\frac{(a+b)k}{a+b}=k=\frac{2}{x}&lt;/math&gt;. So since &lt;math&gt;k=\frac{2}{x}&lt;/math&gt;, we can plug this back into the original equation to get &lt;math&gt;\left(\frac{2}{x}\right)^2(x+5)=3&lt;/math&gt;. This means that &lt;math&gt;\frac{3x^2}{4}-x-5=0&lt;/math&gt; which has roots -2 and &lt;math&gt;\frac{10}{3}&lt;/math&gt; which means our &lt;math&gt;CI=\frac{10}{3}&lt;/math&gt; and our answer is &lt;math&gt;\boxed{013}&lt;/math&gt;.<br /> <br /> ==Solution 5==<br /> Since &lt;math&gt;\angle BCD&lt;/math&gt; and &lt;math&gt;\angle BAD&lt;/math&gt; both intercept arc &lt;math&gt;BD&lt;/math&gt;, it follows that &lt;math&gt;\angle BAD=\gamma&lt;/math&gt;. Note that &lt;math&gt;\angle AID=\alpha+\gamma&lt;/math&gt; by the external angle theorem. It follows that &lt;math&gt;\angle DAI=\angle AID=\alpha+\gamma&lt;/math&gt;, so we must have that &lt;math&gt;\triangle AID&lt;/math&gt; is isosceles, yielding &lt;math&gt;AD=ID=5&lt;/math&gt;. Note that &lt;math&gt;\triangle DLA \sim \triangle DAC&lt;/math&gt;, so &lt;math&gt;\frac{DA}{DL} = \frac{DC}{DA}&lt;/math&gt;. This yields &lt;math&gt;DC = \frac{25}{3}&lt;/math&gt;. It follows that &lt;math&gt;CI = DC - DI = \frac{10}{3}&lt;/math&gt;, giving a final answer of &lt;math&gt;\boxed{013}&lt;/math&gt;.<br /> <br /> ==Solution 6==<br /> Let &lt;math&gt;I_C&lt;/math&gt; be the excenter opposite to &lt;math&gt;C&lt;/math&gt; in &lt;math&gt;ABC&lt;/math&gt;. By the incenter-excenter lemma &lt;math&gt;DI=DC \therefore&lt;/math&gt; &lt;math&gt;LI_C=8,LI=2,II_C=10&lt;/math&gt;. Its well known that &lt;math&gt;(I_C,I,L,C)=-1 \implies \dfrac{LI_C}{LI}.\dfrac{CI}{CI_C}=-1 \implies \dfrac{CI}{CI+10}=\dfrac{1}{4} \implies \boxed{CI=\dfrac{10}{3}}&lt;/math&gt;.&lt;math&gt;\blacksquare&lt;/math&gt;<br /> ~Pluto1708<br /> <br /> Alternate solution: &quot;We can use the angle bisector theorem on &lt;math&gt;\triangle CBL&lt;/math&gt; and bisector &lt;math&gt;BI&lt;/math&gt; to get that &lt;math&gt;\tfrac{CI}{IL}=\tfrac{CI}{2}=\tfrac{BC}{BL}&lt;/math&gt;. Since &lt;math&gt;\triangle CBL \sim \triangle ADL&lt;/math&gt;, we get &lt;math&gt;\tfrac{BC}{BL}=\tfrac{AD}{DL}=\tfrac{5}{3}&lt;/math&gt;. Thus, &lt;math&gt;CI=\tfrac{10}{3}&lt;/math&gt; and &lt;math&gt;p+q=\boxed{13}&lt;/math&gt;.&quot;<br /> (https://artofproblemsolving.com/community/c759169h1918283_geometry_problem)<br /> <br /> == See also ==<br /> {{AIME box|year=2016|n=I|num-b=5|num-a=7}}<br /> {{MAA Notice}}</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Physics_books&diff=109071 Physics books 2019-08-20T22:41:25Z <p>Mag1c: fix Mathlinks link</p> <hr /> <div>These '''Physics books''' are recommended by [[Art of Problem Solving]] administrators and members of the [https://artofproblemsolving.com/wiki/index.php/MathLinks AoPS-MathLinks Community].<br /> <br /> Before adding any books to this page, please review the [[AoPSWiki:Linking books]] page.<br /> <br /> <br /> == Books by subject ==<br /> === Astrophysics and Cosmology ===<br /> * [http://www.amazon.com/exec/obidos/ASIN/0756613647/artofproblems-20 Universe] by Robert Dinwiddie, et al.<br /> * [http://www.amazon.com/exec/obidos/ASIN/0007162219/artofproblems-20/103-8732293-1555047 Big Bang] by Simon Singh<br /> <br /> === Chaos Theory ===<br /> * [http://www.amazon.com/exec/obidos/ASIN/0756613647/artofproblems-20 Chaos: Making a New Science] by James Gleick<br /> <br /> === Introductory Textbooks ===<br /> * [https://www.amazon.com/s?k=conceptual+physics&amp;ref=nb_sb_noss Conceptual Physics] by Paul Hewitt<br /> * [http://www.amazon.com/Physics-Scientists-Engineers-Standard-Version/dp/0716783398/ref=pd_bbs_sr_5/103-7161656-8805468?ie=UTF8&amp;s=books&amp;qid=1191019209&amp;sr=8-5 Physics for Scientists and Engineers] by Paul A. Tipler and Gene Mosca<br /> <br /> === Error Analysis ===<br /> * [https://www.goodreads.com/book/show/1017766.Introduction_to_Error_Analysis_Second_Edition Introduction to Error Analysis, Second Edition: The Study of Uncertainties in Physical Measurements] by John R. Taylor<br /> <br /> === Relativity, Quantum Mechanics, Particle Physics ===<br /> * [https://smile.amazon.com/Dreams-Final-Theory-Steven-Weinberg/dp/0679419233/ Dreams of a Final Theory] by Weinberg<br /> * [http://www.amazon.com/exec/obidos/ASIN/0393058581/artofproblems-20 The Elegant Universe: Superstrings, Hidden Dimensions, and the Quest for the Ultimate Theory] by Brian Greene.<br /> * [http://www.amazon.com/exec/obidos/ASIN/0375727205/artofproblems-20 The Fabric of the Cosmos: Space, Time, and the Texture of Reality] by Brian Greene.<br /> * [http://www.amazon.com/exec/obidos/ASIN/0060531096/artofproblems-20 Warped Passages: Unraveling the Mysteries of the Universe's Hidden Dimensions] by Lisa Randall.<br /> * [https://smile.amazon.com/General-relativity-B-Robert-Geroch/dp/0226288633/ General Relativity from A to B] by Geroch<br /> * [https://smile.amazon.com/Spacetime-Physics-John-Archibald-Wheeler/dp/0716703149/ Spacetime Physics] by Taylor and Wheeler<br /> * [https://smile.amazon.com/Quantum-Mechanics-Simple-Matrix-Physics/dp/0486445305/ Quantum Mechanics in Simple Matrix Form] by Jordan<br /> * [https://smile.amazon.com/Modern-Physics-Kenneth-S-Krane/dp/1118061144/ Modern Physics] by Krane<br /> * [https://www.goodreads.com/book/show/1989671.Quantum_Mechanics Quantum Mechanics: Theory and Applications] by Ghatak and Lokanathan<br /> * [https://www.goodreads.com/book/show/260190.Principles_of_Quantum_Mechanics Principles of Quantum Mechanics] by Shankar<br /> <br /> === Studying for the F=ma Exam ===<br /> The F=ma exam is the first round selection exam for the US Physics team, which selects five travelers to compete in the International Physics Olympiad.<br /> <br /> * [https://www.amazon.com/s?k=conceptual+physics&amp;ref=nb_sb_noss Conceptual Physics] by Paul Hewitt. This book is a basic introduction to physics.<br /> * [https://www.amazon.com/Thinking-Physics-Understandable-Practical-Reality/dp/0935218084/ Thinking Physics] by Lewis Carroll Epstein. This book contains hundreds of conceptual problems. Only some of the problems focus on mechanics.<br /> * [https://www.amazon.com/Problems-Solutions-Introductory-Mechanics-David/dp/1482086921/ Problems and Solutions in Introductory Mechanics] by David Morin. This is the single most-important book for F=ma training. A few of the problems require calculus (which the F=ma exam does not), but anyone who works through this entire book should be well-prepared for the test.<br /> * [https://smile.amazon.com/Physics-1-Robert-Resnick/dp/0471320579/ Physics] by Halliday, Resnick, and Krane (see note in USAPhO section) This is a calculus-based textbook that is very thorough, and good for getting a deeper understanding. It has thousands of challenging problems, and is useful for those who have covered the basics of mechanics and want to go deeper. It also covers many other topics in physics and will carry forward to the USAPhO exam.<br /> * Former F=ma exams are available from AAPT on their [https://www.aapt.org/physicsteam/2019/exams.cfm website]. There is also a [https://drive.google.com/file/d/1zBnBI3xEclkgIG_PNylPEHv6dL21Tyfk/view solution manual] to some of these exams. If your goal is to advance to USAPhO, you should solve all of the problems on all of the past exams.<br /> * Try [https://isaacphysics.org/ IsaacPhysics] for additional practice problems.<br /> * Take the [https://artofproblemsolving.com/school/course/fma AoPS F=ma Problem-Solving Series] course for additional practice, problem-solving forums, an original practice exam, and personalized guidance from expert teachers and assistants.<br /> <br /> === Studying for the USAPhO, IPhO, and other physics olympiads ===<br /> * [https://smile.amazon.com/Physics-1-Robert-Resnick/dp/0471320579/ Physics] by Halliday, Resnick, and Krane (see note below). This is the single-most important book to read to prepare for the USAPhO exam. This book covers everything and contains many challenging problems.<br /> * [https://smile.amazon.com/Introduction-Classical-Mechanics-Problems-Solutions/dp/0521876222 Introduction to Classical Mechanics] by David Morin. This book will take you deeper into mechanics, including some material (such as Lagrangian mechanics) beyond the syllabus of olympiads.<br /> * [https://smile.amazon.com/Electricity-Magnetism-Edward-M-Purcell/dp/1107014026/ Electricity and Magnetism] by Purcell and Morin. This is a great book on electromagnetism for those who want to learn it with multidimensional and vector calculus.<br /> * [https://www.amazon.com/Feynman-Lectures-Physics-boxed-set/dp/0465023827/ The Feynman Lectures on Physics] by Feynman. This is a deeply-insightful set of lectures that covers a very broad swath of physics, but does not on its own contain practice problems.<br /> * [https://www.aapt.org/physicsteam/2019/exams.cfm Past USAPhO Exams] are available from AAPT.<br /> * Take [https://artofproblemsolving.com/school/woot-physics PhysicsWOOT] to practice USAPhO-style problem solving, take four original USAPhO practice exams and two original F=ma exams, access problem-solving forums, get personalized feedback and help from expert teachers and assistants, and for even more practice.<br /> * [https://www.ipho-new.org/documentations/ Official IPhO problems] from past Olympiads are available for download.<br /> * [https://www.ioc.ee/~kalda/ipho/ Jaan Kalda's resources] contain a huge number of practice problems.<br /> <br /> Note: There are two introductory physics texts by Halliday and Resnick. This happened because after their first textbook had existed for a decade, some colleges began asking for an easier version.<br /> <br /> &quot;Physics&quot; by Resnick, Halliday, and Krane is in its 5th edition (published 2002). This book is often called &quot;HRK&quot;. It is the recommended book for Olympiad preparation. The current editor is Paul Stanley, former academic director of the US Physics team. This edition has many challenging problems in it.<br /> <br /> &quot;Fundamentals of Physics&quot; by Halliday, Resnick, and Walker is in its 10th edition (published 2013). This edition describes the basic physics of the same topics as HRK. However, it goes into less detail, omits some of the interesting calculations, and has fewer challenging problems. Although this is a good book, it is not written to train students to the same level of problem-solving ability as HRK. So HRK is recommended for those interested in improving their problem-solving ability to the level of the USAPhO or similar olympiad physics competitions.<br /> <br /> There are a large number of introductory, calculus-based textbooks available. They all cover similar material, so other books, such as Giancoli, Thomas Moore, Sherwood and Sherwood, Knight, Mazur, Cummings Laws Redish and Cooney, etc. are all acceptable for basic readings. However, for those seeking to earn medals or make the US Physics team on USAPhO, additional problem-solving practice through old exams, PhysicsWOOT, and other sources of problems is recommended.<br /> <br /> === Books of Problems ===<br /> <br /> * [https://smile.amazon.com/Thinking-Physics-Understandable-Practical-Reality/dp/0935218084 Thinking Physics] by Lewis Carroll Epstein (a book of conceptual problems for beginners and intermediate-levels)<br /> * [https://smile.amazon.com/Problems-Solutions-Introductory-Mechanics-David/dp/1482086921 Problems and Solutions in Introductory Mechanics] by David Morin (A good book for preparing to the F=ma exam and for practicing basic mechanics)<br /> * [https://smile.amazon.com/200-Puzzling-Physics-Problems-Solutions/dp/0521774802 200 Puzzling Physics Problems] by Gnadig (USAPhO / IPhO level problems)<br /> * [https://smile.amazon.com/Creative-Physics-Problems-Solutions-Learning/dp/1843318695 300 Creative Physics Problems with Solutions] by Holics (USAPhO / IPhO level problems)<br /> * [https://smile.amazon.com/Physics-Degree-G-Thomas/dp/9056992775 Physics to a Degree] by Thomas and Raine (USAPhO / IPhO level problems)<br /> * [https://smile.amazon.com/Thinking-Like-Physicist-Undergraduates-1987-07-01/dp/B01K0RZDYK Thinking Like a Physicist] by Thompson (USAPhO / IPhO level problems)<br /> <br /> == General interest ==<br /> * [http://www.amazon.com/exec/obidos/ASIN/0553380168/artofproblems-20 A Brief History of Time] by Steven Hawking<br /> * [http://www.amazon.com/exec/obidos/ASIN/0684813785/artofproblems-20 The Making of the Atomic Bomb] by Richard Rhodes<br /> * [http://www.amazon.com/exec/obidos/ASIN/0393316041/artofproblems-20 'Surely You're Joking, Mr. Feynman!' (Adventures of a Curious Character)] by Richard P. Feynman, et al.<br /> * [http://www.amazon.com/exec/obidos/ASIN/0679776311/artofproblems-20 The Road to Reality: A Complete Guide to the Laws of the Universe] by Roger Penrose.<br /> * [https://www.nsta.org/publications/quantum.aspx#index Quantum Magazine] Only archives available; publication ceased.<br /> <br /> == See Also ==<br /> * [[Science books]]<br /> * [[Physics competitions]]<br /> * [[Physics scholarships]]<br /> * [[Physics]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Physics_books&diff=109070 Physics books 2019-08-20T22:40:41Z <p>Mag1c: fix Mathlinks link</p> <hr /> <div>These '''Physics books''' are recommended by [[Art of Problem Solving]] administrators and members of the &lt;url&gt;https://artofproblemsolving.com/wiki/index.php/MathLinks AoPS-MathLinks Community&lt;/url&gt;.<br /> <br /> Before adding any books to this page, please review the [[AoPSWiki:Linking books]] page.<br /> <br /> <br /> == Books by subject ==<br /> === Astrophysics and Cosmology ===<br /> * [http://www.amazon.com/exec/obidos/ASIN/0756613647/artofproblems-20 Universe] by Robert Dinwiddie, et al.<br /> * [http://www.amazon.com/exec/obidos/ASIN/0007162219/artofproblems-20/103-8732293-1555047 Big Bang] by Simon Singh<br /> <br /> === Chaos Theory ===<br /> * [http://www.amazon.com/exec/obidos/ASIN/0756613647/artofproblems-20 Chaos: Making a New Science] by James Gleick<br /> <br /> === Introductory Textbooks ===<br /> * [https://www.amazon.com/s?k=conceptual+physics&amp;ref=nb_sb_noss Conceptual Physics] by Paul Hewitt<br /> * [http://www.amazon.com/Physics-Scientists-Engineers-Standard-Version/dp/0716783398/ref=pd_bbs_sr_5/103-7161656-8805468?ie=UTF8&amp;s=books&amp;qid=1191019209&amp;sr=8-5 Physics for Scientists and Engineers] by Paul A. Tipler and Gene Mosca<br /> <br /> === Error Analysis ===<br /> * [https://www.goodreads.com/book/show/1017766.Introduction_to_Error_Analysis_Second_Edition Introduction to Error Analysis, Second Edition: The Study of Uncertainties in Physical Measurements] by John R. Taylor<br /> <br /> === Relativity, Quantum Mechanics, Particle Physics ===<br /> * [https://smile.amazon.com/Dreams-Final-Theory-Steven-Weinberg/dp/0679419233/ Dreams of a Final Theory] by Weinberg<br /> * [http://www.amazon.com/exec/obidos/ASIN/0393058581/artofproblems-20 The Elegant Universe: Superstrings, Hidden Dimensions, and the Quest for the Ultimate Theory] by Brian Greene.<br /> * [http://www.amazon.com/exec/obidos/ASIN/0375727205/artofproblems-20 The Fabric of the Cosmos: Space, Time, and the Texture of Reality] by Brian Greene.<br /> * [http://www.amazon.com/exec/obidos/ASIN/0060531096/artofproblems-20 Warped Passages: Unraveling the Mysteries of the Universe's Hidden Dimensions] by Lisa Randall.<br /> * [https://smile.amazon.com/General-relativity-B-Robert-Geroch/dp/0226288633/ General Relativity from A to B] by Geroch<br /> * [https://smile.amazon.com/Spacetime-Physics-John-Archibald-Wheeler/dp/0716703149/ Spacetime Physics] by Taylor and Wheeler<br /> * [https://smile.amazon.com/Quantum-Mechanics-Simple-Matrix-Physics/dp/0486445305/ Quantum Mechanics in Simple Matrix Form] by Jordan<br /> * [https://smile.amazon.com/Modern-Physics-Kenneth-S-Krane/dp/1118061144/ Modern Physics] by Krane<br /> * [https://www.goodreads.com/book/show/1989671.Quantum_Mechanics Quantum Mechanics: Theory and Applications] by Ghatak and Lokanathan<br /> * [https://www.goodreads.com/book/show/260190.Principles_of_Quantum_Mechanics Principles of Quantum Mechanics] by Shankar<br /> <br /> === Studying for the F=ma Exam ===<br /> The F=ma exam is the first round selection exam for the US Physics team, which selects five travelers to compete in the International Physics Olympiad.<br /> <br /> * [https://www.amazon.com/s?k=conceptual+physics&amp;ref=nb_sb_noss Conceptual Physics] by Paul Hewitt. This book is a basic introduction to physics.<br /> * [https://www.amazon.com/Thinking-Physics-Understandable-Practical-Reality/dp/0935218084/ Thinking Physics] by Lewis Carroll Epstein. This book contains hundreds of conceptual problems. Only some of the problems focus on mechanics.<br /> * [https://www.amazon.com/Problems-Solutions-Introductory-Mechanics-David/dp/1482086921/ Problems and Solutions in Introductory Mechanics] by David Morin. This is the single most-important book for F=ma training. A few of the problems require calculus (which the F=ma exam does not), but anyone who works through this entire book should be well-prepared for the test.<br /> * [https://smile.amazon.com/Physics-1-Robert-Resnick/dp/0471320579/ Physics] by Halliday, Resnick, and Krane (see note in USAPhO section) This is a calculus-based textbook that is very thorough, and good for getting a deeper understanding. It has thousands of challenging problems, and is useful for those who have covered the basics of mechanics and want to go deeper. It also covers many other topics in physics and will carry forward to the USAPhO exam.<br /> * Former F=ma exams are available from AAPT on their [https://www.aapt.org/physicsteam/2019/exams.cfm website]. There is also a [https://drive.google.com/file/d/1zBnBI3xEclkgIG_PNylPEHv6dL21Tyfk/view solution manual] to some of these exams. If your goal is to advance to USAPhO, you should solve all of the problems on all of the past exams.<br /> * Try [https://isaacphysics.org/ IsaacPhysics] for additional practice problems.<br /> * Take the [https://artofproblemsolving.com/school/course/fma AoPS F=ma Problem-Solving Series] course for additional practice, problem-solving forums, an original practice exam, and personalized guidance from expert teachers and assistants.<br /> <br /> === Studying for the USAPhO, IPhO, and other physics olympiads ===<br /> * [https://smile.amazon.com/Physics-1-Robert-Resnick/dp/0471320579/ Physics] by Halliday, Resnick, and Krane (see note below). This is the single-most important book to read to prepare for the USAPhO exam. This book covers everything and contains many challenging problems.<br /> * [https://smile.amazon.com/Introduction-Classical-Mechanics-Problems-Solutions/dp/0521876222 Introduction to Classical Mechanics] by David Morin. This book will take you deeper into mechanics, including some material (such as Lagrangian mechanics) beyond the syllabus of olympiads.<br /> * [https://smile.amazon.com/Electricity-Magnetism-Edward-M-Purcell/dp/1107014026/ Electricity and Magnetism] by Purcell and Morin. This is a great book on electromagnetism for those who want to learn it with multidimensional and vector calculus.<br /> * [https://www.amazon.com/Feynman-Lectures-Physics-boxed-set/dp/0465023827/ The Feynman Lectures on Physics] by Feynman. This is a deeply-insightful set of lectures that covers a very broad swath of physics, but does not on its own contain practice problems.<br /> * [https://www.aapt.org/physicsteam/2019/exams.cfm Past USAPhO Exams] are available from AAPT.<br /> * Take [https://artofproblemsolving.com/school/woot-physics PhysicsWOOT] to practice USAPhO-style problem solving, take four original USAPhO practice exams and two original F=ma exams, access problem-solving forums, get personalized feedback and help from expert teachers and assistants, and for even more practice.<br /> * [https://www.ipho-new.org/documentations/ Official IPhO problems] from past Olympiads are available for download.<br /> * [https://www.ioc.ee/~kalda/ipho/ Jaan Kalda's resources] contain a huge number of practice problems.<br /> <br /> Note: There are two introductory physics texts by Halliday and Resnick. This happened because after their first textbook had existed for a decade, some colleges began asking for an easier version.<br /> <br /> &quot;Physics&quot; by Resnick, Halliday, and Krane is in its 5th edition (published 2002). This book is often called &quot;HRK&quot;. It is the recommended book for Olympiad preparation. The current editor is Paul Stanley, former academic director of the US Physics team. This edition has many challenging problems in it.<br /> <br /> &quot;Fundamentals of Physics&quot; by Halliday, Resnick, and Walker is in its 10th edition (published 2013). This edition describes the basic physics of the same topics as HRK. However, it goes into less detail, omits some of the interesting calculations, and has fewer challenging problems. Although this is a good book, it is not written to train students to the same level of problem-solving ability as HRK. So HRK is recommended for those interested in improving their problem-solving ability to the level of the USAPhO or similar olympiad physics competitions.<br /> <br /> There are a large number of introductory, calculus-based textbooks available. They all cover similar material, so other books, such as Giancoli, Thomas Moore, Sherwood and Sherwood, Knight, Mazur, Cummings Laws Redish and Cooney, etc. are all acceptable for basic readings. However, for those seeking to earn medals or make the US Physics team on USAPhO, additional problem-solving practice through old exams, PhysicsWOOT, and other sources of problems is recommended.<br /> <br /> === Books of Problems ===<br /> <br /> * [https://smile.amazon.com/Thinking-Physics-Understandable-Practical-Reality/dp/0935218084 Thinking Physics] by Lewis Carroll Epstein (a book of conceptual problems for beginners and intermediate-levels)<br /> * [https://smile.amazon.com/Problems-Solutions-Introductory-Mechanics-David/dp/1482086921 Problems and Solutions in Introductory Mechanics] by David Morin (A good book for preparing to the F=ma exam and for practicing basic mechanics)<br /> * [https://smile.amazon.com/200-Puzzling-Physics-Problems-Solutions/dp/0521774802 200 Puzzling Physics Problems] by Gnadig (USAPhO / IPhO level problems)<br /> * [https://smile.amazon.com/Creative-Physics-Problems-Solutions-Learning/dp/1843318695 300 Creative Physics Problems with Solutions] by Holics (USAPhO / IPhO level problems)<br /> * [https://smile.amazon.com/Physics-Degree-G-Thomas/dp/9056992775 Physics to a Degree] by Thomas and Raine (USAPhO / IPhO level problems)<br /> * [https://smile.amazon.com/Thinking-Like-Physicist-Undergraduates-1987-07-01/dp/B01K0RZDYK Thinking Like a Physicist] by Thompson (USAPhO / IPhO level problems)<br /> <br /> == General interest ==<br /> * [http://www.amazon.com/exec/obidos/ASIN/0553380168/artofproblems-20 A Brief History of Time] by Steven Hawking<br /> * [http://www.amazon.com/exec/obidos/ASIN/0684813785/artofproblems-20 The Making of the Atomic Bomb] by Richard Rhodes<br /> * [http://www.amazon.com/exec/obidos/ASIN/0393316041/artofproblems-20 'Surely You're Joking, Mr. Feynman!' (Adventures of a Curious Character)] by Richard P. Feynman, et al.<br /> * [http://www.amazon.com/exec/obidos/ASIN/0679776311/artofproblems-20 The Road to Reality: A Complete Guide to the Laws of the Universe] by Roger Penrose.<br /> * [https://www.nsta.org/publications/quantum.aspx#index Quantum Magazine] Only archives available; publication ceased.<br /> <br /> == See Also ==<br /> * [[Science books]]<br /> * [[Physics competitions]]<br /> * [[Physics scholarships]]<br /> * [[Physics]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Chicken_McNugget_Theorem&diff=109069 Chicken McNugget Theorem 2019-08-20T22:35:12Z <p>Mag1c: simplify table</p> <hr /> <div>The '''Chicken McNugget Theorem''' (or '''Postage Stamp Problem''' or '''Frobenius Coin Problem''') states that for any two [[relatively prime]] [[positive integer]]s &lt;math&gt;m,n&lt;/math&gt;, the greatest integer that cannot be written in the form &lt;math&gt;am + bn&lt;/math&gt; for [[nonnegative]] integers &lt;math&gt;a, b&lt;/math&gt; is &lt;math&gt;mn-m-n&lt;/math&gt;.<br /> <br /> A consequence of the theorem is that there are exactly &lt;math&gt;\frac{(m - 1)(n - 1)}{2}&lt;/math&gt; positive integers which cannot be expressed in the form &lt;math&gt;am + bn&lt;/math&gt;. The proof is based on the fact that in each pair of the form &lt;math&gt;(k, (m - 1)(n - 1) - k+1)&lt;/math&gt;, exactly one element is expressible.<br /> <br /> == Origins ==<br /> There are many stories surrounding the origin of the Chicken McNugget theorem. However, the most popular by far remains that of the Chicken McNugget. Originally, McDonald's sold its nuggets in packs of 9 and 20. Math enthusiasts were curious to find the largest number of nuggets that could not have been bought with these packs, thus creating the Chicken McNugget Theorem (the answer worked out to be 151 nuggets). The Chicken McNugget Theorem has also been called the Frobenius Coin Problem or the Frobenius Problem, after German mathematician Ferdinand Frobenius inquired about the largest amount of currency that could not have been made with certain types of coins.<br /> <br /> <br /> <br /> <br /> <br /> ==Proof Without Words==<br /> &lt;math&gt;\begin{array}{ccccccc}<br /> 0\mod{m}&amp;1\mod{m}&amp;2\mod{m}&amp;...&amp;...&amp;...&amp;(m-1)\mod{m}\\<br /> \hline<br /> \cancel{0n}&amp;1&amp;2&amp;&amp;...&amp;&amp;m-1\\<br /> \cancel{0n+m}&amp;...&amp;&amp;\vdots&amp;&amp;...&amp;\\<br /> \cancel{0n+2m}&amp;...&amp;&amp;\cancel{1n}&amp;&amp;...&amp;\\<br /> \cancel{0n+3m}&amp;&amp;&amp;\cancel{1n+m}&amp;&amp;\vdots&amp;\\<br /> \cancel{0n+4m}&amp;&amp;&amp;\cancel{1n+2m}&amp;&amp;\cancel{2n}&amp;\\<br /> \cancel{0n+5m}&amp;&amp;&amp;\cancel{1n+3m}&amp;&amp;\cancel{2n+m}&amp;\\<br /> \vdots&amp;&amp;&amp;\vdots&amp;&amp;\vdots&amp;\\<br /> \cancel{\qquad}&amp;\cancel{\qquad}&amp;\cancel{ \qquad}&amp;\cancel{ \qquad}&amp;\mathbf{(m-1)n-m}&amp;\cancel{\qquad }&amp;\cancel{\qquad }\\<br /> \cancel{\qquad}&amp;\cancel{\qquad}&amp;\cancel{ \qquad}&amp;\cancel{ \qquad}&amp;\cancel{(m-1)n}&amp;\cancel{\qquad }&amp;\cancel{\qquad }<br /> \end{array}&lt;/math&gt;<br /> <br /> ==Proof 1==<br /> &lt;b&gt;Definition&lt;/b&gt;. An integer &lt;math&gt;N \in \mathbb{Z}&lt;/math&gt; will be called &lt;i&gt;purchasable&lt;/i&gt; if there exist nonnegative integers &lt;math&gt;a,b&lt;/math&gt; such that &lt;math&gt;am+bn = N&lt;/math&gt;.<br /> <br /> We would like to prove that &lt;math&gt;mn-m-n&lt;/math&gt; is the largest non-purchasable integer. We are required to show that (1) &lt;math&gt;mn-m-n&lt;/math&gt; is non-purchasable, and (2) every &lt;math&gt;N &gt; mn-m-n&lt;/math&gt; is purchasable. <br /> Note that all purchasable integers are nonnegative, thus the set of non-purchasable integers is nonempty.<br /> <br /> &lt;b&gt;Lemma&lt;/b&gt;. Let &lt;math&gt;A_{N} \subset \mathbb{Z} \times \mathbb{Z}&lt;/math&gt; be the set of solutions &lt;math&gt;(x,y)&lt;/math&gt; to &lt;math&gt;xm+yn = N&lt;/math&gt;. Then &lt;math&gt;A_{N} = \{(x+kn,y-km) \;:\; k \in \mathbb{Z}\}&lt;/math&gt; for any &lt;math&gt;(x,y) \in A_{N}&lt;/math&gt;.<br /> <br /> &lt;i&gt;Proof&lt;/i&gt;: By [[Bezout's Lemma]], there exist integers &lt;math&gt;x',y'&lt;/math&gt; such that &lt;math&gt;x'm+y'n = 1&lt;/math&gt;. Then &lt;math&gt;(Nx')m+(Ny')n = N&lt;/math&gt;. Hence &lt;math&gt;A_{N}&lt;/math&gt; is nonempty. It is easy to check that &lt;math&gt;(Nx'+kn,Ny'-km) \in A_{N}&lt;/math&gt; for all &lt;math&gt;k \in \mathbb{Z}&lt;/math&gt;. We now prove that there are no others. Suppose &lt;math&gt;(x_{1},y_{1})&lt;/math&gt; and &lt;math&gt;(x_{2},y_{2})&lt;/math&gt; are solutions to &lt;math&gt;xm+yn=N&lt;/math&gt;. Then &lt;math&gt;x_{1}m+y_{1}n = x_{2}m+y_{2}n&lt;/math&gt; implies &lt;math&gt;m(x_{1}-x_{2}) = n(y_{2}-y_{1})&lt;/math&gt;. Since &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are coprime and &lt;math&gt;m&lt;/math&gt; divides &lt;math&gt;n(y_{2}-y_{1})&lt;/math&gt;, &lt;math&gt;m&lt;/math&gt; divides &lt;math&gt;y_{2}-y_{1}&lt;/math&gt; and &lt;math&gt;y_{2} \equiv y_{1} \pmod{m}&lt;/math&gt;. Similarly &lt;math&gt;x_{2} \equiv x_{1} \pmod{n}&lt;/math&gt;. Let &lt;math&gt;k_{1},k_{2}&lt;/math&gt; be integers such that &lt;math&gt;x_{2}-x_{1} = k_{1}n&lt;/math&gt; and &lt;math&gt;y_{2}-y_{1} = k_{2}m&lt;/math&gt;. Then &lt;math&gt;m(-k_{1}n) = n(k_{2}m)&lt;/math&gt; implies &lt;math&gt;k_{1} = -k_{2}.&lt;/math&gt; We have the desired result. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> &lt;b&gt;Lemma&lt;/b&gt;. For any integer &lt;math&gt;N&lt;/math&gt;, there exists unique &lt;math&gt;(a_{N},b_{N}) \in \mathbb{Z} \times \{0,1,\ldots,m-1\}&lt;/math&gt; such that &lt;math&gt;a_{N}m + b_{N}n = N&lt;/math&gt;.<br /> <br /> &lt;i&gt;Proof&lt;/i&gt;: By the division algorithm, there exists one and only one &lt;math&gt;k&lt;/math&gt; such that &lt;math&gt;0 \le y-km \le m-1&lt;/math&gt;. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> &lt;b&gt;Lemma&lt;/b&gt;. &lt;math&gt;N&lt;/math&gt; is purchasable if and only if &lt;math&gt;a_{N} \ge 0&lt;/math&gt;.<br /> <br /> &lt;i&gt;Proof&lt;/i&gt;: If &lt;math&gt;a_{N} \ge 0&lt;/math&gt;, then we may simply pick &lt;math&gt;(a,b) = (a_{N},b_{N})&lt;/math&gt; so &lt;math&gt;N&lt;/math&gt; is purchasable. If &lt;math&gt;a_{N} &lt; 0&lt;/math&gt;, then &lt;math&gt;a_{N}+kn &lt; 0&lt;/math&gt; if &lt;math&gt;k \le 0&lt;/math&gt; and &lt;math&gt;b_{N}-km &lt; 0&lt;/math&gt; if &lt;math&gt;k &gt; 0&lt;/math&gt;, hence at least one coordinate of &lt;math&gt;(a_{N}+kn,b_{N}-km)&lt;/math&gt; is negative for all &lt;math&gt;k \in \mathbb{Z}&lt;/math&gt;. Thus &lt;math&gt;N&lt;/math&gt; is not purchasable. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> Thus the set of non-purchasable integers is &lt;math&gt;\{xm+yn \;:\; x&lt;0,0 \le y \le m-1\}&lt;/math&gt;. We would like to find the maximum of this set. <br /> Since both &lt;math&gt;m,n&lt;/math&gt; are positive, the maximum is achieved when &lt;math&gt;x = -1&lt;/math&gt; and &lt;math&gt;y = m-1&lt;/math&gt; so that &lt;math&gt;xm+yn = (-1)m+(m-1)n = mn-m-n&lt;/math&gt;.<br /> <br /> ==Proof 2==<br /> We start with this statement taken from [[Fermat%27s_Little_Theorem#Proof_2_.28Inverses.29|Proof 2 of Fermat's Little Theorem]]:<br /> <br /> &quot;Let &lt;math&gt;S = \{1,2,3,\cdots, p-1\}&lt;/math&gt;. Then, we claim that the set &lt;math&gt;a \cdot S&lt;/math&gt;, consisting of the product of the elements of &lt;math&gt;S&lt;/math&gt; with &lt;math&gt;a&lt;/math&gt;, taken modulo &lt;math&gt;p&lt;/math&gt;, is simply a permutation of &lt;math&gt;S&lt;/math&gt;. In other words, <br /> <br /> &lt;center&gt;&lt;cmath&gt;S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.&lt;/cmath&gt;&lt;/center&gt;&lt;br&gt;<br /> <br /> Clearly none of the &lt;math&gt;ia&lt;/math&gt; for &lt;math&gt;1 \le i \le p-1&lt;/math&gt; are divisible by &lt;math&gt;p&lt;/math&gt;, so it suffices to show that all of the elements in &lt;math&gt;a \cdot S&lt;/math&gt; are distinct. Suppose that &lt;math&gt;ai \equiv aj \pmod{p}&lt;/math&gt; for &lt;math&gt;i \neq j&lt;/math&gt;. Since &lt;math&gt;\text{gcd}\, (a,p) = 1&lt;/math&gt;, by the cancellation rule, that reduces to &lt;math&gt;i \equiv j \pmod{p}&lt;/math&gt;, which is a contradiction.&quot;<br /> <br /> Because &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are coprime, we know that multiplying the residues of &lt;math&gt;m&lt;/math&gt; by &lt;math&gt;n&lt;/math&gt; simply permutes these residues. Each of these permuted residues is purchasable (using the definition from Proof 1), because, in the form &lt;math&gt;am+bn&lt;/math&gt;, &lt;math&gt;a&lt;/math&gt; is &lt;math&gt;0&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; is the original residue. We now prove the following lemma.<br /> <br /> &lt;b&gt;Lemma&lt;/b&gt;: For any nonnegative integer &lt;math&gt;c &lt; m&lt;/math&gt;, &lt;math&gt;cn&lt;/math&gt; is the least purchasable number &lt;math&gt;\equiv cn \bmod m&lt;/math&gt;.<br /> <br /> &lt;i&gt;Proof&lt;/i&gt;: Any number that is less than &lt;math&gt;cn&lt;/math&gt; and congruent to it &lt;math&gt;\bmod m&lt;/math&gt; can be represented in the form &lt;math&gt;cn-dm&lt;/math&gt;, where &lt;math&gt;d&lt;/math&gt; is a positive integer. If this is purchasable, we can say &lt;math&gt;cn-dm=am+bn&lt;/math&gt; for some nonnegative integers &lt;math&gt;a, b&lt;/math&gt;. This can be rearranged into &lt;math&gt;(a+d)m=(c-b)n&lt;/math&gt;, which implies that &lt;math&gt;(a+d)&lt;/math&gt; is a multiple of &lt;math&gt;n&lt;/math&gt; (since &lt;math&gt;\gcd(m, n)=1&lt;/math&gt;). We can say that &lt;math&gt;(a+d)=gn&lt;/math&gt; for some positive integer &lt;math&gt;g&lt;/math&gt;, and substitute to get &lt;math&gt;gmn=(c-b)n&lt;/math&gt;. Because &lt;math&gt;c &lt; m&lt;/math&gt;, &lt;math&gt;(c-b)n &lt; mn&lt;/math&gt;, and &lt;math&gt;gmn &lt; mn&lt;/math&gt;. We divide by &lt;math&gt;mn&lt;/math&gt; to get &lt;math&gt;g&lt;1&lt;/math&gt;. However, we defined &lt;math&gt;g&lt;/math&gt; to be a positive integer, and all positive integers are greater than or equal to &lt;math&gt;1&lt;/math&gt;. Therefore, we have a contradiction, and &lt;math&gt;cn&lt;/math&gt; is the least purchasable number congruent to &lt;math&gt;cn \bmod m&lt;/math&gt;. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> This means that because &lt;math&gt;cn&lt;/math&gt; is purchasable, every number that is greater than &lt;math&gt;cn&lt;/math&gt; and congruent to it &lt;math&gt;\bmod m&lt;/math&gt; is also purchasable (because these numbers are in the form &lt;math&gt;am+bn&lt;/math&gt; where &lt;math&gt;b=c&lt;/math&gt;). Another result of this Lemma is that &lt;math&gt;cn-m&lt;/math&gt; is the greatest number &lt;math&gt;\equiv cn \bmod m&lt;/math&gt; that is not purchasable. &lt;math&gt;c \leq m-1&lt;/math&gt;, so &lt;math&gt;cn-m \leq (m-1)n-m=mn-m-n&lt;/math&gt;, which shows that &lt;math&gt;mn-m-n&lt;/math&gt; is the greatest number in the form &lt;math&gt;cn-m&lt;/math&gt;. Any number greater than this and congruent to some &lt;math&gt;cn \bmod m&lt;/math&gt; is purchasable, because that number is greater than &lt;math&gt;cn&lt;/math&gt;. All numbers are congruent to some &lt;math&gt;cn&lt;/math&gt;, and thus all numbers greater than &lt;math&gt;mn-m-n&lt;/math&gt; are purchasable.<br /> <br /> Putting it all together, we can say that for any coprime &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt;, &lt;math&gt;mn-m-n&lt;/math&gt; is the greatest number not representable in the form &lt;math&gt;am + bn&lt;/math&gt; for nonnegative integers &lt;math&gt;a, b&lt;/math&gt;. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> ==Corollary==<br /> This corollary is based off of Proof 2, so it is necessary to read that proof before this corollary. We prove the following lemma.<br /> <br /> &lt;b&gt;Lemma&lt;/b&gt; For any integer &lt;math&gt;k&lt;/math&gt;, exactly one of the integers &lt;math&gt;k&lt;/math&gt;, &lt;math&gt;mn-m-n-k&lt;/math&gt; is not purchasable.<br /> <br /> &lt;i&gt;Proof&lt;/i&gt;: Because every number is congruent to some residue of &lt;math&gt;m&lt;/math&gt; permuted by &lt;math&gt;n&lt;/math&gt;, we can set &lt;math&gt;k \equiv cn \bmod m&lt;/math&gt; for some &lt;math&gt;c&lt;/math&gt;. We can break this into two cases.<br /> <br /> &lt;i&gt;Case 1&lt;/i&gt;: &lt;math&gt;k \leq cn-m&lt;/math&gt;. This implies that &lt;math&gt;k&lt;/math&gt; is not purchasable, and that &lt;math&gt;mn-m-n-k \geq mn-m-n-(cn-m) = n(m-1-c)&lt;/math&gt;. &lt;math&gt;n(m-1-c)&lt;/math&gt; is a permuted residue, and a result of the lemma in Proof 2 was that a permuted residue is the least number congruent to itself &lt;math&gt;\bmod m&lt;/math&gt; that is purchasable. Therefore, &lt;math&gt;mn-m-n-k \equiv n(m-1-c) \bmod m&lt;/math&gt; and &lt;math&gt;mn-m-n-k \geq n(m-1-c)&lt;/math&gt;, so &lt;math&gt;mn-m-n-k&lt;/math&gt; is purchasable.<br /> <br /> &lt;i&gt;Case 2&lt;/i&gt;: &lt;math&gt;k &gt; cn-m&lt;/math&gt;. This implies that &lt;math&gt;k&lt;/math&gt; is purchasable, and that &lt;math&gt;mn-m-n-k &lt; mn-m-n-(cn-m) = n(m-1-c)&lt;/math&gt;. Again, because &lt;math&gt;n(m-1-c)&lt;/math&gt; is the least number congruent to itself &lt;math&gt;\bmod m&lt;/math&gt; that is purchasable, and because &lt;math&gt;mn-m-n-k \equiv n(m-1-c) \bmod m&lt;/math&gt; and &lt;math&gt;mn-m-n-k &lt; n(m-1-c)&lt;/math&gt;, &lt;math&gt;mn-m-n-k&lt;/math&gt; is not purchasable.<br /> <br /> We now limit the values of &lt;math&gt;k&lt;/math&gt; to all integers &lt;math&gt;0 \leq k \leq \frac{mn-m-n}{2}&lt;/math&gt;, which limits the values of &lt;math&gt;mn-m-n-k&lt;/math&gt; to &lt;math&gt;mn-m-n \geq mn-m-n-k \geq \frac{mn-m-n}{2}&lt;/math&gt;. Because &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are coprime, only one of them can be a multiple of &lt;math&gt;2&lt;/math&gt;. Therefore, &lt;math&gt;mn-m-n \equiv (0)(1)-0-1 \equiv -1 \equiv 1 \bmod 2&lt;/math&gt;, showing that &lt;math&gt;\frac{mn-m-n}{2}&lt;/math&gt; is not an integer and that &lt;math&gt;\frac{mn-m-n-1}{2}&lt;/math&gt; and &lt;math&gt;\frac{mn-m-n+1}{2}&lt;/math&gt; are integers. We can now set limits that are equivalent to the previous on the values of &lt;math&gt;k&lt;/math&gt; and &lt;math&gt;mn-m-n-k&lt;/math&gt; so that they cover all integers form &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;mn-m-n&lt;/math&gt; without overlap: &lt;math&gt;0 \leq k \leq \frac{mn-m-n-1}{2}&lt;/math&gt; and &lt;math&gt;\frac{mn-m-n+1}{2} \leq mn-m-n-k \leq mn-m-n&lt;/math&gt;. There are &lt;math&gt;\frac{mn-m-n-1}{2}+1=\frac{(m-1)(n-1)}{2}&lt;/math&gt; values of &lt;math&gt;k&lt;/math&gt;, and each is paired with a value of &lt;math&gt;mn-m-n-k&lt;/math&gt;, so we can make &lt;math&gt;\frac{(m-1)(n-1)}{2}&lt;/math&gt; different ordered pairs of the form &lt;math&gt;(k, mn-m-n-k)&lt;/math&gt;. The coordinates of these ordered pairs cover all integers from &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;mn-m-n&lt;/math&gt; inclusive, and each contains exactly one not-purchasable integer, so that means that there are &lt;math&gt;\frac{(m-1)(n-1)}{2}&lt;/math&gt; different not-purchasable integers from &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;mn-m-n&lt;/math&gt;. All integers greater than &lt;math&gt;mn-m-n&lt;/math&gt; are purchasable, so that means there are a total of &lt;math&gt;\frac{(m-1)(n-1)}{2}&lt;/math&gt; integers &lt;math&gt;\geq 0&lt;/math&gt; that are not purchasable.<br /> <br /> In other words, for every pair of coprime integers &lt;math&gt;m, n&lt;/math&gt;, there are exactly &lt;math&gt;\frac{(m-1)(n-1)}{2}&lt;/math&gt; nonnegative integers that cannot be represented in the form &lt;math&gt;am + bn&lt;/math&gt; for nonnegative integers &lt;math&gt;a, b&lt;/math&gt;. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> ==Generalization==<br /> If &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are not relatively prime, then we can simply rearrange &lt;math&gt;am+bn&lt;/math&gt; into the form<br /> &lt;cmath&gt;\gcd(m,n) \left( a\frac{m}{\gcd(m,n)}+b\frac{n}{\gcd(m,n)} \right)&lt;/cmath&gt;<br /> &lt;math&gt;\frac{m}{\gcd(m,n)}&lt;/math&gt; and &lt;math&gt;\frac{n}{\gcd(m,n)}&lt;/math&gt; are relatively prime, so we apply Chicken McNugget to find a bound<br /> &lt;cmath&gt;\frac{mn}{\gcd(m,n)^{2}}-\frac{m}{\gcd(m,n)}-\frac{n}{\gcd(m,n)}&lt;/cmath&gt;<br /> We can simply multiply &lt;math&gt;\gcd(m,n)&lt;/math&gt; back into the bound to get<br /> &lt;cmath&gt;\frac{mn}{\gcd(m,n)}-m-n=\textrm{lcm}(m, n)-m-n&lt;/cmath&gt;<br /> Therefore, all multiples of &lt;math&gt;\gcd(m, n)&lt;/math&gt; greater than &lt;math&gt;\textrm{lcm}(m, n)-m-n&lt;/math&gt; are representable in the form &lt;math&gt;am+bn&lt;/math&gt; for some positive integers &lt;math&gt;a, b&lt;/math&gt;.<br /> <br /> =Problems=<br /> <br /> ===Simple===<br /> *Marcy buys paint jars in containers of &lt;math&gt;2&lt;/math&gt; and &lt;math&gt;7&lt;/math&gt;. What's the largest number of paint jars that Marcy can't obtain? <br /> <br /> Answer: &lt;math&gt;5&lt;/math&gt; containers<br /> <br /> *Bay Area Rapid food sells chicken nuggets. You can buy packages of &lt;math&gt;11&lt;/math&gt; or &lt;math&gt;7&lt;/math&gt;. What is the largest integer &lt;math&gt;n&lt;/math&gt; such that there is no way to buy exactly &lt;math&gt;n&lt;/math&gt; nuggets? Can you Generalize ?(ACOPS) <br /> <br /> Answer: &lt;math&gt;n=59&lt;/math&gt; <br /> <br /> *If a game of American Football has only scores of field goals (&lt;math&gt;3&lt;/math&gt; points) and touchdowns with the extra point (&lt;math&gt;7&lt;/math&gt; points), then what is the greatest score that cannot be the score of a team in this football game (ignoring time constraints)?<br /> <br /> Answer: &lt;math&gt;11&lt;/math&gt; points<br /> <br /> ===Intermediate===<br /> *Ninety-four bricks, each measuring &lt;math&gt;4''\times10''\times19'',&lt;/math&gt; are to stacked one on top of another to form a tower 94 bricks tall. Each brick can be oriented so it contributes &lt;math&gt;4''\,&lt;/math&gt; or &lt;math&gt;10''\,&lt;/math&gt; or &lt;math&gt;19''\,&lt;/math&gt; to the total height of the tower. How many different tower heights can be achieved using all ninety-four of the bricks? [[1994 AIME Problems/Problem 11|AIME]]<br /> <br /> *Find the sum of all positive integers &lt;math&gt;n&lt;/math&gt; such that, given an unlimited supply of stamps of denominations &lt;math&gt;5,n,&lt;/math&gt; and &lt;math&gt;n+1&lt;/math&gt; cents, &lt;math&gt;91&lt;/math&gt; cents is the greatest postage that cannot be formed. [[2019 AIME II Problems/Problem 14|AIME II 2019 Problem 14]]<br /> <br /> ===Olympiad===<br /> *On the real number line, paint red all points that correspond to integers of the form &lt;math&gt;81x+100y&lt;/math&gt;, where &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; are positive integers. Paint the remaining integer points blue. Find a point &lt;math&gt;P&lt;/math&gt; on the line such that, for every integer point &lt;math&gt;T&lt;/math&gt;, the reflection of &lt;math&gt;T&lt;/math&gt; with respect to &lt;math&gt;P&lt;/math&gt; is an integer point of a different colour than &lt;math&gt;T&lt;/math&gt;. (India TST)<br /> <br /> *Let &lt;math&gt;S&lt;/math&gt; be a set of integers (not necessarily positive) such that<br /> <br /> (a) there exist &lt;math&gt;a,b \in S&lt;/math&gt; with &lt;math&gt;\gcd(a,b)=\gcd(a-2,b-2)=1&lt;/math&gt;;<br /> <br /> (b) if &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; are elements of &lt;math&gt;S&lt;/math&gt; (possibly equal), then &lt;math&gt;x^2-y&lt;/math&gt; also belongs to &lt;math&gt;S&lt;/math&gt;. <br /> <br /> Prove that &lt;math&gt;S&lt;/math&gt; is the set of all integers. (USAMO)<br /> <br /> ==See Also==<br /> *[[Theorem]]<br /> *[[Prime]]<br /> <br /> [[Category:Theorems]]<br /> [[Category:Number theory]]</div> Mag1c https://artofproblemsolving.com/wiki/index.php?title=Chicken_McNugget_Theorem&diff=109068 Chicken McNugget Theorem 2019-08-20T22:30:30Z <p>Mag1c: /* Proof Without Words */</p> <hr /> <div>The '''Chicken McNugget Theorem''' (or '''Postage Stamp Problem''' or '''Frobenius Coin Problem''') states that for any two [[relatively prime]] [[positive integer]]s &lt;math&gt;m,n&lt;/math&gt;, the greatest integer that cannot be written in the form &lt;math&gt;am + bn&lt;/math&gt; for [[nonnegative]] integers &lt;math&gt;a, b&lt;/math&gt; is &lt;math&gt;mn-m-n&lt;/math&gt;.<br /> <br /> A consequence of the theorem is that there are exactly &lt;math&gt;\frac{(m - 1)(n - 1)}{2}&lt;/math&gt; positive integers which cannot be expressed in the form &lt;math&gt;am + bn&lt;/math&gt;. The proof is based on the fact that in each pair of the form &lt;math&gt;(k, (m - 1)(n - 1) - k+1)&lt;/math&gt;, exactly one element is expressible.<br /> <br /> == Origins ==<br /> There are many stories surrounding the origin of the Chicken McNugget theorem. However, the most popular by far remains that of the Chicken McNugget. Originally, McDonald's sold its nuggets in packs of 9 and 20. Math enthusiasts were curious to find the largest number of nuggets that could not have been bought with these packs, thus creating the Chicken McNugget Theorem (the answer worked out to be 151 nuggets). The Chicken McNugget Theorem has also been called the Frobenius Coin Problem or the Frobenius Problem, after German mathematician Ferdinand Frobenius inquired about the largest amount of currency that could not have been made with certain types of coins.<br /> <br /> <br /> <br /> <br /> <br /> ==Proof Without Words==<br /> &lt;math&gt;\begin{array}{cccccccc}<br /> 0\mod{m}&amp;1\mod{m}&amp;2\mod{m}&amp;...&amp;...&amp;...&amp;...&amp;(m-1)\mod{m}\\<br /> \hline<br /> \cancel{0n}&amp;1&amp;2&amp;&amp;...&amp;&amp;&amp;m-1\\<br /> \cancel{0n+m}&amp;...&amp;&amp;\vdots&amp;&amp;...&amp;&amp;\\<br /> \cancel{0n+2m}&amp;...&amp;&amp;\cancel{1n}&amp;&amp;...&amp;&amp;\\<br /> \cancel{0n+3m}&amp;&amp;&amp;\cancel{1n+m}&amp;&amp;&amp;\vdots&amp;\\<br /> \cancel{0n+4m}&amp;&amp;&amp;\cancel{1n+2m}&amp;&amp;&amp;\cancel{2n}&amp;\\<br /> \cancel{0n+5m}&amp;&amp;&amp;\cancel{1n+3m}&amp;&amp;&amp;\cancel{2n+m}&amp;\\<br /> \vdots&amp;&amp;&amp;\vdots&amp;&amp;&amp;\vdots&amp;\\<br /> \cancel{\qquad}&amp;\cancel{\qquad}&amp;\cancel{ \qquad}&amp;\cancel{ \qquad}&amp;\mathbf{(m-1)n-m}&amp;\cancel{ \qquad}&amp;\cancel{\qquad }&amp;\cancel{\qquad }\\<br /> \cancel{\qquad}&amp;\cancel{\qquad}&amp;\cancel{ \qquad}&amp;\cancel{ \qquad}&amp;\cancel{(m-1)n}&amp;\cancel{ \qquad}&amp;\cancel{\qquad }&amp;\cancel{\qquad }<br /> \end{array}&lt;/math&gt;<br /> <br /> ==Proof 1==<br /> &lt;b&gt;Definition&lt;/b&gt;. An integer &lt;math&gt;N \in \mathbb{Z}&lt;/math&gt; will be called &lt;i&gt;purchasable&lt;/i&gt; if there exist nonnegative integers &lt;math&gt;a,b&lt;/math&gt; such that &lt;math&gt;am+bn = N&lt;/math&gt;.<br /> <br /> We would like to prove that &lt;math&gt;mn-m-n&lt;/math&gt; is the largest non-purchasable integer. We are required to show that (1) &lt;math&gt;mn-m-n&lt;/math&gt; is non-purchasable, and (2) every &lt;math&gt;N &gt; mn-m-n&lt;/math&gt; is purchasable. <br /> Note that all purchasable integers are nonnegative, thus the set of non-purchasable integers is nonempty.<br /> <br /> &lt;b&gt;Lemma&lt;/b&gt;. Let &lt;math&gt;A_{N} \subset \mathbb{Z} \times \mathbb{Z}&lt;/math&gt; be the set of solutions &lt;math&gt;(x,y)&lt;/math&gt; to &lt;math&gt;xm+yn = N&lt;/math&gt;. Then &lt;math&gt;A_{N} = \{(x+kn,y-km) \;:\; k \in \mathbb{Z}\}&lt;/math&gt; for any &lt;math&gt;(x,y) \in A_{N}&lt;/math&gt;.<br /> <br /> &lt;i&gt;Proof&lt;/i&gt;: By [[Bezout's Lemma]], there exist integers &lt;math&gt;x',y'&lt;/math&gt; such that &lt;math&gt;x'm+y'n = 1&lt;/math&gt;. Then &lt;math&gt;(Nx')m+(Ny')n = N&lt;/math&gt;. Hence &lt;math&gt;A_{N}&lt;/math&gt; is nonempty. It is easy to check that &lt;math&gt;(Nx'+kn,Ny'-km) \in A_{N}&lt;/math&gt; for all &lt;math&gt;k \in \mathbb{Z}&lt;/math&gt;. We now prove that there are no others. Suppose &lt;math&gt;(x_{1},y_{1})&lt;/math&gt; and &lt;math&gt;(x_{2},y_{2})&lt;/math&gt; are solutions to &lt;math&gt;xm+yn=N&lt;/math&gt;. Then &lt;math&gt;x_{1}m+y_{1}n = x_{2}m+y_{2}n&lt;/math&gt; implies &lt;math&gt;m(x_{1}-x_{2}) = n(y_{2}-y_{1})&lt;/math&gt;. Since &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are coprime and &lt;math&gt;m&lt;/math&gt; divides &lt;math&gt;n(y_{2}-y_{1})&lt;/math&gt;, &lt;math&gt;m&lt;/math&gt; divides &lt;math&gt;y_{2}-y_{1}&lt;/math&gt; and &lt;math&gt;y_{2} \equiv y_{1} \pmod{m}&lt;/math&gt;. Similarly &lt;math&gt;x_{2} \equiv x_{1} \pmod{n}&lt;/math&gt;. Let &lt;math&gt;k_{1},k_{2}&lt;/math&gt; be integers such that &lt;math&gt;x_{2}-x_{1} = k_{1}n&lt;/math&gt; and &lt;math&gt;y_{2}-y_{1} = k_{2}m&lt;/math&gt;. Then &lt;math&gt;m(-k_{1}n) = n(k_{2}m)&lt;/math&gt; implies &lt;math&gt;k_{1} = -k_{2}.&lt;/math&gt; We have the desired result. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> &lt;b&gt;Lemma&lt;/b&gt;. For any integer &lt;math&gt;N&lt;/math&gt;, there exists unique &lt;math&gt;(a_{N},b_{N}) \in \mathbb{Z} \times \{0,1,\ldots,m-1\}&lt;/math&gt; such that &lt;math&gt;a_{N}m + b_{N}n = N&lt;/math&gt;.<br /> <br /> &lt;i&gt;Proof&lt;/i&gt;: By the division algorithm, there exists one and only one &lt;math&gt;k&lt;/math&gt; such that &lt;math&gt;0 \le y-km \le m-1&lt;/math&gt;. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> &lt;b&gt;Lemma&lt;/b&gt;. &lt;math&gt;N&lt;/math&gt; is purchasable if and only if &lt;math&gt;a_{N} \ge 0&lt;/math&gt;.<br /> <br /> &lt;i&gt;Proof&lt;/i&gt;: If &lt;math&gt;a_{N} \ge 0&lt;/math&gt;, then we may simply pick &lt;math&gt;(a,b) = (a_{N},b_{N})&lt;/math&gt; so &lt;math&gt;N&lt;/math&gt; is purchasable. If &lt;math&gt;a_{N} &lt; 0&lt;/math&gt;, then &lt;math&gt;a_{N}+kn &lt; 0&lt;/math&gt; if &lt;math&gt;k \le 0&lt;/math&gt; and &lt;math&gt;b_{N}-km &lt; 0&lt;/math&gt; if &lt;math&gt;k &gt; 0&lt;/math&gt;, hence at least one coordinate of &lt;math&gt;(a_{N}+kn,b_{N}-km)&lt;/math&gt; is negative for all &lt;math&gt;k \in \mathbb{Z}&lt;/math&gt;. Thus &lt;math&gt;N&lt;/math&gt; is not purchasable. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> Thus the set of non-purchasable integers is &lt;math&gt;\{xm+yn \;:\; x&lt;0,0 \le y \le m-1\}&lt;/math&gt;. We would like to find the maximum of this set. <br /> Since both &lt;math&gt;m,n&lt;/math&gt; are positive, the maximum is achieved when &lt;math&gt;x = -1&lt;/math&gt; and &lt;math&gt;y = m-1&lt;/math&gt; so that &lt;math&gt;xm+yn = (-1)m+(m-1)n = mn-m-n&lt;/math&gt;.<br /> <br /> ==Proof 2==<br /> We start with this statement taken from [[Fermat%27s_Little_Theorem#Proof_2_.28Inverses.29|Proof 2 of Fermat's Little Theorem]]:<br /> <br /> &quot;Let &lt;math&gt;S = \{1,2,3,\cdots, p-1\}&lt;/math&gt;. Then, we claim that the set &lt;math&gt;a \cdot S&lt;/math&gt;, consisting of the product of the elements of &lt;math&gt;S&lt;/math&gt; with &lt;math&gt;a&lt;/math&gt;, taken modulo &lt;math&gt;p&lt;/math&gt;, is simply a permutation of &lt;math&gt;S&lt;/math&gt;. In other words, <br /> <br /> &lt;center&gt;&lt;cmath&gt;S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.&lt;/cmath&gt;&lt;/center&gt;&lt;br&gt;<br /> <br /> Clearly none of the &lt;math&gt;ia&lt;/math&gt; for &lt;math&gt;1 \le i \le p-1&lt;/math&gt; are divisible by &lt;math&gt;p&lt;/math&gt;, so it suffices to show that all of the elements in &lt;math&gt;a \cdot S&lt;/math&gt; are distinct. Suppose that &lt;math&gt;ai \equiv aj \pmod{p}&lt;/math&gt; for &lt;math&gt;i \neq j&lt;/math&gt;. Since &lt;math&gt;\text{gcd}\, (a,p) = 1&lt;/math&gt;, by the cancellation rule, that reduces to &lt;math&gt;i \equiv j \pmod{p}&lt;/math&gt;, which is a contradiction.&quot;<br /> <br /> Because &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are coprime, we know that multiplying the residues of &lt;math&gt;m&lt;/math&gt; by &lt;math&gt;n&lt;/math&gt; simply permutes these residues. Each of these permuted residues is purchasable (using the definition from Proof 1), because, in the form &lt;math&gt;am+bn&lt;/math&gt;, &lt;math&gt;a&lt;/math&gt; is &lt;math&gt;0&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; is the original residue. We now prove the following lemma.<br /> <br /> &lt;b&gt;Lemma&lt;/b&gt;: For any nonnegative integer &lt;math&gt;c &lt; m&lt;/math&gt;, &lt;math&gt;cn&lt;/math&gt; is the least purchasable number &lt;math&gt;\equiv cn \bmod m&lt;/math&gt;.<br /> <br /> &lt;i&gt;Proof&lt;/i&gt;: Any number that is less than &lt;math&gt;cn&lt;/math&gt; and congruent to it &lt;math&gt;\bmod m&lt;/math&gt; can be represented in the form &lt;math&gt;cn-dm&lt;/math&gt;, where &lt;math&gt;d&lt;/math&gt; is a positive integer. If this is purchasable, we can say &lt;math&gt;cn-dm=am+bn&lt;/math&gt; for some nonnegative integers &lt;math&gt;a, b&lt;/math&gt;. This can be rearranged into &lt;math&gt;(a+d)m=(c-b)n&lt;/math&gt;, which implies that &lt;math&gt;(a+d)&lt;/math&gt; is a multiple of &lt;math&gt;n&lt;/math&gt; (since &lt;math&gt;\gcd(m, n)=1&lt;/math&gt;). We can say that &lt;math&gt;(a+d)=gn&lt;/math&gt; for some positive integer &lt;math&gt;g&lt;/math&gt;, and substitute to get &lt;math&gt;gmn=(c-b)n&lt;/math&gt;. Because &lt;math&gt;c &lt; m&lt;/math&gt;, &lt;math&gt;(c-b)n &lt; mn&lt;/math&gt;, and &lt;math&gt;gmn &lt; mn&lt;/math&gt;. We divide by &lt;math&gt;mn&lt;/math&gt; to get &lt;math&gt;g&lt;1&lt;/math&gt;. However, we defined &lt;math&gt;g&lt;/math&gt; to be a positive integer, and all positive integers are greater than or equal to &lt;math&gt;1&lt;/math&gt;. Therefore, we have a contradiction, and &lt;math&gt;cn&lt;/math&gt; is the least purchasable number congruent to &lt;math&gt;cn \bmod m&lt;/math&gt;. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> This means that because &lt;math&gt;cn&lt;/math&gt; is purchasable, every number that is greater than &lt;math&gt;cn&lt;/math&gt; and congruent to it &lt;math&gt;\bmod m&lt;/math&gt; is also purchasable (because these numbers are in the form &lt;math&gt;am+bn&lt;/math&gt; where &lt;math&gt;b=c&lt;/math&gt;). Another result of this Lemma is that &lt;math&gt;cn-m&lt;/math&gt; is the greatest number &lt;math&gt;\equiv cn \bmod m&lt;/math&gt; that is not purchasable. &lt;math&gt;c \leq m-1&lt;/math&gt;, so &lt;math&gt;cn-m \leq (m-1)n-m=mn-m-n&lt;/math&gt;, which shows that &lt;math&gt;mn-m-n&lt;/math&gt; is the greatest number in the form &lt;math&gt;cn-m&lt;/math&gt;. Any number greater than this and congruent to some &lt;math&gt;cn \bmod m&lt;/math&gt; is purchasable, because that number is greater than &lt;math&gt;cn&lt;/math&gt;. All numbers are congruent to some &lt;math&gt;cn&lt;/math&gt;, and thus all numbers greater than &lt;math&gt;mn-m-n&lt;/math&gt; are purchasable.<br /> <br /> Putting it all together, we can say that for any coprime &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt;, &lt;math&gt;mn-m-n&lt;/math&gt; is the greatest number not representable in the form &lt;math&gt;am + bn&lt;/math&gt; for nonnegative integers &lt;math&gt;a, b&lt;/math&gt;. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> ==Corollary==<br /> This corollary is based off of Proof 2, so it is necessary to read that proof before this corollary. We prove the following lemma.<br /> <br /> &lt;b&gt;Lemma&lt;/b&gt; For any integer &lt;math&gt;k&lt;/math&gt;, exactly one of the integers &lt;math&gt;k&lt;/math&gt;, &lt;math&gt;mn-m-n-k&lt;/math&gt; is not purchasable.<br /> <br /> &lt;i&gt;Proof&lt;/i&gt;: Because every number is congruent to some residue of &lt;math&gt;m&lt;/math&gt; permuted by &lt;math&gt;n&lt;/math&gt;, we can set &lt;math&gt;k \equiv cn \bmod m&lt;/math&gt; for some &lt;math&gt;c&lt;/math&gt;. We can break this into two cases.<br /> <br /> &lt;i&gt;Case 1&lt;/i&gt;: &lt;math&gt;k \leq cn-m&lt;/math&gt;. This implies that &lt;math&gt;k&lt;/math&gt; is not purchasable, and that &lt;math&gt;mn-m-n-k \geq mn-m-n-(cn-m) = n(m-1-c)&lt;/math&gt;. &lt;math&gt;n(m-1-c)&lt;/math&gt; is a permuted residue, and a result of the lemma in Proof 2 was that a permuted residue is the least number congruent to itself &lt;math&gt;\bmod m&lt;/math&gt; that is purchasable. Therefore, &lt;math&gt;mn-m-n-k \equiv n(m-1-c) \bmod m&lt;/math&gt; and &lt;math&gt;mn-m-n-k \geq n(m-1-c)&lt;/math&gt;, so &lt;math&gt;mn-m-n-k&lt;/math&gt; is purchasable.<br /> <br /> &lt;i&gt;Case 2&lt;/i&gt;: &lt;math&gt;k &gt; cn-m&lt;/math&gt;. This implies that &lt;math&gt;k&lt;/math&gt; is purchasable, and that &lt;math&gt;mn-m-n-k &lt; mn-m-n-(cn-m) = n(m-1-c)&lt;/math&gt;. Again, because &lt;math&gt;n(m-1-c)&lt;/math&gt; is the least number congruent to itself &lt;math&gt;\bmod m&lt;/math&gt; that is purchasable, and because &lt;math&gt;mn-m-n-k \equiv n(m-1-c) \bmod m&lt;/math&gt; and &lt;math&gt;mn-m-n-k &lt; n(m-1-c)&lt;/math&gt;, &lt;math&gt;mn-m-n-k&lt;/math&gt; is not purchasable.<br /> <br /> We now limit the values of &lt;math&gt;k&lt;/math&gt; to all integers &lt;math&gt;0 \leq k \leq \frac{mn-m-n}{2}&lt;/math&gt;, which limits the values of &lt;math&gt;mn-m-n-k&lt;/math&gt; to &lt;math&gt;mn-m-n \geq mn-m-n-k \geq \frac{mn-m-n}{2}&lt;/math&gt;. Because &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are coprime, only one of them can be a multiple of &lt;math&gt;2&lt;/math&gt;. Therefore, &lt;math&gt;mn-m-n \equiv (0)(1)-0-1 \equiv -1 \equiv 1 \bmod 2&lt;/math&gt;, showing that &lt;math&gt;\frac{mn-m-n}{2}&lt;/math&gt; is not an integer and that &lt;math&gt;\frac{mn-m-n-1}{2}&lt;/math&gt; and &lt;math&gt;\frac{mn-m-n+1}{2}&lt;/math&gt; are integers. We can now set limits that are equivalent to the previous on the values of &lt;math&gt;k&lt;/math&gt; and &lt;math&gt;mn-m-n-k&lt;/math&gt; so that they cover all integers form &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;mn-m-n&lt;/math&gt; without overlap: &lt;math&gt;0 \leq k \leq \frac{mn-m-n-1}{2}&lt;/math&gt; and &lt;math&gt;\frac{mn-m-n+1}{2} \leq mn-m-n-k \leq mn-m-n&lt;/math&gt;. There are &lt;math&gt;\frac{mn-m-n-1}{2}+1=\frac{(m-1)(n-1)}{2}&lt;/math&gt; values of &lt;math&gt;k&lt;/math&gt;, and each is paired with a value of &lt;math&gt;mn-m-n-k&lt;/math&gt;, so we can make &lt;math&gt;\frac{(m-1)(n-1)}{2}&lt;/math&gt; different ordered pairs of the form &lt;math&gt;(k, mn-m-n-k)&lt;/math&gt;. The coordinates of these ordered pairs cover all integers from &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;mn-m-n&lt;/math&gt; inclusive, and each contains exactly one not-purchasable integer, so that means that there are &lt;math&gt;\frac{(m-1)(n-1)}{2}&lt;/math&gt; different not-purchasable integers from &lt;math&gt;0&lt;/math&gt; to &lt;math&gt;mn-m-n&lt;/math&gt;. All integers greater than &lt;math&gt;mn-m-n&lt;/math&gt; are purchasable, so that means there are a total of &lt;math&gt;\frac{(m-1)(n-1)}{2}&lt;/math&gt; integers &lt;math&gt;\geq 0&lt;/math&gt; that are not purchasable.<br /> <br /> In other words, for every pair of coprime integers &lt;math&gt;m, n&lt;/math&gt;, there are exactly &lt;math&gt;\frac{(m-1)(n-1)}{2}&lt;/math&gt; nonnegative integers that cannot be represented in the form &lt;math&gt;am + bn&lt;/math&gt; for nonnegative integers &lt;math&gt;a, b&lt;/math&gt;. &lt;math&gt;\square&lt;/math&gt;<br /> <br /> ==Generalization==<br /> If &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are not relatively prime, then we can simply rearrange &lt;math&gt;am+bn&lt;/math&gt; into the form<br /> &lt;cmath&gt;\gcd(m,n) \left( a\frac{m}{\gcd(m,n)}+b\frac{n}{\gcd(m,n)} \right)&lt;/cmath&gt;<br /> &lt;math&gt;\frac{m}{\gcd(m,n)}&lt;/math&gt; and &lt;math&gt;\frac{n}{\gcd(m,n)}&lt;/math&gt; are relatively prime, so we apply Chicken McNugget to find a bound<br /> &lt;cmath&gt;\frac{mn}{\gcd(m,n)^{2}}-\frac{m}{\gcd(m,n)}-\frac{n}{\gcd(m,n)}&lt;/cmath&gt;<br /> We can simply multiply &lt;math&gt;\gcd(m,n)&lt;/math&gt; back into the bound to get<br /> &lt;cmath&gt;\frac{mn}{\gcd(m,n)}-m-n=\textrm{lcm}(m, n)-m-n&lt;/cmath&gt;<br /> Therefore, all multiples of &lt;math&gt;\gcd(m, n)&lt;/math&gt; greater than &lt;math&gt;\textrm{lcm}(m, n)-m-n&lt;/math&gt; are representable in the form &lt;math&gt;am+bn&lt;/math&gt; for some positive integers &lt;math&gt;a, b&lt;/math&gt;.<br /> <br /> =Problems=<br /> <br /> ===Simple===<br /> *Marcy buys paint jars in containers of &lt;math&gt;2&lt;/math&gt; and &lt;math&gt;7&lt;/math&gt;. What's the largest number of paint jars that Marcy can't obtain? <br /> <br /> Answer: &lt;math&gt;5&lt;/math&gt; containers<br /> <br /> *Bay Area Rapid food sells chicken nuggets. You can buy packages of &lt;math&gt;11&lt;/math&gt; or &lt;math&gt;7&lt;/math&gt;. What is the largest integer &lt;math&gt;n&lt;/math&gt; such that there is no way to buy exactly &lt;math&gt;n&lt;/math&gt; nuggets? Can you Generalize ?(ACOPS) <br /> <br /> Answer: &lt;math&gt;n=59&lt;/math&gt; <br /> <br /> *If a game of American Football has only scores of field goals (&lt;math&gt;3&lt;/math&gt; points) and touchdowns with the extra point (&lt;math&gt;7&lt;/math&gt; points), then what is the greatest score that cannot be the score of a team in this football game (ignoring time constraints)?<br /> <br /> Answer: &lt;math&gt;11&lt;/math&gt; points<br /> <br /> ===Intermediate===<br /> *Ninety-four bricks, each measuring &lt;math&gt;4''\times10''\times19'',&lt;/math&gt; are to stacked one on top of another to form a tower 94 bricks tall. Each brick can be oriented so it contributes &lt;math&gt;4''\,&lt;/math&gt; or &lt;math&gt;10''\,&lt;/math&gt; or &lt;math&gt;19''\,&lt;/math&gt; to the total height of the tower. How many different tower heights can be achieved using all ninety-four of the bricks? [[1994 AIME Problems/Problem 11|AIME]]<br /> <br /> *Find the sum of all positive integers &lt;math&gt;n&lt;/math&gt; such that, given an unlimited supply of stamps of denominations &lt;math&gt;5,n,&lt;/math&gt; and &lt;math&gt;n+1&lt;/math&gt; cents, &lt;math&gt;91&lt;/math&gt; cents is the greatest postage that cannot be formed. [[2019 AIME II Problems/Problem 14|AIME II 2019 Problem 14]]<br /> <br /> ===Olympiad===<br /> *On the real number line, paint red all points that correspond to integers of the form &lt;math&gt;81x+100y&lt;/math&gt;, where &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; are positive integers. Paint the remaining integer points blue. Find a point &lt;math&gt;P&lt;/math&gt; on the line such that, for every integer point &lt;math&gt;T&lt;/math&gt;, the reflection of &lt;math&gt;T&lt;/math&gt; with respect to &lt;math&gt;P&lt;/math&gt; is an integer point of a different colour than &lt;math&gt;T&lt;/math&gt;. (India TST)<br /> <br /> *Let &lt;math&gt;S&lt;/math&gt; be a set of integers (not necessarily positive) such that<br /> <br /> (a) there exist &lt;math&gt;a,b \in S&lt;/math&gt; with &lt;math&gt;\gcd(a,b)=\gcd(a-2,b-2)=1&lt;/math&gt;;<br /> <br /> (b) if &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; are elements of &lt;math&gt;S&lt;/math&gt; (possibly equal), then &lt;math&gt;x^2-y&lt;/math&gt; also belongs to &lt;math&gt;S&lt;/math&gt;. <br /> <br /> Prove that &lt;math&gt;S&lt;/math&gt; is the set of all integers. (USAMO)<br /> <br /> ==See Also==<br /> *[[Theorem]]<br /> *[[Prime]]<br /> <br /> [[Category:Theorems]]<br /> [[Category:Number theory]]</div> Mag1c