Question 1 of 9: Programming — Floyd's Triangle and the Three-Way Gold-Bar Division

Question 1: Programming — Floyd's Triangle and the Three-Way Gold-Bar Division (20 marks: (a) 10, (b) 10)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) The number of rows $n$; row $i$ (1-indexed) holds $i$ consecutive integers continuing a single running count that starts at 1. (b) Three successive thieves each split the CURRENT pile into three equal shares with exactly one bar left over, take one share plus the extra bar, and leave the other two shares (i.e. $2\lfloor \text{pile}/3\rfloor$ bars) for the next thief; the final three-way split next morning also leaves exactly one bar over. Loot $\le 500$ bars.

Find. (a) A program printing the first $n$ rows of Floyd's triangle. (b) Every possible size of the original loot, found via a subprogram that tests whether a candidate count of bars is consistent with all four divisions described.

Approach. (a) Keep one running counter that never resets between rows; row $i$ simply consumes the next $i$ values of that counter. (b) Write is_possible(n) to replay the three thieves' divisions in sequence, each requiring $n_k \bmod 3 = 1$ and reducing the pile to $2\lfloor n_k/3\rfloor$, then require the same remainder condition on the resulting pile the next morning; scan every $n$ from 1 to 500 and report the ones that pass.

(a) Floyd's triangle (10 marks)

1. Design the running-counter loop. A naive per-row restart would need to know how many integers precede row $i$ ($\binom{i}{2}=i(i-1)/2$); simpler and exactly what the problem's "successive lines start with the next integer" wording describes is a single counter $k=1$ that is never reset, printed $i$ times per row $i$ then advanced.
2. Write the program.

   #include <stdio.h>
   
   int main(void)
   {
       int n, i, j, k = 1;
   
       printf("Enter number of rows: ");
       scanf("%d", &n);
   
       for (i = 1; i <= n; i++) {
           for (j = 1; j <= i; j++) {
               printf("%d", k++);
               if (j < i) printf(" ");
           }
           printf("\n");
       }
       return 0;
   }
   

3. Confirm against the worked example. For $n=5$ the counter emits row 1: {1}; row 2: {2,3}; row 3: {4,5,6}; row 4: {7,8,9,10}; row 5: {11,12,13,14,15} — the exact triangle printed in the question, and the last value equals $n(n+1)/2 = 15$. $$\boxed{\text{last value for } n=5 \text{ rows}=15}$$

(b) The gold-bar puzzle (10 marks)

1. Translate the story into a divisibility chain. Let $n_0$ be the original loot. Thief 1 requires $n_0 \bmod 3 = 1$ and leaves $n_1 = n_0 - (\lfloor n_0/3\rfloor + 1) = 2\lfloor n_0/3\rfloor$. The same rule applies to thief 2 ($n_1\to n_2$) and thief 3 ($n_2\to n_3$). The morning division then requires $n_3 \bmod 3 = 1$ as well (that division's one leftover bar is what the thieves fight over).
2. Write the subprogram and driver.

   #include <stdio.h>
   
   /* returns 1 if n bars survive all three night-time divisions plus the
      final morning division, each leaving exactly one bar over */
   int is_possible(int n)
   {
       int pile = n, i;
   
       for (i = 0; i < 3; i++) {
           if (pile % 3 != 1) return 0;
           pile = 2 * (pile / 3);        /* two piles left behind for the rest */
       }
       return (pile % 3 == 1);           /* final morning division */
   }
   
   int main(void)
   {
       int n;
   
       printf("Possible original loot sizes (<= 500 bars):\n");
       for (n = 1; n <= 500; n++)
           if (is_possible(n))
               printf("%d\n", n);
       return 0;
   }
   

3. Confirm by brute force and characterise the family. Running the subprogram over $n=1\ldots500$ gives exactly six values: 79, 160, 241, 322, 403, 484 — consecutive terms differ by 81 ($=3^4$, one factor of 3 for each of the four divisions), so the general solution is $n = 79 + 81m$ for integer $m\ge0$. The smallest, 79, is the usual "textbook" answer, but every value up to 500 is a valid original loot size and the program reports all of them. $$\boxed{n \in \{79,\ 160,\ 241,\ 322,\ 403,\ 484\}}$$