What Your Math Teacher didn't Teach You?

Did you ever wonder on what day you were born or whether Oct. 3, 1995 was a Wednesday or a Monday? (Actually, it was a Tuesday.) Now there is a way to calculate which day of the week a day is on.

where

• d = day of the month
• m = month (March = 1, April = 2, ..., January = 11, February = 12)
• y = the last 2 digits of the year (if the day falls on January or February of a year, we consider the year to be the year before.)
• c = the first 2 digits of the year

For example, if we want to know which day of the week January 8, 1974 was, we have d = 8, m = 11, y = 73, c = 19.

If w = 0, then the day is a Sunday; the day is a Monday if w = 1, and so on. So January 8, 1974 was a Wednesday.

This method yields the day for any date from October 15, 1582 AD, the day when the Gregorian calender was first adopted, onwards. For dates prior to October 4, 1582, using the following formula instead:

One question that appears in brain teaser books is the following: find two integers a and b so that a × b = a + b. There are two solutions to this problem: a = b = 0 or a = b = 2.

However, if we allow a, b to be rational numbers (i.e. fractions), then there is an infinite number of solutions to this equation. From the following we can see, with one exception, that for any rational number a, there exists a rational number b such that a × b = a + b.

We suppose that a, b are rational numbers such that a × b = a + b. Then we have the following:

ab - b = a
b (a - 1) = a
b = a/(a - 1)

So if a ≠ 1, there exists a unique rational number b so that a × b = a + b.

To show that b is unique, suppose there exists a rational number c so that b and c are not equal, a × b = a + b, and a × c = a + c. So b = a/(a - 1) and c = a/(a - 1), a contradiction.

We now show that the only integer solutions to this equation are a = b = 0 and a = b = 2. Suppose there is another integer solution to this equation, so a is an integer other than 0 or 2.

Suppose a = 1, then we have a + 1 = a, which is impossible. So if a > 0, then a > 2. Since a > 2, a = 1 (mod (a - 1)). Since a > 2, this means that a is not divisible by (a - 1). Thus a/(a - 1) is not an integer.

If a < 0, then a - 1 < 0. So 0 < a/(a - 1). Since a < 0, |a| < |a - 1| and a/(a - 1) = |a|/|a - 1| (as a and (a - 1) have the same sign). So a/(a - 1) < 1.

In either case, a contradiction occurs. So the only integer solutions to a × b = a + b are a = b = 0 and a = b = 2.

Now we consider the problem of finding integers a, b, c so that a × b × c = a + b + c.

There are an infinite number of solutions to this problem — we have a solution if we set a to be any integer, b = -a, and c = 0. However, if we add the restriction that none of a, b, c can be 0, then there are only two solutions to this problem: (a,b,c) = (3,2,1) or (-3,-2,-1).

In fact, for any integer n ≥ 2, there is an integer solution to the equation
a₁ + a₂ + ... + a_n = a₁ × a₂ × ... × a_n
such that a₁, a₂, ... a_n are all non-zero — take a₁ = n, a₂ = 2, and a_i = 1 for i = 3,4,...,n.

Most of us have heard of tricks used to see if an integer is divisible by a small integer (for example, if the last digit of a number is even, it is divisble by 2). The tricks for divisibility by 2, 3, 4, 5, 6, 8, 9, 10, and 11 are quite well known. However, it seems that when the divisibility tricks are taught, the trick for divisibility by 7 is not mentioned. One explanation given is that no such trick exists. However, the contrary is true, such a trick exists.

First, we will see the trick used to check if an integer is divisible by 7. Note that it only works for integers with 4 digits or more. For numbers smaller than 1000, we can check whether it is divisible by 7 the old-fashioned way — actually dividing the number by 7 and see if the remainder is 0.

Let's say we want to see if a is divisible by 7, where a is an integer having 4 or more digits. If a is negative, remove the negative sign so that a becomes positive. Then we express a in the following form:

where b_i are integers between 0 and 999 and n = floor(log₁₀(a)/3). (In other words, if we start from the left, b₀ consists of the final 3 digits of a, b₁ the 3 digits before that, and so on.)

Let c = b₀ - b₁ + b₂ - b₃ + ... + (-1)ⁿ × b_n. If c is a multiple of 7, then a is divisible by 7. If c is still too large, repeat the process. (We should be able to reduce any number we encounter into a 3-digit number by repeating this process at most twice, as |c| ≤ 999(n + 1). For example, we can reduce a 300-digit integer into an integer with 6 digits or fewer after just one iteration. We will see why the inequality holds later.)

To see if a number is divisible by 13, check if c is divisible by 13 instead of 7.

For example, suppose we want to find out if
a = 444,031,154,930,525,092,999,304,411,100,630,156 is divisible by either 7 or 13.

a has 36 digits, so log₁₀(a)/3 = 11.67. Thus n = 11 and b₀ = 156, b₁ = 630, b₂ = 100, b₃ = 411, b₄ = 304, b₅ = 999, b₆ = 092, b₇ = 525, b₈ = 930, b₉ = 154, b₁₀ = 031, bnd b₁₁ = 444.

So c = 156 - 630 + 100 - 411 + 304 - 999 + 92 - 525 + 930 - 154 + 31 - 444 = -1550.

We can either repeat the process or divide c by 7 and 13 to see if it is a multiple of 7 and/or 13. In this case, we divide c directly. If we divide the c = -1550 by 7 and 13, the respective remainders are both -3. So a is not divisible by either 7 or 13.

(As an aside, the trick to find out if a number is divisble by 37 is similar to the above method — we define c as the sum of b_m's instead of the above definition. If c > 999, repeat the process. Otherwise, multiply the leading digit of c by 111 and subtract the product from c. If the difference is one of -74, -37, 0, 37, 74, then the original number is divisible by 37.)

The factorial of a positive integer n, n! is the product of the first n positive integers. It turns out that there is another (rather surprising) way of finding the number n! for any positive n.

We will first explain method for obtaining n!

1. Set up an array of (n + 1) rows and (n + 1) columns. Let A be the array and A_i,j be the entry in the i-th row and j-th column
2. In the first column, insert the value iⁿ in the i-th row (or A_i,1=iⁿ)
3. In the j-th column, where j=2,3, ..., n + 1, insert the difference between the entries in the (i + 1)-th row and i-th row of the (j - 1)-th column in the i-th row
   (In other words, A_i,j=A_i+1,j-1 - A_i,j-1, i = 1,2, ..., n - j + 1 j=2,3, ..., n + 1)

The number in the first row of the (n + 1)-th column should be the number n!

The following formula is another way of describing the above method for computing n!

The formula below is the general form of the above formula, where m is any non-negative integer.

Note that the above formula are not very useful in practice, as it requires more computations than the naive way of computing n!

At the beginning of a season, the supporters of each team wonder how their favourite team will fare in the upcoming season. While most people hope for a season in which the team emerges victorious in every game, the players, coaches, fans set the number of victories/points the team will gain. This may lead someone (me?) to wonder the number of possible ways a team's record can be at the conclusion of a season. (In the following, assume a team plays n games a season.)

If the table/standing only displays wins and losses, then there are (n + 1) possible combinations of wins and losses. (For any integer i = 0,1,...n, if a team wins i games, it loses n - i games. So we have (n + 1) combinations.)

For leagues where games can end in draws, we can compute the number of win-draw-loss combinations as follows: first assume that a team draws i games in the season, then there are n - i games in which the team wins or loses. Then we can use the argument in the previous paragraph to deduce that there are (n - i + 1) possible win-loss combinations. Now i can be any integer between 0 and n. So the number of possible win-draw-loss combinations in a season in which a team plays n games is

In cases where a game can end in four possible ways, we can compute the number of ways a team's record can appear in the standings as follows: we first name the four possible outcomes A, B, C, and D. Then we assume that the team gets result A in j games. For the remaining n - j games, the result is one of B, C, or D. Using the reasoning for three possible outcomes and the fact that j is an integer between 0 and n, we can see that the number of possible ways a team's record can appear in the final standings is

A multiplicative perfect number n is a positive integer where the product of its (positive) integer divisors is n².

All multiplicative perfect numbers can be expressed as one of the two following forms: p³ or p q, where p, q are distinct prime numbers.

When I was (a lot) younger, a problem was presented to me (and my classmates) during math class. The problem is as follows: n coins is minted. One of them is found to be defective (fraudulent in some versions) and this particular coin weighs less compared to all others. The goal is to find the defective coin using a balance as few times as possible.

To find the one defective coin among n coins, we do the following:

Let k = n and divide the coins into three sets, called sets 1, 2, and 3 such that set 1 has the most number of coins and set 3 has the least number of coins and the difference in the number of coins between any two sets is one or zero. In other words, if j = floor(k/3), then the number of coins in sets 1, 2, and 3 are as follows:

Select two equally-sized sets and place each of one side of the balance. If the balance is level, then the two sets are equal in weight and the third set of coins contains defective coin. The two sets of coins on the balance are discarded. If the balance tilts towards one side, then the defective coin is contained in the set of coins placed on the other side of the balance. The set containing the defective coin is kept while the other two sets are discarded.

Let k = the number of coins in the set containing the defective coin and repeat the process until the defective coin is found.

The maximum number of balance weightings needed, m, using this method is:

The problem here is similar to the one in the previous section, except that this time there are two defective coins among the n minted. The goal is the same as before: to find the defective coins using a balance as few times as possible.

To find the two defective coins among n coins, let k = n and we do the following:

Step 1:Divide the coins into three subsets, named A,B,C, such that there are k = floor(n/3) coins in each subset. If there is any coins remaining (there will be no more than 2), set aside them for now.

Step 2:

1. If all three subsets have the same weight (the balance is level for all three weightings), then the defective coin(s) can be found from the coins set aside earlier.
2. If no two subsets have the same weight, then the heaviest subset of coins contain no defective coin while the other two contain one defective coin each.
3. If two subsets have the same weight while the third subset is heavier, the lighter two subsets contain one defective coin each.
4. If two subsets have the same weight while the third subset is lighter, the lighter subset contains at least one defective coin.

In card games, the deck is shuffled between games so that the cards will not be dealt in the same order. However, if one shuffles perfectly the cards will eventually stacked in the original order. The question is how many shuffles are required for that to happen.

We number the cards in the deck of n cards as follows: the card at the top of the deck is in position 1, the card directly below is in position 2, and so on (the card at the bottom of the deck is in position n).

During a shuffle, a deck is split into two (decks A and B), each consists of exactly half the deck. So deck A consists of cards with positions 1 to n/2 and deck B consists of cards in positions (n/2) + 1 to n.

We define a perfect shuffle as follows: after the cards are shuffled, all cards with odd-numbered positions are from deck A and cards with even-numbered positions are from deck B, or vice versa. The former is called an out shuffle while the latter is called an in shuffle.

For 1 ≤ i < b, where b is a positive integer, let C_i(b) = {2^j i (mod b) | j ≥ 1 }.

The deck would be stacked in the original order after |C₁(n + 1)| in shuffles |C₁(n - 1)| out shuffles.

The problem here is to find out the number of shuffles needed for all the cards in a deck of n cards, where n is odd, to be stacked in the original order.

We number the cards in the deck of n cards as follows: the card at the top of the deck is in position 1, the card directly below is in position 2, and so on (the card at the bottom of the deck is in position n).

Let m = (n - 1)/2. During a shuffle, a deck is split into two (decks A and B), with one consisting of m cards and the other m + 1 cards. After the cards are shuffled, all cards with odd-numbered positions are from deck A and cards with even-numbered positions are from deck B, or vice versa. The former is called an out shuffle while the latter is called an in shuffle. The deck can be split in two ways:

1. Deck A has m cards, containing cards in position 1, 2, ... m, while Deck B has m + 1 cards, containing cards in position m + 1, m + 2, ... n
2. Deck A has m + 1 cards, containing cards in position 1, 2, ... m + 1, while Deck B has m cards, containing cards in position m + 2, m + 3, ... n

So the deck can be shuffled in 4 ways:

1. Deck A has m cards and Deck B has m + 1 cards, each shuffle is an out shuffle
2. Deck A has m cards and Deck B has m + 1 cards, each shuffle is an in shuffle
3. Deck A has m + 1 cards and Deck B has m cards, each shuffle is an out shuffle
4. Deck A has m + 1 cards and Deck B has m cards, each shuffle is an in shuffle

For each of the 4 cases, the cards in the deck of n cards will be stacked in the original order after the following number of shuffles:

Note that if we perform Case 4 shuffles, the number of schuffles needed for the deck to be stacked in its original order may be smaller, but it is always a factor of
(|C₁(n + 2)|, |C₁(n + 2)| - 1).

Suppose n people are playing a game, where they line up in a circle and face the same direction (clockwise or counterclockwise). The players are assigned numbers 1 to n, with player 1 standing behind player 2, who stands behind player 3, and so forth. (So player n stands behind player 1). The game involves people tagging the person directly in front of them and the player being tagged removed from the game. The last player remaining in the game would be the winner. For the players, the natural question is "where should I stand to guarantee victory". (In the following we assume that the game starts with Player 1 tagging Player 2.)

Any even-numbered player has no chance of winning — Player 2 is tagged by Player 1, Player 4 is tagged by Player 3 and so forth.

In a game with n players, let m = floor (log₂ n). Then winner would be player i, where
i = 2n - 2^{(m + 1)} + 1

Suppose you are playing a game with another person. The rules are as follows:

• There are a objects on the table.
• Both players take turns removing objects from the table. In each turn, a player can take 1, 2, &ldots; or b objects for some positive integer b.
• The player taking the final object wins.

The goal, naturaly, is to come up with a strategy which guarantees victory. The good news is that there is one.

Let c = a (mod b + 1). Assuming you pick first, during the first turn, you should pick c objects. For the rest of the game, if the other player picks d objects during a turn, you should pick b + 1 - d objects in your next turn. (So if the other player picks 2 objects in the last turn, you should pick b - 1 objects.)

However, if a is divisible by b + 1 (or c = 0), the player picking second would win by following this strategy. If you pick first you would have to wait until the number of objects remaining is not divisible by b + 1 after the other player's turn.

If the player taking the final object loses and you pick first, you should pick c - 1 objects in the first turn. Then apply the above strategy for the rest of the game. (If c = 1, you should pick second.)

From the above, we can see that you should pick second when c = 0 and the player taking the final object wins; or when c = 1 and the player taking the final object loses. Otherwise you should pick first.

In single-elimination tournaments, teams may receive byes and enter the tournament in later rounds (instead of the first round). If the draw determining the matchups for each round is held individually (ie the teams/competitors do not know who they will face in the next round until the draw for that round is made) and the round consists of teams advancing from a previous round and those entering the tournament at this round (the 3rd round of the English FA Cup, for example), one may ask how likely each team advancing from a previous round is drawn to face a team entering the tournament at the current round. In other words, the round does not feature any matchup between teams advancing from a previous round.

Suppose there are m teams advancing from the previous round and n matches in the current round, the chance that each team advancing from a previous round is drawn to face a team entering the tournament at the current round is

(If m > n, the probability is 1 — it is certain that at least one match will feature two teams advancing from a previous round.)

One may also use this formula to calculate the chance teams from the same country avoid each other in the draw of a specific round of a tournament.

• Combinatorics — Everything I know about Advanced Mathematics I learned from Kindergarten
• Introduction to Combinatorial Optimization
  Subtitle: Big Words 101
• Combinatorial Design and its Applications — from Sudoku to bridge tournamnets
• Group Theory for Shy People
• Graph Matchings with Applications in Dating
• Topics in Ring Theory for engaged couples
• Maple for Backyard Gardeners
• Introduction to the Theory of The Matrix
• Measure Theory for Surveyors
• Lie Algebras — the Truth and Nothing But
• The K-Distribution Revealed
• Student's Guide to Student's t-distribution
• The Buckingham Pi Theorem for Royal Watchers
• Careers in Mathematics: More than Just Teachers
• SAS: Supression of Aversion to Statistics
• SPSS: Study of Phobias in Statistics Students
• Finite Fields — The Infinite Universe
• i — Our Imaginary Friend
• The Greedy Algorithm
  No, it was NOT invented by Al Gore

"2 plus 2 is 4. 2 plus 2 is 4."

A purple dinosaur not named Barney

"1 = 2"

Hong Kong anti-smoking slogan

"Choosing a basis for a vector space is an act of violence."

An University of Chicago professor circa 1989

"The value of π is 10, base root π."

Brett Stevens

"Presentation is a one, talent is a zero. Combined and you have a 10."

Mateja Sajna

"God made the integers, all the rest are the work of man."

Leopold Kronecker

"ASCII and ye shall receive."

Jeffrey Armstrong

"If at first you succeed — try to hide your astonishment."

Harry F. Banks

"The good Lord made us with two ends — one to sit on and one to think with. How well you succeed in life depends on which one you use."

Issac Dworetsky

"A mathematician is a machine for turning coffee into theorems."

Paul Erdos

"Damn it, if the machine can detect an error, why can't it locate the position of the error and correct it?"

Richard W. Hamming

"Have you noticed that there's no attempt being made to find really large numbers that aren't prime? I mean, wouldn't you like to see a news report that says 'Today the CS Department at the University of Washington announced that 2^58111625031+8 is even. This is the largest non-prime yet reported.' "

Bathroom graffiti, University of Washington, circa 1988

"Let bi-gons (lines) be bygones."

Benjamin Steinberg

"I don't know if a rational being governs the universe, but I am sure that a rational being governs the world of mathematics."

Walter Burgess

(After a student asked "what is a matrix?")"A matrix is a rectangular array which contains a number in each entry."
(I got this from memory, so the actual quote may be a little different.)

John Fester (circa May 1999, the time when The Matrix first hit the theatres)

References and Acknowledgments

• Barnet, S. Discrete Mathematics — Numbers and Beyond. Addison-Wesley Longman, Essex, 1998.
• Gallian, J. Contemporary Abstract Algebra, 4th Edition. Houghton Mullin Company, Boston, 1998.
• Koblitz, N. A Course in Number Theory and Cryptography, 2nd Edition, Graduate Text in Mathematics, v. 114. Springer-Verleg, New York, 1994.
• Sandor, J. Multiplicatively perfect numbers, J. Ineq. Pure Appl. Math.. Vol. 2, No. 1, Article 3, 2001.
• Uspensky, J.V. and Heaslet, M.A., Elementary Number Theory, McGraw-Hill, New York, 1939.

The section on sums of powers is based on material presented in the course CO 380 (Mathematical Inventions and Discovery) at University of Waterloo, taught by Peter Crippin, in 2002.