Question 1 of 8: Programming

Question 1: Programming

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.

(a) Floyd's triangle

Approach. A single running counter is printed across the whole triangle; row k consumes exactly k values of that counter before starting a new line.

void floyd_triangle(int n) {
    int counter = 1;
    for (int row = 1; row <= n; row++) {
        for (int col = 1; col <= row; col++) {
            printf("%d ", counter);
            counter++;
        }
        printf("\n");
    }
}

int main(void) {
    int n;
    printf("Enter number of rows: ");
    scanf("%d", &n);
    floyd_triangle(n);
    return 0;
}

For n = 5 the counter runs 1..15 and the inner loop lengths are 1,2,3,4,5, reproducing exactly the triangle shown on the question paper (row 1: 1; row 2: 2 3; …; row 5: 11 12 13 14 15). The total value printed on the last row is always $n(n+1)/2$, since that is how many integers have been consumed after $n$ full rows.

(b) The gold-bar puzzle

Given. Three secret three-way divisions (each: split the current stash into 3 equal piles, one bar left over, the divider hides one pile plus the extra bar and leaves the other two piles behind), followed by a fourth, final three-way division that also leaves exactly one bar over. Loot size $N \le 500$ bars. Find. Every possible value of $N$.

Approach. Write a subprogram feasible(n) that simulates the three secret divisions and then checks the final division, returning true only if every stage divides evenly with remainder 1; call it for every $n$ from 1 to 500 (brute force is fine — the search space is tiny).

/* Returns 1 if a stash of n bars is consistent with the puzzle, else 0. */
int feasible(int n) {
    for (int round = 0; round < 3; round++) {
        if ((n - 1) % 3 != 0) return 0;    /* must leave exactly 1 over */
        int pile = (n - 1) / 3;
        n = 2 * pile;                      /* two piles left behind */
    }
    return (n - 1) % 3 == 0;               /* final morning division */
}

int main(void) {
    for (int n = 1; n <= 500; n++)
        if (feasible(n)) printf("%d\n", n);
    return 0;
}

1. Trace the smallest hit, N = 79. Bandit 1: $79 = 3(26)+1$, buries $26+1=27$, leaves $2(26)=52$. Bandit 2: $52 = 3(17)+1$, buries $17+1=18$, leaves $2(17)=34$. Bandit 3: $34 = 3(11)+1$, buries $11+1=12$, leaves $2(11)=22$. Morning: $22 = 3(7)+1$ — each gets 7, one bar left to fight over. Every stage lands on remainder 1, so $N=79$ is feasible.
2. Sweep n = 1..500. Running feasible(n) across the full range finds exactly six hits, spaced 81 apart (three secret halvings-by-two-thirds compound into a period of $3^4=81$ once the recursion is unrolled algebraically): $$\boxed{N \in \{79,\,160,\,241,\,322,\,403,\,484\}}.$$