Exoplanet tickets

Nice way to solve it! One small thing, when stating Chicken McNugget Theorem, we should say "m and n are relatively prime", right?

Curious mind wants to know Why (X-1)(Y-1)=30?

I understand that this problem is based on the buyer having exact change without respect to the seller giving anything back, but I am still confused here. On a quick look, 4 and 11 seem to have greater than 15 integers that cannot be paid exactly using only additive arithmetic (1,2,3,5,6,7,9,10,13,14,17,18,21,25,28,29--at least). I am coming off 4 12-hour nightshifts so I could be making a simple math error. Where am I going wrong?

Why can't it be 17? Bills of 10 and 7. No matter how you combine them, it can never sum up 18.

Is the only way to solve it using the Chicken McNugget Theorem?

Confused by problem wording. "No need for overpayment or dispute over underpayment" doesn't preclude the possibility of making change. I could pay 18 eleven bills and receive 45 four bills in change. Pay 198 get 180 back I paid 18 without an overpayment or underpayment.

There is something about this question and the answer that I don't understand at all. I calculate that there are a total of 21 integers that cannot be paid with only $8 and $7 dollar bills. The total list of unpayable amounts is. 1,2,3,4,5,6,9,10,11,12,13,17,18,19,20,25,26,27,33,34,41. any integer value above 41 can be paid .

Can anyone demonstrate how to pay any of these 21 integer values with only $7 and $8 dollar bills?

Now! If the two bill where $ 7 and $5 dollars I calculate that there are only 12 integer values that cannot be paid. That list is 1,2,3,4,6,8,9,11,13,16,18,23. In this case any integer value above 23 can be paid.

What am I missing hear?

Can anyone please add a proof to this theorum?

This can be solved using the process of elimination. 1 to 3 can build 18 so are not candidates. Number 4 in combination might work however

4, 5 5+5+4+4 is 18 4, 6 6+6+6 is 18 4, 7 7+7+4 is 18 4, 8 only produce products of 4 so eliminated 4, 9 9+9 is 18 so 4, 10 4+4+10 is 18 so out 4, 11 is the first logical candidate which indeed works and produces all but the 15.

So focusing on the 18 rather than the 15 is more cost effective using a POE.

Can't I pay 18 by giving him six bills of 11 and get back 12 bills of 4 as a change, as 6(11-2*4) =18, right?

I found the formula (m-1)(n-1)/2 by a different method. My method was not via a rigorous proof but it gave me enough confidence to seek for an answer of the form (X-1)(Y-1)=30. Having found 4 and 11 as a possible solution I checked and it worked.

So here's my thought processes which led to the formula. First I realised that every integer =mn or greater could be expressed as am+bn. 'Proof': the sequence m, 2m, 3m ... (n-1)m (all modulo n) must contain every number between 1 and n-1 without duplication. Taking k such that 0 < k < n then am = k (modulo n) so am = bn+k for some positive integers a and b. Hence k=am-bn. Therefore mn+k can be expressed as am+(m-b)n. Note that b<m (since a<n so bn < bn+k <nm) and hence both a and (m-b) are positive integers. This provides a solution for mn+1 up to mn+n-1. (m+1)n is simply a multiple of n and the next (n-1) numbers can be obtained by repeating the above trick. And so on indefinitely.

So all the inexpressible integers must be less than mn. Next I decided to count all the expressible integers from 0 to 2mn inclusive. At least, expressible in a restricted way. That is, I considered all integers of the form am+bn where a ranges from 0 to n and b ranges from 0 to m. The smallest this can be is zero. The largest it can be is 2mn. I satisfied myself [proof omitted] that each couple [a, b] led to a different sum with one exception: a=0, b=m gives the same result as a=n, b=0. Therefore the (m+1)(n+1) combinations produce (m+1)(n+1)-1 different expressible integers between 0 and 2mn inclusive, and hence the number of inexpressible integers (restricted to a<=n and b<=n) is (2mn+1) - (m+1)(n+1) +1 which simplifies to (m-1)(n-1).

Finally, the non-rigorous intuitive bit. I felt in my bones that the pattern created by generating integers of the form am+bn (with a=0 to n and b=0 to m) would be symmetrical around the midpoint mn. Hence the number of inexpressible integers less than mn would be (m-1)(n-1)/2. The other half (between mn and 2mn) are only inexpressible in my restricted sense. They can be expressed as am+bn where either a>n or b>m.