# 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

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.

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.

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

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

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

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

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.

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.

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) \vee 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.

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.

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 at 20:04