Reverse Chicken McNugget Theorem

Computer Science Level 2

For non-negative integers $a$ and $b$ , Let $T_i$ denote the $i^{\text{th}}$ largest positive integer such that there's no solution to $11a + 12b = T_i$ .

What is the value of $T_1 + T_2 + T_3 + T_4 + T_5 + T_6 + T_7 + T_8 + T_9 + T_{10}$ ?

Details and assumptions:

This is a Computer Science problem, but you're welcome to try to solve it with mathematics alone.

The answer is 860.

1 solution

Hasmik Garyaka
Sep 20, 2017

Numbers are 1 2 3 4 5 6 7 8 9 10 13 14 15 16 17 18 19 20 21 25 26 27 28 29 30 31 32 37 38 39 40 41 42 43 49 50 51 52 53 54 61 62 63 64 65 73+74+75+76+85+86+87+97+98+109

How did you get these numbers?

Pi Han Goh - 3 years, 8 months ago

All numbers except 11 12 22 23 24 and so on. 11n ...12... excluded for each n.

Hasmik Garyaka - 3 years, 8 months ago

How do you know this is true? How do you know you have accounted for every single integer?

Pi Han Goh - 3 years, 8 months ago

11 and 12 are relative primes, 11n+12m=1 has solution n=11 m=-10 so we can solve for any T, but for some numbers a and b will be negative. For large positives a and be will be also positive.

Hasmik Garyaka - 3 years, 8 months ago

Every time exclude one more number and at the end we can get any number >=110

Hasmik Garyaka - 3 years, 8 months ago

Exclude one more number from what?

Pi Han Goh - 3 years, 8 months ago

From all natural numbers

Hasmik Garyaka - 3 years, 8 months ago

Reverse Chicken McNugget Theorem

The answer is 860.

1 solution

0 pending reports