NUS Matriculation Number Checkdigit 2

Previously, I described how to calculate the checkdigit of the NUS matriculation number. Unfortunately, the numbering scheme for the matriculation number has changed since the turn of the decade, which means the old calculation method no longer applies.

I have studied the new matriculation numbers (which are prefixed with A) and have managed to reverse engineer the new checkdigit scheme.

Assume the numerical digits of the matriculation number are C1,C2,C3,C4,C5, C6. Take the sum of the digits C1 to C6, and find the modulus (remainder) of this sum when divided by 13.

Compare the remainder with the following table to obtain the checkdigit.

Y	X	W	U	R	N	M	L	J	H	E	A	B
0	1	2	3	4	5	6	7	8	9	10	11	12

Reverse-engineering the checkdigit scheme was easier this time round, for two reasons. First, the ordering of the checkdigits followed that of the earlier scheme, albeit reversed. Second, and more importantly, the checkdigit scheme was of a lower complexity, being a simple sum of the component digits. This I found puzzling, because it actually fails to preserve an important property that was present in the previous scheme.

A checkdigit serves only one purpose: it is a quick way to determine if a given registration number is correctly entered. Taking the remainder of a sum of the component digits allows us to detect if one digit has been wrongly typed; if one digit is mistyped, the checkdigit would be different. Also, if several digits have been mistyped, the error is still detectable, though there is a small chance that the sum of errors just happens to be a multiple of 13 and hence undetectable.

The weakness of taking the modulus of the sum is that it does not allow transposed digits to be detected. For example, if any or all the digits in a registration number were scrambled around, this would be undetectable as the sum of digits would remain the same. A more robust checkdigit scheme accounts for this by weighting each digit position with a different weight, thus allowing for most digit transpositions to be detected.

Transpositions are fairly common when typing strings of numbers, so it is fairly unacceptable for the checkdigit scheme to fail to account for this.

Missing Keys in the Pocket

I have recently encountered an interesting problem online, which requires knowledge of conditional probability to solve.

You leave your apartment groggily one morning, closing the door behind you. Suddenly, you are hit by a terrifying question: Do you have your keys, or are you now locked out?

You stand there thinking about it for a few seconds, before deciding that yes, you probably have your keys, further estimating that 80% of the time, you have them. You also decide that there is an equal chance of your keys either being in your left pocket or your right pocket, and if they aren’t in either pocket then you don’t have them at all.

Slowly, perversely enjoying the sweat, you slide your hand into your right pocket, and find that your keys are not there. What should you now think is the probability that your keys are in your left pocket? 

The answer:

Two-thirds. To solve this without (much) explicit calculation, imagine all the scenarios where your right pocket is empty. 60% of the time, your right pocket will be empty (20% of the time because you forgot the keys, and 40% of the time where you remembered the keys but they were in the left pocket). The given information puts you in this 60%. Of this 60%, 2/3 of the time you actually have the keys. 

Of course, the above could be expressed more elegantly in equations.

Riddles about Pants and Shorts

One day I met four men, only one of whom was wearing purple pants. Each of them made one statement, then left.

A: At least two of us are lying.
B: The purple pants person is lying.
C: Everyone here is lying.
D: Only one of the other people is lying.

Who is wearing the purple pants?

---

On another day, I met another three people, only one of whom was wearing scarlet shorts. They made one statement each, and then left.

A) B wears the scarlet shorts!
B) A wears the scarlet shorts!
C) If B is lying, so am I. If B is telling the truth, so am I.

Who wears the scarlet shorts?

Problems with Friends

A is a friend of B if and only if B is a friend of A.

Problem 1:
There are N people in the world, N > 1. Is it possible for everyone to have a unique number of friends?

---

A person is popular if none of his friends have more friends than him.
A person is a loner if none of his friends have less friends than him.

Problem 2:
In general, are there more loners or popular people?

Page Flipping in the Lecture Halls

One lecturer likes to provide lecture notes consisting of many slides. As it is costly to print out that many number of pages, most students fit multiple slides onto a single page to reduce the number of pages needed.

A useful consequence of fitting multiple slides on one page is that one only needs to flip the page every X slides, where X is the number of slides on one page. This itself leads to the interesting phenomenon of there being a loud series of page flipping sounds every X slides, since most students need to flip the page to get to the next slide.

One day, I fell asleep during the lecture. I was awoken by the sound of page flipping. Apparently, the lecturer had just advanced past a slide. No worries, time to pay attention. The lecturer continued to teach, and slowly finished two more slides. Another loud series of page flipping sounds echoed through the lecture hall. Then he taught another slide, and when he was done many students began flipping their pages as well.

Glancing about myself, I suddenly realized that students tended to fit 4, 6, and 9 pages onto a slide. And, knowing that the lecturer had not taught past slide 50, I was able to deduce which slide the lecturer was on when I woke up.

Measuring the Volume of a Container

My sister was packing for an overseas vacation when she found herself with a small bottle of hand moisturizer. Unfortunately, she was uncertain as to whether the bottle was of a size within the travel limits, which was 100ml. My assistance was sought.

The first and probably the most commonsensical solution I came up with was to compare the size of the bottle with other containers of known capacity, such as my water bottle which has 100ml markings. But this method was unsatisfactory as the precision was poor.

I then suggested to fill the bottle with water, and to then measure the amount of water contained. However, this too was unfeasible, since the container already contained some moisturizer.

Being trained or born with scientific and mathematical thinking, I then came up with a most intelligent approach. First, I observed that the container was almost a perfect cylinder. Thus, using a ruler and the simple volume formula, I was able to calculate that the container was almost certainly a 100ml container.

Basic mathematical knowledge proves to be useful to daily life.

In retrospect, a fourth solution is possible, but this is rooted in more science. We can simply immerse the container in a beaker of water such that it is fully submerged. Then, the volume of the container is simply the amount of water displaced. This solution is clearly generalizable to all shapes of containers, assuming they are watertight.

Sweets Sharing Puzzle

Two kids (who are not goats), Alice and Bala, have 100 sweets to share between themselves. However, they cannot agree on how to split the shares. Because of their arguing, a random authority figure arrives to impose order. The authority figure demands for Alice to make a sharing proposal (in the form of a sweet split) to Bala, who then has the choice to accept the proposal or not. If Bala does not accept the proposal, he can then make a counter-offer to Alice. This process of offering and counter-offering proceeds back and forth until a proposal is accepted. However, the authority figure, for his troubles, will levy a "friendliness tax" of 20 sweets each time a proposal or counter-proposal is rejected, thus reducing the number of sweets to be shared.

Now, assuming that both Alice and Bala are perfect logicians, and that their aim is to maximize their sweets, what sweet split would Alice make as her first proposal?

Most Used Digits

What are the most commonly encountered numerical digits? On first thought, it does not seem that any particular digit ought to be favored, as numbers seem to be randomly distributed; however, in fact some digits are more common than others.

I recently took a photograph of a used calculator lying around in my house, which should provide an instructive insight into the answer.
The wear patterns on the calculator suggest that the lower digits are used more often, in particular 0 and 1. Possible explanations for this distribution include Benford's law, which proposes that if one compiles several sources of real world data, the most common leading digit is 1; whereas for 0, it may appear often after rounding to a significant figure.

PS: I also wonder whether people would be capable of immediately determining the digit configuration if all the digits were non-visible due to wear.

More Tests?

If the aim of assessment is to assess the true ability of a student, then from a statistical point of view, it is better to have more small tests rather than a single big exam.

First, assume that we are using some consistent estimator of a student's ability. The natural conclusion of this assumption is that the more tests we conduct, the more likely it is that the estimate will be close to the true value.

The argument is also intuitive; with more elements of assessment, the impact of a "freak event" that affects student performance is greatly reduced. The result is hence more likely to reflect the true performance of the student, and is fairer due to the reduced role of luck.

Proofs of Arithmetic Progression

Challenge:

Find as many proofs of the arithmetic progression; i.e. prove 1 + 2 + 3 + 4 + ... + n = 0.5 * n * (n + 1)

I have thought of four proofs, as detailed below.

---

Proof 1: Proof by Pairing

We pair the first and last elements, then the second first and second last elements, and so on. Each pair will have the same sum, since the earlier element gains 1 while the later element loses 1. Now, divide any pair by half. If there are even number of elements, all elements will be paired, and since each pair is the same, the average is found by diving any pair by half. Now, if there are odd number of elements, the remaining element, lying in the center of the sequence, will have the same value as the half of any pair, and this also yields the average.

Having the average, the sum can be found by simply multiplying by the number of elements, which is n. Hence,

Sum = 0.5 * (first element + last element) * (number of elements)
==> Sum = 0.5 * (n + 1) * (n)

---

Proof 2: Proof by Mathematical Induction

Suppose that the sum for a sequence (1 + 2 + ... + n) is equal to 0.5 * n * (n + 1) for some value of n = k.

Then, for the sum of a sequence (1 + 2 + ... + (k +1)), we have:
Sum = (1 + 2 + ... + k) + (k + 1)
==> Sum = 0.5 * k * (k + 1) + (k + 1)
==> Sum = 0.5 * (k + 2) * (k + 1)

Hence, if the identity is valid for n = k, it is also valid for n = k+1.

Now, consider n = 1.
Sum = 0.5 * (1) * (1+1) = 1.
Hence, it is true for n=1 ==> true for all n.

---

Proof 3: Proof by Square

Consider the following image.

A (n+1) by (n+1) square can be broken up into three pieces; n + 1 unit squares, and two arithmetic progressions of (1 + 2 + ... + n). Using this relation,

(n + 1) ^ 2 = (n + 1) + 2 * Sum
==> Sum = 0.5 * ((n + 1) * (n + 1) - (n + 1))
==> Sum = 0.5 * (n) * (n + 1)

---

Proof 4: Proof by Triangle

Consider the following image.

A triangle of base (n+1) and height (n+1) can be obtained from an arithmetic sequence of of (1 + 2 + ... + n) by adding n + 1 triangles of 0.5 unit area. Using this idea,

Sum = o.5 * (n + 1) * (n + 1) - 0.5 * (n + 1)
==> Sum = 0.5 * (n) * (n + 1)

---

I hope that you have found this exercise to be entertaining.

Coin Problems

You have pennies (1c), nickels (5c), dimes(10c), quarters (25c), and half-dollars (50). Solve the following problems:

a) Choose a combination of exactly 100 coins such that the total sum is exactly $5. There must be at least one of each coin.

b) Choose a combination of exactly 100 coins such that the total sum is exactly $5. There must be at least two of each coin.

c) Choose a combination of exactly 100 coins such that the total sum is exactly $5. There must be at least three of each coin.

d) Choose a combination of exactly 100 coins such that the total sum is exactly $10. There must be at least one of each coin.

Note: For some of the problems, there are multiple possible solutions. It is possible to arrive at a solution by trial and error. However, the ideal way of solving this exercise is to discover a method to solve all the above problems in a less tedious manner than trial and error. =)

Blood and Bags

A medical helicopter has a special compartment for carrying blood bags; in particular, the compartment can carry 4 blood bags of any capacity.

Now, the maximum amount of blood needed for any heli-rescue mission is 4.95 units; any more and the patient is already beyond the capabilities of the medical crew. Considering this, it is wise for the helicopter to carry not more than 4.95 units of blood.

Another problem faced is blood wastage. Since blood transfusions involve connecting the blood bag to the patient, the blood in each used bag is 'contaminated' and cannot be reused for other transfusions. Hence, using a 4.95 unit bag for an patient that requires only 0.50 units of blood is discouraged, since 4.45 units of blood are not used and wasted. However, unopened bags can be reused for subsequent missions and are hence not wasted.

Considering the above, it is desired to choose some capacity for each of the 4 blood bags such that the amount of blood wastage in the worst case is minimized. It is assumed that the flight doctor is capable of accurately determining the exact amount of blood needed for transfusion before the transfusion takes place.

What are the capacities of the 4 blood bags?

Prisoners and Boxes

In a certain despotic nation, there are many prisoners being jailed. To alleviate the problem, the Emperor has decreed for all the prisoners to be "removed". What is decreed must be done; however the person doing the actual work is the High Jailer.

The Jailer thinks that the cost of bullets to execute everyone is too high, so he offers the prisoners the chance to earn their freedom. He proposes a game. There are X boxes in a room, with each box having the name of one unique prisoner. Since there are X prisoners, each prisoner's name is found in one and only one box.

The game is as follows: Each prisoner will be allowed to enter the room one at a time. The prisoner can then open all but one of the boxes; however, if the unopened box contains his name, everyone will be executed. If he does find his name in the opened boxes, he must restore the room to its original condition and leave the room. The prisoner will not be allowed to communicate to any prisoners that have yet to enter the room. If after all the prisoners have visited the room and found their names, they will all be released.

Needless to say, the boxes are arranged randomly. Still, each prisoner has a fairly good chance of finding his name; there is only a 1 / X chance of failing outright.

One of the prisoners, who is an amateur mathematician, remarks that the chance of everyone surviving is ( (X - 1) / X ) ^ X . He notes that by applying limits and using l'Hôpital's rule, the chance of surviving will increase with X, reaching e^-1 (0.368) when there are infinity prisoners. Not too bad a chance, he thinks.

At this point of time, another prisoner, an expert mathematician, speaks up and claims to have a better strategy! He shouts, "Why, with my plan, it is almost certain that we'll all survive!"

What is the mathematician's plan, and what is the chance of survival?

---

Note: This problem was derived from The condemned prisoners and the boxes, but the solution for our problem is more easily obtained.

Estimating NUS EE Statistics II

Since my last post I did a more accurate count on the actual numbers, and the result is sufficiently different for me to revise my previous statistics.

The actual data is:
12.7% - First
28.9% - Second Upper
28.6% - Second Lower
10.7% - Third
19.1% - Pass

Using this new data and the previously described method, the new statistics are:
µ = 3.812
σ = 0.611

This puts me at about the 80th percentile of EE graduates in this cohort. The new data also portrays the Second Lower degree a lot better than previously suggested, though it still means that a person with a Second Lower is likelier to be below average than above average.

Note that however the normal distribution is less good fit with this new data. A better statistical fit may need to be found.

Estimating NUS EE Statistics

The NUS commencement booklet has much data, including the names and honors classification of each graduate in the cohort. Privacy issues aside, this vast amount of data can be put to some use.

Doing a very rough count of the number of graduating EE students in each honors class, I found the following numbers: 15% First, 30% Second Upper, 30% Second Lower, 10% Third, 15% Pass. Coupled with the additional knowledge of the CAP requirement to obtain these honors classifications, I was able to obtain an estimate of the statistics of the NUS EE cohort.

First, I assumed a normal fit for the CAP distribution. Combining this with the known honors distribution, I was able to obtain a series of equations, like 0.15 = P(X > 4.5) , which represents the First Class degrees. These equations are made normal by assuming two parameters, µ and σ.

Of course, the linear system yields no solution. Hence, it is necessary to find the best fit for the linear system, such as via linear least squares. I used an applet for this task, arriving at the values of µ=3.884 and σ=0.626. In other words, the mean CAP for an ECE graduate is 3.884 while the std. dev is 0.626.

Now, all this seems pretty useless, with one exception. Using the normal statistics, I was able to compute the percentile that I was at, given the knowledge of my CAP at graduation. This should be a computation that anyone with a basic knowledge of statistics can perform.

Sharing Communities and Upload Ratio

Bittorent file sharing communities are set up such that files can be shared more efficiently ; selfish agents that download but do not upload can be detected by their poor upload ratio and banned from the community.

It becomes absurd, however, when the minimum sharing ratio is set to a figure greater than 1. Since each uploaded byte must correspond to a downloaded byte, if someone has upload ratio greater than 1, then someone must have downloaded more than uploaded. If an altruist is defined as being an agent with a sharing ratio of greater than 1, then it is clear that any closed community of agents cannot be solely comprised of altruists.

If however the sharing rule is temporarily waived for new agents, say for the first week, then it is possible for everyone to be altruistic, barring new agents. However, this requires a continuous stream of new agents joining the community, which is unfeasible in the extreme run.

Children and Daughters

Here are two interesting problems for you.

Problem 1:

I have 100 children. The oldest 99 are girls. What is the chance that I have 100 daughters?

Show Answer

The answer is 1/2. Quite obvious, really.

Simple, no? Now for the next problem.

Problem 2:

I have 100 children. At least 99 of them are girls. What is the chance that I have 100 daughters?

Show Hint 1

No, the answer is not 1/2. Try again.

Show Hint 2

Use conditional probability to solve the problem.

Show Answer

The answer is 1/101. Compute this by finding P(A|B), where event A is having 100 daughters, and event B is having at least 99 daughters.

A fun problem, though I didn't really get it right instantly too.

Divisiblity Tests

I describe a method to generate a divisibility test for the divisor 13.

For a dividend B, express B in terms of its digits, i.e,
B = 10X + Y , where Y is the ones digit and X are the digits left of Y.

Working in modulo 13, if B is divisible by 13, then
10X + Y ≡ 0 .

We then propose a divisibility test that uses X and Y to check the divisibility. We propose
X - KY ≡ 0 ,
meaning that we subtract K times Y from the X digits and test whether 13 divides it.

Manipulating and substituting,
10KY + Y ≡ 0 => (10K+1) ≡ 0 .

Solving the equation, we obtain a value of K = -4. Hence, to test whether a number is divisible by 13, we take the ones digit, multiply it by 4 and add it to the digits on the left. If the result is divisible by 13, then the number is divisible.

To demonstrate the use of the test, let us test the numbers 1234, 2468, and 1781. For 1234, 123 + 4*4 = 139, which is clearly not divisible by 13. Hence, 1234 is not divisible by 13. For 2468, 246 + 4*8 = 278. We can recur the test, 27 + 4*8 = 59, and hence 2468 is not divisible by 13. Lastly, for 1781, 178+4 = 182, 18 + 4*2 = 26. Hence, 1781 is divisible by 13.

The method for generating the divisibility test is general, and can be extended to other numbers. However, for larger numbers, it might be necessary to compute the tens and hundreds digits (and increasingly higher powers of ten), so it might not be feasible for very large numbers.

As a last note, divisibility tests are useful for trivial tasks such as prime factorization using your head.

Factoring on the Go

Yesterday, I started factoring numbers. Apart from being a method to make waiting less mundane, it also works the brain.

I managed to factor the numbers from 1 to 100 while waiting for my bus to arrive. This would have been a minor feat, were it not for the absurd frequency of the bus service.

I also managed to factor 638 before 6:39pm. After more practice, I hope to be able to perform faster factoring.

Good-Enough Random Number Generators from Complex Systems

Given a sufficiently complex system, it might be possible to create a good-enough random number generator.

Of course, the definition of a complex system is lacking. In my usage, a complex system is one where it is extremely difficult to predict the next state of the system, as there are too many variables to consider. Such systems tend to exist in the real world, where there are many chaotic factors.

In particular, I believe that something that is inadvertently created by many users is considerably complex. For example, the number of web users online, or the number of students on campus at any moment, are both figures that are complex and difficult to predict.

One possible way to implement a good-enough random number generator from a complex system is as follows:

Using a number (for example, three) of seed words, google the seed words. Access the first document of the results, and analyze the document. Use the total number of words in the document, modulo by a small base, as the random number.

For repeated number generation, take the fourth, first, and fifth most frequent terms of the document as seed words for the next query, following the same procedure for repeated searches.

While it is possible that the same seed words would appear after some number of searches, the dynamic nature of the web (documents continuously being created and destroyed), the results would vary from search to search. Furthermore, the Google server being used might vary from time to time too.

Such a random number generator would be difficult to analyze and to predict the results of. However, it might be possible to control the results if the adversary were to be able to control the first seed words. For example, a search for a set of hapaxes would lead to a single document result, which could be planted by the adversary. Subsequent results could then be controlled in the same manner.

It would be interesting, though, to analyse the statistical qualities of such a random number generator. If any patterns were discovered, it could be indicative of a sort of pattern in online documents/search engines.

PS: The numbers in the random number generator are actually "nothing up my sleeve" numbers. They are the digits of PI. In base ten, of course.