# 17 camels trick

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 18th camel of a wise man).

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.

• Maybe calculating the derivative of a function at a point could be considered as an example of this – Geoff Robinson Jun 7 '17 at 14:14
• Well, you add a small increment to allow you to calculate a ratio which makes sense, then slowly decrease the increment until it disappears, but you are left a meaningful answer. Probably not the sort of thing you intended, but not an entirely unreasonable interpretation. – Geoff Robinson Jun 7 '17 at 14:29
• No, the point was to realize that the division was by proportion, not by ratio, of the values (1/2,1/3,1/9). Remember the language in those days was differently expressive. Gerhard "And Not As Notationally Compact" Paseman, 2017.06.07. – Gerhard Paseman Jun 7 '17 at 16:20
• Chemistry is the true home of this approach – every catalyst acts this way. – Gerry Myerson Jun 7 '17 at 23:45
• I wonder if there's a classification of all sets of reciprocals where this can happen. Say, for which sets of integers $\alpha_i$ is there a solution to $(n+1)\sum \frac{1}{\alpha_i} = n$ with $\alpha_i | n+1$. – Aaron Bergman Jun 8 '17 at 0:50

# 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.$$

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.

• Sorry, how to divide 9 people into two volleyball teams? I am confused. – Fedor Petrov Jun 8 '17 at 8:41
• There are 9 people who want to play volleyball. And we need to divide them somehow. – Alexey Ustinov Jun 8 '17 at 8:47
• ok, but we can not divide them by 6+6, right? So, should we divide by 5+4 or not necessarily? – Fedor Petrov Jun 8 '17 at 8:53
• I think the point is that each player has a weight and you want the distribution of weight to be as fair as possible - so it is not necessary that the division is 4-5... – Asvin Jun 9 '17 at 12:06
• Yes, 4+5 is not necessary. One captain may take 3 empty players and they will get 3+6. – Alexey Ustinov Jun 9 '17 at 12:17

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.

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$.

• Aha ! This is classic. – Aditya Guha Roy Jul 19 '20 at 13:06
• Do you know whether or not $|T|\le n+1$ is tight for the second problem? When $n$ is odd, you can further prove $|T|\le n$, and this is tight (let $T$ be the set of complements of singletons). When $n$ is even, though, I cannot even find a valid $T$ with size $n$. – Mike Earnest Dec 15 '20 at 6:43

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.

• Adding expressions like $x-x$ is used, for example, in factorizations, like $x^4+4=x^4+4x^2+4-4x^2=(x^2+2)^2-(2x)^2=(x^2-2x+2)(x^2+2x+2)$. – Fedor Petrov Feb 16 '19 at 20:04

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.

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.

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.

• He was also lucky. What would he have done, had the father left only 16 camels? or, indeed, any number other than a multiple of 17? – Gerry Myerson Jun 12 '17 at 23:44
• @GerryMyerson. . . If you see the addition of partitions, its 17 out of 18. So these partitions were created according to number 17. 18 is LCM among partitions. If there were 16 camels, Father must have divided partitions according to number 16, so that addition must have become 16/{LCM} – hanish singla Jun 13 '17 at 5:34
• So, you think the father worked out that the sons would need a wise old man to come along to help them? Then the father must have been an even better mathematician, to devise such a problem. – Gerry Myerson Jun 13 '17 at 6:58
• @GerryMyerson. . certainly. . As far I remember the tale, father was a merchant. It was a test for passing legacy to his children. Here in India, many tales of same kind are popular. In one story, dying father asked his son to always go to shop in shade (He meant go to shop before sunrise and return after sunset always). So mistook the advise by putting tents in the way and ruined business. – hanish singla Jun 14 '17 at 7:19

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:

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$.

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}$).

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.

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.

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.

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?

• Yes, but conjugation with a set of camels is not socially acceptable in many cultures. Gerhard "Let's Just Not Go There" Paseman, 2019.12.31. – Gerhard Paseman Dec 31 '19 at 18:40
• I see, polycamelism is still a tabu – Pietro Majer Dec 31 '19 at 19:07

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.

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

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.

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.

• Well, using extra structures is of course used widely in mathematics, but it looks slightly different thing for me: they do not disappear as the 18th camel. – Fedor Petrov Jun 3 '20 at 21:18