# Problem of the Week Problem E and Solution Let’s All Ride a Bike

## Problem

Let’s All Ride a Bike

Grayson’s Groupcycles rents bikes with multiple seats for large groups of people. They rent $$7$$-seater, $$13$$-seater, and $$25$$-seater bikes. A group of $$14$$ people could fit on two $$7$$-seater bikes, however a group of $$15$$ people could not fit exactly on any of the bikes since no combination of bikes have exactly $$15$$ seats.

What is the largest group size that cannot fit exactly on any combination of bikes from Grayson’s Groupcycles?

## Solution

Any group size that is a multiple of $$7$$ can fit on multiple $$7$$-seater bikes. Similarly, any group size that is a multiple of $$13$$ can fit on multiple $$13$$-seater bikes, and any group size that is a multiple of $$25$$ can fit on multiple $$25$$-seater bikes. These multiples are listed below.

• multiples of $$7$$: $$7,~14,~21,~28,~35,~42,~49,~\ldots$$

• multiples of $$13$$: $$13,~26,~39,~52,~\ldots$$

• multiples of $$25$$: $$25,~50,~75,~\ldots$$

Putting these numbers together, along with sums of the different multiples, gives us the following list of group sizes that can fit exactly on some combination of bikes from Grayson’s Groupcycles.

$$7$$, $$13$$, $$14$$, $$20\ (=7+13)$$, $$21$$, $$25$$, $$26$$, $$27\ (=14+13)$$, $$28$$, $$32\ (=7+25)$$, $$33\ (=7+26)$$, $$34\ (=21+13)$$, $$35$$, $$38\ (=13+25)$$, $$39$$, $$40\ (=14+26)$$, $$41\ (=28+13)$$, $$42$$, $$45\ (=7+13+25)$$, $$46\ (=21+25)$$, $$47\ (=21+26)$$, $$48\ (=35+13)$$, $$49$$, $$50$$, $$51\ (=26+25)$$

The missing numbers from the above list correspond to the group sizes that cannot fit exactly on any combination of bikes. The largest of these group sizes appears to be $$44$$, however we must justify that this is the maximum group size that cannot fit exactly on any combination of bikes. To do this, we note that group sizes of $$45,~46,~47,~48,~49,~50,$$ and $$51$$ can all fit exactly on some combination of bikes. This corresponds to $$7$$ consecutive group sizes. If we add $$7$$ to each of these group sizes, the additional $$7$$ people could fit on a $$7$$-seater bike. It follows that group sizes of $$52,~53,~54,~55,~56,~57,$$ and $$58$$ can also fit exactly on some combination of bikes. In this way, we can continue to add $$7$$ to each of these group sizes to obtain the next set of $$7$$ consecutive group sizes and determine that they can also fit exactly on some combination of bikes. It follows that every group size of $$45$$ or more can fit exactly on some combination of bikes.

Thus, the largest group size that cannot fit exactly on any combination of bikes from Grayson’s Groupcycles is $$44$$.

Extension: It turns out there are only $$26$$ group sizes that cannot fit exactly on any combination of bikes. If Grayson’s Groupcycles added a $$3$$-seater bike, how many group sizes wouldn’t be able to fit exactly on any combination of bikes?