{"id":2298,"date":"2018-05-05T00:21:05","date_gmt":"2018-05-05T05:21:05","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=2298"},"modified":"2018-05-05T13:46:39","modified_gmt":"2018-05-05T18:46:39","slug":"counting-coconuts","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/counting-coconuts\/","title":{"rendered":"Counting coconuts"},"content":{"rendered":"

This Riddler<\/a> problem is about divisibility… of coconuts!<\/p>\n

\nSeven pirates wash ashore on a deserted island after their ship sinks. In order to survive, they gather as many coconuts as they can find and throw them into a central pile. As the sun sets, they all go to sleep.<\/p>\n

One pirate wakes up in the middle of the night. Being the greedy person he is, this pirate decides to take some coconuts from the pile and hide them for himself. As he approaches the pile, though, he notices a monkey watching him. To keep the monkey quiet, the pirate tosses it one coconut from the pile. He then divides the rest of the pile into seven equally sized bunches and hides one of the bunches in the bushes. Finally, he recombines the remaining coconuts into a single pile and goes back to sleep. (Note that individual coconuts are very hard, and therefore indivisible.)<\/p>\n

Later that night, a second pirate wakes up with the same idea. She tosses the monkey one coconut from the central pile, divides the pile into seven bunches, hides her bunch, recombines the rest, and goes back to sleep. After that, a third pirate wakes up and does the same thing. Then a fourth. Then a fifth, and so on until all seven pirates have hidden a share of the coconuts.<\/p>\n

In the morning, the pirates look at the remaining central pile and notice that it has gotten quite small. They decide to split the pile into seven equal bunches and take one bunch each. (Note: The monkey does not get one this time.) If there were N coconuts in the pile originally, what is the smallest possible value of N?\n<\/p><\/blockquote>\n

Here is a short solution:
\n[Show Solution]<\/a><\/p>\n

\n

Suppose there are $M$ coconuts in the central pile when one of the pirates takes their turn. One coconut is given to the monkey, the rest are divided into seven equal piles, and six of the piles are returned to the central pile. Mathematically, this corresponds to the function: $f(M) = \\tfrac{6}{7}(M-1)$. In other words, every time a pirate visits the central pile, the number of coconuts shrinks as $M\\mapsto f(M)$.<\/p>\n

After seven visits, the initial number of coconuts has shrunken to a (positive) number that is divisible by $7$. We can express this as:
\n\\[
\nf^{(7)}(N) = f(f(f(f(f(f(f(N))))))) = 7k
\n\\]Expanding this formula, it is a linear equation relating $N$ and $k$, which is:
\n\\[
\nN=\\frac{5764801 k+3261642}{279936}
\n\\]The problem asks us to find the smallest $N$. This is equivalent to finding the smallest positive integer $k$ such that $N$ is an integer. This sort of problem is called a linear congruence equation<\/a> and it can be solved using modular arithmetic. In Mathematica, the command is:<\/p>\n

Reduce[5764801 k + 3261642 == 0, k, Modulus -> 279936]
\n<\/code><\/p>\n

It can also be solved using WolframAlpha<\/a>. The smallest solution is $k=39990$, which leads to $N=823537$. That’s a lot of coconuts!<\/p>\n<\/div>\n

If you’d like to learn more about how to solve such problems (what is modular arithmetic anyway!?) then read on!
\n[Show Solution]<\/a><\/p>\n

\n

I’ll assume you already read the above solution. In order to understand where the solution comes from, we need to take a brief detour into the world of modular arithmetic…<\/p>\n

Detour: modular arithmetic<\/h3>\n

I’ll illustrate the technique using a simpler example. Let’s find the smallest positive $k$ such that $\\frac{5k+2}{3}$ is an integer. Put another way, we want $5k+2$ to be divisible by 3. This is written as:
\n\\[
\n5k+2 \\equiv 0 \\pmod{3}
\n\\]The only thing that matters when we’re working “modulo 3” is the remainder upon division by 3. For example, the numbers $\\{\\dots,-3,0,3,6,\\dots\\}$ are all equivalent to 0 mod 3 because they are divisible by 3. Likewise, the numbers $\\{\\dots,-2,1,4,7,\\dots\\}$ are all equivalent to 1 mod 3 because they have a remainder of 1 (i.e. they are of the form $3k+1$ for some integer $k$). When adding or multiplying numbers together, we can replace them by any equivalent numbers modulo 3 and this doesn’t change the result. So, for example:
\n\\[
\n5k+2\\equiv 0 \\pmod{3}
\n\\quad\\text{is the same as solving}\\quad
\n2k\\equiv 1\\pmod{3}
\n\\]Naturally, because we’re working modulo 3, we only need to try $k=\\{0,1,2\\}$, and we find the solution is $k\\equiv 2$. This means, of course, that we could have used any $k$ of the form $3m+2$ and it would have also worked. The smallest positive $k$ is therefore $k=2$, and this works; $5\\times 2+2=12$, which is divisible by 3.<\/p>\n

Let’s turn our attention to the question of solving $ak\\equiv b \\pmod{m}$. Here, $a$, $b$, $m$ are fixed, and we want to solve for $k$. This is called a linear congruence equation<\/a> and it is a well-known concept in number theory. I’ll summarize the key results below.<\/p>\n

First, note that there need not be any solutions at all! For example, $5k\\equiv 2 \\pmod{15}$ clearly has no solution, since $5k$ can only be equal to $\\{0,5,10\\}$ modulo 15. There can also be multiple solutions. For example, $4k\\equiv 2 \\pmod{6}$ has solutions $k\\equiv 2$ or $k\\equiv 5$. In general,<\/p>\n

    \n
  1. Let $g=\\textrm{gcd}(a,m)$ (greatest common divisor). Then the equation $ak\\equiv b\\pmod{m}$ has a solution if and only if $g$ divides $b$.<\/li>\n
  2. If $k_0$ is a particular solution, then there are $g$ solutions in total, given by: $\\left\\{k_0,\\, k_0+\\frac{m}{g},\\, k_0+\\frac{2m}{g},\\,\\dots,\\,k_0+\\frac{(g-1)m}{g} \\right\\}$<\/li>\n
  3. The modified equation $(\\tfrac{a}{g})k \\equiv \\tfrac{b}{g} \\pmod{\\tfrac{m}{g}}$ reduces to the case $g=1$ because $\\textrm{gcd}(\\tfrac{a}{g},\\tfrac{m}{g})=1$ by definition. Consequently this modified equation has a unique solution, which can serve as $k_0$ for the original equation.<\/li>\n
  4. To solve the case $g=1$, B\u00e9zout’s Identity<\/a> states that there must exist $s$ and $t$ such that $sa+tm=1$. Then, we have $bsa+btm=b$, which implies that $k_0 = bs$ solves our equation. B\u00e9zout’s Identity can be solved via the Extended Euclidean Algorithm<\/a>.<\/li>\n<\/ol>\n

    Back to coconuts!<\/h3>\n

    Our goal was to find the smallest positive integer $k$ such that $N=\\frac{5764801 k+3261642}{279936}$ is also an integer. This amounts to solving the linear congruence equation
    \n\\[
    \n5764801k+3261642 \\equiv 0\\pmod{279936}
    \n\\]Reducing and rearranging this is equivalent to:
    \n\\[
    \n166081k \\equiv 97590\\pmod{279936}
    \n\\]The first thing to observe is that $279936=2^7\\cdot 3^7$ whereas $166081$ is a prime number. Therefore, $\\mathrm{gcd}(166081,279936)=1$. So we know the linear congruence has a unique solution. The solution to the B\u00e9zout Identity can be computed using the Mathematica function:
    \n    {g, {s, t}} = ExtendedGCD[166081, 279936]<\/a><\/code>.
    \nThis yields the result:
    \n\\[
    \n(123073)(166081)+(-73017)(279936)=1
    \n\\]So the solution is $k\\equiv 97590 \\cdot 123073 \\equiv 39990\\pmod{279936}$. We can now compute $N$ as:<\/p>\n

    $\\displaystyle
    \nN=\\frac{5764801\\cdot 39990 +3261642}{279936} = 823537
    \n$<\/span><\/p>\n

    If we want to find all<\/em> solutions, we can add multiples of $279936$ to the base $k_0$ we found. This yields a solution set of the form:
    \n\\[
    \nN = 823537 + 5764801m\\qquad\\text{for: }m=0,1,2,\\dots
    \n\\]<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

    This Riddler problem is about divisibility… of coconuts! Seven pirates wash ashore on a deserted island after their ship sinks. In order to survive, they gather as many coconuts as they can find and throw them into a central pile. As the sun sets, they all go to sleep. One pirate wakes up in the … Continue reading “Counting coconuts”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[36,2],"class_list":["post-2298","post","type-post","status-publish","format-standard","hentry","category-riddler","tag-number-theory","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2298","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2298"}],"version-history":[{"count":8,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2298\/revisions"}],"predecessor-version":[{"id":2309,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2298\/revisions\/2309"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2298"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2298"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2298"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}