# How High Can You Go?

By Stephen Meskin

Let {a1, a2, …, an} be a non-empty set of relatively prime positive integers, for example {3, 8} for n = 2 or {6, 10, 15} for n = 3. Then the question arises: Which positive integers are linear combinations of the a1s with non-­negative coefficients? The answer is not all positive integers are such linear combinations but surprisingly most are.

Using the first example, {3, 8}, the following clearly are not {1, 2, 4, 5, 7, 10} whereas 100 = 4 × 3 + 11 × 8 is. Indeed, every positive integer greater than 100 is. So, there must be a largest positive integer (less than 100) which is not a non-negative linear combination of 3 and 8. The same is true for any non-empty set of relatively prime positive integers, {a1, a2, …, an}; i.e., there is a largest positive integer that is not a non-negative linear combination of {a1, a2, …, an}. That largest positive integer is denoted g0(a1, a2, …, an).

Problem 1. Find g0(3, 8) and prove it is.

Problem 2. Find g0(6, 10, 15) and prove it is.

The expression of 100 as a non-negative linear combination of 3 and 8 is not unique. Indeed 100 = 20 × 3 + 5 × 8 also. Indeed, every positive integer greater than 100 is a non-unique non-negative linear combination of 3 and 8. But there are positive integers which are a unique non-negative linear combination of 3 and 8, for example g0(3, 8) + 2. So, there must be a largest positive integer (less than 100 again) which is a unique non-negative linear combination of 3 and 8. And as before the same is true for any non-empty set of relatively prime positive integers, {a1, a2, …, an}; i.e., there is a largest positive integer that is a unique non-negative linear combination of {a1, a2, …, an}. That largest positive integer is denoted g1(a1, a2, …, an). (We could go on and define g2, g3, … etc. but we won’t need them here.)

Problem 3. Find g1(3, 8) and prove it is.

Solutions may be emailed to
cont.puzzles@gmail.com.
In
order to make the solver list, your solutions must be received by Jan. 1, 2018.

Solution to Previous Puzzle—Straight Flush!?

What is the probability of forming a straight flush in seven cards? Let’s break this down into three cases. If all seven cards form a seven card straight flush (e.g., 3, 4, 5, 6, 7, 8, 9 of clubs), there are eight ways to get seven cards in a row, times four suits for 32 cases.

To form a six-card straight flush, for the two straight flushes Ace through six and the case of nine through Ace, there are 45 options for the “blank” extra card (NOT 46, as one card creates a seven-card straight flush) and four suits.

So 2 × 45 × 4 = 360. There are seven other possible ways to create a six-card straight flush (2 through 7 all the way to 8 through King), and in these cases there are 44 possibilities for the “blank” card, times four suits. So 7 × 44 × 4 = 1,232. And 1,232 + 360 = 1592. For a five-card straight flush, for the two specific cases of Ace through 5 and 10 through Ace, there are possibilities for the ‘blank’ two cards, and again four potential suits: 2 × 1,035 × 4 = 8,280. For the remaining eight cases, 2 through 6 all the way up to 9 through King, there are cases for the two “blank” cards: 8 × 7,920 × 4 = 31,680. This gives us 31,680 + 8,280 = 39,960. Summing 32 + 1592 + 39,960 = 41,584. There are or 133,584,770 possible ways to get dealt seven unordered cards. The quotient of these two numbers gives us our answer of 0.03108 percent probability. What is the probability of getting a 9 or higher straight flush? Using the same reasoning as part A by dividing the problem into three cases, but now limiting the straight flushes to those with the final card is nine or higher, leads to the probability of 0.0187 percent.

What is the revised probability of part B if your individual cards must both make the highest possible straight flush available? The trick here is that your straight flush counts ONLY if the two cards that do not form the best straight flush are not in your hand. In this case, there is a 5/7th chance that the first card will be part of the best five cards, and given that to be true, a 4/6th chance that your second card is also part of the best five. So (5/7) × (4/6) × (the answer to part B) gives us 0.00891 percent.

What is the probability of a 9 or better straight flush if both of your individual cards can be used to form a straight flush? This answer is similar to that of part C, with two additional things to consider. First, if there is a six- or seven-card straight possible, we need to add in these cases as long as both of our individual cards get used in the straight flush. And finally, we need to adjust for the fact that if your individual cards contain either a 3 or a 4, your straight flush does NOT count, as it will not be 9 or higher. Accounting for these two adjustments leads to a final answer of 0.009076 percent.

Solvers

Clive Keating, Doug Szper, Daniel Wade, Bill Feldman, Andrew Dean, Bernie Erickson, Bob Byrne, John Snyder, Yan Fridman, Al Spooner, David Promislow, William Carroll, Rui Guo, Ronald Stokes, Chi Kwok, Bob Conger, and Robert Bartholomew

Next article Some Assembly Required
Previous article How Will You Be Remembered?