YouTip

# C Programming Exercise - Example 80: The Monkey and the Peaches Problem In this tutorial, we will explore a classic mathematical puzzle known as the **"Monkey and the Peaches"** problem. We will analyze the problem, design an algorithm to solve it, and implement the solution in C. --- ## 1. Problem Description There is a pile of peaches on a beach, and five monkeys plan to divide them. 1. **The first monkey** arrives, divides the pile into five equal parts, and finds there is **one extra peach**. The monkey throws the extra peach into the sea, takes its one-fifth share, and leaves. 2. **The second monkey** arrives, divides the remaining peaches into five equal parts, and also finds **one extra peach**. It throws the extra peach into the sea, takes its one-fifth share, and leaves. 3. **The third, fourth, and fifth monkeys** arrive one after another and perform the exact same operation (dividing the remaining peaches into five parts, throwing away the one extra peach, and taking one share). **Question:** What is the minimum number of peaches that must have been in the pile initially? --- ## 2. Mathematical Analysis Let $S_i$ be the number of peaches before the $i$-th monkey performs their operation, where $i \in \{1, 2, 3, 4, 5\}$. * $S_1$ is the initial number of peaches. * For each monkey $i$, the division is valid only if: $$(S_i - 1) \pmod 5 == 0$$ * After monkey $i$ throws away $1$ peach and takes $\frac{1}{5}$ of the remaining, the number of peaches left for the next monkey ($S_{i+1}$) is: $$S_{i+1} = \frac{4}{5}(S_i - 1)$$ We need to find the smallest positive integer $S_1$ such that this division process can be successfully repeated $5$ times. --- ## 3. C Implementation We can solve this problem using a brute-force search. We start testing from $1$ peach and increment the count until we find a starting number that successfully satisfies the division condition for all $5$ monkeys. ### Source Code ```c #include int main() { int n = 0; // n represents the initial number of peaches int i, count; int found = 0; while (!found) { n += 1; // Try the next possible initial number of peaches count = n; for (i = 0; i < 5; i++) { // Check if the current pile can be divided into 5 parts with 1 left over if ((count - 1) % 5 == 0) { // Calculate the remaining peaches after the monkey takes its share count = (count - 1) / 5 * 4; } else { // If the condition fails at any step, break and try the next 'n' break; } } // If the loop successfully ran 5 times, we found our answer if (i == 5) { found = 1; } } printf("The minimum number of peaches initially is: %d\n", n); return 0; } ``` --- ## 4. Execution and Output When you compile and run the program, it will output the following result: ```text The minimum number of peaches initially is: 3121 ``` --- ## 5. Code Explanation & Considerations ### How the Algorithm Works 1. **Outer Loop (`while (!found)`)**: This loop increments the candidate initial peach count `n` by 1 in each iteration. 2. **Inner Loop (`for (i = 0; i < 5; i++)`)**: This simulates the process for each of the 5 monkeys. * `(count - 1) % 5 == 0` ensures that after throwing away one peach, the remaining pile is perfectly divisible by 5. * `count = (count - 1) / 5 * 4` updates the pile size to represent the remaining $\frac{4}{5}$ of the peaches. 3. **Termination Condition**: If the inner loop completes all 5 iterations (`i == 5`), it means the starting number `n` successfully satisfied the condition for all 5 monkeys. The program sets `found = 1` to terminate the search and prints the result. ### Optimization & Mathematical Insight While brute-force is simple and fast enough for 5 monkeys, this problem can also be solved mathematically using modular arithmetic. The general formula for $m$ monkeys is: $$\text{Minimum Peaches} = a \cdot m^m - (m - 1)$$ Where $a$ is the smallest positive integer that makes the result positive. For $m = 5$ monkeys: $$\text{Minimum Peaches} = 1 \cdot 5^5 - (5 - 1) = 3125 - 4 = 3121$$ This mathematical shortcut confirms that our program's output of **3121** is absolutely correct!