Web Rarely

I've started going through the book Foundations of Higher Mathematics: Exploration and Proof (Fendel and Resek, 1990) again. It's a great math book, probably the best I've seen, because of its fresh approach — with a focus on personal exploration rather than endless problem solving. I'm posting the results of my first few explorations, primarily in hopes that somebody smarter than me will post a message providing new insights or pointing out places where I'm mistaken. If you want to buy the book, you should probably stop reading so as to not spoil the exercises for yourself.

Note: If you cannot view some of the math on this page, you may need to add MathML support to your browser. If you have Mozilla/Firefox, go here and install the fonts. If you have Internet Explorer, go here and install the MathPlayer plugin.

Exploration 1: SubDivvy — a game

SubDivvy is a simple game played by two players. It proceeds as follows:

1. Choose at random a natural number greater than one. Let's call it `N`. (You may want to set a reasonable upper limit.)
2. On your turn, choose a positive divisor of `N`, that is not equal to `N`. Subtract the divisor from `N`. The result of the subtraction is given to the other player.
3. Play continues until the result reaches 1. The player who produces the result 1 is the winner.

An example game: The number chosen randomly is 68. Player 1 chooses 4 (a divisor of 68) and subtracts, yielding 64. Player 2 chooses 16 and subtracts, yielding 48. Player 1 chooses 24, yielding 24. Player 2 chooses 8, yielding 16. Player 1 chooses 8, yielding 8. Player 2 chooses 4, yielding 4. Player 1 chooses 2, yielding 2. Player 2 is forced to choose 1, yielding 1, and player 2 is the winner.

My analysis: (Because the game takes place with the natural numbers, the statements below assume the domain of natural numbers.)

1. An odd number can only be reduced to an even number because odd numbers have only odd divisors, and an odd number minus an odd number is an even number.
2. An even number can always be reduced to an odd number by subtracting 1, which is a divisor of all natural numbers.
3. The number 2 wins because 2 can be reduced to 1. In fact, 2 is the only number that can be reduced to 1 in a single step by subtracting a divisor. This is because to reduce `N` to 1, it must have a divisor equal to `N - 1`. That is to say, `N/(N - 1)` must be an whole number, and that is only true when `N=2`. (`2/1` is a whole number, but not `3/2`, `4/3`, `5/4`, ... `100/99`, etc.) So getting an even number, 2, is needed to win.
4. A player with an even number can continue getting even numbers by reducing the number to an odd number (by #2), which the opponent will be forced to reduce back into an even number (by #1). Eventually the number will be reduced to 2 by this process, and the number 2 wins (by #3).
5. Therefore, having an even number is a winning position, because there is strategy that guarantees a win from that position. Due to #1, an odd number is a losing position, because it can only be reduced into an even number, which is a winning position for the opponent. Thus, with optimal play, the winner is determined solely by whether the original number is odd or even.
6. A good strategy is to subtract the largest odd divisor if you have an even number, and subtract 1 if you have an odd number. This strategy is guaranteed to win if you have an even number. If you have an odd number, subtracting 1 is not a winning move, but gives the opponent more choices of divisors, more turns, and therefore more opportunities to blunder, which is the only hope one has with an odd number.
7. Given an initial number `N`, the maximum number of turns is `N - 1`, with 1 being subtracted on each turn. The minimum number of turns results from subtracting the greatest possible divisor on each turn, and is equal to `"minturns"(N) = {(1,if N=2),(1+"minturns"[N-"greatestDivisor"(N)],if N>2):}} ~~ |~log_2 N~|`. As `N` increases, `"minturns"(N)` is less likely to be equal to `|~log_2 N~|`, but I believe that `0 <= "minturns"(N) - |~log_2 N~| < 1`, although I haven't proven it. (Can you prove or disprove that?) (On a rereading, this seems nonsensical. I think I made a mistake typing this up, but I don't remember what I was originally thinking...)

Exploration 2: Sets of integers that are closed under subtraction

A set `S` is said to be closed under subtraction if for all pairs of members `a` and `b` chosen from the set, `a-b` is also in the set, including the case when `a=b`.

Here are my observations of such sets:

1. Sets of integers closed under subtraction must contain zero, because any member minus itself is zero.
2. They are symmetrical around zero because they contain zero (by #1) and any member `m` subtracted from zero is `-m`. That is to say, if `m` exists, `-m` must exist.
3. The only finite set that is closed under subtraction is `{0}`, because if a set contains any member `m` besides zero, then `-m` must exist (by #2), and `m` could be subtracted from `-m` yielding `-2m`. Similarly, `-m` could be subtracted from `m` yielding `2m`. The process could be repeated yielding `-3m` and `3m`, and so on. Therefore, if `m` exists, all multiples of `m` must exist.
4. More specifically, infinite sets (see #3) contain every multiple of the GCD (greatest common divisor) of all non-zero members. That is, if the GCD of the non-zero members is 3, then the set contains (and only contains) all multiples of three. This is because every non-zero member `m` is divisible by the GCD by definition, so every such `m` can be represented as `m=n*d` where `n` is an integer and `d` is the GCD. Given two such members, `m_1` and `m_2`, represented as `n_1*d` and `n_2*d` respectively, `m_1 - m_2 = (n_1*d) - (n_2*d) = d(n_1 - n_2)`, which is also divisible by `d`. Therefore, the difference of any two members is another number, divisible by the GCD, which also exists (by #3). This also can be visualized by imagining each number as a line of dots, with the number `n` having `n` dots. So 4 is . Then, a number `d` is a divisor of a number `n` if `n` can be broken into an integer number of groups, with each group containing `d` dots. If you imagine two numbers (eg, 9 and 6), lined up one above the other, like this: , you can see that for every common divisor `d` of the two numbers, the groups of `d` dots in each number line up, so that a subtraction of the two numbers doesn't break any groups. That is, the result of the subtraction has the same common divisors, and more importantly, does not introduce any new common divisors. Thus, all subtractions yield multiples of the GCD.

Can you think of any other properties of sets of integers closed under subtraction?

Exploration 3: Sets of integers that are closed under addition

A set `S` is said to be closed under addition if for all pairs of members `a` and `b` chosen from the set, `a+b` is also in the set, including the case when `a=b`.

Here are my observations of such sets:

1. The only finite set closed under addition is `{0}`, because if a non-zero member `m` exists, it can be added to itself, yielding `2m`, and added again yielding `3m`, etc. So if `m` exists, all multiples of `m` with the same sign must also exist. Numbers of the opposite sign needn't exist because adding two numbers with the same sign always produces a result with that same sign. (This means that if 2 exists, then 4, 6, 8, etc. must also exist, but -4 needn't exist.)
2. If the set contains both positive and negative numbers, it must also be closed under subtraction (see above) because of the definition of subtraction: `a-b=a+(-b)`. By #1, if a set closed under addition contains 2, it must contain 4, 6, 8, etc., and if it contains -4, it must contain -8, -12, -16, etc. But consider the set `S`, closed under addition, with a subset {-4, 2}. Because `2 + (-4) = 2 - 4 = -2`, -2 must also exist, so by #1 the positive series (2, 4, 6, 8, ...) is duplicated on the negative side (-2, -4, -6, -8, ...). By similar reasoning, the negative series (-4, -8, -12, ...) is also duplicated on the positive side. This symmetry means that if `m` exists, then `-m` exists, and because `m + (-m) = 0`, 0 must also exist. See the discussion of sets closed under subtraction, above.
3. If a set `S` is closed under addition but not subtraction (ie, it does not contain numbers of opposite sign) and contains non-zero members, it contains (and only contains) multiples of the GCD (greatest common divisor) of all non-zero members, with the same sign as those members. In addition, it contains all multiples of the GCD greater than or equal to twice the value of the smallest non-zero member. So far this is rather tautological, but it allows you to determine the closure of a set over addition. For example, the closure of the set {9,12} (which has a GCD of 3) is {9,12,18,21,24,27,30,...}.
4. If the set is not closed under subtraction, then it may contain zero, although it is not required. The presence of zero does not imply the existence any other members, because `a+0=a`.

The sets of integers closed under addition are more complex than those closed under subtraction, so I'm more likely to be mistaken here, or missing some other properties. Can you find any other properties of these sets?

Exploration 4: Make It More — another game

Make It More is another two-player game. Each player has a 3-digit number to fill in, so a playing sheet might look like:

Player 1: __ __ __
Player 2: __ __ __

Player 1 begins by choosing any digit except 0 or 5, and writing it in his ones column. Player 2 doubles the digit player 1 chose, and chooses any digit except 0 or 5 that is less than or equal to the ones digit of the doubled value, and writes it into his ones column.

Player 1 doubles the digit player 2 just chose and, like player 2, picks a digit other than 0 or 5 that is less than or equal to the ones digit of the doubled value, and writes it in his tens column. This process continues until both numbers are filled out. The winner is the player whose final 3-digit number is larger.

Here is a sample game:

Move	Board	Comments
1	4	(Player 1 chooses 4 for the ones column.)
2	4           7	(Twice 4 is 8; player 2 chooses 7, which is less than or equal to 8, for the ones column.)
3	3   4           7	(Twice 7 is 14; player 1 chooses 3, which is less than or equal to 4 [the ones digit of 14], for the tens column.)
4	3   4       6   7	(Twice 3 is 6; player 2 chooses 6 for the tens column.)
5	1   3   4       6   7	(Twice 6 is 12; player 1 chooses 1, which is less than or equal to 2, for the hundreds column.)
6	1   3   4   2   6   7	(Twice 1 is 2; player 2 chooses 2 for the hundreds column.)

267 is greater than 134, so player 2 wins this game.

This doesn't seem like much of a game to me, but I could be wrong. Here's what I think:

1. The digit 9 can only be chosen during move 1. After the first move, the previous digit is doubled. Since only the ones digit of the doubled value is considered, the doubling is effectively done modulo 10, and no integer number times 2, modulo 10, is greater than or equal to 9. It won't be equal to 9 because 9 is odd, and multiplying by 2 makes a number even, and it won't be greater because 9 is the maximum integer modulo 10. On the other hand, the values 1 and 2 are available to be chosen on every turn, because even if the smallest digit, 1, is chosen for the previous turn, when doubled it will be equal to 2.
2. The hundreds column dominates the other columns. The other columns don't even need to be considered unless the two choices for the hundreds column are equal.
3. Because the hundreds column dominates the other columns, and because the digits 1 or 2 can always be chosen, player 2 can win this game every time. If player 2 chooses 1 or 2 for his tens column, player 1's choices for his hundreds column will be limited to 1, 2, 3, or 4, and no matter which one of those he chooses, player 2 can double it and win.