Time for some math puzzles

It’s been a long long quarantine with not much to do, so why not give the brain some exercise through a bunch of interesting puzzles.

1.) A yard sale consists of many old broken toys and other items. The greedy toy collector Al McWhiggin spots Woody and asks Mrs. Davis about buying it. Mrs. Davis refuses to say Woody is Andy’s favorite toy. After much persuasion from Al, she agrees to sell Woody only if Al completes her demands. She tells Al that he must pay her in only denominations of 97, 98, and 99. Moreover, the amount Al must pay her, let’s say N, should be such that any integral sum greater than N can be paid by using denominations of 97, 98, and 99 in a single exchange. How much money must Al pay to buy Woody?

So we’re in a world where Al can pay Mrs. Davis by using only coins of three values — 97, 98 or 99. Now it’s quite obvious that all amounts cannot be paid using these three coins.

Amount A = 97x + 98y + 99z, where x, y, z are non-negative integers.

Our task is to find the smallest N, such that every number greater than or equal to N can be formed by the above equation. Let f(N) be a function that returns a Boolean value (True or False) if the amount N can be formed using the denominations 97, 98, and 99. We need to find N such that,

f(N-1) = False, f(N) = True, f(N+1) = True, f(N+2) = True, and so on…

Since we only have coins of value 97, 98, and 99, in order to be able to form a certain amount N, it must also be possible to form an amount of N-97 or N-98 or N-99, because it’s just the addition of one more coin of either denomination. Hence, we have,

f(N) = f(N-97) || f(N-98) || f(N-99), where || denotes logical OR.

f(N-1) = f(N-98) || f(N-99) || f(N-100)

Since f(N-1) has to be false, the logical OR of all three quantities has to be false as well. Hence f(N-98) = false, f(N-99) = false, f(N-100) = false. From the equation for f(N) we will now have f(N-97) = true, for f(N) to be true.

Let’s keep this recurrence relation in our mind, and come back to it later, while we look at a few simple cases in the meanwhile. It’s obvious that any multiple of 97, 98 or 99 can be formed. Let’s say we have m coins of 97 value. We can form the amount 97m. In order to form 97m + 1, I could just replace one coin of 97 with 98. I can continue doing this coin replacement trick to increment the amount by one, until all m coins have become 99. Hence it is possible to form all numbers between 97m and 99m, both inclusive. This results in the ability to form (2m+1) amounts. Every range that can be formed will begin with a multiple of 97, and end with a multiple of 99, with f(99m + 1) as false, until we find the answer N. Thus, our smallest possible N, beyond which all numbers are formable, will also have to be a multiple of 97.

N = 97m, which implies f(99m) = True

We need to find m such that f(99m + 1) is also true, so that all numbers can be formed beyond N.

f(99m + 1) = f(99m - 96) || f(99m - 97) || f(99m - 98)

For f(99m + 1) to be true, one of these three have to be true. For smallest m, we must have, f(99m - 96) [ because 99m - 96 is the largest among the three] to be true, and the rest to be false. This would mean that 99m - 96 is the beginning of a possible range, and hence has to be divisible by 97, and for the smallest number case, it will have to be at the beginning of the same range.

99m - 96 = 97m, => m = 48. Thus,

N = 97m = 4656.

All amounts greater than or equal to 4656 can be formed with coins of denomination 97, 98, and 99.

2.) Mr. Potato Head, Woody and Buzz are playing a game. The rules of this game are as follows.

1. One who wins continues to play with the resting player.

2. No matches end with a tie.

The results are as follows:

1. Mr. Potato Head played 13 matches.

2. Woody played 19 matches.

3. Buzz played 22 matches.

Who lost the 8th match?

We have three players playing a number of games, where the loser sits out, and the resting player faces the winner in the next game. We do not know which was the first game, or anything about the order. But we do know how many games each player has played. With this information, we can compute the total number of games played.

Let x → number of games between Potato Head and Woody

Let y → number of games between Woody and Buzz

Let z → number of games between Potato Head and Buzz

x + z = 13

x + y = 19

y + z = 22

Solving these three equations, we have x = 5, y = 14, z = 8.

Total matches played = x + y + z = 27.

Now the 27 matches are played, in order to find the order in which they were played, we can represent them as a string of x, y, z of length 27. Since the loser of a particular game sits out the next game, we cannot have two consecutive characters (x, y, z) to be the same, as the same match cannot be played twice in a row, since there is always a winner and a loser. A key observation is to note that y = 14, and there are 27 matches in total.

Since we cannot have two consecutive y’s, the only possibility that remains is, there has to be a y once in every two matches. And since 27 is odd, y has to occur in all odd matches. The string of matches will look something like this:

y _ y _ y _ y _ y _ y _ y _ y _ y _ y _ y _ y _ y _ y (Length = 27)

The 9th match is y, that is, between Woody and Buzz. Mr. Potato Head is sitting out the 9th match, because he lost the 8th match.

Source of problems: Technothlon