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.
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.
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 2R×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.
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.
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
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.
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.
The maximum product is for four 3's, giving 3×3×3×3=81.
Instead of 12, let's work with any number n. Suppose one of the pieces m adding to it is even. When will we get a value greater than m if we split n in half, giving two pieces of size m/2? We wamt (m/2)(m/2) ≥ m. This gives m ≥ 4. For any value of n, none of the even values m adding up to it can be greater than 4, because we can always split that piece to get a product that is at least as large.
Odd values are similar. Let's compare (m+1)/2 (m-1)/2 to m. We want (m+1)/2 (m-1)/2 > m. Sine m+1 > m, we can say (m+1)/2 (m-1)/2 > (m/2)(m-1)/2. If we can set this second expression greater than m, the first will also be greater than m, giving us (m/2)(m-1)/2 > m. Solving gives us m > 5. It turns out that the original inequality hold for m = 5, since 3×2 > 5.
Putting things together, for any value n, none of the values m adding up to it need be greater than 4. That leaves us with 1,2, 3 and 4. Using 4 is the same as using two 2's. Pieces of size 1 are never helpful, for reasons that should be evident. That leaves us with 2 and 3. There can never be three or more 2's, because 3×3 > 2×2×2, so we can always replace three 2's with two 3's.
For any n, the rules then are as follows: If n is divisible by 3, use all 3's. If n has a remainder of 2 when divided by 3, use one 2 and the rest 3. If n has a remainder of 1 when divided by 3, use two 2's and the rest 3.
Where does the 3 come from? If you know calculus, the following derivation may shine some light on this. For xi valuues adding to n, we want the maximum product of xi. Maximizing the product of the xi values is the same as maximizing the log of the product of the xi values, which is the same as maximizing the sum of the log xi values. Think of n as a time interval divided into subintervals of size xi. Think of log xi as being the distance traveled in time subinterval xi. We want to maximize the total distance traveled. This will happen if we maximize the speed that we travel in each interval. The speed is (log xi)/ xi. Taking derivatives, it is a simple matter to find where (log x)/x is maximal, at x = e, the natural logarithm base. The local maximum is a global maximum since (log x) / x goes to 0 for large x and to minus infinity for small positive x.
e is about equal to 2.7. The two closest integers are 2 and 3, so (log x)/x must take on a maximal value over integers at 2 or 3. Working with log(32) > log(23) gives us (log 3)/ 3 > (log 2 )/2, giving the value at x=3. Since the largest value for integers is for x=3, the second largest value for integers must occur as x=2 or x=4. log 4 = 2 log 2, so (log x)/x is the same for 2 and 4. Again we reach the conclusion to use 3 whenever possible and 2 when a value other than 3 is necessary.
HOME