The seventeen camels riddle, and Noga Alon’s camel proof and algorithms

Three children inherited 17 camels. The will gave one half to one child, one third to a second child and one ninth to the third. The children did not know what to do and  a neighbor offered to lend them a camel. Now there were 18 camels. One child got \frac{18}{2}=9 camels the second got \frac{18}{3}=6 camels, and the third got \frac{18}{9}=2 camels. Altogether they got 17 camels so they could give back the extra camel to the kind neighbor.

In the very short 2003 paper A simple algorithm for edge-coloring bipartite multigraphs, Information Processing Letters 85 (2003), 301-302, Noga Alon used a similar idea for algorithmic purposes. (He also observed the connection to the camel riddle). Here is how the extra camel idea is used for:

Theorem:  A bipartite cubic graph G has a perfect matching.

(A cubic graph is a  3-regular graph.)

Proof: Suppose that G has n vertices. Multiply each edge r times (r large) so that the degree of each vertex 3r is of the form 2^m-1. Now ask your neighbor to give you an additional perfect matching and add it to the graph which now is regular of degree 2^{m} . The new graph has an Eulerian cycle. (If not connected, every connected component has an Eulerian cycle.) When we walk on the Eulerian cycle and take either the even edges or the odd edges we get two subraphs of degree 2^{m-1}.  At least one of them does not use all the edges of the neighbor. We move to this subgraph and give the unused edge back to the neighbor.  We repeat, and in each step we move to a regular subgraph of degree  a smaller power of two, and give back at least one edge to the kind neighbor. If r is large enough to start with we will end with a perfect matching that uses only the original edges of our graph.

(Remark: We can take m=n/2 or m=n/2+1. If we are a little more careful and in each step try to give many edges back to the kind neighbor we can use m=\log n or so.)

This entry was posted in Combinatorics and tagged . Bookmark the permalink.

3 Responses to The seventeen camels riddle, and Noga Alon’s camel proof and algorithms

  1. Gil Kalai says:

    Of course, it will be interesting if some thing like this can work for finding 3-edge coloring for other classes of cubic graphs which are 3-edge colorable.

  2. vegafrank says:

    In general, UP vs NP is a completely different problem than P vs. NP. In particular, while a strong connection of NP and (promise) UP is already known, P is widely believed to be different than NP. We define a problem that we call General Quadratic Congruences. We show General Quadratic Congruences is an NP-complete problem. Moreover, we prove General Quadratic Congruences is also in UP. In this way, we demonstrate that UP = NP.

  3. Pingback: Proof By Lice! | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s