There was recently a discussion on patterns in modular arithmetic, in which the author showed some interesting pictures that result from plotting various functions. They introduced modular arithmetic by the standard appeal to time (an example wikipedia follows too) including the awesome fact that Japan uses neither a 12 nor a 24-hour clock - they will talk about things occurring at 28 o'clock (four AM tomorrow).
I get tired of hearing the same examples as common applications of modular arithmetic, so here's my contribution.
The basic point is that, for some applications, discreteness matters. If you want to divide up $5 among 3 people, and you are writing checks, you can just give each of them a fractional dollar amount. Problems only occur if you have 5 $1 bills and you can't make change.
A common example of this is card games - you frequently want to deal an equal number of cards to everyone and you can't exactly rip a card in half to make it work. Our standard deck has an abysmal 52 = 2*2*13 cards, which means that it's evenly divisible among 2, 4 or 13 players, resulting in our inability to play Hearts with 3 or 5 players.
What you really want is a number with a lot of prime factors, an idea roughly captured by the number's abundance. If our deck had 60 = 2*2*3*5 cards, we could play hearts with two, three, four, five or six players.
This idea occurred to me while playing Clue (apparently known as "Cluedo" outside the US). The game involves taking three cards out of the deck and then dividing the rest among the players. It supports 3-6 players, so finding the optimal number of cards involves finding a number that:
- Has a remainder of three when divided by 3
- Has a remainder of three when divided by 4
- Has a remainder of three when divided by 5
- And has a remainder of three when divided by 6
The solution to this problem can be found using the Chinese remainder theorem which, like all theorems discovered by people with foreign-sounding names, is titled after the discoverer's country (cf. Polish notation). It turns out that the first two solutions are 3 and 63 cards, which would make for either a really short or a really long game of Clue[do].
According to Wikipedia, the original design of the game called for 29 cards which leaves 26 after removing the three to hide in the envelope. The astute reader will see that 26 = 13 * 2, meaning the game could only work correctly if there were two or thirteen players!
Parker Brothers revamped the game to have 21 cards total, leaving 18 to divide among the players. This works out perfectly for three and six players, but leaves a couple extra cards when four or five people play. An improvement to be sure, but better options include 15 and 27 cards, both of which fail to divide in only one case.
Anyway, these are a couple examples of why we you might find the integers interesting. Of course there are many more (virtually every form of modern cryptography springs to mind) but hopefully these are some easy to understand instances.
Thanks for the wonderful advises and tips.
ReplyDeleteAstute Games in Singapore