17 camels trick

Question

The following popular mathematical parable is well known:

A father left 17 camels to his three sons and, according to the will, the eldest son should be given a half of all camels, the middle son the one-third part and the youngest son the one-ninth. This is hard to do, but a wise man helped the sons: he added his own camel, the oldest son took 18/2=9 camels, the second son took 18/3=6 camels, the third son 18/9=2 camels and the wise man took his own camel and went away.

I ask for applications of this method: when something is artificially added, somehow used and, after that, taken away (as was this 18^th camel of a wise man).

Let me start with two examples from graph theory:

1. We know Hall's lemma: if any $k=1,2,\dots$ men in a town like at least $k$ women in total, then all the men may get married so that each of them likes his wife. How to conclude the following generalized version?

   If any $k$ men like at least $k-s$ women in total, then all but $s$ men may get married.

   Proof. Add $s$ extra women (camel-women) liked by all men. Apply usual Hall lemma, after that say pardon to the husbands of extra women.

2. This is due to Noga Alon, recently popularized by Gil Kalai. How to find a perfect matching in a bipartite $r$-regular multigraph? If $r$ is a power of 2, this is easy by induction. Indeed, there is an Eulerian cycle in every connected component. Taking edges alternatively we partition our graph onto two $r/2$-regular multigraphs. Moreover, we get a partition of edges onto $r$ perfect matchings. Now, if $r$ is not a power of 2, take large $N$ and write $2^N=rq+t$, $0<t<r$. Replace each edge of our multigraph onto $q$ edges, also add extra edges formed by arbitrary $t$ perfect matchings. This new multigraph may be partitioned onto $2^N$ perfect matchings, and if $N$ is large enough, some of them do not contain extra edges.

Answer 1

Slack variables in linear programming. Quote from the link:

In an optimization problem, a slack variable is a variable that is added to an inequality constraint to transform it to an equality. Introducing a slack variable replaces an inequality constraint with an equality constraint and a nonnegativity constraint.

Answer 2

Lagrange multipliers: to extremize $f(x,y)$ subject to constraint $g(x,y)=0$, add a variable $\lambda$ and

introduce an auxiliary function $$ {\mathcal {L}}(x,y,\lambda )=f(x,y)-\lambda \cdot g(x,y) $$ and solve [unconstrained!] $$ \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0. $$ Note that this amounts to solving three equations in three unknowns. This is the method of Lagrange multipliers. Note that $\nabla _{\lambda }{\mathcal {L}}(x,y,\lambda )=0$ implies $g(x, y) = 0$. To summarize $$ {\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\iff {\begin{cases}\nabla _{x,y}f(x,y)=\lambda \nabla _{x,y}g(x,y)\\g(x,y)=0.\end{cases}}} $$

Answer 3

Maybe this example is too elementary for this site, but I'd say the proof that a closed subset of a compact set is compact itself looks like this. Given an open cover of a $A$ where $A$ is a closed subset of a compact set $K$ we add $K\setminus A$ to the cover, obtain a finite subcover using compactness of $K$ and then discard the extra set as it is not needed to cover $A$.

Answer 4

The AM-GM inequality (as well as other inequalities, for instance the discrete version of Jensen's inequality) can be proved with the following trick due to Cauchy, known as "forward-backward induction":

Let $P(n)$ be the proposition "For any $n$ positive reals, $\frac1n \sum a_i \geq (\prod a_i)^{1/n}$" (AM-GM inequality with $n$ terms).

The proof is made of three parts.

1. Prove $P(2)$ directly.
2. Use $P(n)$ and $P(2)$ to prove $P(2n)$ (hence by induction we can now prove $P(2^k)$ for each $k$).
3. Given $n$ terms $a_1,a_2,\dots, a_{n}$, use $P(n+1)$ on the $n+1$ terms $a_1,a_2,\dots, a_n, \frac1n \sum a_i$ to derive $P(n)$ with a few manipulations.

So when we want to prove $P(n)$ for a generic $n$, we use part 3 to add several "phantom" terms equal to $AM=\frac1n \sum a_i$ to make $n$ a power of 2, then use parts 1+2.

The proof is described in more detail here.

Answer 5

The usual way to prove the Strong Nullstellensatz from the Weak Nullstellensatz is the so-called Rabinowitsch trick.

In short, adding an extra variable allows us to apply the "weak" version of the theorem; then we can come back to the smaller polynomial ring and get the "strong" version by simply clearing denominators.

See also this MO question.

Answer 6

Another example of this could be a proof by induction where we add additional constraints to our induction hypothesis to prove something stronger. For example,

Show that $\sum_{k = 1}^{n} \frac{1}{k^2} < 2$

cannot be proved by induction, but we can add in a tiny modification and prove the following instead:

Show that $\sum_{k = 1}^{n} \frac{1}{k^2} < 2 - \frac{1}n.$

We can then 'take away' the $\frac{1}n$ to return to our original statement.

Answer 7

Since nobody did, I would like to mention the obvious: The 17 camels trick is routinely used in apportionment procedures called divisor methods.

The task is to divide a number of $N\in\mathbb N$ items (e.g., seats in a parliament) according to fixed proportions $p_1,\ldots,p_n>0$ (e.g., results of an election). One way to do this is to define a rounding procedure $\mathbb R\to\mathbb Z:x\mapsto[x]$. The idea is to add additional $\epsilon\in\mathbb R$ virtual seats and tweak it such that the contingents $N_i:=[p_i(N+\epsilon)]$ sum up to $N$. This is almost always possible and the $N_i$ are unique in this case.

The different divisor methods differ by the rounding method: If $[x]$ is

• rounding down: Jefferson's (aka d'Hondt) method
• rounding up: Adam's method
• rounding at the arithmetic mean: Webster/Sainte-Laguë method
• rounding at the geometric mean: Huntington–Hill method (currently used for the US-House of Representatives)

Answer 8

The general formula for solving second degree equations. You need to add a term to complete the square and then subtract a little more to take the square root.

Answer 9

A common task in digital signal processing is to compute the convolution of two functions over $\{0,\ldots,n-1\}$. The standard approach is to first "pad with zeros" by viewing these as functions over $\mathbb{Z}/2^k\mathbb{Z}$ with $2^k\geq 2n$. Then it suffices to compute the circular convolution, which can be obtained in $O(n\log n)$ time via the Cooley–Tukey fast Fourier transform.

This is also the main trick under the hood of the Schönhage–Strassen algorithm for fast integer multiplication.

Answer 10

A nice example is Parking Functions. This is a well-known topic in combinatorics with connections ranging from spanning trees of graphs to non-crossing partitions to hyperplane arrangements to priority queues.
Our wise man will realize that the ostensibly linear setting I describe below would be significantly easier to handle if he lent us a placeholder camel which could offer us cyclic symmetry. This camel-on-loan will provide the structure to do a trivial calculation, and in the end, we can simply pluck out all the solutions that didn't involve it, discarding the rest.

(Although I could be cheeky and state the entire problem in terms of camels, I'll try to resist and be faithful to the normal presentation).

Imagine a shopping plaza with $n$ parking spaces laid out linearly in front of the stores. In the morning, $n$ shoppers $s_i$ file into the plaza one at a time ($s_1$ arrives, then $s_2$, then $s_3$, etc.) each one having a strong preference for parking space $p_i$ in front of the store they are visiting.

The problem is that the parking lot is narrow — the flow of traffic is one way — and the shoppers are rather shortsighted and obstinate: shopper $s_i$ drives up to their preferred space $p_i$, and if they find it occupied, they keep going to the first available $p$ such that $p > p_i$; if no such $p$ exists, they get frustrated and shop elsewhere.

The situation for n = 12 is shown below. Supposing the next four shoppers $s_7$ thru $s_{10}$ were all both planning to park at space $8$ and get breakfast at Subway, they'll land at the $8$th, $10$th, and $11$th spots respectively, and the $10$th shopper will find a sandwich elsewhere.

We can encode the preferences of the shoppers with an $n$-tuple $(p_1, p_2, \ldots, p_n)$. Now we denote by $P(n)$ the set of $n$-tuples encoding situations in which all $n$ shoppers will find a place to park — the parking functions of length $n$.

To calculate the size of $P(n)$, you can scratch your head for a while thinking about the problem linearly, or you can exercise an "add one subtract one" trick — let's take the old wise man up on his offer and throw a camel into the mix:

Consider adding another space $n+1$ to the parking lot which "glues" together the two ends (so now shoppers that can't park in their preferred spot will go around in a circle til they find a place). That means that in our new arrangement, everyone can always park! Moreover, there's always one space left empty. Preferences for this augmented lot are encoded as $n$-tuples taking values as residue classes modulo $n+1$, so there are $(n+1)^n$ of them. The placement of the single unoccupied parking space is equidistributed, so $(n+1)^{n-1}$ preference tuples leave the $n+1$ spot vacant. We lastly verify that each of these preference tuples leaving the $n+1$ spot vacant, when taken at face-value, is a parking function:

Suppose you considered a parking function as encoding preferences for the augmented circular lot. Since it was a parking function, the shoppers don't need to loop around in order to park, and the resultant arrangement leaves the $n+1$ space empty. Conversely, a preference tuple on the augmented lot that results in the $n+1$ space unoccupied was such that no shopper had a preference for the $n+1$ space, and no shopper ever did a loop around the lot (since they park as soon as possible), hence it's a parking function.

Thus we find $P(n) = (n+1)^{n-1}$ by thinking about an extra space gluing the ends of the parking lot together, and then showing that all the ways of avoiding that extra structure are the very objects we are enumerating.

Actually if I squint hard enough this almost seems vaguely reminiscent of the general methodology of proving something about a topological space $X$ by porting a result on some compactification of $X.$

Answer 11

One instance I am very fond of:

If $m,n$ are positive integers and $n$ is odd, then $S^m\times S^n$ has trivial tangent bundle.

Proof. Here the wise man is the tangent bundle of $S^n$. Think $T(S^m\times S^n)=TS^m\oplus TS^n$. Since $n$ is odd, $S^n$ has a nowhere vanishing vector field, so up to isomorphism $TS^n$ splits as $\mathbb{R}\oplus F$, where $\mathbb{R}$ denotes the trivial one-dimensional vector bundle.

Now the wise man $TS^n$ lends the trivial piece $\mathbb{R}$ to $TS^m$ and $TS^m\oplus\mathbb{R}$ becomes trivial, since (the pullback by $S^m\hookrightarrow\mathbb{R}^{m+1}$ of) $T\mathbb{R}^{m+1}$ equals $TS^m\oplus\mathbb{R}$, due to the presence of the outward unit normal.

So $TS^m\oplus\mathbb{R}=\mathbb{R}^{m+1}$ and now the wise man takes (a copy of) his $\mathbb{R}$ back to form again $TS^n$. Finally, he takes another $\mathbb{R}$ to trivialize himself in the same way.

Answer 12

In many cases, an integral over the reals can be conveniently evaluated with the help of contour integration in the complex plane.

Answer 13

Evaluation of definite integrals via the method of differentiation under the integral sign has this character. This probably needs no introduction, but the idea is to view the integrand $f(x)$ of $\int_a^b f(x)\; dx$ as belonging to a (judiciously chosen) parametrized family of functions $F(x, t)$, say at $t = t_0$. (So the parameter $t$ is the 18th camel.) Under mild hypotheses the function

$$G(t) = \int_a^b F(x, t)\; dx$$

has derivative

$$G'(t) = \int_a^b \frac{\partial}{\partial t} F(x, t)\; dx$$

and in many cases this will be simple enough to allow one to solve for $G(t)$. Then the original integral is $G(t_0)$. The Wikipedia article gives some examples of this technique (made popular by Feynman through his book "Surely You're Joking, Mr. Feynman!").

My impression is that the method of creative telescoping is similar in nature; perhaps others more knowledgeable about this can weigh in.

Answer 14

The ancient proof of the Pythagorean Theorem: add four triangles to $c^2$ and remove them to get $a^2+b^2$.

Answer 15

This method is rather common when considering topological invariants. We often add structure to define some quantity, then later show that the quantity is independent of the choice we made.

A simple example is the computation of the Euler characteristic of a surface. We typically choose a triangulation, then compute #vertices - #edges + #triangles. More recent constructions like singular homology allow us to define Euler characteristic without adding a camel choosing a triangulation, but the computation with triangulations is concrete and relatively quick.

More complicated examples abound, where the camel may take the form of a Riemannian metric, a Morse function, a projection of a link to a plane, etc.

Answer 16

I think a fun example of this is the simplification of $$\sum_{k=1}^n \sin kx.$$ First multiply by $\sin \frac x2$ to get $$\sum_{k=1}^n \sin kx \sin \frac x2 = \sum_{k=1}^n \frac 12 \left[ \cos (k - \frac 12)x - \cos(k + \frac 12)x \right] = \frac{\cos \frac x2 - \cos(n + \frac 12)x}2$$ then divide by the same term to find $$\sum_{k=1}^n \sin kx = \frac{\cos \frac x2 - \cos(n + \frac 12)x}{2\sin \frac x2}.$$

Answer 17

The Catalan number $C_n= \frac{2n \choose n}{n+1}$ counts the number of binary strings with $n$ $1$s and $n$ $0$s so that every prefix has at least as many $1$s as $0$s. There is a combinatorial proof, I think due to Cauchy, which involves an 18th camel.

There are $2n \choose n$ binary strings with $n$ of each letter. Add an $n+1$st $1$ to the end of each word! There are $n+1$ cyclic rotations ending in $1$. Precisely one of these has the property that each prefix has at least as many $1$s as $0$s. (This is nontrivial but not hard to prove.)

For example, the $5$ rotations of $11100010$ are

$$\begin{eqnarray}11100010{\color{red}1} \newline 11000101{\color{red}1} \newline 10001011{\color{red}1} \newline 00010111{\color{red}1}\newline 01111000{\color{red}1}\end{eqnarray}$$

with the 18th camels in red.

Answer 18

This does not quite match your criteria, but feels similar. It is a method for multiplying two decimals, say $13 \times 27$. Form two columns headed by $13$ and $27$. Halve $13$ and discard any remainder, and double $27$. Continue halving the first column and doubling the second until the first column reaches $1$:

\begin{array} \mbox{13} & 27 \\ {\color{red}{6}} & {\color{red}{54}} \\ 3 & 108 \\ 1 & 216 \end{array}

Now discard any row for which the first column is even ($\color{red}{6}$ above). Sum the remaining elements of the second column: $$27 + 108 + 216 = 351 = 13 \times 27 \;.$$ This is of course using the binary representation $13 = 2^0 + 2^2 + 2^3$, and first including but later excluding the $2^1$ row $\color{red}{6} \;\; \color{red}{54}$.

Answer 19

The replica trick/method in statistical physics (and more recently machine learning) computes a property of a system by considering $n$ copies of the system and then taking a limit $n \downarrow 0$.

Answer 20

This seems like a good place to advertise LSpice's great answer (spread out over a series of comments) to my earlier MO question Where does the really nice '8-dimensional' description of the $E_7$ root system come from?, where LSpice shows that $E_8$ has a $E_7 \times A_1$ subalgebra by adding and removing one node to/from the Dynkin diagram.

Answer 21

I just want to precise what really happened in the story, in case some are left wondering:

There was no way to partition the 17 camels as described, without having non-integer parts of camels... To (wisely) avoid that, the wise man changed the partitionning a bit (in the end, each son got a different amount of camels than they should have had, but they all got live camels, which is a win). The wise man made sure that he added whatever camels were needed to ensure a integer division among the sons, and took those back in the end.

Ie, the sons never received "1/2" "1/3" and "1/9" of 17 camels, but instead received the 1/2th, 1/3th and 1/9th of 18 camels, which amounted to only 17 camels (as 1/2, 1/3 and 1/9 is equal to 9/18+6/18+2/18 = 17/18. The wise man just represented the remaining 1/18th part with his camel.)

Answer 22

In physics, the canonical example is the case of gauge theories. There are different levels of sophistication:

• Classical electromagnetism: here the "physical" variables are the components of the two form $F$ (the electromagnetic field). In principle, one may formulate the theory purely in terms of $F$, with no extra camels. On the other hand, the general analysis greatly simplifies if one introduces extra variables in the form of a one form $A$, such that $F=\mathrm dA$. As usual, the differential form $A$ is defined up to an arbitrary exact form. General field configurations (the solutions of the equations of motion), when written in terms of $A$, depend on one arbitrary function, reflecting the presence of extra "unphysical" degrees of freedom.

• Classical Yang-Mills: here we have several two-forms $F$ (living in the adjoint representation of a certain Lie Group) such that $F=\mathrm dA+A\wedge A$. Here, and unlike before, it is impossible to formulate the theory purely in terms of $F$, and therefore one is forced to introduce the one forms $A$. As before, these are not uniquely determined given $F$, and therefore general field configurations depend on several arbitrary functions.

• Quantum Yang-Mills: in order to have a manageable and consistent theory, one is obliged to introduce more "unphysical variables", i.e., more extra fields. These are the so-called Faddeev-Popov ghosts, and they greatly simplify the general formalism but, once again, they are auxiliary, unobservable fields. They do not affect measurable predictions.

• Other quantum gauge theories: the most general and systematic approach to the quantisation of gauge theories that we know of as of today is the Batalin-Vilkovisky formalism. In this formalism, one introduces one auxiliary variable for each field that one is working with. That is, the first step towards the quantisation of the theory is to duplicate the number of variables (which include the gauge fields themselves, as well as any Faddeev-Popov ghost, or any other auxiliary field that is present). These variables are eventually eliminated, but their presence greatly simplifies the general analysis.

---

Other examples in physics:

• Stückelberg fields, which are extra fields that are introduced to maintain gauge invariance in massive theories. In the same vein, the Goldstone-like components of the Higgs field.

• Pauli-Villars fields, which are introduced to ensure convergence of certain integrals. They are eventually eliminated (after making sure that there are no measurable divergences).

• Inonu-Wigner contraction: sometimes, one may understand a certain group as the contraction of a larger group. If the larger group is simpler than the contracted one, one may use this information to simplify the analysis of the contracted group. Such is the case of the Poincaré Group, which is the contraction of $\mathrm{SO}(4,1)$ (the latter being semi-simple, and the former not). The explicit contraction allows us to obtain, for example, the rank and Casimirs of Poincaré in terms of those of $\mathrm{SO}(4,1)$.

• The method of image charges, which is a strategy to solve certain problems in electrostatics by introducing extra "fictitious" point-charges, and exploiting the symmetry of the resulting configuration. One should note that this technique can be used to obtain certain Green functions provided the domain is simple enough.

---

Finally, I'm surprised no one has mentioned the standard trick to calculate the Gaussian integral $$ \int\mathrm e^{-x^2}\mathrm dx=\sqrt{\pi} $$ by introducing a second coordinate $y$, such that $$ \left(\int\mathrm e^{-x^2}\mathrm dx\right)^2=\int\mathrm e^{-r^2}\mathrm dx\,\mathrm dy $$ and changing to polar coordinates.

Answer 23

A very simple application of this technique is a mental math strategy: round to a number that's easy to work with, then reverse the rounding later.

? = 56 + 17

? = 60 + 17 - 4

? = 77 - 4

? = 73

You have to be a bit more careful with multiplication and division, but it works just the same.

? = 43.25 * 15%

? = 43.25 * 10% + 43.25 * 5%

? = 4.32 + 43.25 * 10% / 2

? = 4.32 + 4.32 / 2

? = 4.32 + 2.16

? = 6.48

Answer 24

To learn a good classifier, you want a large training set of labeled data. In many settings, data is cheap but labels are expensive, requiring human labor. So what do we do with a bunch of unlabeled data?

Sometimes, the unlabeled data will reveal helpful clusterings:

Incorporating unlabeled data in the classification task is called semi-supervised learning, and this has found success recently in various state-of-the-art classifiers based on deep learning.

Answer 25

In model theory, you often add different symbols to the language you're interested in, to prove a result and then go back to the original language to have the theorem you wanted.

To be more precise, here's an example : suppose you want to show that a theory $T$ in a language $L$ with arbitrarily large finite models has infinite models of arbitrarily large cardinality.

You pick a cardinal $\kappa$, add $\kappa$-many new symbols $c_\alpha$ for $\alpha<\kappa$ to the language $L$ to get $L'$. Then you notice that $T\cup\{c_\alpha\neq c_\beta \mid \alpha\neq \beta \in \kappa\}$ is finitely consistent by hypothesis; and so by compactness it is consistent.

Take a model $M$ of $T'$ and consider its $L$-reduct $\tilde{M}$. This is a model of $T$ and it has cardinality $\geq \kappa$ : we added stuff to $L$ to get what we wanted, then removed it to have a theorem about $L$.

Answer 26

When proving that a finite flat simple group scheme $G$ of $2$-power order over $\mathrm{Spec}\,\mathbf{Z}$ is of order $2$ (and hence isomorphic to $\mu_2$ or $\mathbf{Z}/2$), one proves that for $K = \mathbf{Q}(G(\bar{\mathbf{Q}}))$ the Galois group $\mathrm{Gal}(K/\mathbf{Q})$ is a $2$-group.

In order to prove this, one enlarges $G$ to $\tilde{G} := G \times G_{-1}$ with the Katz-Mazur group scheme $G_{-1}$ sitting in an exact sequence $1 \to \mu_2 \to G_{-1} \to \mathbf{Z}/2 \to 0$. Then one proves that $\mathbf{Q}(G_{-1}(\bar{\mathbf{Q}})) = \mathbf{Q}(i)$, and by the Odlyzko bounds (this uses that $\tilde{K} := \mathbf{Q}(\tilde{G}(\bar{\mathbf{Q}}))$ is totally imaginary since $\mathbf{Q}(i)$ is), one has $[\tilde{K}:\mathbf{Q}] \leq 4$, so since one has the inclusions of fields $\tilde{K} \supseteq \mathbf{Q}(i) \supseteq \mathbf{Q}$, $\mathrm{Gal}(\tilde{K}/\mathbf{Q})$ is a $2$-group, hence so is $\mathrm{Gal}(K/\mathbf{Q})$.

So the trick is to add $G_{-1}$.

This is used in proving Fontaine's theorem that there is no non-trivial Abelian scheme over $\mathrm{Spec}\,\mathbf{Z}$. See the notes of René Schoof https://math.dartmouth.edu/~jvoight/notes/274-Schoof.pdf, p. 41–43.

Answer 27

Grobner basis methods for testing subalgebra membership are another example. You add extra variables in order to take advantage of the good features of Grobner bases for elimination orders. You can throw them out afterward.

For example: say you want to find out whether a given polynomial $f\in k[x_1,\dots,x_n]$ is in the subalgebra generated by a specific set $g_1,\dots,g_\ell \in k[x_1,\dots,x_n]$ of other polynomials, and if it is, to find a representation of $f$ in terms of the $g_i$'s. Create a new polynomial ring with new indeterminates $G_1,\dots,G_\ell$ and $F$:

$$R = k[x_1,\dots,x_n,F,G_1,\dots,G_\ell]$$

Now compute a Grobner basis for the ideal

$$(g_1-G_1,\dots,g_\ell-G_\ell,f-F)$$

with respect to an elimination order in which $x_i > F > G_j$ for all $i,j$. If $f$ is a polynomial in the $g$'s, then there will be a corresponding element in the Grobner basis with the form

$$F-\text{polynomial in the }G\text{'s},$$

indicating the representation of $f$ in terms of $g$'s. If not, there will be no such element in the Grobner basis.

Answer 28

The spoiler effect in voting theory concerns how a "spoiler candidate" with ideology similar one major candidate can split the vote in favor of another major candidate. This effect is a common criticism of the IIA axiom, and enjoys a history of application in real-world democracy.

Answer 29

I think that an example much in the spirit of the original question is one of proofs of the fact that Tychonnoff Theorem for compact spaces entails existence of choice functions. To show this for an arbitrary family of non-empty sets $(R_i)_{i\in I}$ we consider an object $x\notin\bigcup_{i\in I}R_i$ and the family of compact spaces $\mathscr{O}_i=\{\emptyset,\{x\},R_i^x\}$ with $R_i^x=R_i\cup\{x\}$. Each of the spaces is compact, so $\prod_{i\in I}R^x_i$ is compact by TT. Thus to show that some $f\colon I\rightarrow\bigcup_{i\in I}R_i$ exists it is enough to show that the family of closed sets $\{\pi^{-1}_i[R_i]\mid i\in I\}$ has finite intersection property. Taking $R_{i_1},\ldots,R_{i_k}$ we define $g\colon I\rightarrow \bigcup_{i\in I}R_i^x$ by: $g(i)\in R_i$ in case $i_1\leqslant i\leqslant i_k$, and $g(i)=x$ otherwise. It follows that $g\in\pi^{-1}_{i_1}[R_{i_1}]\cap\ldots\cap\pi^{-1}_{i_k}[R_{i_k}]$. So there is $f\in\prod_{i\in I}R_i$.

So, it is a bit like adding a camel to ensure that given any finite collection of flocks of camels we can find its respective representatives, and afterwards taking the camel away and conclude that any flock of camels from a given family of flocks can be represented by exactly one camel.

Answer 30

When learning the derivative and its various rules, the intuitive undergrad way of proving the product formula kind of does this. We add an $f(x+h)g(x) - f(x+h)g(x)$ and the product formula just pops out. Of course I've never seen this proof rigorously done. I've just seen it used as an ad hoc way to convince people not fluent in epsilon-delta.

Answer 31

Poissonization. When $N$ balls are placed in $M$ urns we get a multinomial distribution. For many calculations it's easier to consider the alternative (and apparently more complex) model in which the number of balls is random: $N$ is not fixed, only its mean. The models are (asymptotically, in some some sense) equivalent.

In the same vein, when computing asympotical statistics for head/tail runs of a sequence of $N$ random coins, it's sometimes convenient to consider that $N$ is random. For example.

In a similar vein (I guess the analogy has been noted somewhere), in Statistical Physics, the Canonical ensemble seems more complex than necessary (the kinetic energy is not fixed, as it is in the seemingly simpler and more natural microcanonical ensemble); actually, the Canonical ensemble is much easier to deal with. A similiar consideration applies when going from the Canonical to the Grand-Canonical ensemble, in which also the number of particles is not fixed.

Answer 32

Integrating factor

If we have an ODE of the form: $$ y'(x) + p(x)y=q(x),$$ then we can multiply both sides by the so called integrating factor $I(x) = e^{\int p(x) \mathrm{d}x}$. This will reduce the problem into one of taking the anti-derivative: $$ \left( I(x)y(x) \right)' = I(x)q(x). $$ Once we integrate the right hand side we will have to divide by $I(x)$ to solve for $y(x)$. We are removing the camel, so to speak.

Example

Here is a very simple example from wikipedia, but also see the more general one there. Start with:

$$ y' - 2\frac{y}{x} = 0 $$

The integrating factor turns out to be $I(x)=\frac{1}{x^2}$. Multiplying we get: $$ \frac{y'}{x^2} - \frac{2}{x^3}y = \left(\frac{y}{x^2}\right)'=0,$$ at once solving the ODE: $$\frac{y}{x^2} = C \implies y=Cx^2.$$

Answer 33

Suppose that we need to divide 9 people into two volleyball teams. Usually we start with two captains (best players). First captain choose one player. After that second captain and first captain choose two players on each step. The problem is in bad players which may have negative weight in the team. And in the end of this procedure captains obliged to choose bad players.

This algorithm will work better if we'll complete the original group with 3 (3+9=12) virtual (empty) players (with zero weight). So each captain may take one of the empty player instead of negative ones.

Answer 34

This answer is for those who didn't get the above explanations and still wonder why the old man added only $1$ camel, not $3$ to make it $20$ and then divide. How come he knew that he should have $18$ camels from all the other numbers?

If he had added $3$ and divided $20$ camels: \begin{gather} 20 \cdot \frac{1}{2} = 10, \\ 20 \cdot \frac{1}{3} = 6.\overline{6}, \\ 20 \cdot \frac{1}{9} = 2.\overline{2}. \end{gather} You see the problem. The point here is to get the LCM of the partitions, i.e., the LCM of $2$, $3$, and $9$ is $18$.

So old man calculated the LCM and then adjusted the count of camels according to it.

But how his camel remained after partitioning:

Addition of the partitions should lead to $1$, but in this case what we get is $$ \frac{1}{2} + \frac{1}{3} + \frac{1}{9} = \frac{17}{18} $$ so if we add one more partition to it $$ \frac{1}{2} + \frac{1}{3} + \frac{1}{9} + \frac{1}{18} = \frac{18}{18} = 1 . $$ We must say the old wise man was a good mathematician.

Answer 35

We know the Oddtown theorem: for any set $S$ with $|S|=n$ and $T \subseteq 2^{S}$ with each element of $T$ having odd cardinality and the intersection of two distinct elements of $T$ having even cardinality, $|T| \leq n$.

To show the following:

for any set $S$ with $|S|=n$ and $T \subseteq 2^{S}$ with each element of $T$ having even cardinality and the intersection of two distinct elements of $T$ having odd cardinality, $|T| \leq n+1$

we just add a new element to $S$ and all the elements of $T$, apply the Oddtown theorem, and then remove this element from $S$ and all the elements of $T$.

Answer 36

This might not be completely as asked, as the thing added is removed in a slightly different form. But it is still such a common thing that I felt it merited mention.

In algebraic geometry, it is often convenient to focus on closed subsets (subvarieties/subschemes), as these will have more natural descriptions.
On the other hand, we also want to consider the group of units of the base ring $k$, which is not a closed subset of $\operatorname{Spec}(k[x])$, but rather an open one.
The solution is to instead consider it as a closed subset of $\operatorname{Spec}(k[x,y])$, given by $xy = 1$. Since this clearly has codimension $1$, we have thus first added an extra dimension (the $y$), then removed it again (by identifying it with $x^{-1}$).

Answer 37

In homotopy theory, this happens when you use stable splittings of spaces to analyze homotopy types. For example, (writing $X_+$ for $X$ with a disjoint basepoint), $X_+ \not\simeq X \vee S^0$ (as pointed spaces, generally), but $$ \Sigma ( X_+ ) \simeq \Sigma X \vee S^1 \simeq \Sigma ( X_+ \vee S^0 ). $$ Also $\Sigma (X\wedge Y) \simeq (\Sigma X) \wedge Y \simeq X \wedge \Sigma Y$ (since $\Sigma X = S^1 \wedge X$ and $\wedge$ is commutative and associative). From this we get, for example $$ \Sigma ( (X\times Y)_+ ) = \Sigma( X_+ \wedge Y_+) \simeq \Sigma ( (X\vee S^0) \wedge (Y\vee S^0) ) = \Sigma ((( X\vee Y \vee (X \wedge Y))_+). $$ This is a pretty painless way to show the stable splitting of products. Another simple formula that is useful for this kind of argument is the James splitting $$ \Sigma ( \Omega \Sigma X) \simeq \Sigma \textstyle\left( \bigvee_{n\geq 0} X^{\wedge n} \right). $$ This is used by B. Gray, for example, in his nice proof of the Hilton-Milnor theorem.

Answer 38

I'm not sure, if adding $0$ counts as an 18th camel:

Sometimes adding $0$ expressed as the difference of two equal values or variables simplifies things; a very basic application is squaring numbers by utilizing the 3rd binomial identity $(a+b)(a-b) = a^2-b^2$ which used in the form $a^2=(a+b)(a-b)+b^2$. In order to calculate e.g. $35^2$ one would calculate $30\cdot40+25$.

I have also seen proofs that utilize the trick of adding $0$ in the form $x-x$, but unfortunately I can't remember what it was.

Answer 39

How to define an analytic branch of the function $\sqrt{z^2-1}$ on the domain $\mathbb{C}\setminus [-1,1]$? We add an additional cut $[1,\infty)$ and define $\sqrt{z-1}$ on $\mathbb{C}\setminus [1,\infty)$ and $\sqrt{z+1}$ on $\mathbb{C}\setminus [-1,\infty)$ by usual way (using the formula $\sqrt{re^{i\theta}}=\sqrt{r}e^{i\theta/2}$ for $0<\theta<2\pi$.) Now we multiply these square roots and define $\sqrt{z^2-1}=\sqrt{z-1}\times \sqrt{z+1}$ on $\mathbb{C}\setminus [-1,\infty)$. We see that the limit values of so defined $\sqrt{z^2-1}$ in the points $t+0i$ and $t-0i$, $t>1$, are equal, so we may define the function on $(1,\infty)$ by continuity and remove this camel-cut.

Answer 40

Two real valued sinudoidal voltages are treated as complex, and added together. Then only the real part is kept.

Answer 41

Dr. Vogler's trick for removing radicals from equations, which essentially amounts to turning a linear equation into a system of equations for a specific set of monomials, each of which is considered a different variable. Of all the monomial-variables that have been determined, all that do not represent a radical of the original equation, are discarded.

also related are these questions and answers:

• Rewrite sum of radicals equation as polynomial equation

• Tools for Removing Radicals from Equations

Answer 42

Given a self-adjoint, bounded-below, compactly-resolved operator $T$ densely defined in a Hilbert space, one method to study its eigenvalues is to consider the closure of its domain with respect to the norm $\langle Tu, u\rangle$.

However if $T$ is not positive, this is not a norm. So one considers instead the eigenvalues of operator $T + c$, where $c$ is chosen so that $T+c$ is positive. Apply the machinery to obtain eigenvalues of $T+c$.

Then the eigenvalues of $T$ are simply the eigenvalues of $T+c$, less $c$.

Answer 43

A simple graph theory example in the spirit of the question.

THM. Let $G$ be a connected graph with $2j$ vertices of odd degree. Then there are $j$ (open) eulerian trails whose endpoints are the vertices of odd degree.

PROOF. Add $j$ edges between the odd-degree vertices to make $G$ into a (multi-)graph with only even degrees. Choose an eulerian circuit, then remove the extra edges.

Answer 44

I'm surprised, that the Method of Complements hasn't been mentioned yet.

The trick it does, is to replace subtraction with addition and is commonly used in (mechanical) calculators, like the Curta.

Answer 45

Variants of matching problems can often be reduced to standard matching problems by adding further vertices and edges, to the orginal problem:

• the gadgets of Tutte or Lovasz and Plummer for reducing the task of finding a optimal f-factor (provided its existence) of a possibly weighted graph.

• given a graph with $n$ vertices, the problem of finding an optimal matching with $k$ edges can be solved by adding $n-2k$ vertices that are adjacent every original vertex via an edge with cost $0$ in case of a minimization problem.

Answer 46

Let's generalize a bit, and instead of adding artificially something and taking it away when we are done, let's do whatever operation brings us in a situation where we are able to reach our aim, and then revert the operation. Isn't this the idea of conjugation?

Answer 47

I think Strategy-stealing arguments from combinatorial game theory are in the same vein. Here is a classic example.

Prove that in two-move chess, Black does not have a winning strategy.

Proof. Suppose not. White can move one of her knights on her first move, and then return the knight to its original square on her second move. By symmetry, she is now playing as Black and can use Black's winning strategy against Black. $\square$

Here the 'extra camel' is to do nothing and end up as the second player.

Answer 48

simplifying algorithms by adding sentinel elements, that can be easily identified, e.g. adding $-INF$ and $+INF$ to guarantee, that a search will always find a closed interval in which the queried value would have to be. Another example is sorting, where adding elements of value $+INF$ till the number of elements reaches the next power of two allows a simpler Divide&Conquer algorithm.

Answer 49

Fact: Let $G$ be a compact connected Lie group, then the exponential map is surjective.

The proof is to add an "extra" structure of a Bi-invariant Riemannian metric on $G$, then use compactness and Hopf-Rinow to deduce completeness. Finally deduce surjectivity of the exponential map from completeness.

Answer 50

Ramanujan in his 1912 article Note on a set of simultaneous equations explicitly solves a special system of polynomial equations $\boldsymbol{Y}\boldsymbol{x}=\boldsymbol{a};\ \boldsymbol{Y}\in\mathbb{R}^{2n\times n}\ \boldsymbol{x},\boldsymbol{a}\,\in\,\mathbb{R}^n$; $Y_{ij}=y_j^i$ by introducing a variable $\theta$ that seems to come out of the blue.

My impression from reading the article is that $\theta$ only serves the purpose of identifying corresponding terms after having carried out calculations.