· Some Quick Problems

These are some simple problems that I made up. They aren't particularly difficult but I hope they will make you think a little. Maybe you will be motivated to invent your own problems. If you think you have a particularly good one, submit it and I may include it here with appropriate accreditation. However, it must be a problem that you came up with on your own.

1. Difference in Change

Suppose that you manage to find something to purchase that costs less than a dollar. If you have sufficient change in coins to cover the cost, how much more change in coins will you end up with if you pay with a dollar bill than if you paid with the coins? Explain your answer without using algebra.

2. The Most and the Least

This problem is based on a common programming algorithm.

There are four coins of differing weights. Using a balance, simultaneously determine the heaviest and the lightest coins in four weightings.

3. Town Evacuation

A small isolated town is concerned about its ability to evacuate the population in case of an emergency. It has a single bumpy dirt road going through it that can only handle traffic traveling up to 30 miles per hour. If the road is upgraded to handle traffic up to 60 mph, why won't the maximum rate of evacuation double?

4. Small Quantity Discount

You ordinarily buy several pounds of Qibx at $10.00 per pound. Unfortunately, your regular supplier is out and won't be getting any until tomorrow. You have an immediate need for one pound of Qibx, so you go to another supplier. A one pound package goes for $12.00. You can also buy a three-pound package for $33.00, or $11.00 per pound. Which package is more economical?

5. Final Jeopardy

For those who have never watched the television quiz show Jeopardy: In the final round of the show, each contestant can wager any amount up to the person's current winnings. If the person answers the question correctly, the amount wagered is added to the previous winnings. Otherwise it is deducted.

Suppose there are two contestants in the final round and that the one in second-place enters the round with winnings of $12,000. The most that this person could end up with is $24,000. The leading contestant would be assured of at least a tie by starting the round with $24,000 or more.

If the leader has less than $24,000 she can not be assured of at least a tie. Suppose that we eliminate the case where the leader answers the question incorrectly and her opponent answers correctly. How much would the leader need to assure at least a tie?

6. The Noomian Translation

This is another problem that draws its inspiration from computer programming.

Until recently, the Noomians had a thriving culture. There are currently no speakers of the Noomian language. This highly literate people left behind an extensive literature, including a book written in Noomian telling how to translate from Noomian into English. There is also a book written in the language of Narus telling how to translate from Noomian to Narus.

All Language Publishers would like to produce a book written in English that tells how to translate from Noomian into English. They have located one of the few remaining speakers of Narus. Unfortunately, the gentleman speaks no other language. With considerable effort the people of All Language have managed to convey their desire to produce an English translation of the Noomian to English book and the man has agreed to do it. How does he go about writing the book?

Some more difficult problems:

. No Doubles

What is the size of the largest collection of numbers from 1 to 100 with the property that no number in the collection is exactly twice as large as any other number in the collection?

What is the size of the smallest double-free collection of numbers from 1 to 100 which is complete, where by complete is meant that adding another number to the collection will cause some number in the collection to be twice as large as some other number in the collection?.

. At Least One Divisor

Shortly after I thought of the previous problem I read about this one, whose statement and solution are closely related. It provides a nice contrast between the product of a hacker such as myself and true genius.

This problem seems monstrously difficult but it has a simple solution.

First an easy problem. Find 50 numbers from 1 to 100 such that none of them divides evenly into any of the others. There are many solutions to this. If there were not, the second part of the problem would be easy. There is, however, one solution that is fairly obvious.

Now show that 50 numbers is the best that can be done. That is, show that for any 51 numbers from 1 to 100 one of them must be divisible by one of the others.

Hint: Show that all numbers can be expressed as O*2ⁿ, where O is odd.

Use the insight gained from the previous demonstration to devise a scheme for finding the 50 smallest numbers up to 100 such that no number divides any of the others.

Here is a variation of this problem that you should be able to solve using your intuition. Find a set of numbers S of smallest size that satisfies the following:
1. Every number is greater than 1 and less than or equal to 100
2. No number in S divides any other number in S
3. Including any additional numbers in S causes a violation of (1) or (2).

. Checkerboard Patterns

Given a 4 by 4 checkerboard, suppose that you can reverse the colors of any row or any column. How many patterns can you create by selecting different combinations of rows and columns. You might want start on a 2 by 2 checkerboard or a 2 by 1 checkerboard.

Note that squares belonging to the intersection of a selected row and a selected column may be thought of as being reversed twice, once by the column and one by the row, and so will end up with their original color.

.The Lovesick Commuter

a. Young Tom has become infatuated with Vera, a toll collector on the highway that Tom rides to work on. There are 3 tollbooths and Tom has learned that the toll collectors are randomly assigned to a tollbooth subject to the constraint that nobody works at the same tollbooth two days in a row. To simplify the problem assume that both Tom and Vera work 7 days a week. Assume also that Tom is unable to see who is working in any tollbooth other than the one where he is at. What strategy should Tom employ to maximize the chances of seeing the object of his affection? On average, how often will he see Vera?

b. This part is harder on both Tom and the reader. One day Tom notices Vera wearing an engagement ring. He is heartbroken, his only consolation being that Vera has never taken notice of him. He wishes to see Vera as little as possible. What strategy should he now employ? What are the chances on any particular day that the sight of Vera's countenance will take its toll upon Tom?

.Minimum Attained Once

Consider the function f(x) = x² + 1/x² + x + 1/x for x > 0.  For large values of x the x² term dominates as the function goes to infinity.  As x goes to zero the 1/x² term dominates as the function again goes to infinity.  It is reasonable to suppose that for some intermediate value of x the function attains a minimum value. To properly find this minimum value requires the use of calculus but given the information that the minimum is attained for a single value of x a small insight into the nature of this function allows you to easily determine the value of x where the function has its minimal value.  What is the value of x? What is the minimum value of the function?

.How many people are on the bus?

A bus route has 14 stops. For each pair of stops there is exactly one passenger who gets on at the first stop and also gets off at the second. For example, there is one passenger who gets on at stop 2 and also gets off at stop 8. Find an equation for the number of passengers on the bus after it unloads and loads passengers at stop x. At what stop does the bus have the maximum number of passengers as it pulls away from the stop? How many people are on the bus at that point?

The Answers

HOME