Can You Shape the Peloton?

A peloton of cyclists rides in rows. Its shape can be a triangle, a rhombus, or something in between: rows of $1, 2, 3, \dots$ riders widening to a widest row, then narrowing again by one rider per row, but stopping anywhere from straight after the widest row (a triangle) to a final single rider (a rhombus). With a widest row of four riders there are four such formations, shown below.

Some numbers of riders allow more than one formation. With $15$ riders there are two: a triangle five riders wide, and a rhombus four riders wide missing its bottom rider. After $15$, what is the next number of riders with two distinct formations?

The Fiddler, Zach Wissner-Gross, September 22, 2023(original post)

The official solution appeared in the post of September 29, 2023 and gives $36$ for the main puzzle and $141$ for the Extra Credit. Both agree with the answers below.

Solution

First, count the riders in a formation. Write $a$ for the width of the widest row. A full rhombus has rows $1, 2, \dots, a, \dots, 2, 1$, and it holds $a^2$ riders: it is a square of side $a$ squashed sideways, and indeed $a + 2(1 + 2 + \dots + (a - 1)) = a + a(a - 1) = a^2$. Every other formation is this rhombus with its bottom rows removed, and the removed rows, $b, b - 1, \dots, 1$, form a triangle holding the triangular number $T_b = 1 + 2 + \dots + b = \tfrac12 b(b + 1)$. So a formation has $$N \;=\; a^2 - T_b \text{ riders}, \qquad 0 \le b \le a - 1 ,$$ with $b = 0$ the rhombus and $b = a - 1$ the triangle, which holds $T_a$ riders.

So the formations with a widest row of $a$ give the numbers from $T_a$ up to $a^2$, spaced by triangular numbers below $a^2$. Listing them row by row:

This table is complete for every count up to $36$, because a formation with widest row $a$ has at least $T_a$ riders, and $T_9 = 45$. So the formations for any number up to $36$ all appear above. Reading the counts above $15$ in order, $16, 19, 21, 22, 24, 25, 26, 28, 30, 33, 34, 35$ each appear once, and the next count, $36$, appears twice: as the triangle eight wide and as the rhombus six wide. $$\boxed{\ 36 \text{ riders}. \ }$$ That $36$ is both a square and a triangular number is exactly what makes it work here. The next two counts with two formations, $43$ and $49$, are visible in the table too.

The computation

The program builds every formation up to a widest row of $30$ riders, row by row exactly as described in the puzzle, counts its riders, and groups the formations by count. A formation with widest row $a$ has at least $1 + 2 + \dots + a$ riders, so every count up to $1 + 2 + \dots + 30 = 465$ has all its formations in the list, and the search only looks there.

from collections import defaultdict

W = 30                 # widest formation built
shapes = defaultdict(list)
for a in range(1, W + 1):          # widest row
    for b in range(a):             # bottom rows removed
        rows = [*range(1, a + 1), *range(a - 1, b, -1)]
        shapes[sum(rows)].append(rows)

# Every formation has at least 1+2+...+a riders, so any count
# up to 1+2+...+W is covered by widths at most W: complete.
limit = W * (W + 1) // 2
def smallest(k, above=0):
    return min(n for n, f in shapes.items()
               if above < n <= limit and len(f) >= k)

print("main:", smallest(2, above=15))

It prints

main: 36

Extra Credit

What is the fewest number of riders with three distinct formations?

Solution

Turn the formula around. A count $N$ has a formation with widest row $a$ exactly when $a^2 - N$ is a triangular number $T_b$ with $b \le a - 1$, and that last condition holds exactly when $N \ge T_a$. So to list the formations of $N$, run through the squares $a^2$ from the first one at least $N$, stop when $T_a$ passes $N$, and keep each $a$ for which the gap $a^2 - N$ is triangular.

For $N = 141$ the candidates are $a = 12$ to $16$, since $12^2 = 144$ is the first square past $141$ and $T_{17} = 153$ is too big:

So $141$ has three formations, none of them a triangle or a rhombus.

That no smaller count has three is a matter of checking each count below $141$ the same way, and there is no shortcut that avoids it: the counts with two formations are scattered irregularly ($15, 36, 43, 49, 64, 66, 78, \dots$). The exhaustive check is the computation below. Its verdict is $$\boxed{\ 141 \text{ riders}. \ }$$

The computation

The list of formations from The computation above already settles it: ask for the smallest count with at least three formations, and print their widest and last rows.

n = smallest(3)
print("extra credit:", n)
for rows in shapes[n]:
    print(f"  widest row {max(rows)}, last row {rows[-1]}")

It prints

extra credit: 141
  widest row 12, last row 3
  widest row 13, last row 8
  widest row 14, last row 11