Some Quick Problems:

1.   Difference in Change

A little experimenting should convince you that the answer is \$1. What is the simplest way to prove that this must be so? In each of the two cases you end up with the same total amount of money. Since by paying with a dollar bill you end up with \$1 less in paper money compared to the other case, this must be compensated for with a dollar more in change.

2.   The Most and the Least

Divide the coins into two pairs and weigh each pair. This takes two weighings. Now weigh together the heavier coins from the first two weighings. The heavier of these two is the heaviest coin of the group. Similarly, weigh the two lighter coins. The lighter of these is the lightest of the group.

This problem is easily generalized to n coins. Divide the coins into n/2 pairs and weigh each pair. Group the n/2 heavier coins together and group the n/2 lighter coins together. It takes (n/2 -1) weighings to find the heaviest of the heavy coins, which will also be the heaviest coin of the group. Similarly, it takes (n/2 - 1) weighings to find the lightest coin. The total number of weighings is 3*(n/2) - 2.

3.  Town Evacuation

The easiest way to envision this problem is to think of the road as a conveyor belt with the cars motionless with respect to the road. The number of cars per hour that reach the end of the conveyor belt depends on the speed at which the belt is moving and by how densely the cars are packed together. Thus the equation for the number of cars per hour that can be evacuated is found by multiplying the speed of cars by the number of cars per mile.

The rule in the driver's manual is that car separation should be one car length for every ten miles per hour of driving speed. Suppose that this rule were actually followed. At 30 mph there would be one car for every 4 car lengths - 3 lengths of separation plus the car's own length. At 60 mph there would be one car for every 7 car lengths. At 60 mph the speed would double but the density would be 4/7 so the comparative rate of evacuation would be 2 * (4/7) = 8/7, for an increase of about 14%. Although the car separation rule is not followed in practice it is still true that cars are further apart when they travel faster so that doubling the speed from thirty miles per hour to sixty miles per hour is offset by the decrease in traffic density.

4. Small Quantity Discount

Although it goes against the grain to buy something at the higher unit price, you have to look at what it will cost to get three pounds. Buying the three-pound package costs \$33. The cost of three pounds buying the one-pound package is \$12 for the one-pound package plus \$20 for two pounds from the regular supplier for a total of \$32, which is \$1 less.

If you still think that you should always go with the smaller unit price consider the case where the one-pound package costs \$1000 and the three-pound package costs \$1500.
This problem illustrates a basic concept in economics. In economics, opportunity cost is defined as the difference in price between an item and the best possible price for the item. The principle is to always try to minimize the opportunity cost. The best price in this case is \$10 per pound. The one-pound package is preferable because it has an opportunity cost of \$2 compared to a \$3 opportunity cost for the three-pound package.

5. Final Jeopardy

There are really only two cases to consider - if both contestants answer correctly or if both answer incorrectly. If the person in second place anwers wrong and wagers nothing he will end up with \$12000. If he guesses correctly and wagers everything he will end up with \$24000. To cover both these cases it is necessary to be in the middle of \$12000 and \$24000, \$18000 and to wager \$6000.

To solve the problem algebracally let X = the amount that the person in first has and W = the amount of her wager. Then we have:

X - W = \$12000 and
X + W = \$24000, which gives the above solution.

6. The Noomian Translation

To simplify things let us refer to the Noomian to English book as Book 1 and the Noomian to Narus book as Book 2.

The speaker of Narus can use Book 2, which is written in his own language, to translate Book 1 into Narus. He can now use this translated version of Book 1 to tell how to translate the original Book 1 into English.

What this problem has to do with computers

Some more difficult problems:
1. No Doubles

To find the largest double-free collection of numbers from 1 to 100, start with the 50 odd numbers. Since none of these numbers is twice as large as any number, none is larger than any other in the collection. We can add to these numbers by choosing numbers which are equal to four times an odd number. There are 13 such numbers from 4*1 to 4*25. Next add the numbers which are 4*4 times an odd number. There are three such numbers: 16, 32, 48. Finally, add the one number which is 4*4*4 times an odd number, namely 64. This gives a total of 50 + 13 + 3 + 1 = 67 numbers. It is possible to produce another collection of size 67 by modifying some of the members of the collection. For example, the numbers 3, 3*4 and 3*16 can be replaced by the numbers which are twice as large as these numbers - 6, 24 and 96.

Producing the smallest double-free collection is a little trickier. The basic idea is to first start out, where possible, with two times an odd number. For example, start with 6 instead of 3. Choosing 6 makes it impossible to later add 3. Next, multiply the previously chosen number by 8, giving 8*6 = 48. We will not be able to later add either 2*6 or 4*6. When choosing 8 times a number is too large then try to choose 4 times the number. Following this strategy gives the following 57 numbers:

2 16 64, 6 48, 10 80, 14 56, 18 72, 22 88, 26, 30, 34, 38, 42, 46, 50, 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99.

As in the previous case, it is possible to make substitutions to get another complete double-free collection of the same size.

2. At Least One Divisor

Among the numbers 51 to 100 it should be evident that no number evenly divides any of the others. Note that in this collection any even number can be replaced with half its value. For example, 86 could be replaced with 43 because 86 is the only number under 100 that 43 divides.

Every number can be expressed as O
×2n where O is odd. A number of the form 2n would be expressed in this notation as 1×2n and an odd number  O would be expresed as O×20.

Given two numbers in this notation using the same odd number, O×2m and O×2n, one of these numbers must be divisible by the other. There are 50 odd numbers from 1 to 100. Therefore if we express any 51 of them as O×2n, at least two of them must have the same O and therefore one of them will be divisible by the other.

Note that the numbers 51 to 100 can be selected using the following rule:

To find the smallest set of 50 numbers, apply the following rule:
For each odd number O, choose the largest value of O
×2n less than or equal to 100.

To see why this works we need only consider two odd numbers O1 and O2 where O1 divides O2.  O2 = k
×O1 for some nunmber k.  We find the largest m such that O2×2m is less than or equal to 100.  O2×2m = k×O1×2m and since k > 2, we know that O1 can be multiplied by a greater power of 2 than O1 and so we will get O1×2n where n > m and O1×2n will not divide O2×2m.

The number chosen corresponding to 5, for example, is 5
×24=80.

To find the smallest set of 50 numbers, apply the following rule:

For each odd number O, choose O
×2n where n is the largest number such that O×3n is less than or equal to 100.

To see how this works, again consider the numbers O1 and O2 where O2 = k×O1.   Since O1 and O2 are odd k >= 3 and so we can get two numbers less than 100 of the form O2
×3m and  O1×3n  where n > m.  Using these values of m and n we choose O2×2m and  O1×2n.

3. Checkerboard Patterns

Let us divide this problem into two parts, input and output.

Input:

By input I mean the combination of different rows and columns. For each row and each column there are two possibilities - it is either chosen or it is not. Adding an additional row or column doubles the total number of possibilities. For a R by C checkerboard there are thus 2R+C input possibilities.

Output:

The output consists of the checkerboard patterns. The total possible number of such patterns is two raised to the power of the number of squares in the checkerboard, 2R×C. Obviously, the total number of patterns due to the input must be less than or equal to the minimum of 2
R×C and 2R+C.

Each combination of rows and columns does not necessarily result in a distinct output. For example choosing every row and every column is the same as not choosing any rows or columns - the checkerboard is unchanged. Now for any input combination we can superimpose on it the combination of all rows and all columns. The result will be that the original rows and columns will be "zeroed out" leaving a reverse image of the original input pattern which produces the same output as the original. For example reversing the first row of the checkerboard is the same as reversing every column and every row except the first row. We then have at least two input combinations that produce the same output pattern.

To show that there are only two input combinations for each output, we only have to consider the number of ways of producing no change. The reason for this is that if we take the difference between two combinations that produce the same output that difference combination should result in no change.

You should be able to convince yourself that the only combinations of rows that result in no change are either choosing none of the rows and columns or choosing all of them. Thus the output possibilities are one half the input, 2R+C/2 = 2R+C-1. For the original problem this comes to:

24+4-1 = 27 = 128 output patterns.

A very brief introduction to Group Theory:

If you have been following this, I would like to add one more twist to the explanation by relating this problem to the previous discussion of isomorphisms.

Denote by I, a combination of input rows Ri and columns Cj. We can define an operation & on two such combinations, I1 and I2, by having the rows and columns common to I1 and I2 cancel and keeping the rest. If I1 = {R1, R2, C1} and I2 = {R1, C2} then I1 & I2 = {R2, C1, C2}.

Denote by O a checkerboard whose spaces are filled with 0's and X's, where 0 means do not reverse the color and X means reverse the color. We can define an addition operation O1 % O2 in the obvious way - superimpose the two checkerboards and add the two values for each square with 0 and 0 (no change and no change) resulting in 0, 0 and X (no change and reverse) resulting in X, and X and X (double reversal) resulting in 0.

Note that there is a zero value O0, having all the squares filled with 0, which has the property that for any other output pattern O, O % O0 = O. Similarly, there is a zero value I0 formed by choosing no rows or columns.

The original problem defines a function f(I) = O which relates the input combination of rows and columns to the corresponding output change pattern. Furthermore,

f(I1 & I2) = f(I1) % f(I2).

This would be an isomorphic relation if the function f had an inverse, which we just showed is not the case. In this case we have a homomorphism. The problem of finding all the input combinations resulting in no change can now be described as looking for all I such that f(I) = O0. By working with the properties of homomorphisms, the informal explanation that I gave above could be put on a formal basis.

This is as far as I want to carry this discussion. To say much more would require me to say a whole lot more. What I have done is provide a very brief and somewhat quirky introduction to group theory, which is a part of abstract algebra. I encourage the interested reader to pursue this subject further, although I would first suggest studying probability and linear algebra, which are both more practical and which provide good examples to illustrate ideas in group theory.

4. The Lovesick Commuter

a. There are two cases to consider. If Tom meets Vera on a particular day then he knows that the next day she will be at one of the other tollbooths. In this case he should randomly choose between the two of them for his next visit.

If Tom does not meet Vera on a particular day, then she is at one of the other tollbooths and will not be at it the next day. To avoid that tollbooth Tom's best strategy is to keep visiting the same tollbooth that he is currently at until he meets Vera. His chances of meeting her are again one in two.

Since Tom's chances of meeting Vera on the next day are one in two regardless of whether he meets her on any particular day his overall chances of meeting her are one in two.

A way of looking at this that is helpful in the second part of the problem is to assume that the probability of meeting will eventually converge to a constant value. This can in fact be shown for a large class of problems similar to this one. We can then compute the probability of meeting on the next visit based on the probablity of meeting on the current visit.

Let pm be the probability of meeting and pn be the probability of not meeting.

We then have:
pm = pm*(1/2) + pn*(1/2).
We get pm = pn, and since pm+ pn=1, pm = 1/2.

b. It should be fairly clear that Tom's strategy in this case is the reverseof his previous one.

If he meets Vera then by visiting the same tollbooth again he is assured of not meeting her the next day.

If he does not meet her on a particular day then he should switch tollbooths so that he has a one in two chance of visiting the tollbooth that Vera is currently at. In this case his chance of seeing her the next day is thus 1/2 (the chances of not choosing the tollbooth she is currently at) * 1/2 (the chance that he chooses the tollbooth that she will be assigned to) = 1/4.

Let pm be the probability of meeting and pn be the probability of not meeting. The only chance Tom has of meeting Vera the following day is if he does not meet her today and in that case his chance of seeing her is 1/4, so we have pm = (1/4)*pn, or pn= 4* pm. Substituting this expression for pn into pm+ pn =1, gives a value for pm of 1/5.

The assumption was made that the probability of meeting will converge to a constant value. Let us look at the first few visits to observe this.

The probability of a meeting, pm, is initially 1/3 and pn = 2/3.

pm for the second visit = (2/3)*(1/4)=1/6, so pn for the second visit=5/6.

For the third visit pm=(1/4)*(5/6)=5/24. We are pretty close to 1/5 at this point and further visits will just keep bringing pm closer to 1/5.

5. Minimum Attained Once

The small insight is to recognize that f(1/x) = f(x). Therefore for each value of y there will be at least two values of x such that f(x) = y, unless x and 1/x are the same, that is x = 1/x. Since it is given that the minimum value is attained only once, at the minimum x = 1/x and so x = 1. The minimum value of the function is f(1)=4.

Apply the idea for this problem to finding the minimum value of
f(x) = 1/x + 1/(4-x) between x=0 and x=4.

Another approach to original problem

6. How many people are on the bus?

After the bus unloads and loads passengers at stop x, every passenger on the bus got on at stop less than or equal to x and will be getting off the bus at stop greater than x. Since the number of stops greater than x is (14 – x) the number of combinations of entry and exit point is x(14-x).

You can find the maximum by comparing all the values of x(14-x). There are only 7 values to look at since f(14 –x) = f(x). f(x) = x(14-x) is the equation of a parabola and you can also find the maximum by completing the square. f(x) = -(x – 7)2 + 49, which obviously has a maximum value of 49 for x = 7. If you know calculus the maximum is easily found by taking a derivative.

The problem provides a rather simplistic model for the distribution of passengers on a bus or train, but it agrees with my experience that the number of passengers tends to steadily increase up to some maximum and then steadily decreases.

If we let p(i, j) be the number of passengers getting on at stop i and getting off at stop j then:
f(x) = sum (i
x and j >x) p(i, j). For this problem p(i,j) = 1 for all i,j. Since the number of p(i,j) terms for n stops is x(n – x) there will be a tendency for the number of passengers to follow a parabolic arc if these values are fairly randomly distributed.
7. The first square-free century
Instead of looking inside of centuries, let's turn things around and look at square values.  For a century not to have an exact square, there must be a squared value preceding the century with the next squared value coming after the century.  It follows that for a century not to have a square value, a necessary condition is that there must be over 100 years between two consecutive square values.  (x+1)2 - x2 >= 101. 2x+1 >= 101. x >= 50. 502 = 2500.  The next square, 512 , equals 2601. If, as some favor. we ended centuries in years ending in 00, then 2500 would be the last year of the 25th century and 2601 would be the first year of the 27th, leaving the 26th century square-free.  Since we are not following that convention, we will show that in fact the 36th century is the first that is square-free.  602 = 3600. 3600 - 2500 = 1100, so there are 11 centuries from 3600 - 2500.  We are not counting 60, since it comes after the end of the 36th century, so we the ten square values from 502 to 592. Since there are over 100 years beteween squared values once we get to 50, no century can have more than on exact square.  We have 10 squares and 11 centuries. Exactly one of the centuries is missing a square.  Since there are over 100  years between these exact squares, 592 < 3600 - 100 = 3500, so that the 36th century does not have an exact square.

Here is another approach.  Again we start with 502 = 2500.  Let's look at the first few squares after 50. 512=2601, 522 = 2704 and 532 = 2809.  There seems to be a simple pattern, which we can verify algebraically:
(50 + n)2 = 2500 + 2(50n) + n2 = (25+n)100 + n2.  Each successive square give the  n2 year of the next century.  This works unti we get to n = 10.  We go from 592 = 3481 to 602 = 3600, jumping over the 36th century.

HOME