North Dakota Mathematics Talent Search 2004-2005
SOLUTION SET 2
(Posted on 02/07/2005)
- This is a typical search problem. We have four variables,
X, Y, Z, and T, that represent
the prices of four items. Each variable takes a value
between 0.01 and 7.08. (The smallest price might be 0.01
and since the total price for all four items is 7.11, the
largest possible price of any single item is 7.08.) To
avoid dealing with fractional numbers, let's change its
formulation into integers - we will talk about prices in
cents, rather than dollars and cents. In that way the
domain of each variable is the set of integers between
1 and 708. The problem is than to find integers
X, Y, Z, T in that range, such that
X + Y + Z + T = 711 and
X * Y * Z * T = 711000000
Note that during the conversion from dollars and cents into
just cents, each variable was multiplied by 100, thus their
product increased 108 times. As
711000000 = 26 * 32 * 56 * 79,
there are many cases to consider, exhaustively searching every
possible combination would give us a solution, but it would
also take a great deal of time. Let us try to investigate some
shortcuts. It is clear that the price (in cents) of one of the
items (say, X) is divisible by 79 (the largest
prime factor of 711000000). Then we have only the following
cases to consider:
X = 1 * 79 = 79;X = 2 * 79 = 158;X = 3 * 79 = 237;X = 4 * 79 = 316;X = 5 * 79 = 395;X = 6 * 79 = 474;X = 8 * 79 = 632.
Since 9 * 79 = 711 would be already out of range while 7 * 79
is not allowed because the price of any item can not be divisible
by 7. In each of the above cases, the number of subcases to
consider shrinks. For example,
If X = 2 * 79, then we have
Y + Z + T = 553 and
Y * Z * T = 25 * 32 * 56
Here it is impossible for all variables Y, Z, T to
be divisible by 5 (as their total is not), so the product of
two variables (say, Y and Z) is
divisible by 56. Now we have several subcases:
Y = 56 * Y';Y = 55 * Y' and
Z = 51 * Z';Y = 54 * Y' and
Z = 52 * Z';Y = 53 * Y' and
Z = 53 * Z'.
for some Y' > 1, Z' > 1. In first 3 subcases,
Y + Z > 632, which is impossible. So the only
subcase we need to consider is number 4, when problem becomes:
125 * (Y' + Z') + T = 632 and
Y' * Z' * T = 26 * 32
The number of possibilities to consider here is considerably
smaller, and it is easy to see that none of them would lead to
a solution. Thus case X = 2 * 79 would not work.
Repeating the same reasoning for other cases, shrinking step
by step the number of subcases to consider (and, perhaps,
using a computer or a calculator for exhaustive search through
reduced subcases), one can see that the only case when the
problem has a solution is X = 4 * 79 = 316.
Then Y = 125, Z = 120, T = 150. Thus, the prices
are:
$3.16, $1.25, $1.20, $1.50.
A final note: at any moment, for each case and each subcase
(as well as for the entire problem), we could just use a computer
to do an exhaustive search, but, as you can see, that would not
be the most efficient way to proceed. A better approach is to
reduces the problem into much smaller cases/subcases suitable
for fast exhaustive searches.
- The counterintuitive answer is that the gap is almost 32 cm!
That's over one foot! Even a small child could squeeze
under the ring! This is so because the difference in
circumference between the Earth and the ring is 100cm:
(2 * Pi * R) - (2 * Pi * r) = 100
so the difference in their diameters is
(2 * R) - (2 * r) = 100 / Pi = 31.83 cm.
- Here we are faced with a problem of locating a single item with
a certain characteristic from an assortment of other items that
don't have the same characteristic. The tool we have in front
of us is a balancing scale which can only tell us that one side
is heavier than the other, or that both sides are equal. The
natural thing to do is to start dividing the 12 coins into groups
where one group could be weighed against another. The difficulty,
however, is to get the answer with just three uses of the scale.
Let's partition coins in 3 groups of 4:
A=(1,2,3,4); B=(5,6,7,8); C=(9,10,11,12)
In the first weighing we compare groups A and
B. Either they balance or not. Let's consider
these two cases in turn.
- If
A and B balance, then the fake
coin must be in C. In our second weighing we
can compare three arbitrary genuine coins with three coins
from group C, say
(1,2,3) versus (9,10,11)
If the coins balance, then the fake coin is 12. Then the third
weighing (say, 1 against 12) would determine whether the fake
coin is heavier or lighter than the rest.
If the coins do not balance, then the fake coin is either 9,
10, or 11 (and we know if the fake is lighter or heavier).
Then the third weighing (say, 9 against 10) would determine
which coin is counterfeit.
- If
A and B do not balance, then
the counterfeit coin is in A or B,
and coins in the group C are genuine. This is
probably the most difficult step in getting the solution.
It's important to arrange the second weighing in a meaningful
way. We can do this by moving one of the coins from
B (say, item 5) to the left side of the balance,
and by adding a genuine coin (say, item 12) to the right side.
Thus, the second weighing is
(1,2,5) versus (3,4,12).
Assume that in the first weighing coins (1,2,3,4) were
heavier than coins (5,6,7,8). Then there are three
possible outcomes of the second weighing:
- Coins (1,2,5) are heavier. This means that coins 3, 4,
and 5 are genuine because we changed their locations
on the scale but the outcome remained the same (i.e.
the left-hand side is heavier). Since coin 12 is also
genuine, the fake is either 1 or 2, and it is heavier.
A third weighing (1 versus 2) determines the fake.
- Coins (3,4,12) are heavier. This means that the fake
coin had to have been moved from one side to the other.
Thus, either coin 3 or 4 is fake and heavier, or coin
5 is fake and lighter. A third weighing (3 versus 4)
determines the counterfeit.
- Coins (1,2,5) and (3,4,12) balance. This means that
fake wasn't included in the second weighing, so it must
be 6, 7, or 8, and it is lighter. A third weighing
(6 versus 7) will determine the counterfeit.
Thus, in three weighings the man and the jeweler can
determine the counterfeit coin and also know if it is
lighter or heavier than the rest.
- The problem has seven solutions in total. It is important here
to analyze the problem before we attempt to solve it. It might
be a good idea to "play" with some random integers to see what
is going on. After a short time we'd discover that it's unlikely
that all of these numbers are large. If
A, B, C,
and D are sufficiently large, then the product of
A and B is much greater than twice
their sum. The same is true for C and D.
For example, if A > 4 and B > 4,
then AB > 2 * (A + B). This simple observation
leads to the following conclusion: If all of the numbers
A, B, C, D are 5 or more, then
A*B > 2*(A+B) = C*D > 2*(C+D) = A*B
resulting in a contradiction. Assuming, then, that A
is the smallest of the numbers, it is sufficient to consider only
for cases, namely A = 1, 2, 3, or 4.
Notice the way the search space (set of all possibilities) was
reduced here! Let's work out one of these cases, say
A = 2: In that case the problem reduces to
2B = 2(C+D) and CD = 2(2+B),
which simplifies to
B = C + D and CD = 4 + 2B,
replacing B in the second equation we get
CD = 4 + 2C + 2D,
which gives us
C = (2D+4)/(D-2) = 2 + 8/(D-2).
As C is a positive integer, D
must be 3, 4, 6, or 10. For these we get two pairs of
symmetrical solutions (C,D) = (3,10) or
(C,D) = (4,6). Thus:
(A,B,C,D) = (2,13,3,10) or
(A,B,C,D) = (2,10,4,6)
In a similar fashion, other cases will lead to:
(1,54,5,22)
(1,38,6,13)
(1,34,7,10)
(3,6,3,6)
(4,4,4,4)
It is important to keep in mind the way the search space was
reduced here. "Playing" with the problem may give us important
insights into its nature and provides the opportunity to discover
ways for considering only a fraction of the possible solutions.
The key point is not to give up!
- There are a few ways to determine the solution. Probably the
simpliest way is to calculate the side area of the rolls:
Area of roll A
= Pi * (7.52 - 22) = 164.15; and
Area of roll B
= Pi * (82 - 32) = 172.79.
On the other hand, the total length of the tissues is:
Length of roll A = 480 * 16 = 7680; and
Length of roll B = 480 * 17 = 8160.
Then the tissue thickness for each of the rolls is:
Roll A = 164.15/7680 = 0.0214 cm and
Roll B = 172.79/8160 = 0.0212 cm.
So, roll A has slightly thicker tissues. Note that
we can equally answer an additional question: what is the
number of turns of tissue on each roll? Can you see how?
|
|
