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

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 2

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 3

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 4

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 5

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 6

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 7

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 8

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 9

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 10

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 11

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

Answer 12

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 13

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 14

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 15

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 16

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 17

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.

Answer 18

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 19

Here's an example from elementary linear algebra.

Lemma: If $A$ is $n \times m$ and $B$ is $m \times n$, then the characteristic polynomials of $AB$ and $BA$ are related by: $$ t^m \det(\lambda I_n - AB) = t^n \det(\lambda I_m - BA). $$

Proof: If $n=m$, it follows easily when $A$ is invertible, and hence also for $A$ singular by "continuity". If $n > m$, apply the square case to \begin{align*} \begin{pmatrix} A & 0_{n \times (n-m)} \\ \end{pmatrix} \begin{pmatrix} B \\ 0_{n \times (n-m)} \\ \end{pmatrix} &= AB \\ \begin{pmatrix} B \\ 0_{n \times (n-m)} \\ \end{pmatrix} \begin{pmatrix} A & 0_{n \times (n-m)} \\ \end{pmatrix} &= \begin{pmatrix} BA & 0_{n-m} \\ 0_{n-m} & 0_{n-m} \end{pmatrix}. \Box \end{align*}

Both the singular case and the non-square case of the above argument can be thought of as adding something that's then taken away in the end.

Answer 20

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 21

Derivation of "sine-tangent relations" from quadratic Gauss sums of some orders involves reversing not one but two manipulations: one involving a multiplier term and the other involving the direction in which we take an identity. We illustrate this with order $11$.

The nonzero quadratic residues $\bmod 11$ are, of course, $\{1,3, 4,5,9\}$. So the corresponding quadratic Gauss sum takes this form:

$\exp(2\pi i/11)-\exp(4\pi i/11)+\exp(6\pi i/11)+\exp(8\pi i/11)+\exp(10\pi i/11)-\exp(12\pi i/11)-\exp(14\pi i/11)-\exp(16\pi i/11)+\exp(18\pi i/11)-\exp(20\pi i/11)=i\sqrt{11}$

Taking imaginary parts and using the periodicity and odd parity of the sine function that results, we reduce this to

$\sin(2\pi/11)-\sin(4\pi/11)+\sin(6\pi/11)+\sin(8\pi/11)+\sin(10\pi/11)=\sqrt{11}/2$

Now multiply by $2\cos(2\pi/11)$ and apply the trigonometric sum-product relation

$2\sin(u)\cos(v)=\sin(u+v)+\sin(u-v)$

to the terms on the left side. This gives

$\sin(4\pi/11)-\sin(6\pi/11)-\sin(2\pi/11)+\sin(8\pi/11)+\sin(4\pi/11)+\sin(10\pi/11)+\sin(6\pi/11)-\sin(10\pi/11)+\sin(8\pi/11)=\sqrt{11}\cos(2\pi/11)$

Certain terms like $\sin(4\pi/11)$ are doubled, while others like $\sin(6\pi/11)$ are cancelled out, giving

$\color{blue}{2\sin(4\pi/11)}-\sin(2\pi/11)+\color{blue}{2\sin(8\pi/11)}=\sqrt{11}\cos(2\pi/11)$

We now apply the above trigonometric sum-product relation in reverse to the blue terms giving

$4\sin(6\pi/11)\cos(2\pi/11)-\sin(2\pi/11)=\sqrt{11}\cos(2\pi/11)$

and divide out that $\cos(2\pi/11)$ multiplier we applied earlier to get

$4\sin(6\pi/11)-\tan(2\pi/11)=\sqrt{11}.$

Answer 22

In a way one could claim that all of formalized mathematics works that way. As already observed by David Hilbert a century ago, when one formalizes a piece of mathematics, spurious ideal entities tend to creep in that you didn't expect to have originally. One may perhaps be tempted to amend such a claim to apply only to infinitary mathematics, but the distinction itself between finite and infinite requires formalisation and is not as absolute as it may seem, as has been widely discussed at MO in the context of the multiverse of Hamkins (and his question for the mathematical oracle).

Historically - say in the 17th century - negatives, imaginaries, and infinitesimals were viewed as such ideal elements that facilitate the art of discovery. We don't blink when we use complex numbers to find real roots of cubic polynomials, but when Leibniz wrote to his mentor Huygens about this, the latter replied by saying that there is something incomprehensible about this.

When we use the so-called real numbers to calculate the trajectory of a cannon ball, we no longer stop to think just how much idealisation is involved in the mathematics we use to solve such a concrete problem. But perhaps we should.

Answer 23

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.