Half Linearly Expressible

let k(x,y) be the numbers between 1 and 60 that can be expressed as ax + by.
if x and y are not coprime, then any numbers not a multiple of gcd(x,y) cannot possibly be expressed. hence $k(x,y) \leq \frac{60}{gcd(x,y)}$ . Since 60/2 = 30, so as long as either x or y is 2, and the other number is either a multiple of 2 or 61 and above, all the even numbers between 1 and 60 can be expressed; 30 numbers. This gives us (2,2), (2,4)... (2,60), (2,61)...(2,100), 70 solutions. But since (x,y) is an ordered pair, we have 69 more solutions of (4,2)...(60,2), etc. This gives us a total of 139 solutions. There are no other solutions with $\gcd(x,y) \geq 2$ .

If x and y are coprime, then assume without loss of generality that x < y. then $k(x,y) = \left \lfloor \frac{60}{x} \right \rfloor + \sum_{i=1}^{\left \lfloor \frac{60}{y} \right \rfloor} (\left \lfloor \frac{60 - iy}{x} \right \rfloor + 1)$ . Also note that $k(x, (y+1)) \leq k(x,y)$ , with equality possible only if $\left \lfloor \frac{y}{x} \right \rfloor = \left \lfloor \frac{y+1}{x} \right \rfloor$ . [Note: This equation, and inequality, is key to finding the actual sets - Calvin]

From here on, it's trying out different ordered pairs of (x,y) knowing fully that with each value of x, very few values of y can satisfy the conditions.

k(3,61) = 20. We need 10 more numbers; easily achieved with the set (31, 34, 37... 58) or (32, 35... 59). So four more possible ordered pairs are found: (3,31), (3,32), (31,3), (32,3). Moving further, we find (4,21), (5,16), (6,13), (7,11). After this, k(8,9) = 32 and using the facts that $k(x, (y+1)) \leq k(x,y)$ and gcd(x,y) = 1, there are no more possible solutions. This gives us a total of 139 + 4 + 2 + 2 +2 + 2 = 151 ordered pairs.

Suppose $x,y$ (WLOG $x \le y$ ) with $x \ge 9$ . Then note that the only numbers expressible as $ax + by$ under $60$ have $a+b \le 6$ . But then it is easy to show at most $28$ numbers are expressible. Thus it follows if $x,y$ works the minimum of the two must be at most $8$ .

Now we do casework on $\min(x,y)\ = x$ . Obviously $x \neq 1$ . Clearly if $x=2$ , then the pair works iff $y$ is even and $y \le 60$ or $y \ge 61$ .

Observe that $\gcd(x,y) = 1,2$ because it is clear that at most $\displaystyle \left \lfloor \frac{60}{\gcd(x,y)} \right \rfloor$ integers are expressible. The rest of this solution will assume this without mention. For the rest of this solution if we say a set of numbers are the only expressible ones, it means all expressible numbers under $60$ are a subset of the given set.

If $x = 3$ , note that $y > 30$ as otherwise $3,6,...,60, y, y+3, y+6,...,y+30$ are $31$ distinct expressible numbers (remember that $3 \nmid y$ ). It is easy to check $31,32$ work and that all integers above $32$ fail due to $3,6,...,60, y,y+3,...,y+3k$ for some $k < 9$ being the only expressible integers.

If $x = 4$ then we need $y > 20$ as otherwise $4,8,...,60, y+4,..., y + 40, 2y, ..., 2y + 20, 3y$ are expressible (this fails for $y$ even due to them not being distinct, but then just note that $y$ even and this working forces $2$ to be expressible so $y=2$ , contradicting $y \ge x$ ). One can check $y = 21$ works and for $y \ge 23$ it fails because the expressible integers are only $4,8,...,60, y+4,..., y + 4k_1, 2y, ..., 2y + 4k_2$ for some $k_1 \le 9, k_2 \le 3$ and that for $y = 22$ it fails due to it being even.

If $x = 5$ then $y > 15$ as otherwise $5,...,60, y,...,y+45, 2y,...,2y+30, 3y, ..., 3y+15, 4y$ . Clearly $y = 16$ works. If $y > 16$ then the only expressible integers are $5,...,60, y,..., y + 40, 2y,...., 2y + 25, 3y, 3y + 5$ which has less than $30$ elements.

If $x = 6$ then clearly $y$ is odd by arguments made earlier. We see that $y > 12$ as otherwise $6,...,60, y,...,y + 48, 2y,..., 2y + 36, 3y,..., 3y + 24, 4y,..., 4y + 12, 5y$ are expressible. It is obvious $y=13$ works and then for $y > 13$ only $6,...,60, y,...,y + 42, 2y,..., 2y + 30, 3y,..., 3y + 18, 4y$ which only has $29 < 30$ elements.

If $x = 7$ then we see that $y > 10$ as otherwise $7,...,56, y,...,y + 49, 2y,..., 2y + 35, 3y,..., 3y + 28, 4y,..., 4y + 14, 5y, 5y + 7, 6y$ are expressible. It is obvious $y=11$ works and then for $y > 11$ only $7,...,56, y,...,y + 42, 2y,..., 2y + 35, 3y,..., 3y + 21, 4y, 4y + 7, 5y$ which only has $28 < 30$ elements.

If $x = 8$ then $y$ must be odd. It is easy to check $y = 9$ fails so $y \ge 11$ . But then only $8,...,56, y,..., y + 48, 2y,..., 2y+32, 3y, ..., 3y + 24, 4y, ..., 4y + 16, 5y$ are expressible which has $27 < 30$ elements. Thus there are no solutions when $x = 8$ .

Summarizing our work, we have found $6 \cdot 2 = 12$ solutions when the minimum is not $2$ . When the minimum is $2$ clearly there are $30 \cdot 2 - 1 + 2 \cdot 40 = 139$ solutions. Therefore there are $12 + 139 = 151$ total solutions and thus we are done.

If $x$ and $y$ are not relatively prime, $(2,2k)$ and $(2k,2)$ will work for $1 \leq k \leq 50$ . This gives $99$ pairs. If $x$ and $y$ are not relatively prime, then let $g = \gcd(x,y)$ . If $g = 2$ and neither $x$ , nor $y$ is equal to $2$ , then we can get at most $29$ number between 1 and 60, since we can only get even numbers, and we cannot get $2$ . If $g > 2$ then we get at most $\frac{60}{g} < 30$ possible numbers. Henceforth we may assume that $g = 1$ .

By the Chicken McNugget Theorem, if $x,y \leq 9$ then there are fewer than 30 numbers that cannot be expressed. If $x,y \geq 9$ , then any number less than or equal to 60 that can be expressed as $ax + by$ has $a + b \leq 6$ . When $a + b = k$ , there are at most $k+1$ different sums less than or equal to 80 that we can get. Combining these two facts, we have that there are at most $2 + 3 + 4 + 5 + 6 + 7 = 27$ different numbers less than 60 that can be expressed this way.

Thus, we may conclude that $x \leq 8$ and $y \geq 10$ or vice versa. $x = 1$ yields no solutions since all numbers are expressible. $x = 2$ gives us 30 expressible numbers of the form $ax$ . So as long as $y \geq 61$ , $(2,y)$ will have 30 expressible numbers. This gives 20 additional solutions.

This leaves $x = 3,4,5,6,7,8$ to consider. Notice that if $p \leq x, q \leq y$ and $\gcd(p,q) = \gcd(x,y) = 1$ then the number of non-expressible numbers less than 60 of the form $ax + by$ is greater than or equal to the number non-expressible numbers less than 60 of the form $ap + aq$ . By the Chicken McNugget Theorem, we must have $(x-1)(y-1) \geq 60$ . When $(x-1)(y-1) = 60$ then all 30 non-expressible numbers are less than 60, and so the pair will work.

When $x = 3$ , we must have $y \geq 31$ . We see that $y = 31$ will work since $2 \times 30 = 60$ . $y = 32$ also gives 30 expressible numbers. $y=34$ gives only 29 expressible numbers, so $31$ and $32$ are the only $y$ values which work.

When $x = 4$ , $y = 21$ will work, since $3 \times 20 = 60$ . $y = 23$ does not work, and so nothing larger than $y = 21$ will.

When $x = 5$ , $y = 16$ will work, since $4 \times 15 = 60$ . $y = 17$ does not work and so nothing larger than $y = 16$ will.

When $x = 6$ , $y = 13$ will work, since $5 \times 12 = 60$ . $y = 17$ does not work and so nothing larger than $y = 13$ will.

When $x = 7$ , $y = 11$ will work, since $6 \times 10 = 60$ . $y = 12$ does not work and so nothing larger than $y = 11$ will.

When $x = 8$ , there is no $y$ such that $7(y-1) = 60$ . The smallest $y\geq 10$ that is coprime with $8$ is $y = 11$ . For any pair $(a,b)$ such that $8a + 11b \leq 60$ , the pair $7a + 11b \leq 60$ . We know there are exactly 30 pairs that make $7a + 11b \leq 60$ , however the pair $(8,0)$ will not work for $8a + 11b \leq 60$ , so there are no solutions when $x = 8$ .

This has given us 26 solutions when $x$ and $y$ are relatively prime, $x \leq 8$ and $y \geq 10$ : $(3,31),(3,32),(4,21),(5,16),(6,13),(7,11)$ and the 20 solutions of the form $(2,2k+1)$ . When $x \geq 10$ and $y \leq 8$ we get the same number of solutions. Thus, in total we have $99 + 52 = 151$ ordered pairs.