Solution to "Beans, Beans, Beans"


The sons inherited and planted 19{,}897 beans in a rectangle of dimensions 197 \times 101 beans.

Here is one way to arrive at this answer:

Let n represent our elusive number of beans. We will go clue by clue imposing new conditions until we have met all of them.

We have three primary clues: There are (1) 3 left when counting by 7, (2) 7 left when counting by 9, and (3) 196 left when counting by 1+2+3+\cdots. There are some secondary clues, such as n < 30{,}000, which we will remember for later. For now, let's go to the first primary clue: if you count them by 7's you end up with a remainder of 3. Then we can say for some i\ge 0, n=7i+3. The next clue is that n leaves a remainder of 7 when divided by 9, so then using the Chinese Remainder Theorem we will set up our second congruence using the results of the first:

n=7i+3\equiv 7\pmod{9}

7i\equiv 4\pmod{9}.

Since \gcd{(7,9)}=1, we expect one incongruent solution \pmod{9} for i. And by eying it, that would be

i\equiv 7\pmod{9},\text{ or}

i=9j+7

for some j\ge 0.

n=7i+3 and i=9j+7, then

n=7(9j+7)+3=63j+52.

Now the last primary clue is that when the sons take one more than the other in sequence until impossible to continue the pattern, there are 196 left, which gives us the equation

n=\left( 1+2+3+\cdots+m\right) + 196,\text{ or}

n=\left(\sum_{k=1}^{m}{k}\right) +196= \frac{m(m+1)}{2} + 196 = \frac{1}{2}m^2+\frac{1}{2}m+196,

where m represents the number of turns they go back and forth until they can no longer continue the pattern. This also implies that m\ge 196 since if they took fewer turns than that and still had 196 beans left, there would be enough beans to continue the pattern.

Previously we showed that n\equiv 52\pmod{63}, therefore

\frac{1}{2}m^2+\frac{1}{2}m+196\equiv 52\pmod{63}

\frac{1}{2}m^2+\frac{1}{2}m\equiv 45\pmod{63}

m^2+m\equiv 90\equiv 27\pmod{63}.

Here we can rewrite m as 64m since 1\equiv 64\pmod{63}, and we then complete the square. So

m^2+64m+1024\equiv 27+1024\equiv 1051\equiv 43 \pmod{63}

(m+32)^2\equiv 43\pmod{63}.

Now we need to know what numbers when squared leave a remainder of 43 when divided by 63. The quickest way to do this is with a chart. Since 43 is not a perfect square, then we can eliminate every number whose square is less than 63, therefore let's start with 8. The calculations are expedited by use of a table of squares as well as a modulo calculator (there are some free apps for this).


x 8 9 10 11 12 13 14 15 16 17 18 19
x^2\pmod{63} 1 18 37 58 18 43 7 36 4 37 9 46
x 20 21 22 23 24 25 26 27 28 29 30 31 32
x^2\pmod{63} 22 0 43 25 9 58 46 36 28 22 18 16 16

We only have to go half-way to 63 as the remaining will be a mirror reflection of the first half. In other words, if we extended our table further with x=33,34,35,36,\dots, then we would expect x^2\pmod{63}=18,22,28,36,\dots. So it appears that we have two values less than 63/2, and by using the fact just mentioned, we can get the other two values greater than 63/2. So x=13,22,41,50 all give us x^2\equiv 43\pmod{63}. Thus

m+32\equiv 13,22,41,50\pmod{63}

m\equiv 9,18,44,53\pmod{63}.

Now remember that m\ge 196. If we model the above congruences for m as such:

m=9+63a,

m=18+63a,

m=44+63a,\text{ or}

m=53+63a,

for some a\ge0, then we could apply the restriction m\ge 196 to each case to get

m=198+63b,

m=207+63b,

m=233+63b,\text{ or}

m=242+63b,

for some b\ge 0.

We have a formula for n (number of beans the boys inherited) in terms of m (n=\frac{1}{2}m^2+\frac{1}{2}m+196) and we have all the values for m, then we can calculate all possible values less than 30{,}000 (the clue I said we would come back to!). The first four values of m provide us all n<30{,}000:

m n=\frac{1}{2}m^2+\frac{1}{2}m+196
198 19{,}897
207 21{,}724
233 27{,}457
242 29{,}599

The last clue which will narrow the answer down to one is that there is only one way to form a rectangle out of the beans, which means that (1) n is not prime (otherwise it couldn't be formed into a rectangle of more than one row), and (2) there is only one unique factorization for n other than 1\cdot n. Using an app for prime factorization, the following can be deduced very quickly:

n=19{,}897=101\cdot 197,

n=21{,}724=2^2\cdot 5{,}431,

n=27{,}457 \text{ is prime, and}

n=29{,}599 \text{ is prime.}

So our only non-prime n with one unique factorization is n=19{,}897=101\cdot 197 and we have our solution!