Permutations and Circular Permutations

Hello everyone! In this post, we will explore permutations and circular permutations. I will be providing example problems with various solutions to approach them! I hope you all enjoy!

We will first start by learning the definition of a permutation.

Permutations:

Let S = {a1, …, an} be a set with n elements. If we arrange the elements of S in order, we get a permutation of S. More generally, if we select r elements from S and arrange them in order, we get an r permutation of S. We’ll use P (n, r) or nPr to denote the number of r- permutations of a set with n elements.

Theorem> P(n, r) = n(n-1)... (n-r+1) = n(n-1)...(n-r+1) [(n-r)(n-r-1)...2*1]/ [(n-r)(n-r-1)...2*1]= n!(n- r)!

        (We are choosing r elements out of n in order. First we have n elements to choose from, then we have n- 1 elements to choose from after choosing element, and after choosing another element, we would have n- 2 elements to select from. If we have to choose a total of r elements, we would end up with the left side of the equation by the multiplication principle.)

Example 1> How many ways can we arrange 5 couples in a row, if the people in each couple are together?

Answer: 5! 2^5 ( 5! Is the number of ways of arranging each of the couples and 2^5 accounts for arranging the people in each couple)

Example 2> Find the number of ways to arrange 6 adults and 4 children in a row if the children must be together.

Solution A> We can consider the 4 children as a single entity and consider each of the adults as a single entity. So in total, we have 7 entities. We would arrange the 7 entities in 7! Ways and within the entity of 4 children, we can arrange the 4 children in 4! ways. By the multiplication principle, the total number of ways would be 7! 4!

Solution B> First, consider the way of lining 6 adults first; this would be 6!. Afterwards, we would be able to place the 4 children in 7 spots (very left, very right, and in between each of the adults would be a total of 7 possible spots). Again, the 4 children can be lined up in 4! ways and by the multiplication principle, the total number of ways would be 6! 74!.

Circular Permutations.

In how many ways can we select r people from a set of n people and arrange them in a circle if all rotations of a given arrangement are considered the same? We can answer this question using the concept of circular permutations. We will denote this case by Q (n, r), the number of circular r- permutations of n objects.

Theorem> Q(n, r) = nPr ( Idea of proof:  P(n, r) = r Q(n, r) since each circular r- permutation corresponds to r regular permutations)

Special Case: Q( n, n)= (n - 1)!

Since Q(n, n) = P (n, n)* n= n!*n= ( n - 1)!

Example 1> Find the number of ways to arrange 6 adults and 4 children in a circle if the children must be together?

Answer: 6! * 4! (6!: number of ways to arrange 7 entities in a circle, 4!: ways of arranging the 4 children).

Example 2> Find the number of ways to arrange 7 people in a circle, if Carol and Tom cannot be together.

Answer: 6! - 5!*2 (6!: Total ways to arrange people, 5!*2: Number of cases in which Carol and Tom sit together)

Example 3> Find the number of ways to seat 5 men and 5 women in a circle, if the men and women alternate?

Solution 1> 4! (ways of seating men) * 5! (ways of seating the women in the gaps)

Solution 2> First seat a women, then there are 4! Ways to seat the other women. Then, the number of ways to seat the men in 5 fixed seats is 5!. Thus with the multiplication principle, the total number of ways to seat the people: 5! * 4!

Solution 3> 5! (pair men and women together) * 4! (arrange 5 entities into a circle).

This is all for today! Please feel free to contact me or comment below if you have any questions :)

Congruence in Modular Arithmetic

Hello! When I hear the word “congruence,” the first thing that pops up in my mind is congruence in geometry. It turns out, however, that there can be congruence in numbers, well specifically in modular arithmetic! In this post, we will explore congruence in modular arithmetic.

Given integers a, b, and n, with n > 0, we say that a is congruent to b modulo n, or a ≡ b (mod n), if the value of (a - b) is visible by n. Two numbers a and b are said to be “congruent to modulo n” if (a mod n) = (b mod n). For example, 73 ≡ 4 (mod 23) since 73 - 23 = 69 is divisible by 23.

    Now that we have an idea about the definition of congruence, we will explore some properties of congruence:

Consider four integers a, b, c, and d and a positive integer m (m >0) such that a ≡ b (mod m) and c ≡ d (mod m). In modular arithmetic, the following properties hold:

1. Addition: a + c ≡ b + d (mod m)
2. Subtraction: a - c ≡ b - d (mod m)
3. Multiplication: ac ≡ bd (mod m)
4. Division: (a/e) ≡ (b/e) {mod m/gcd (m, e)} where e is a positive integer that divides both a and b.
5. Exponentiation: a^e ≡ b^e (mod m) where e is a positive integer
6. a ≡ b (mod n) => b ≡ a (mod m)
7. a ≡ b (mod m) and b ≡ c (mod n) => a ≡ c (mod n)

Some examples of the more advanced properties of congruence relations include the following:

• Fermat's little theorem: If p is prime, then a p – 1 ≡ 1 (mod p) for 0 < a < p
• Wilson's theorem: p is prime if and only if (p − 1)! ≡ −1 (mod p)
• Chinese remainder theorem: If x ≡ a (mod m) and x ≡ b (mod n) such that m and n are co-prime (the only positive integer that divides both of them is 1), then x ≡ b mn–1 m + a nm–1 n (mod mn) where mn−1 is the inverse of m modulo n and nm−1 is the inverse of n modulo m
• Lagrange's theorem: The congruence f (x) ≡ 0 (mod p), where p is prime, and f (x) = a0 xn + ... + an is a polynomial with integer coefficients such that a0 ≠ 0 (mod p), has at most n roots.

This is it for today and I hope you all have a great rest of the day. Also, please feel free to contact me or comment below if you have any questions!

Introduction to Modular Arithmetic

Hello mathletes! In this post, we will be exploring the basics of modular arithmetic. Modular arithmetic is a system of arithmetic for integers, in which numbers "wrap around" upon reaching the modulus (plural moduli). The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

“Modulo n” includes numbers between 0 and n-1. The easiest way to convert numbers in modular arithmetic is by doing Euclidean Division and taking the remainder.

In r = n mod m, we can remove as many multiples of m as possible until we are left with an answer between 0 and m-1. In this case, r would be the remainder and m would be the modulus. So for example, 34 mod 4 = 2 and 19 mod 7 = 5. If n is a negative number, then we add as many multiples of m as needed to have an answer between 0 and -(m-1). Thus, -23 mod 5 = 2 and -78 mod 9 = 3.

Here are some basic properties of Modular Arithmetic:

1> [ (a mod n) + (b mod n) ] mod n = ( a + b) mod n

ex) [(37 mod 6) + (99mod 6)] = 4 mod 6 = 4 and (37 + 99) mod 6 = 136 mod 6 = 4

2> [ (a mod n) - (b mod n) ] mod n = (a - b) mod n

ex) [ (37 mod 6) - (99mod 6)] mod 6 = -2mod 6 = 4 and (37 - 99)mod 6 = -62 mod 6 = 4

3> [ (a mod n)* (b mod n)] mod n = ab mod n

ex) [ (37mod6) * (99mod6)] mod 6 = 3 mod 6 = 3 and (37* 99) mod6 = 3663 mod 6 = 3

Lastly, the set of integers {0, 1, 2, …, n − 1} is called the least residue system modulo n. Any set of n integers, no two of which are congruent modulo n, is called a complete residue system modulo n. It is clear that the least residue system is a complete residue system, and that a complete residue system is simply a set containing precisely one representative of each residue class modulo n. The least residue system modulo 4 is {0, 1, 2, 3}. Some other complete residue systems modulo 4 include {1, 2, 3, 4}, {13, 14, 15, 16}, {−2, −1, 0, 1}, {−13, 4, 17, 18}, {−5, 0, 6, 21} and {27, 32, 37, 42}.

In the next post, we will explore the concept of congruence! Please contact me or comment below if you have any questions and have a great day!

If we replaced our 12 with a 0 in our clock,

the numbers on the clock would show us the way in which we would count in modulo 12.

San Francisco Exploratorium- Buffon's Needle

Today, I visited the Exploratorium in San Francisco. There were various exhibits in the Mathematics section from the parabola- powered calculator to models of various Archimedean solids to the square shaped wheel. One of the exhibits I found interesting was the “Pi(𝜋) Toss,” in which the value of pi would be estimated by tossing chips. I would be given chips and I would randomly toss any number of chips onto the table. According to the instructions, tossing all 22 would be preferable. Then, I had to count how many times the lines on the chips cross the lines on the table and using the calculator, I divided the total number of chips tossed by the number of crossings. This answer would yield an approximation of pi. This value was not very close to pi at first, but with several more rounds of tosses and averaging the results over time, I was able to obtain values closer to the actual value of pi.

    Pi is a famous mathematical constant relating the circumference of a circle to its diameter. More tosses would yield more accurate results; hence, if we were to have the patience to toss chips all day, all week, all year we would obtain an increasingly accurate estimate of pi. This method of calculating pi, also known as Buffon’s Needles, was discovered over 300 years ago by a French mathematician, Count Buffon. Buffon discovered this method in an accident as he had wanted to calculate the odds of winning in a then-popular game of chance, in which one would toss a coin onto a tiled floor and bet on whether it would land entirely within one of the tiles.

Rolle's Theorem and the Mean Value Theorem

Hi everyone! I hope you all had a great weekend. Rolle's Theorem and the Mean Value Theorem are two theorems of Calculus that can seem similar in a way, as they share a common hypothesis. Today, we will explore what these theorems state and examine interesting problems that could be approached with these theorems.

First, let's go over what the theorems state!
1> Rolle's Theorem:
If function f is continuous on the closed interval [a, b], differentiable in the open interval (a, b) and
f(a) = f(b), there exists a number c in (a, b) such that f '(c) = 0.

2> Mean Value Theorem (MVT):
If function f is continuous on the closed interval [a, b] and differentiable in the open interval (a, b), there exists a number c in (a, b) such that f '(c) = {f(b) - f(a)} /( b - a)

Now, let's look at some example problems.

Example 1> Prove that x^3 + x - 1 = 0 has exactly one zero.

Solution> First, we have to use the Intermediate value theorem to prove that there is a zero. For those of us who are not familiar with the Intermediate Value Theorem (IVT), the IVT states that if f is continuous on [a, b] and f(a) < w < f(b), there exists a number c between a and b such that f(c) = w. Let f(x) = x^3 + x - 1. Since f is a polynomial function, it is continuous on its domain (-∞, ∞). Thus f is continuous on [0, 1]. Notice f (0) = -1, f (1) = 1. Thus by the IVT, there exists a number c in (0, 1) such that f (c) = 0. Now, we will use proof by contradiction. Suppose that x^3 + x - 1 has two zeros at a and b. Without loss of generality, let a < b. x^3 + x - 1 is continuous on [0, 1] and since f '(x)= 3x^2 + 1 and this is never undefined, f (x) is differentiable in (0, 1). Since a and b are zeros, f(a) = f(b) = 0. Therefore, by Rolle's Theorem, there exists a number d in (0, 1) such that f '(d) = 0. But, f '(x)= 3x^2 + 1 ≥ 1 and this is a contradiction. Therefore, our hypothesis that f has two zeros were incorrect and therefore we have exactly one zero.

Example 2> Suppose that f(0) = -3 and f '(x) ≤ 5 for all values of x. How large can f (2) possibly be?

Solution> Since f is differentiable in (-∞, ∞), f is continuous in (-∞, ∞), and thus f is continuous on [0, 2]. Therefore, by the Mean Value Theorem, there exists a number c in (0, 2) such that f '(c) = {f(2) - f(0)}/2 = ( f(2)+ 3 )/2 ≤ 5. So, f(2) ≤ 2*5 - 3 = 7. Therefore, the largest f (2) can possibly be is 7.

I just wanted to introduce you all to these theorems and set of questions, because I was intimidated by these proof type questions using these theorems when I saw them. I was confused as of when to use the MVT, IVT, or Rolle's Theorem. Familiarity with the theorems are crucial, and it is important that we remember how to approach each of these problems using the theorems. I hope you all have a great rest of the day and please contact me if you do have any questions.

Mean Value Theorem; for a given arc between two endpoints,

there is at least one point at which the tangent to the arc is parallel

to the secant through its endpoints.

Understanding Early Number Systems

Hi! I apologize for not being able to post for the past few weeks; I was a little busy with all the AP testing, but I hope you all had a wonderful weekend and...
In this post, we will be exploring the basic idea and patterns behind some of the earliest number systems!

The Egyptians and the Babylonians are known to have come up with one of the first number conventions. These conventions often used symbols that represented specific numbers, known as “Nodal numbers.” Other numbers would be formed by grouping nodal numbers together in certain way. This system is known as the “Additive System.”

The Egyptians adopted this system in their number conventions. For example, in ancient Egyptian notation, the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 19, 40 would be represented by:

From this notation, we can observe that 1 and 10 were nodal numbers; 1 would be represented by a vertical dash, while 10 would be represented by a symbol that looks like an upside-down U.

The Babylonians used 1, 10 and 60 as their nodal numbers. The Babylonians used a sexagesimal positional number system, in which the value of a particular digit depends both on the digit itself and its position within the number. It has been proposed that 60 was used as the base number, as 60 = 2^2 x 3 x 5, which makes it divisible by 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, and 30.

Other Fun Facts:

• The Babylonians understood the concept of nothingness, but it was not seen as a number. The Babylonians understood “nothingness” as absence of a number, and thus represented nothingness with a space at first. Later on, a placeholding symbol was used to show the nonexistence of a digit in a certain place value.

This is the placeholding symbol

used by the ancient Babylonians to

represent 0.

• Nodal numbers are also used in Roman Numerals, in which many of us are familiar with. In the Roman number system the nodal numbers are 1, 5, 10, 50, 100, 500, 1000, represented respectively by the signs I, V, X, L, C, D, M. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 19, 40 would be represented by I, II, III, IV, V, VI, VII, VIII, IX, X, XIX, XL in Roman numerals.

I hope you all enjoyed this post, and please contact me if you have any questions!

Sources:

https://www.encyclopediaofmath.org/index.php/Numbers,_representations_of

https://en.wikipedia.org/wiki/Babylonian_numerals

The Shoelace Formula- Example Problem

Hello, in this post we will see a very simple example problem using the Shoelace Formula, a topic about which I posted last time. In this example, we will be finding the area of a triangle given the coordinates of its three vertices. I hope that this example will make the usage of this method more clear for you all!

The Fields Medal

Hello everyone! I think you all have heard at least once about the Fields Medal. Well in this post, I will be sharing information about this very prestigious award!

The Greek mathematician Archimdes (B.C.287~B.C.212) was

engraved onto the medal along with the Latin verse,

"TRANSIRE SVVM PECTVS MVNDOQVE POTIRI."

The Fields Medal is considered one of the most prestigious awards in mathematics; often times, it is viewed as a “Nobel Prize” in the field of mathematics. The Fields Medal is a prize awarded to two, three, or four mathematicians under 40 years of age at the International Congress of Mathematicians (ICM) hosted by the International Mathematical Union (IMU), a meeting that takes place every four years.

The prize comes with a monetary award, which since 2006 has been C$15,000 (Canadian Dollars). This award was named “Fields,” in the honour of the Canadian mathematician and Professor of the University of Toronto, John Charles FIelds, who played a key role in establishing the award, designing the medal, and funding the monetary component.

The medal was first awarded in 1936 to the Finnish mathematician Lars Ahlfors, who was "Awarded medal for research on covering surfaces related to Riemann surfaces of inverse functions of entire and meromorphic functions. Opened up new fields of analysis." and to the American mathematician Jesse Douglas who "Did important work of the Plateau problem which is concerned with finding minimal surfaces connecting and determined by some fixed boundary." The medal has been awarded every four years since 1950.

This medal was created to give recognition and support to younger mathematical researchers who have made major contributions, and the latin words “TRANSIRE SVVM PECTVS MVNDOQVE POTIRI” on the medal means “Exceed above oneself and grasp the world.”

The Shoelace Formula

Hi, today I will introduce you all to the Shoelace Formula, which is also known as Gauss’s Area Formula. This formula would provide a quick and easy way to find the area of a triangle given the coordinates of the triangle. Since this formula would be hard to explain without an appropriate visual, I added in a picture with a diagram of a triangle along with a summary of steps. Make sure you refer to this picture as you read the explanations for each step :)

Step 1: Write down all the x and y coordinates in a manner shown in “Step 1” in the picture. Note that one of the coordinates will have to be written twice. The order in which you list the coordinates do not matter.

Step 2: Starting on the x coordinates, draw an arrow moving down diagonally (depicted with pink lines). Starting on the y coordinates, draw an arrow moving up diagonally (depicted with blue lines).

Step 3: Multiply the pair of values that are tied by a line. For the values that were connected with a pink line, place them in the absolute value without changing their signs and for values that were connected with a blue line, place them in the absolute value with an opposite sign (in other words, add a negative sign).

I apologize if my explanation was a little confusing or vague, but in my next post, I will put up an example and you guys will see how convenient and quick this formula can be in some cases. There are so many different ways to find the area of a triangle. However, when you are only given the coordinates of each vertex, the Shoelace Formula would most likely be the most convenient. For instance, if we tried to use the traditional 1/2 times bases times height, it would be hard to find the height. If we tried to use Heron's formula, we would have to start out by finding the lengths of each sides (which is possible, of course, using the distance formula), which can be very time consuming. In my Calculus class, we approached this same problem using concepts of Calculus; we applied the method of finding area between two curves, and this process to turned out harder and more time consuming. So I hope you all find this method helpful!! Have a great restful day!

Pi Facts

Hey guys! Today I will introduce some interesting facts about Pi (𝝅), an irrational number defined as the ratio of the circumference of a circle to its diameter.

1. 39 decimal places of pi are enough to compute the circumference of a circle the size of the known universe with an error no greater than the radius of a hydrogen atom.
2. “Pi Day” is celebrated on March 14, and the official celebration begins at 1:59 PM, to form 3.14159 when written together with the date.
3. The symbol for pi (π) has been used regularly in its mathematical sense only for the past 250 years.
4. Egyptologists and followers of mysticism have been fascinated for centuries by the fact that the Great Pyramid at Giza seems to approximate pi. The vertical height of the pyramid has the same relationship to the perimeter of its base as the radius of a circle has to its circumference.
5. The first 144 digits of pi add up to 666 (which many scholars say is “the mark of the Beast”). And 144 = (6+6) x (6+6).
6. Pi is also referred to as the “circular constant,” “Archimedes’ constant,” or “Ludolph’s number.”
7. Albert Einstein was born on Pi Day (3/14/1879) in Ulm Wurttemberg, Germany.

I apologize for not being able to post this before Pi Day, but Pi facts are always good to know! I hope you all found these facts interesting as much as I did! Have a great rest of the day!

The Apollonius Theorem

Post 2: The Apollonius Theorem

Hello, I hope you all had a great day! In this post, we will be exploring the Apollonius Theorem, which can be thought of as a special case of the Stewart Theorem. The Apollonius Theorem will relate the length of the median of the triangle to the length of its sides. The Apollonius Theorem states that the sum of the squares of any two sides of any triangle equals twice the square on half the third side, together with twice the square on the median bisecting the third side. So, in other words, c^2+b^2=2(m^2+d^2) in the diagram below. Like the Stewart Theorem, we will prove this theorem using the law of cosines.

<Proof>

b^2=m^2+d^2+2dmcos𝜃  ….①

c^2=m^2+d^2+2dmcos𝜃’ (<= cos𝜃=cos𝜃’ since 𝜃 and 𝜃’ are supplements)

=m^2+d^2 - 2dmcos𝜃 ….②

① + ② yields

b^2+c^2=2(m^2+n^2), which is the Apollonius Theorem.

The Stewart Theorem

Post 1: The Stewart Theorem

Matthew Stewart (1717-1785) was a Scottish mathematician who is known for the publication of his best known work, Some General Theorems of Considerable use in the Higher Parts of Mathematics. This book is best known for “proposition II”, or what is now known as Stewart’s Theorem, which yields a relation between the lengths of the sides of the triangle and the length of a cevian of the triangle.

For those of us not familiar with “cevian,” a cevian is any line segment in a triangle that has one endpoint on a vertex of the triangle and the other on the opposite side. So, for example, medians, altitudes, and angle bisectors are all cevians. So what exactly is the Stewart Theorem?

Theorem: Suppose a, b and c are sides of a triangle. Let d be the length of a cevian to the side of length a. If the cevian divides a into two segments of length m and n, with m adjacent to c and n adjacent to b, then b^2m+c^2n=a(d^2+mn).  Notice, if you were to foil this out, you would get man+dad=bmb+cnc, which can be memorized easily with the mnemonic device, “A man and his dad put a bomb in a sink.”

Now, before we go about proving this theorem, are we all familiar with the law of cosines? If yes great, if not, don’t worry as I will be going over the law of cosines as the proof of this theorem can be seen as an application of the law of cosines.

So let us observe this triangle. The law of cosine states: a^2=b^2+c^2-2bccosA, b^2=a^2+c^2-2accosB, c^2=a^2+b^2-2abcosC

Now that we have reviewed the law of cosines, we will now observe the proof of the Stewart theorem.

In the given diagram, 𝛳 and 𝛳’ are supplementary. Therefore cos𝛳=cos𝛳’. From the law of cosines, we can write

b^2= n^2+d^2-2dncos𝛳’=n^2+d^2+2dncos𝛳 => ①

c^2=m^2+d^2-2mdcos𝛳 => ②

①* m +②* n=b^2m+c^2n=nm^2+n^2m+(n+m)d^2=(m+n)(mn+d^2) =a(mn+d^2), and this equation is the theorem.