Tag Archives: arithmetic

Three people and a monkey

Personally, I’ve always thought of educated Trial-and-Error as a valid problem-solving technique, or at least a problem-insight technique.  The challenge with this approach is the difficulty of trial-and-error to distinguish between situations with multiple solutions and those with only one.  I take every opportunity to remind my students of the dual goals of every problem solution:

  1. Show that your solution(s) is (are) correct, and
  2. Show that no other solution(s) exist(s).

Following is a variation of a fun problem from a member of the CPAM list-serve.

PARENTS:  This problem has been around for centuries in many different forms and more importantly, is a great problem-solving opportunity for elementary and middle school children.  Change the roles, genders, and animal to make the problem interesting for your children/students.

Three people and their pet monkey spend a day gathering bananas and go to sleep.  During the night, one wakes up, splits the bananas into three equal piles with one banana left over.  She gives the extra banana to the monkey, hides one pile for herself, combines the other two piles and goes back to sleep.
A little later, another person wakes and splits the remaining pile of bananas into three equal piles with one left over.  She gives the extra to the monkey, hides one pile for herself, combines the other two piles and goes back to sleep.
The third person wakes later and repeats the process.
In the morning, the remaining pile is divided evenly among the three peo
ple with nothing left for the monkey. 

What is the smallest number of bananas that could have been in the original pile?

Don’t read any further if you want to solve this problem for yourself.

Because the problem asks for the smallest size of the original pile, there is only one answer and the fundamental weakness of a trial-and-error solution has been eliminated.

The recent CPAM post asked:  “Please help me to solve the attached problem in the way I could explain it to grade 6-7 students. I came up with very complicated equations. Is there any other method to solve it?”

From experience, I knew that I could approach this with lots of equations involving fractions, but I could instantly hear the groans of so many middle school students if this approach was the first attempted.  That’s when I tried another great problem-solving approach:  Work Backwards!

Because the problem wanted the smallest possible pile, I wondered if there could have been 1 banana each in the divided piles the next morning.  If so, there would have been 3 bananas in the re-combined pile, an impossible situation when you remember that this pile was the result of combining the two piles that remained after the third person had split the piles and hid her “share.”

Because the sum of three odd numbers is always odd, the evenly divided piles the next morning must have an even number of bananas each to avoid the impossible situation from that of the paragraph above.

So what if there were 2 bananas each in the divided piles the next morning?

  • That would give 6 bananas in the re-combined pile after the 3rd person went back to sleep.
  • The 6 bananas would have been in piles of 3 & 3 after the 3rd person’s pile of 3 was hidden and the monkey had 1, giving 10 (3+3+3+1) bananas in the re-combined pile after the 2nd person went back to sleep.
  • Those 10 bananas would have been in piles of 5 & 5 after the 2nd person’s pile of 5 was hidden and the monkey had 1, giving 16 (5+5+5+1) bananas in the re-combined pile after the 1st person went back to sleep.
  • Those 16 bananas would have been in piles of 8 & 8 after the 1st person’s pile of 8 was hidden and the monkey had 1, giving 25 (8+8+8+1) bananas in the original pile.

The answer must be 25. 

GENERALIZATION:  The original problem suggests that there are lots of solutions, so algebra may be the best way from here.  The approach learned from the trial-and-error approach can guide the global solution.

  • If there are x bananas in each final pile the next morning, then there were 3x after the 3rd went to sleep.
  • That means there were \frac{3x}{2} in each of the 3rd person’s piles for a total of 3*\frac{3x}{2}+1=\frac{9x+2}{2} bananas after the 2nd went to sleep.
  • So there were \frac{(9x+2)/2}{2}=\frac{9x+2}{4} in each of the 2nd person’s piles for a total of 3*\frac{9x+2}{4}+1=\frac{27x+10}{4} bananas after the 1st went to sleep.
  • Finally, there were \frac{(27x+10)/4}{2}=\frac{27x+10}{8} in each of the 1st person’s piles for a total of 3*\frac{27x+10}{8}+1=\frac{81x+38}{8} original bananas.

Notice that x=2 gives \frac{81*2+38}{8}=\frac{200}{8}=25, confirming the trial-and-error solution from earlier.

CONCLUSIONS:

  • Because the answer is an integer, 81x+38 must be a multiple of 8 which can only happen for even values of x, confirming the earlier hypothesis.
  • 81x+38=(80x+32)+(x+6)=8(10x+4)+(x+6), therefore the only solutions, x, to this problem are those which make x+6 a multiple of 8.  The smallest positive value for which this is true is x=2, again confirming the trial-and-error solution.  All such final pile values of x form an arithmetic sequence:  2, 10, 18, 26, ...  which correspond to initial piles of size 25, 106, 187, 268, ....

In my opinion, the initial trial-and-error solution is attainable by any elementary school student who knows how to add, but the logic to get there might need to be scaffolded for younger students.  The arithmetic behind the generalization can be expected of middle school students, but the inclusion of a variable on top of the trial-and-error procedure would push it out of reach of most students who haven’t had a pre-algebra course.  There are many high school students who eventually could understand the factoring arguments in the conclusion, but that logic, again, seems to be absent from most curricula.

This is a good problem that can be approached again and again by students as their mathematical sophistication matures.  I’d love to hear how others tackle it or specific results of student attempts.

Area 10 Squares – Proof & Additional Musings

Additional musings on the problem of Area 10 Squares:

Thanks, again to Dave Gale‘s inspirations and comments on my initial post. For some initial clarifications, what I was asking in Question 3 was whether these square areas ultimately can all be found after a certain undetermined point, thereby creating a largest area that could not be drawn on a square grid. I’m now convinced that the answer to this is a resounding NO–there is no area after which all integral square areas can be constructed using square grid paper. This is because there is no largest un-constructable area (proof below). This opens a new question.

Question 4:
Is there some type of 2-dimensional grid paper which does allow the construction of all square areas?

The 3-dimensional version of this question has been asked previously, and this year in the College Math Journal, Rick Parris of Exeter has “proved that if a cube has all of its vertices in then the edge length is an integer.”

Dave’s proposition above about determining whether an area 112 (or any other) can be made is very interesting. (BTW, 112 cannot be made.) I don’t have any thoughts at present about how to approach the feasibility of a random area. As a result of my searches, I still suspect (but haven’t proven) that non-perfect square multiples of 3 that aren’t multiples of pre-existing squares seem to be completely absent. This feels like a number theory question … not my area of expertise.

Whether or not you decide to read the following proof for why there are an infinite number of impossible-to-draw square areas using square grids, I think one more very interesting question is now raised.

Question 5:
Like the prime numbers, there is an infinite number of impossible-to-draw square areas. Is there a pattern to these impossible areas? (Remember that the pattern of the primes is one of the great unanswered questions in all of mathematics.)

THE PROOF
My proof does not feel the most elegant to me. But I do like how it proves the infinite nature of these numbers without ever looking at the numbers themselves. It works by showing that there are far more integers than there are ways to arrange them on a square grid, basically establishing that there is simply not enough room for all of the integers forcing some to be impossible. I don’t know the formal mathematics name for this principle, but I think of it as a reverse Pigeonhole Principle. Rather than having more pigeons than holes (guaranteeing duplication), in this case, the number of holes (numbers available to be found) grows faster than the number of pigeons (the areas of squares that can actually be determined on a square grid), guaranteeing that there will always be open holes (areas of squares that cannot be determined on using a square grid).

This exploration and proof far exceeds most (all?) textbooks, but the individual steps require nothing more than the ability to write an equation for an exponential function and find the sum a finite arithmetic sequence. The mathematics used here is clearly within the realm of what high school students CAN do. So will we allow them to explore, discover, and prove mathematics outside our formal curricula? I’m not saying that students should do THIS problem (although they should be encouraged in this direction if interested), but they must be encouraged to do something real to them.

Now on to a proof for why there must be an infinite number of impossible-to-draw square areas on a square grid.

This chart shows all possible areas that can be formed on a square grid. The level 0 squares are the horizontal squares discussed earlier. It is lower left-upper right symmetric (as noted on Dave’s ‘blog), so only the upper triangle is shown.

From this, the following can be counted.
Level 1 – Areas 1-9: 6 of 9 possibilities found (yellow)
Level 2 – Areas 10-99: 40 of 90 possibilities found (orange)
Level 3 – Areas 100-999: 342 of 900 possibilities found (blue)

The percentage of possible numbers appears to be declining and is always less than the possible number of areas. But a scant handful of data points does not always definitively describe a pattern.

Determining the total number of possible areas:
Level 1 has 9 single-digit areas. Level 2 has 90 two-digit areas, and Level 3 has 900 three-digit areas. By this pattern, Level M has M-digit areas. This is the number of holes that need to be filled by the squares we can find on the square grid.

Determining an upper bound for the number of areas that can be accommodated on a square grid:
Notice that if a horizontally-oriented square has area of Level M, then every tilted square in its column has area AT LEAST of Level M. Also, the last column that contains any Level M areas is column where floor is the floor function.

In the chart, Column 1 contains 2 areas, and every Column N contains exactly (N+1) areas. The total number of areas represented for Columns 1 through N is an arithmetic sequence, so an upper bound for the number of distinct square areas represented in Columns 1 to N (assuming no duplication, which of course there is) is .

The last column that contains any Level M areas has column number . Assuming all of the entries in the data chart up to column are Level M (another overestimate if is not an integer), then there are

maximum area values to fill the Level M area holes. This is an extreme over-estimate as it ignores the fact that this chart also contains all square areas from Level 1 through Level (M-1), and it also contains a few squares which can be determined multiple ways (e.g., area 25 squares).

Conclusion:
Both of these are dominated by base-10 exponential functions, but the number of areas to be found has a coefficient of 9 and the number of squares that can be found has coefficient 1/2. Further, the number of squares that can be found is decreased by an exponential function of base , accounting in part for the decreasing percentage of found areas noted in the data chart. That is, the number of possible areas grows faster than the number of areas that actually can be created on square grid paper.

While this proof does not say WHICH areas are possible (a great source for further questions and investigation!), it does show that the number of areas of squares impossible to find using a square grid grows without bound. Therefore, there is no largest area possible.