Aviso: Si quieres contribuir y no estás aún registrado, por favor, crea una cuenta. Si ya estás registrado y deseas seguir contribuyendo, podrás hacerlo si has confirmado tu dirección de correo; por favor, accede con tu usuario y contraseña y ve a Especial:Preferencias. Si lo haces, todas tus ediciones serán atribuidas a tu nombre de usuario, además de disponer de otras ventajas. Muchísimas gracias por tu colaboración.
Warning: If you want to collaborate and you are not joined the Epistemowikia yet, please do not hesitate to create an account. If you are already a registered user and you wish to continue sharing your knowledge, you may, provided that you confirm your email, do it; please, log in with your username and password and browse to Special:Preferences. If you do this, your edits will be attributed to your username, along with other benefits. Thank you very much for your collaboration.

Epistemowikia

Epistemowikia:Proyecto de aprendizaje/Discrete and numerical mathematics

De Epistemowikia
Saltar a navegación, buscar
Discrete and numerical mathematics
Free learning project.
(Free as defined in Freedomdefined).

Fundamentals

  • Logic
  • Sets[TI], relations[TI] and functions[TI]
  • Cardinality
  • Sequences[TI] and sums[TI]
  • Matrices[TI]

Numbers and numericals

  • Algorithms[TI]
  • Number theory
  • Induction[TI] and recursion[TI]
  • Verification[TI]
  • Computability[TI]
  • Numerical Algebra and Calculus

Counting, recounting and discrete non-wild guessing

  • Combinatorial theory
  • Discrete probability[TI]
  • Recurrence relations
  • Stochastic processes[TI]

Visualizing relationships: graphs, trees and networks

  • Algebraic structures[TI]
  • Graphs
  • Trees
  • Networks
  • Game theory[TI]
  • Optimization[TI]
[TI] = Transversal issue.
The School of Technology (Escuela Politécnica, EPCC) of the University of Extremadura at the Campus of Cáceres, Extremadura, Spain.


The learning community of the course 'Further Mathematics' at the School of Technology (Escuela Politécnica, EPCC) of the University of Extremadura, in Cáceres, hopes to contribute to the English Wikipedia through this university project.

Contenido

Rationale

It is our aim with this project to contribute to that the so-called evaluation or assessment stops from being a mere measuring instrument of the extent to which students have assimilated the contents received, and it becomes a learning experience, being able of bringing to light, capacities, abilities, attitudes and values that have been intrinsic, reinforced or acquired during the learning process. At the same time, it puts to the test their understanding skills, their abilities to practical work and their creativity, reinforcing the capacity of assuming social responsibilities and the interpersonal and civic competences. In particular, the main elements linked to learning that are strengthened are:

  • Peer learning
  • Sharing and giving
  • Research skills
  • Technical and communication skills
  • Cooperating and collaborating
  • Critical thinking
  • Collaborative problem solving
  • Individual responsibility
  • Socialization
  • Working and processing in teams
  • Knowledge transfer to society

Work schedule

Type and minimum number of contributions

Each student has to do a minimum of four major contributions to the English Wikipedia. These contributions must have to do with discrete or numerical mathematics and students must do at least one contribution per each header topic: «Fundamentals», «Numbers and numericals», «Counting, recounting and discrete non-wild guessing» and «Visualizing relationships: graphs, trees and networks».

Each of these contributions would focus on one or more of the following activities:

  1. Contributing to existing articles.
    After relevant articles to be worked have been found, student would focus their contribution on one or more of the following activities and targets:
    1. Expanding and improving articles.
    2. Critical analysis of existing articles (on the talk page of the article).
      (Respect what the community of the English Wikipedia indicates on the help page about using talk pages and in the talk page guidelines).
    3. Adding examples and case studies.
    4. Adding theoretical and practical applications and cases of use, specially in the field of Science, Technology and Society [STS].
    5. Adding notes, references, bibliography, inner links, external links and multimedia content (photos, illustrations, videos).
    6. Conceptual correction.
    7. Style correction.
    8. Improving an article to be exported to the English Wikipedia and getting it to be highlighted.
      (Read what the community of the English Wikipedia considers a good article and a featured article).
    9. Translating articles.
      (Respect what the community of the English Wikipedia indicates on the help page about translation).
  2. Creating new articles.
    After the topic choice and the related English Wikipedia contents review have been made, student could choose to create a new article.

In all cases, respect what the community of the English Wikipedia indicates on the page about writing better articles — that, specifically, includes direct links to the help page on editing (how to edit a page) and to the manual of style —.

Due dates

  • Monday, February 6, 2017: Beginning date of the academic component in the 2nd semester of the academic year 2016-2017.
  • Thursday, February 9, 2017: You should have joined the Epistemowikia, if not yet, and become familiar with it, specially with edition — for this to happen you can take its help page (in Spanish) as a starting point —.
  • Tuesday, February 21, 2017: Due date for having joined the English Wikipedia, if not yet, and for having chosen the articles of which you become responsible (two highly recommended starting points to address this issue would be the Logic portal and the Thinking portal).
However, from the moment it is clear to you, you can join the list at the English Wikipedia and start to work there.
  • Thursday, April 6, 2017: You should have continually published the public part of a first self-report about what you have developed up to that moment, on your logbook and on the project contributions page.
  • Thursday, May 11, 2017: You should have continually published the public part of your self-report including all you have done, on your logbook page and on the project contributions page.
  • Friday, May 19, 2017: Ending date of the academic component in the 2nd semester of the academic year 2016-2017.
  • Important: It is worth noting that Epistemowikia and Wikipedia are public, free and open wiki sites, therefore out of that date range the project stays open for ever.

Dynamic obligations

While the project is active, each student is required to:

  • develope all their contributions in accordance with the quality criteria of the English Wikipedia;
  • monitor the comments and the edits to their articles;
  • update their logbook as they work on their contributions;
  • collaborate with the rest of the students by reading and reviewing their work and helping them as much as possible.

Starting on Epistemowikia

We use Epistemowikia to develop our major contributions until they reach the minimum standard required by the English Wikipedia.

Some of the following lines are shared by both Epistemowikia and Wikipedia, and what is more, both sites are similar in many of them.

  1. If you want to collaborate, you have to join the Epistemowikia.
    1. First, create an account.
    2. After doing that, your email must be confirmed. To do that, please log in with your username and password and go to your preferences page and follow the directions from there. If you do this, your edits will be attributed to your username, along with other benefits.
  2. You could modify, in accordance with your wishes, your preferences.
  3. On your personal preferences page, you must activate the following three options:
    [X] Enable email from other users
  4. [X] Email me when a page or a file on my watchlist is changed
    [X] Email me when my user talk page is changed
  5. Here is your watchlist. You must include the course forums in it. You can, for instance, edit your raw watchlist including the following page names:
    Epistemowikia:Plan de aprendizaje/Ampliación de Matemáticas - Further Mathematics/Actividades/Foros/Noticias, Actualidad y Ocio - News, Current Events and Leisure
    Epistemowikia:Plan de aprendizaje/Ampliación de Matemáticas - Further Mathematics/Actividades/Foros/Cafetería - Cafe
    Epistemowikia:Plan de aprendizaje/Ampliación de Matemáticas - Further Mathematics/Actividades/Foros/Foro AM-FM - Forum AM-FM
    Epistemowikia:Plan de aprendizaje/Ampliación de Matemáticas - Further Mathematics/Actividades/Foros/Metodología-Evaluación - Methodology-Assessment
    Epistemowikia:Plan de aprendizaje/Ampliación de Matemáticas - Further Mathematics/Actividades/Foros/Trabajos Fin de Asignatura - Term papers
    Epistemowikia:Proyecto de aprendizaje/Matemática discreta y numérica
    Epistemowikia:Proyecto de aprendizaje/Discrete and numerical mathematics
    Thus, as 'Email me when a page or a file on my watchlist is changed' option is checked, you will be emailed every time a message is posted to any of these forums.
    Note: Observe that, at any time, you can include a page into your watchlist simply checking the star that appears near the 'View history' tab.
  6. Join the project on this dedicated page.
  7. Include your major contributions to the project on this common dedicated page.
  8. Any person can watch the list of all your contributions easily on Special:Contributions. Although anyone interested could follow your dedication to the project, you should highlight your major contributions on a personal dedicated page. This must be a subpage of your user page, that you will use as a public, free/libre and open logbook in which you will write down every and each of your contributions (that is, what is finished, what is being depveloped and what still has not started, including reference dates). You can easily create your logbook page, just browse to the following address, replace 'myusername' with your user name and push 'Enter':
    http://cala.unex.es/cala/epistemowikia/index.php/Usuario:myusername/Logbook
  9. Although there is a test page, it seems reasonable that you have a personal one (similar again, browse to the following address, replace 'myusername' with your user name and push 'Enter'):
    http://cala.unex.es/cala/epistemowikia/index.php/Usuario:myusername/sandbox
  10. Important:
    1. On Epistemowikia, mathematical formulas are represented using MathML (through a third-party Mathoid server). If, at some point, you see an error message instead of the formula, browse to your appearance preferences page where you can check the PNG option instead (the first option).
    2. If you make a minor edition, please check that option before saving the page. Doing this you indicate the community that the change made is not an essential change. On the other side, it generates a smaller load on the data base.

On the English Wikipedia

All of the above, although they may lead to parallel but different contributions to Epistemowikia (for example, because of the social point of view), has served as a training ground for effective contributing to the English Wikipedia.

  • Create an account, if you do not have one yet.
  • After doing that, your email must be confirmed. To do that, please log in with your username and password and go to your preferences page and follow the directions from there. If you do this, your edits will be attributed to your username, along with other benefits.
  • You could modify, in accordance with your wishes, your preferences. For instance, on your personal preferences page, you must activate the following three options:
    • [X] Enable email from other users
    • [X] Email me when a page on my watchlist is changed
  • Here is your watchlist.
  • Join the project on this dedicated page.
  • Include your major contributions to the project on this common dedicated page.
  • Any person can watch the list of all your contributions easily on this page. Although anyone interested could follow your dedication to the project, you should highlight your major contributions on a personal dedicated page. This must be a subpage of your user page, that you will use as a public, free/libre and open logbook in which you will write down every and each of your contributions (that is, what is finished, what is being depveloped and what still has not started, including reference dates). You can easily create your logbook page, just browse to the following address, replace 'myusername' with your user name and push 'Enter': https://en.wikipedia.org/wiki/Usuario:myusername/Logbook (precisely, this one is the page that will host your self-report).
  • Your test page is one subpage of your user page, called Sandbox.
  • If you make a minor edition, please check that option before saving the page. Doing this you indicate the community that the change made is not an essential change. On the other side, it generates a smaller load on the data base.
  • If you wish to create an article and you are not sure of how to proceed, you should use the article wizard.
  • Remember, the project main page on the English Wikipedia is: Wikipedia:School and university projects/Discrete and numerical mathematics

Self-report

In all cases, every and each student must continually write, keeping up with the developing of their work, a self-report, on their logbook, about the whole of their contribution to the project and justify the relationship with the four heading topics. A simple format could be:

Private part:

Student (name and surname): __________
Username on the English Wikipedia (username and URL locator of their user page): __________
Comprehensive assessment of all the work done: __________

Public, free/libre & open part (it will be a copy on Epistemowikia): __________

Username on the English Wikipedia (username and URL locator of their user page): __________
Major contributions to the English Wikipedia (page titles and their URL locators): __________
Other contributions to the English Wikipedia: __________
Comprehensive summary of all the work done, justifying their relationship with the four heading topics: __________

Learning university project on discrete mathematics and numerical analysis: learning paths on Wikipedia

Considerations

Examples of exam (self-assessment mock exams) and some solutions

Important note: In an exam, both theoretical (including proofs of theorems) and practical questions about all topics worked out in class may be asked. In no case, the concreteness of the questions within the context of these examples, implies a course content cut.

Part 1: Themes 1 and 2

Example of exam, 1

Maximum time: 2 hours.

Question 1. (2.5 points)
With the help of propositional logic, prove that the following argument is valid or not. "This program will compile whenever we have declared the variables. Mind you, we will declare the variables precisely if we do not forget to do it. It turns out that the program has not compiled. Therefore, we have forgotten to declare the variables."
Important: Do not do it using truth tables.

Solution:
You can check the complete solution through semantic tableaux of a typical example in this document (in Spanish, for the time being).

Question 2. (2.5 points)

  • (a) Propose three sets A, B and C, such that A \in B, B \in C and A \notin C. (0,5 points).
  • (b) According to a survey of a certain group of students, they said that, if they had to decide between two courses, equally interesting because of their contents, they prefer that one for which the time they dedicate to study it is the lowest and for which they foresee the best results in exams. In case of equality of study times and of exam results forecasts, they are indifferent to them. Study the properties of this binary relation. (2 points).

Question 3. (2.5 points)
Find a possible general formula for computing the nth term, that is, a_n, of the sequence a_1 = 1, a_2 = 2, a_3 = 4, a_4 = 7 using the Newton's divided differences interpolation polynomial.

Solution:
Because of custom and maybe tradition we begin considering n = 0, and so we start dealing this question with b_0 = 1, b_1 = 2, b_2 = 4, b_3 = 7 and then adjust to match what was required. Let f(n) be b_n. Then, the table of divided differences is:

{\displaystyle 
\begin{array}{cc|ccc|cccc|cc}
i & j & x_i & f(x_i) & f(x_i,x_j) & i & j & k & l & f(x_i,x_j,x_k) & f(x_i,x_j,x_k,x_l) \\
\hline
0 &   & 0 & 1 &   &   &   &   &   &     &   \\
0 & 1 &   &   & 1 &   &   &   &   &     &   \\
1 &   & 1 & 2 &   & 0 & 1 & 2 &   & 1/2 &   \\
1 & 2 &   &   & 2 & 0 & 1 & 2 & 3 &     & 0 \\
2 &   & 2 & 4 &   & 1 & 2 & 3 &   & 1/2 &   \\
2 & 3 &   &   & 3 &   &   &   &   &     &   \\
3 &   & 3 & 7 &   &   &   &   &   &     &   \\
\end{array}
} where: {\displaystyle 
\begin{align}
f(x_i,x_j) &= \frac{f(x_j) - f(x_i)}{x_j - x_i} \\
f(x_i,x_j,x_k) &= \frac{f(x_j,x_k) - f(x_i,x_j)}{x_k - x_i} \\
&\;\;\vdots \\
f(x_0,x_1,\ldots,x_n) &= \frac{f(x_1,x_2,\ldots,x_n) - f(x_0,x_1,\ldots,x_{n-1})}{x_n - x_0}
\end{align}
} The interpolating polynomial is: {\displaystyle 
\begin{align}
f_n(x) = f(x_0) &+ (x - x_0) f(x_0, x_1) \\
                &+ (x - x_0) (x - x_1) f(x_0, x_1, x_2) \\
                &+ \cdots \\
                &+ (x - x_0) (x - x_1) \ldots (x - x_{n-1}) f(x_0, x_1, \dots, x_n)
\end{align}
} as well as in recurrence form: {\displaystyle 
f_n(x) = f_{n-1}(x) + (x - x_0) (x - x_1) \ldots (x - x_{n-1}) f(x_0, x_1, \dots, x_n)
} Thus:

  • f_0(x) = f(x_0) = f(0) = 1, that is satisfied by x_0, but no longer by x_1 since f_0(x_1) = f_0(1) = 1 \neq 2 = f(1).
  • f_1(x) = f_0(x) + (x - x_0) f(x_0, x_1) = 1 + (x - 0) \cdot 1 = 1 + x, that is satisfied by x_0 and x_1, but no longer by x_2 since f_1(x_2) = f_1(2) = 3 \neq 4 = f(2).
  • f_2(x) = f_1(x) + (x - x_0) (x - x_1) f(x_0, x_1, x_2) = 1 + x + (x - 0) (x - 1) \cdot 1/2 = 1 + \frac{x}{2} + \frac{x^2}{2}, which is satisfied by all of the points, even by x_3 since f_2(x_3) = f_2(3) = 7 = f(3).
  • The next difference is zero, which confirms that the interpolating polynomial, suggested by this method, is a second degree polynomial:

{\displaystyle 
f_2(x) = 1 + \frac{x}{2} + \frac{x^2}{2}
}

In summary, starting with n = 0, the general term is b_n = 1 + \frac{n}{2} + \frac{n^2}{2}, and adjusting to match the n = 1 beginning as required, the general term is: {\displaystyle 
a_n = 1 + \frac{n-1}{2} + \frac{(n-1)^2}{2}
} Sol.: a_n = 1 + \frac{n-1}{2} + \frac{(n-1)^2}{2}.


Question 4. (2.5 points)
In base-ten (decimal numeral system), find the digits x,y such that the number 12xy567 be divisible by 33.

Solution:
33 = 3 \times 11.

A number is divisible by 3 precisely if the sum of all its digits is divisible by 3: {\displaystyle 
3 \,\vert\, 12xy567 \Leftrightarrow 3 \,\vert\, (7 + 6 + 5 + y + x + 2 + 1)
} this is: {\displaystyle 
\begin{align}
3 \,\vert\, 12xy567 &\Leftrightarrow 3 \,\vert\, (21 + x + y) \\
                    &\Leftrightarrow 21 + x + y = \dot{3} \\
                    &\Leftrightarrow x + y = \dot{3} - 21
\end{align}
} Moreover: {\displaystyle 
x,y \mbox{ are digits in base-ten } \Rightarrow 0 \leqslant x,y \leqslant 9
} then: {\displaystyle 
0 \leqslant x + y \leqslant 18
} We have to find out what differences \dot{3} - 21 satisfy the fact of belonging to \left[ 0, 18 \right]: {\displaystyle \dot{3} - 21 = \left\lbrace \ldots, 0(=21-21), 3(=24-21), 6(=27-21), 9(=30-21), 12(=33-21), 15(=36-21), 18(=39-21), \ldots \right\rbrace} so there are 7 possible cases: {\displaystyle x + y = 0 \veebar x + y = 3 \veebar x + y = 6 \veebar x + y = 9 \veebar x + y = 12 \veebar x + y = 15 \veebar x + y = 18}

A number is divisible by 11 precisely if the sum of its digits at even places minus the sum of its digits at odd places is divisible by 11: {\displaystyle 
11 \,\vert\, 12xy567 \Leftrightarrow 11 \,\vert\, ((7 + 5 + x + 1) - (6 + y + 2))
} this is: {\displaystyle 
\begin{align}
11 \,\vert\, 12xy567 &\Leftrightarrow 11 \,\vert\, (5 + x - y) \\
                    &\Leftrightarrow 5 + x - y = \dot{11} \\
                    &\Leftrightarrow x - y = \dot{11} - 5
\end{align}
} Moreover: {\displaystyle 
x,y \mbox{ are digits in base-ten } \Rightarrow 0 \leqslant x,y \leqslant 9
} then: {\displaystyle 
-9 \leqslant x - y \leqslant 9
} We have to find out what differences \dot{11} - 5 satisfy the fact of belonging to \left[ -9, 9 \right]: {\displaystyle \dot{11} - 5 = \left\lbrace \ldots, -5(=0-5), 6(=11-5), \ldots \right\rbrace} so there are 2 possible cases: {\displaystyle x - y = -5 \veebar x - y = 6}

Therefore, there are 7 \times 2 = 14 possible cases:

Table of possible cases
Λ x + y = 0 x + y = 3 x + y = 6 x + y = 9 x + y = 12 x + y = 15 x + y = 18
x - y = -5 2x = -5
x = \frac{-5}{2}
2x = -2
x = -1
2x = 1
x = \frac{1}{2}
2x = 4
x = 2
y = 7
2x = 7
x = \frac{7}{2}
2x = 10
x = 5
y = 10
2x = 13
x = \frac{13}{2}
No: x is not a digit
in base-ten
No: x is not a digit
in base-ten
No: x is not a digit
in base-ten
Yes: x,y are digits
in base-ten
No: x is not a digit
in base-ten
No: y is not a digit
in base-ten
No: x is not a digit
in base-ten
x - y = 6 2x = 6
x = 3
y = -3
2x = 9
x = \frac{9}{2}
2x = 12
x = 6
y = 0
2x = 15
x = \frac{15}{2}
2x = 18
x = 9
y = 3
2x = 21
x = \frac{21}{2}
2x = 24
x = 12
No: y is not a digit
in base-ten
No: x is not a digit
in base-ten
Yes: x,y are digits
in base-ten
No: x is not a digit
in base-ten
Yes: x,y are digits
in base-ten
No: x is not a digit
in base-ten
No: x is not a digit
in base-ten

So there are three possible solutions: \binom{x}{y} \in \left\lbrace \binom{2}{7}, \binom{6}{0}, \binom{9}{3} \right\rbrace.

Thus, the possible numbers are: 1227567, 1260567, 1293567,

which are divisibles by 33. Their quotients are: 37199, 38199, 39199.


Example of exam, 2

Maximum time: 2 hours.

Question 1. (2,5 points).

  • a) Define adequate set of connectives (asc), also called completely expressive or functionally complete set of connectives.
  • b) Provide two examples of two-element asc, explaining why they are so and assuming that we know the asc which elements are the most usual connectives \left\lbrace \neg, \wedge, \vee, \rightarrow, \leftrightarrow \right\rbrace.
Solution:
  • a) In Propositional Logic, an adequate set of connectives (asc) is any set of connectives such that every logical connective can be represented as an expression involving only those belonging to the asc.
  • b) As it is said in the wording, we assume that we know that the set of the most usual connectives,  \lbrace \neg, \wedge, \vee, \rightarrow, \leftrightarrow \rbrace is an asc. Two two-element asc are the sets  \lbrace \neg, \wedge \rbrace and  \lbrace \neg, \vee \rbrace . In effect, we only have to check, for each two-element set, that the missing most usual connectives may be represented only with the ones in the set: {\displaystyle 
\begin{align}
\lbrace \neg, \wedge \rbrace: p \vee q & \equiv \neg (\neg p \wedge \neg q)\\
p \rightarrow q & \equiv \neg (p \wedge \neg q)\\
p \leftrightarrow q & \equiv \neg (p \wedge \neg q) \wedge \neg (\neg p \wedge q)\\
\lbrace \neg, \vee \rbrace: p \wedge q & \equiv \neg (\neg p \vee \neg q)\\
p \rightarrow q & \equiv \neg p \vee q\\
p \leftrightarrow q & \equiv \neg (\neg (\neg p \vee q) \vee \neg (p \vee \neg q))
\end{align}
}

Question 2. (2,5 points).
Proof by definition that \mathbb{N} is an infinite set.

Solution:
A set is infinite precisely if there exists a bijection between it and one of its proper subsets (definition by Dedekind). As an example, consider f:\mathbb{N} \rightarrow \mathbb{N}\setminus\{0\}, defined by n \mapsto f(n) = n+1. Let us prove that it is a bijective mapping. In effect:
  • f is a mapping \Leftrightarrow \left( \forall x \in \mathbb{N} \right) \left( \exists y \in \mathbb{N}\setminus\{0\} \right) \left( f(x) = y \right) \wedge \left( \forall x,x' \in \mathbb{N} \right) \left( x = x' \rightarrow f(x) = f(x') \right), which is trivial, as if x \in \mathbb{N} is given and because of the definition of f, there exists y_x = x+1 \in \mathbb{N}\setminus\{0\}, this y_x being unique for each x, that is, that if x = x', then, because of the definition of f, f(x) = x+1 = y_x = y_{x'} = x'+1 = f(x');
  • f is injective \Leftrightarrow \left( \forall x,x' \in \mathbb{N} \right) \left( f(x) = f(x') \rightarrow x = x' \right), which is trivial because of the definition of f, as if f(x) = f(x'), that is, if x+1 = x'+1, then, x = x';
  • f is surjective \Leftrightarrow \left( \forall y \in \mathbb{N}\setminus\{0\} \right) \left( \exists x \in \mathbb{N} \right) \left( f(x) = y \right), which is also trivial due to the definition of f, as if y is given, then x = y-1 satisfies f(x) = f(y-1) = (y-1) + 1 = y.

Question 3. (2,5 points).
Abigail wants to send Balbina the most simple call message: eh. They can only send numbers. Abigail and Balbina use the letters' position in the alphabet to code them (thus, Abigail codes e as 06 and h as 08). They use RSA to encrypt their messages. If Abigail choose p = 3 and q = 7 as the ground primes for RSA:

  • a) imagine you are Abigail and obtain the encrypted message that you have to send to Balbina;
  • b) imagine you are Balbina and decrypt the encrypted message that Abigail has sent to you.
Solution:
Following the steps of RSA algorithm:
  • 1) p = 3, q = 7.
  • 2) r = p \cdot q = 21.
  • 3) \phi (21) = 12 (Euler phi of 21).
  • 4) We have to choose as the secret key (SK) a relatively prime with 12 and less than 12, at the same time; we choose SK = 5.
  • 5) The secret key and the public key (PK) are linked by the equation SK \cdot PK \equiv 1 \pmod{\phi(r)}, in this case: 5 \cdot PK \equiv 1 \pmod{12}, so PK = 5.
  • 6) If we code the original message, (eh), we have 0608. It can be proven that that if the coded message X satisfies 0 \leq X \leq r-1, then the ciphered message Y, also satisfies 0 \leq Y \leq r-1. As we are interested in code, then cipher, then decipher and finally decode, we have to group into blocks so that each one of their individual coding is less than r-1 = 20. Let X_1 = 06 and X_2 = 08 be the coded blocks and let Y_1 and Y_2 be the ciphered blocks. As RSA method establishes, the X_i encryption is performed by solving the congruence equation X_i^{PK} \equiv Y_i \pmod{r} and the Y_j decryption by solving the congruence equation Y_j^{SK} \equiv X_j \pmod{r}.

Let us answer now the two sections of the question.

  • a) Putting ourselves in the shoes of Abigail, let us assess the ciphered message that we have to send to Balbina. Let us cipher X_1 = 06: the solution of 6^5 \equiv Y_1 \pmod{21} is Y_1 = 6. Let us cipher X_2 = 08: the solution of 8^5 \equiv Y_2 \pmod{21} is Y_2 = 8. Thus, the message that we have to send is: 0608.
  • b) Putting ourselves in the shoes of Balbina, let us decipher the ciphered message that Abigail has sent us. Let us decipher Y_1 = 06: the solution of 6^5 \equiv X_1 \pmod{21} is X_1 = 6. Let us decipher Y_2 = 08: the solution of 8^5 \equiv X_2 \pmod{21} is X_2 = 8. Thus, the message we have just deciphered is: 0608.

Question 4. (2,5 points).
One company spent 100000 euros in buying 100 electronic devices, some of them ground breaking and providing maximum performance. Smartphones were 50 euros each, tablets were 1000 euros each and laptops were 5000 euros each. How many of each device did they buy,knowing that they bought at least one device of each type? Solve this question using the theory of:

  • a) diophantine equations;
  • b) congruence equations.
Solución:
Once translated the information from the wording into a system of linear equations and simplifying the latter:

{\displaystyle 
\begin{align}
\left\lbrace
\begin{align}
x &+ y &+ z &= 100 \\
50x &+ 1000y &+ 5000z &= 100000
\end{align}
\right.
&\Rightarrow
\left\lbrace
\begin{align}
x &+ y &+ z &= 100 \\
x &+ 20y &+ 100z &= 2000
\end{align}
\right. \\
&\Rightarrow
\left\lbrace
\begin{align}
x + y + z &= 100 \\
x + y + z + 19y + 99z &= 2000
\end{align}
\right. \\
&\Rightarrow
100 + 19y + 99z = 2000 \\
&\Rightarrow
99z + 19y = 1900
\end{align}
}

  • a) A diophantine equation ax + by = c has solution precisely if \operatorname{mcd}{(a,b)} \mid c. In such a case, {\displaystyle 
\left( x_0,y_0 \right) = \left( \frac{cp}{d}, \frac{cq}{d} \right)
} is a particular solution of the equation, where d = \operatorname{mcd}{(a,b)} and p and q are a pair of Bézout coefficients (the coefficients of a and b in one linear combination that is equal to d) (Bézout's identity). The general solution of that equation is: {\displaystyle 
\binom{x}{y} = \binom{x_0}{y_0} + \frac{k}{d} \binom{b}{-a}
} where \binom{x_0}{y_0} is a particular solution and k \in \mathbb{Z}.
    The following table shows the use of the extended Euclidean algorithm for this case. The computation stops when the remainder is zero (in red color). The previous remainder, 2 (also in red color), is the greatest common divisor. Bézout coefficients are 5 and -26 (in magenta color). Numbers in cyan color, -19 and 99, are, up to the sign, the quotients of the original numbers by the greatest common divisor.
    index i quotient qi−1 remainder ri si ti
    0 99 1 0
    1 19 0 1
    2 99 ÷ 19 = 5 995 × 19 = 4 15 × 0 = 1 0 − 5 × 1 = −5
    3 19 ÷ 4 = 4 194 × 4 = 3 04 × 1 = −4 1 − 4 × (−5) = 21
    4 4 ÷ 3 = 1 41 × 3 = 1 11 × (−4) = 5 −5 − 1 × 21 = −26
    5 3 ÷ 1 = 3 33 × 1 = 0 −43 × 5 = −19 21 − 3 × (−26) = 99
    Thus,

    {\displaystyle 
\left( z_0,y_0 \right) = \left( \frac{1900 \cdot 5}{1}, \frac{1900 \cdot (-26)}{1} \right) = \left( 9500, -49400 \right)
} is a particular solution and: {\displaystyle 
\binom{z}{y} = \binom{9500}{-49400} + \frac{k}{1} \binom{19}{-99}
} is the general solution, where k \in \mathbb{Z}.
    So, how many of each device did they buy, knowing that they bought at least one device of each type? Let us see. We know that z > 0 and that y > 0. Thus, 9500 + 19k > 0 and -49400 - 99k > 0, and consequently, -500 < k and k < -498,9. As k \in \mathbb{Z}, k = -499. Substituting in the equations, we obtain: z = 19, y = 1 and x = 100 - 1 - 19 = 80.
    Sol.: 80 smartphones, 1 tablets and 19 laptops.

  • b) As a congruence equation, it could be: {\displaystyle 
99z \equiv 1900 \pmod{19}
} Or, equivalently: {\displaystyle 
99z \equiv 0 \pmod{19}
} As \operatorname{mcd}{(99,19)} = 1, this way prompts us to consider all positive multiples of 19, lesser than 100, as possible solutions: z \in \left\lbrace 19, 38, 57, 76, 95 \right\rbrace.
    Let us try the other way. The diophantine equation 99z + 19y = 1900 could also be seen as the following congruence equation: {\displaystyle 
19y \equiv 1900 \pmod{99}
} Or, equivalently: {\displaystyle 
19y \equiv 19 \pmod{99}
} As \operatorname{mcd}{(99,19)} = 1, the equation has a unique solution \pmod{99}, which is: {\displaystyle 
y \equiv 19 \cdot 19^{\phi(99)-1} \pmod{99}
} that is to say, {\displaystyle 
y \equiv 19^{60} \pmod{99}
} Exploring the potential residues, we find out that: {\displaystyle 
19^{10} \equiv 1 \pmod{99}
} and thus, multiplying this congruence six times by itself, side by side: {\displaystyle 
19^{60} \equiv 1 \pmod{99}
} and, as a congruence relation is transitive: {\displaystyle 
y \equiv 1 \pmod{99}
} In other words, y = 1 (since y < 100).
    As 99z + 19y = 1900, we obtain that z = 19.
    Finally, from x + y + z = 100, we can assess the value of x, x = 80.
    Sol.: 80 smartphones, 1 tablets and 19 laptops.

Part 2: Themes 3 and 4

Example of exam, 1

Maximum time: 2 hours.

Question 1. (2.5 points)
Let D be the set of decimal digits, that is, D = \left\lbrace 0,1,2,3,4,5,6,7,8,9 \right\rbrace. Using combinatorial reasoning, calculate:

  • a) The number of subsets of D which elements are all primes.
  • b) The number of subsets of D having a prime number of elements.
Solution:
  • a) Let P = \left\lbrace 2,3,5,7 \right\rbrace be the set consisting of the the prime numbers in D. What is actually requested is the number of nonempty (nonvoid) subsets of P, in other words, subtracting one (the empty set) from the total number of subsets of P: {\displaystyle 
\begin{align}
\left\vert{P}\right\vert - 1 &= 2^4 - 1 \\
          &= 15
\end{align}
} Sol.: 15 subsets.
  • b) The total number of subsets of k elements of a set of n elements is given by C_{n,k} = \binom{n}{k}. Thus, running over the prime numbers in D: {\displaystyle 
\begin{align}
\binom{10}{2} + \binom{10}{3} + \binom{10}{5} + \binom{10}{7} &= \frac{10!}{2! \cdot 8!} \cdot \frac{10!}{3! \cdot 7!} \cdot \frac{10!}{5! \cdot 5!} \cdot \frac{10!}{7! \cdot 3!} \\
          &= 537
\end{align}
} Sol.: 537 subsets.

Question 2. (2.5 points)
A group of twelve people visit a museum. Everybody is wearing a woolen overcoat. Upon entering, they leave their coats in the attended cloakroom. On leaving, the cloakroom attendant puts the twelve coats on the counter. Each person in the group picks out one at random, completely absent-minded because of a very interesting discussion. Using combinatorial reasoning, calculate in how many ways can the coats be chosen by them so that none of them get their own coat back.

Solution:
This involves finding the number of derangements of 12 objects. Instead of calculating for 12, we are going to do for the general case of having n objects. Let  1, 2, \ldots, n denote the objects themselves. Let P be the set of all permutations of the objects and let P_k be the set of all derangements that have k fixed elements. Then, the set of all derangements is:

{\displaystyle 
D = P - \left( \bigcup\limits_{i=1}^{n} P_{i} \right)
} Let us see it:

  • How many permutations fix one specific number? The answer is the number of permutations of the other n-1 (non fixed) numbers, that is to say, (n-1)!, and as there are n numbers, then, the number of permutations that fix any of these n numbers is (n-1)! \cdot n.
  • How many permutations fix two specific numbers? The answer is the number of permutations of the other n-2 (non fixed) numbers, that is to say, (n-2)!, and as there are \binom{n}{2} ways of choosing two different numbers out of n numbers, then, the number of permutations that fix any two of these n numbers is \binom{n}{2} (n-2)!.

Let us note that in the case of n = 2, that is, \left\lbrace 1,2 \right\rbrace, when we subtract those which fix the 1, then we are subtracting once those which fix both the 1 and the 2 and when we subtract those that fix the 2 we are subtracting again those which fix both the 1 and the 2. Thus, we have to add them one time. If we follow this reasoning, the number of permutations (derangements) for which no number is in its original place is: {\displaystyle 
\begin{align}
\left\vert{D}\right\vert &= \left\vert{P}\right\vert - \left\vert{\left( \bigcup\limits_{i=1}^{n} P_{i} \right)}\right\vert \\
          &= \binom{n}{0} n! - \binom{n}{1} (n-1)! + \binom{n}{2} (n-2)! - \cdots + (-1)^{n+1} \binom{n}{n} 0!
\end{align}
} Thus, if n = 12, there are: {\displaystyle 
\binom{12}{0} 12! - \binom{12}{1} (12-1)! + \binom{12}{2} (12-2)! - \cdots + (-1)^{12+1} \binom{12}{12} 0! = 176 \ 214 \ 841
} derangements.
Sol.: In 176 \ 214 \ 841 ways.


Question 3. (2.5 points)
Let the following be the definition of the sum of two natural numbers n and m: {\displaystyle 
\begin{align}
  S(n,0) &= n \\
  S(n,m) &= S(n,m-1) + 1
\end{align}
} Prove that the solution of this recurrence is S(n) = n + m.

Solution:
Let us note that n is alien to recursion. Thus, in an easier but equivalent way, denoting S(n,m) by f(m), we get a linear non homogeneous recurrence relation with constant coefficients and with a constant function as the function on the RHS of the equation:

{\displaystyle 
\begin{align}
  f(0) &= n \\
  f(m) - f(m-1) &= 1
\end{align}
}

  • a) General solution of the homogeneous:
    The characteristic polynomial is: {\displaystyle 
P(x) = x - 1
} thus, 1 is a simple characteristic root.
    The general solution of the homogeneous is: {\displaystyle 
f(m) = c_1 1^m; \;\; c_1 \in \mathbb{R}
}
  • b) Particular solution of the non homogeneous:
    As the function on the RHS is constant, let us try out a general constant (real number) as a possible particular solution: {\displaystyle 
k - k = 1
} but this is a contradiction, so we have to increase the degree of the polynomial. Let us try out with a first degree polynomial, P(m) = Am. Substituting: {\displaystyle 
Am - A(m-1) = 1 \Rightarrow Am - Am + A = 1 \Rightarrow A = 1
} Thus: {\displaystyle 
f(m) = m
} is a particular solution of the non homogeneous.
  • c) General solution of the non homogeneus: {\displaystyle 
f(m) = c_1 + m; \;\; c_1 \in \mathbb{R} \;\;\;\;\; {\scriptstyle(1)}
}
  • d) Considering the initial conditions:
    From the initial condition, f(0) = n, we have: {\displaystyle 
n = f(0) = c_1 + 0 \Rightarrow c_1 = n
} Substituting in (1), we get the desired solution: {\displaystyle 
f(m) = n + m
} or, in other words: {\displaystyle 
S(n,m) = n + m
}

Question 4. (2.5 points)
Let {\displaystyle 
x \ast y = u
} be a binary relation defined on the set A = \left\lbrace 1,3,5,7,9 \right\rbrace, for every two elements x and y in A, where u is the figure of the units of the usual product x \cdot y between two natural numbers (for example, 3 \ast 9 = 7).

  • a) Find out theCayley table for the operation \ast on A.
  • b) Is (A;\ast) an abelian group? (You can reason using the Cayley table).
Solution:
  • a) Here is the Cayley table of the binary operation \ast defined on the set A: {\displaystyle 
\begin{array}{c|ccccc}
\ast & 1 & 3 & 5 & 7 & 9 \\
\hline
1 & 1 & 3 & 5 & 7 & 9 \\
3 & 3 & 9 & 5 & 1 & 7 \\
5 & 5 & 5 & 5 & 5 & 5 \\
7 & 7 & 1 & 5 & 9 & 3 \\
9 & 9 & 7 & 5 & 3 & 1 \\
\end{array}
}
  • b) Let us check if (A, \ast) satisfies the five requirements (axioms) to be qualified as an abelian group:
    • a) A is closed under \ast (it is also said that \ast is a closed operation or an internal composition law on A) since for all a and b in A, a \ast b \in A. It is easy to reason using the table: every number in the table is an element of A.
    • b) \ast is associative on A — we could check every triad, 1 \ast (3 \ast 5) = 1 \ast 5 = 5 = 3 \ast 5 = (1 \ast 3) \ast 5), and so on, however it is easier to reason using the fact that the product (\cdot) of natural numbers is associative: simply, \forall x,y,z \in \mathbb{N}, x \cdot (y \cdot z) = (x \cdot y) \cdot z \Rightarrow x \ast (y \ast z) = (x \ast y) \ast z is true since when we multiply the unit digits among natural numbers we have to carry no number —;
    • c) \ast is conmutative (the table is symmetric with respect to the main diagonal);
    • d) the identity for \ast in A is 1 as can be seen from the Cayley table since the first row and the first column are the same than the heading row and column, respectively;
    • e) it is not true that for every element there exists a reciprocal element — we can use the table for checking this: given a certain number, heading a row, we only have to find out which other number gives the identity when operated with the former one, and this can be done by searching for the identity on that row (for example, 7 is the reciprocal of 3 because 3 \ast 7 = 7 \ast 3 = 1 [we search for 1 on the second row (headed by 3), finding it out on the fourth column (headed by 7])—: the reciprocal of 1 is 1, of 3 is 7, of 7 is 3 and of 9 is 9, but 5 has no reciprocal — whe operating any other number with 5 the result is always 5 (such a number, as 5 in this case, is called an absorbing element for \ast in A [as zero for the product of integers]), so it is impossible to obtain the identity as a result —.

    In short, (A;\ast) has not abelian group structure (it has an abelian monoid structure).


Example of exam, 2

Maximum time: 2 hours.

Question 1. (2.5 points)
An urn contains seven balls numbered one through seven. They are randomly chosen, one by one and without reposition until the urn is empty. As they are removed from the urn, we write their figures down from left to right on a first out, first writen basis. Using combinatorial reasoning calculate how many numbers thus formed start and end with an even digit.

Solution:
There are 7 positions for the figures. At both ends, hypotheses imply even figure. There are three even figures between 1 and 7: 2, 4 and 6. Being guided by the distribution of objects into recipients models, consider these 3 even figures (distinguishable boxes) and the two ends (distinguishable objects) of the seven-digit number, on an underlying injective mapping (at most, one end by each figure, as there are not two balls with the same figure). For each one of these cases at the ends (each one of the variations) we have to take into account all the possibilities for the 5 intermediate positions. The number of these possibilities is given by the permutations of 5 elements (one new abstraction as 5 distinguishable objects [the intermediate positions] being distributed into 5 distinguishable recipients [the figures 1, 3 and 5 and the even figure that is at none of the ends of the seven-digit number thus formed], this time on an underlying bijective mapping). Applying the rule of product:

{\displaystyle 
\begin{align}
V_{3,2} \cdot P_5 &= 3^{\underline{2}} \cdot 5! \\
          &= (3 \cdot 2) \cdot (5!) \\
          &= 6 \cdot 120 \\
          &= 720
\end{align}
} Sol.: 720 numbers.


Question 2. (2.5 points)
A secret ballot is made in a meeting of seventeen people. Two people have cast invalid ballots, three have cast blank ballots, five have cast dissenting votes and seven have cast assenting votes. Using combinatorial reasoning calculate in how many ways this could have occured.

Solution:
Let us use the occupancy model for the non ordered distribution of balls into boxes; balls and boxes representing ballots and people, respectively. Consider the 17 persons (distinguishable boxes) and the 7 assenting ballots (indistinguishable balls), on an underlying injective mapping (at most, one ballot by each person) — alternatively, we could consider the number of subsets of 7 elements from a set of 17 elements —. In any case, there are C_{17,7} ways of distributing the assenting ballots into the boxes. For each one of these cases (each one of the combinations), there are 10 empty boxes left. Now, using a similar reasoning, there are C_{10,5} ways of distributing the dissenting ballots into the boxes, with 5 empty boxes remaining for each one of these cases. Similarly, there are C_{5,3} ways of distributing the blank ballots into the boxes, with 2 empty boxes remaining for each one of the cases. So, lastly, there are C_{2,2} ways in which invalid ballots can be placed into the boxes. Applying the rule of product:

{\displaystyle 
\begin{align}
C_{17,7} \cdot C_{10,5} \cdot C_{5,3} \cdot C_{2,2} &= \binom{17}{7} \cdot \binom{10}{5} \cdot \binom{5}{3} \cdot \binom{2}{2} \\
          &= \frac{17!}{7! \cdot 10!} \cdot \frac{10!}{5! \cdot 5!} \cdot \frac{5!}{3! \cdot 2!} \cdot \frac{2!}{2! \cdot 0!} \\
          &= \frac{17! \cdot \cancel{10!} \cdot \cancel{5!} \cdot \cancel{2!}}{7! \cdot \cancel{10!} \cdot \cancel{5!} \cdot 5! \cdot 3! \cdot \cancel{2!} \cdot 2! \cdot 0!} \\
          &= 49 \ 008 \ 960
\end{align}
} Sol.: In 49 \ 008 \ 960 ways.


Question 3. (2.5 points)
Let x(t) and y(t) be the numbers of malicious software belonging to two malware types, in the day t, that coexist in a certain insecure wide area network (WAN) under malware evolution daily control. Let us assume that the original memberships were of x(0)=3 and y(0)=7 and that the coexistence evolution is as follows:

  • every day, the growth in malware type x is the sum of the triple of the growth in type x on the previous day and the growth in type y also on the previous day plus seven new malware (that were classified as type x),
  • and also every day, the growth in malware type y is the result of subtracting the growth in type x on the previous day from the growth in type y on the previous day, plus three new malware (that were classified as type y).

Find out and solve the system of recurrence equations of the evolution of the malware.

Solution:
Let us analyze the evolutions of the two types of malware on their own growths (that these evolutions had to be calculated in terms of the populations or not is not specified by the wording and, on the other side, calculating them on their growths is easier because the order of the recurrence relation has decreased in one time unit). Let X_{t} and Y_{t} denote the growths from time t to time t+1, i.e. X_{t} = x(t+1) - x(t) and Y_{t} = y(t+1) - y(t). The system of linear recurrence equations that correponds to this situation is:

{\displaystyle 
\left\lbrace
\begin{align}
X_{t+1} &= 3 X_t &+ Y_t &+ 7 \;\;\;\;\; {\scriptstyle(1)} \\
Y_{t+1} &= Y_t &- X_t &+ 3 \;\;\;\;\; {\scriptstyle(2)}
\end{align}
\right.
}

  • a) Calculating X_t:
    From the first equation we get: {\displaystyle 
\begin{align}
Y_t &= X_{t+1} - 3 X_t - 7 \;\;\;\;\; {\scriptstyle(3)} \\
X_{t+2} &= 3 X_{t+1} + Y_{t+1} + 7 \;\;\;\;\; {\scriptstyle(4)}
\end{align}
} Substituting (2) in (4): {\displaystyle 
X_{t+2} = 3 X_{t+1} + Y_t - X_t + 3 + 7
} Substituting (3) in the latter, and simplifying, grouping and sorting, we get a linear non homogeneous recurrence relation with constant coefficients and with a constant function as the function on the RHS (right-hand side) of the equation: {\displaystyle 
X_{t+2} - 4 X_{t+1} + 4 X_t = 3
}
    • a.1) General solution of the homogeneous:
      The characteristic polynomial is: {\displaystyle 
P(X) = X^2 - 4 X + 4
} that is: {\displaystyle 
P(X) = (X - 2)^2
} thus, 2 double characteristic root.
      The general solution of the homogeneous is: {\displaystyle 
X_t = c_1 2^t + c_2 t 2^t; \;\; c_1, c_2 \in \mathbb{R}
}
    • a.2) Particular solution of the non homogeneous:
      As the function on the RHS is constant, let us try out a general constant (real number) as a possible particular solution: {\displaystyle 
k - 4k + 4k = 3
} then k = 3. Thus: {\displaystyle 
X_t = 3
} is a particular solution of the non homogeneous.
    • a.3) General solution of the non homogeneous: {\displaystyle 
X_t = c_1 2^t + c_2 t 2^t + 3; \;\; c_1, c_2 \in \mathbb{R} \;\;\;\;\; {\scriptstyle(5)}
}
  • b) Calculating Y_t:
    Substituting (5) in (1), and simplifying, grouping and sorting, we get: {\displaystyle 
Y_t = \left( 2c_2 - c_1 \right) 2^t - c_2 t 2^t - 13; \;\; c_1, c_2 \in \mathbb{R}
}
  • c) Considering the initial conditions:
    From the initial conditions, x_0 = 3 and y_0 = 7 we have: {\displaystyle 
X_0 = x_1 - x_0 = x_1 - 3 = c_1 2^0 + c_2 \cdot 0 \cdot 2^0 + 3 = c_1 + 3 \Rightarrow c_1 = x_1 - 6  \;\;\;\;\; {\scriptstyle(6)}
} On the other side: {\displaystyle 
Y_0 = y_1 - y_0 = y_1 - 7 = \left( 2c_2 - c_1 \right) 2^0 - c_2 \cdot 0 \cdot 2^0 - 13 = 2c_2 - c_1 - 13  \;\;\;\;\; {\scriptstyle(7)}
} and now, substituting (6) in (7): {\displaystyle 
y_1 - 7 = 2c_2 - x_1 + 6 - 13 \Rightarrow y_1 = 2c_2 - x_1 \Rightarrow c_2 = \frac{x_1 + y_1}{2}
}
  • d) The solution to the situation under the wording of the question (evolution of these two types of malware on their own growths) is: {\displaystyle 
\left\lbrace
\begin{align}
X_t &= \left( x_1 - 6 \right) 2^t + \left( x_1 + y_1 \right) t 2^{t-1} + 3 \\
Y_t &= \left( y_1 + 6 \right) 2^t - \left( x_1 + y_1 \right) t 2^{t-1} - 13
\end{align}
\right.
} where x_1 and y_1 are the populations of both types of malware by the end of the first hour (data not provided in the wording).

Question 4. (2.5 points)
The accompanying graph shows the connections among four tram stations. You may:

  • a) Write the adjacency matrix G of that graph.
  • b) Interpret the matrices G^2 and G^3 (reason what situations they represent).
  • c) Reason, using those matrix representations, if it is a strongly connected graph or not.
  • d) Reason, using those matrix representations, what is the length of the shortest path from A to D and how many paths may be considered as the "shortest" ones.
+—+       +—+
|D| <———> |C|
+—+       +—+
    \      ⋀
     \     |
      \    |
       \   |
        ╶┘ |
+—+       +—+
|A| <———> |B|
+—+       +—+
Solución:
  • a) The adjacency matrix G of this graph is: {\displaystyle 
	G =
	\begin{pmatrix}
	0 & 1 & 0 & 0 \\
	1 & 0 & 1 & 0 \\
	0 & 0 & 0 & 1 \\
	0 & 1 & 1 & 0
	\end{pmatrix}
	} We draw up the adjacency matrix of the graph, by matching the positional subscripts 1, 2, 3 and 4 of its elements with the labels A, B, C and D, so that, for example, g_{23} corresponds to a possible path from B to C, B \rightsquigarrow C. Thus, the element g_{ij} of G is the number of direct connections --- with no intermediate station (paths of length one in the graph) --- between the tram stations corresponding to i and j, in the direction i \rightsquigarrow j. In this way, we interpret g_{23} = 1 as the existence of one direct connection from 2 to 3, 2 \rightarrow 3, this is, B \rightarrow C, whilst g_{32} = 0 corresponds to the non existence of a direct connection from 3 to 2, 3 \nrightarrow 2, this is, C \nrightarrow B.
  • b) The powers 2 and 3 of G are: {\displaystyle 
	G^2 =
	\begin{pmatrix}
	1 & 0 & 1 & 0 \\
	0 & 1 & 0 & 1 \\
	0 & 1 & 1 & 0 \\
	1 & 0 & 1 & 1
	\end{pmatrix}
	\quad \quad
	G^3 =
	\begin{pmatrix}
	0 & 1 & 0 & 1 \\
	1 & 1 & 2 & 0 \\
	1 & 0 & 1 & 1 \\
	0 & 2 & 1 & 1
	\end{pmatrix}
	} The element g^{(2}_{ij} of G^2 is the number of connections with exactly one station in the middle (length two paths in the graph) from the corresponding station to i to the corresponding station to j, under the previous formalization. Similarly, the element g^{(3}_{ij} of G^3 represents the number of connections with two intermediate stations (three length paths in the graph) from the corresponding station to i to the corresponding station to j, again according to the previous formalization.
  • c) A graph is strongly-connected precisely if there exists a path from any vertex to any vertex. On the other side, given a graph G, with n vertices, it is possible to know if there exists a path from the vertex i to the vertex j, regardless of the length but depending on the element p_{ij} of the matrix P = G + G^2 + G^3 + \cdots + G^{n-1} as it is the total number of paths from i to j (if there were i, j such that p_{ij} = 0 then no path would be possible from i to j and the graph would not be strongly connected).
    The graph under our study, G, with 4 vertices, is strongly connected because P = G + G^2 + G^3 has not zero elements: {\displaystyle 
	P = G + G^2 + G^3
	=
	\begin{pmatrix}
	1 & 2 & 1 & 1 \\
	2 & 2 & 3 & 1 \\
	1 & 1 & 2 & 2 \\
	1 & 3 & 3 & 2
	\end{pmatrix}
	} which mean that any two stations are connected each other, either directly or indirectly via one or two intermediate stops. Indeed, for this particular graph, G^2 + G^3 neither has zero elements: {\displaystyle 
	G^2 + G^3
	=
	\begin{pmatrix}
	1 & 1 & 1 & 1 \\
	1 & 2 & 2 & 1 \\
	1 & 1 & 2 & 1 \\
	1 & 2 & 2 & 2
	\end{pmatrix}
	} that is to say, any two stations are connected each other via one or two intermediate stops.
  • d) Denoting by g_{ij}^{(k)} the element at position (i,j) of the matrix G^{k}, we note that g_{14} = g_{14}^{(2)} = 0 and that g_{14}^{(3)} = 1, this being the first non-zero digit, so the shortest path has two intermediate stops and there is only one shortest path (since the value of g_{14}^{(3)} is one).

Everything: Themes 1, 2, 3 and 4 Ambox warning green construction.svg

Example of exam 1

Maximum time: 2 hours.

Question 1. (2.5 points).
On the island of knights and knaves there are two types of inhabitants, `knights' who always tell the truth and `knaves' who always lie. It is assumed that every inhabitant is either a knight or a knave. There were two inhabitants, A and B, standing together in the front yard of a house. You passed by and asked them, `Are you knights or knaves?'

  • a) A answered, `If B is a knight then I am a knave.' Can it be determined whether A and B were knights or knaves? (1.25 p.)
  • b) Afterward, B said, `Don't believe A; he's lying.' With this new information, can it be determined whether A and B were knights or knaves? (1.25 p.)
Solution:
Let us use X for `X is a knight' --- therefore, \neg X is an abbreviation for `X is a knave' ---.
  • a) A's statement, `If B is a knight then I am a knave', can be expressed as B \rightarrow \neg A and the fact that A says it, as A \leftrightarrow (B \rightarrow \neg A). In view of the truth table: {\displaystyle 
		\begin{array}{cc|cccccc}
			A & B & A & \leftrightarrow & (B & \rightarrow & \neg & A) \\
			\hline
			1 & 1 & 1 & \mathbf{0} & 1 & 0 & 0 & 1 \\
			1 & 0 & 1 & \mathbf{1} & 0 & 1 & 0 & 1 \\
			0 & 1 & 0 & \mathbf{0} & 1 & 1 & 1 & 0 \\
			0 & 0 & 0 & \mathbf{0} & 0 & 1 & 1 & 0
		\end{array}
		} the only model for A \leftrightarrow (B \rightarrow A) is the 2nd interpretation, so it can be determined that A is a knight and B a knave.
  • b) B's statement, `Don't believe A; he's lying', is equivalent to `A is a knave', which can be expressed as \neg A and the fact that B says it, as B \leftrightarrow \neg A, which simply says that neither both A and B can be knights nor knaves at the same time, and this adds nothing new, as expected because it was already determined. Indeed, in view of the truth table: {\displaystyle 
		\begin{array}{cc|ccccccccccc}
			A & B & (A & \leftrightarrow & (B & \rightarrow & \neg & A)) & \wedge & (B & \leftrightarrow & \neg & A) \\
			\hline
			1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & \mathbf{0} & 1 & 0 & 0 & 1 \\
			1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & \mathbf{1} & 0 & 1 & 0 & 1 \\
			0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & \mathbf{0} & 1 & 1 & 1 & 0 \\
			0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & \mathbf{0} & 0 & 0 & 1 & 0
		\end{array}
		} we notice that everything remains the way it was, the 2nd interpretation is again a model, but now for (A \leftrightarrow (B \rightarrow \neg A)) \wedge (B \leftrightarrow \neg A).

Example of exam 2

Maximum time: 2 hours.

Question 2. (2.5 points).
Knowing that \mathbb{Z} (integers) is a countable set and that the countable union of countable sets is countable, prove that \mathbb{Q} (rationals) is countable.

Solution:
\mathbb{Q} is a countable set as it can be expressed by the countable union \mathbb{Q} = A_1 \cup A_2 \cup \ldots \cup A_n \cup \ldots, where every A_i = \left\lbrace 0, \frac{-1}{i}, \frac{1}{i}, \ldots, \frac{-k}{i}, \frac{k}{i}, \ldots \right\rbrace is countable, since f: \mathbb{Z} \rightarrow A_i, defined by f(0) = 0 and f(\pm n) = \frac{\pm n}{i} is a biyection. Note that the set A_i is the set of all the rational numbers that have the same denominator i.

Question 3. (2.5 points).
Use congruence relation theory to respond.

  • a) Prove that, for any n \in \mathbb{N}, 21 \cdot 2^{5n+1} - 4 \cdot 3^{3n+1} is divisible by 5. (1.25 p.)
  • b) Calculate the remainder of 3^{6n+1} + 3^{2n+1} \cdot 19^{2n} - 3 (for any n \in \mathbb{N}), when it is divided by 28. (1.25 p.)
Solution:
We use congruence relation theory.
  • a) On the one hand:
    {\displaystyle \left.
            \begin{align}
                2^5 = 32 &\equiv 2 \pmod{5} \\
                3^3 = 27 &\equiv 2 \pmod{5}
            \end{align}
            \right\rbrace}
    {\displaystyle \begin{align}
                &\stackrel{(i)}{\Rightarrow} &2^5 &\equiv 3^3 \pmod{5} \\
                &\stackrel{(ii)}{\Rightarrow} &2^{5n} &\equiv 3^{3n} \pmod{5}   \;\;\;\;\; {\scriptstyle(1)}
            \end{align}}
    On the other:
    {\displaystyle \begin{align}
                &            &7 &\equiv 2 \pmod{5} \\
                &\stackrel{(iii)}{\Rightarrow} &7 \cdot 2 &\equiv 2 \cdot 2 \pmod{5} \\
                &\stackrel{(iv)}{\Rightarrow} &7 \cdot 2 \cdot 3 &\equiv 2 \cdot 2 \cdot 3 \pmod{5}   \;\;\;\;\; {\scriptstyle(2)}
            \end{align}}
    Substituting (2) in (1):
    {\displaystyle \begin{align}
                &            &7 \cdot 3 \cdot 2 \cdot 2^{5n} &\equiv 2 \cdot 2 \cdot 3 \cdot 3^{3n} \pmod{5} \\
                &            &21 \cdot 2^{5n+1} &\equiv 4 \cdot 3^{3n+1} \pmod{5}
            \end{align}}
    which, by definition of congruence relations, means that 21 \cdot 2^{5n+1} - 4 \cdot 3^{3n+1} is divisible by 5.
  • b) On the one hand:
    {\displaystyle \begin{align}
                &            &3^3 = 27 &\equiv -1 \pmod{28} \\
                &\stackrel{(v)}{\Rightarrow} &3^{6n} = \left( 3^3 \right)^{2n} &\equiv (-1)^{2n} = 1 \pmod{28} \\
                &\stackrel{(iv)}{\Rightarrow} &3^{6n+1} &\equiv 3 \pmod{28}   \;\;\;\;\; {\scriptstyle(3)}
            \end{align}}
    On the other:
    {\displaystyle \begin{align}
                &            &57 = 3 \cdot 19 &\equiv 1 \pmod{28} \\
                &\stackrel{(v)}{\Rightarrow} &3^{2n} \cdot 19^{2n} &\equiv 1 \pmod{28} \\
                &\stackrel{(iv)}{\Rightarrow} &3^{2n+1} \cdot 19^{2n} &\equiv 3 \pmod{28}   \;\;\;\;\; {\scriptstyle(4)}
            \end{align}}
    If we add side by side (3) and (4):
    {\displaystyle 
			\begin{align}
				&            &3^{6n+1} + 3^{2n+1} \cdot 19^{2n} &\equiv 6 \pmod{28} \\
				&\Rightarrow &3^{6n+1} + 3^{2n+1} \cdot 19^{2n} - 3 &\equiv 3 \pmod{28}
			\end{align}
		}
    In other words, the requested remainder is 3.


(i) Because congruence relations are symmetric and transitive.
(ii) Rising each side of the congruence relation to the power n.
(iii) Multiplying each side of the congruence relation by 2.
(iv) Multiplying each side of the congruence relation by 3.
(v) Rising each side of the congruence relation to the power 2n.


Question 5. (2.5 points).
Use a combinatorial reasoning to respond.

  • a) A number is palindrome if it reads the same from left to right and from right to left. In base ten, how many seven-digit numbers are palindromes? (1.25 p.)
  • b) Let us assume a n sided polygon network (n-gon network). Calculate n, the number of nodes (vertices) of the network, knowing that the number of line segments (sides + diagonals) is 253. (1.25 p.)
Solution:
  • a) A seven digit palindrome fits into the model abcdcba, where a \neq 0. There are 9 possibilities for a, 10 for b, 10 for c and 10 other possibilities for d. Because of the rule of product, there is a total of 9 \cdot 10 \cdot 10 \cdot 10 = 9000 seven digit palindromes.
  • b) If n is the number of nodes, then the number of line segments is the number of subsets of two elements (each line segment can be viewed as a subset of two elements, as it can be abstracted from the fact that it joins two nodes) from a set of n elements (the n nodes), and this number is, by definition of combination, \binom{n}{2}. Then, \binom{n}{2} = 253 \Rightarrow \frac{n(n-1)}{2} = 253 \Rightarrow n = -22 \vee n = 23. Thus, n = 23.

Logic


To find out more:

  1. The Logic Portal
  2. The Thinking Portal
  3. And more:
    1. Prenex normal form
    2. Outline of logic
    3. Concepts in logic
    4. Boolean algebra
    5. Logic gates
    6. WikiProject Logic

Bibliography: theory and proposed and solved exercises

In English:

  • —¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Chapter 1 and related exercises). McGraw-Hill, New York, New York, United States, 2012, ISBN 978-0-07-338309-5

In Spanish:

  • —¤— Kenneth A. Rosen. Matemática discreta y sus aplicaciones. 5th edition. (Sections 1.1, 1.2, 1.3, 1.4, 1.5, 3.1 and related exercises). McGraw-Hill/Interamericana de España, S.A.U., Aravaca (Madrid), Madrid, Spain, 2004, ISBN 84-481-4073-7

Software

See also

In English:

  • KDEM.DA.HD.703-01.pdf (download) (matching tables for corresponding exercises from the 5th, 6th, 7th and 7th global editions of Rosen's book Discrete mathematics and its applications, Chapter 1 on The Foundations: Logic and Proofs)

In Spanish:

---

Plantilla:Logic Plantilla:Classical logic Plantilla:Mathematical logic Plantilla:Metalogic Plantilla:Non-classical logic Plantilla:Philosophical logic Plantilla:Common logical symbols Plantilla:Logical connectives Plantilla:Logical paradoxes Plantilla:Logical truth

Cardinality


To find out more:

  1. The Set Theory Portal

Bibliography: theory and proposed and solved exercises

In English:

  • —¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Sections 2.1, 2.2, 2.3, 2.5, 5.1, 5.2, 5.3, Chapter 9 and related exercises). McGraw-Hill, New York, New York, United States, 2012, ISBN 978-0-07-338309-5

In Spanish:

See also

Plantilla:Set theory Plantilla:Binary relations

Number theory

Divisibility

Primes

Diophantine equations, systems of Diophantine equations and on their solutions

Modular arithmetic

Congruence equations, systems of congruence equations and on their solutions

Cryptography


To find out more:

  1. The Number Theory Portal
  2. The Cryptography Portal
  3. And more:
    1. Divisibility
      1. Algorithms for division
    2. Primality
      1. Quadratic residues
      2. Quadratic reciprocity
      3. Primality tests
    3. Pseudo-random number generation
      1. Linear congruential generators (LCG)
      2. Combined Linear Congruential Generators
      3. Inversive congruential generator
      4. Generalized inversive congruential pseudorandom numbers
      5. List of random number generators
    4. Cryptography
      1. Highly totient numbers
      2. Plato/Ramanujan's highly composite numbers
      3. Adleman's smooth numbers
      4. Finch's rough numbers
      5. Semiprimes
      6. Elliptic curve cryptography
    5. List of notable numbers

Bibliography: theory and proposed and solved exercises

In English:

  • —¤— Thomas Koshy. Elementary number theory with applications. Academic Press (an imprint of Elsevier Inc.), New York, United States, 2nd edition, 2007, ISBN: 978-0-12-372487-8
  • —¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Chapter 4 and related exercises). McGraw-Hill, New York, New York, United States, 2012, ISBN 978-0-07-338309-5
  • Kenneth A. Rosen. Elementary number theory and its applications. Addison-Wesley, Reading, Massachusetts, United States, 1986, ISBN 0-201-06561

In Spanish:

  • —¤— Máximo Anzola and José Caruncho. Problemas de Álgebra. Tomo 2. Anillos - Polinomios - Ecuaciones. 3rd edition. Primer Ciclo, Madrid, España. (Chapter 7 «Divisibilidad en \mathbb{N} y \mathbb{Z}», 94 solved exercises; Chapter 8 «Ecuaciones diofánticas», 27 solved exercises; Chapter 9 «Sistemas de numeración», 25 solved exercises), 1982. ISBN: 84-300-6417-6.
  • —¤— Francisco José González Gutiérrez. Apuntes de matemática discreta. 12. Ecuaciones diofánticas. University of Cádiz, Cádiz, Andalusia, Spain, 2004. http://www2.uca.es/matematicas/Docencia/2005-2006/ESI/1710003/Apuntes/Leccion12.pdf
  • —¤— Francisco José González Gutiérrez. Apuntes de matemática discreta. 13. Clases de restos módulo m. University of Cádiz, Cádiz, Andalusia, Spain, 2004. http://www2.uca.es/matematicas/Docencia/2005-2006/ESI/1710003/Apuntes/Leccion13.pdf
  • —¤— Kenneth A. Rosen. Matemática discreta y sus aplicaciones. 5th edition. (Sections 2.4, 2.5, 2.6 and related exercises). McGraw-Hill/Interamericana de España, S.A.U., Aravaca (Madrid), Madrid, Spain, 2004, ISBN 84-481-4073-7

See also

Plantilla:Number theory Plantilla:Divisor classes Plantilla:Classes of natural numbers Plantilla:Number theoretic algorithms Plantilla:Prime number classes Plantilla:Prime number conjectures

Numerical analysis


To find out more:

  1. The Analysis Portal

Bibliography: theory and proposed and solved exercises

In English:

In Spanish:

Combinatorial theory


To find out more:

  1. The Discrete Mathematics Portal
  2. And more:
    1. Catalan numbers
    2. Generating functions
    3. Examples of generating functions
    4. Combinatorics (category in Wikipedia)

Bibliography: theory and proposed and solved exercises

In English:

  • —¤— Kenneth P. Bogart. Combinatorics through guided discovery. 2004. https://math.dartmouth.edu/news-resources/electronic/kpbogart/
  • —¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Chapters 6 and 8 and related exercises). McGraw-Hill, New York, New York, United States, 2012, ISBN 978-0-07-338309-5

In Spanish:

  • Máximo Anzola and José Caruncho. Problemas de Álgebra. Tomo 1. Conjuntos-Grupos. Primer Ciclo, Madrid, Spain. (Chapter 8 'Combinatoria', 31 solved problems), 1981.
  • L. Barrios Calmaestra. Combinatoria. In: Proyecto Descartes. Ministry of Education, Government of Spain, 2007. (Open access). http://descartes.cnice.mec.es/materiales_didacticos/Combinatoria/combinatoria.htm
  • M. Delgado Pineda. Material from «Curso 0: Matemáticas». Part: Combinatoria: Variaciones, Permutaciones y Combinaciones. Potencias de un binomio. OCW UNED. (Theory and exercises). 2010. (CC BY-NC-ND). http://ocw.innova.uned.es/matematicas-industriales/contenidos/pdf/tema5.pdf
  • I. Espejo Miranda, F. Fernández Palacín, M. A. López Sánchez, M. Muñoz Márquez, A. M. Rodríguez Chía, A. Sánchez Navas and C. Valero Franco. Estadística Descriptiva y Probabilidad. Servicio de Publicaciones de la Universidad de Cádiz. (Appendix 1: Combinatoria). 2006. (GNU FDL). http://knuth.uca.es/repos/l_edyp/pdf/febrero06/lib_edyp.apendices.pdf
  • —¤— José Ramón Franco Brañas, María Candelaria Espinel Febles and Pedro Ramón Almeida Benítez. Manual de combinatoria. @becedario, Badajoz, Spain, 2008. ISBN: 978-84-96560-73-4
  • —¤— Kenneth A. Rosen. Matemática discreta y sus aplicaciones. 5th edition. (Chapters 4 and 6 and related exercises). McGraw-Hill/Interamericana de España, S.A.U., Aravaca (Madrid), Madrid, Spain, 2004, ISBN 84-481-4073-7

See also

Recurrence relations


Para saber más:

  1. Integer sequences
  2. List of integer sequences in the OEIS that have their own English Wikipedia entries
  3. Index to OEIS: Section Recurrent Sequencies

Bibliography: theory and proposed and solved exercises

In English:

  • Richard Johnsonbaugh. Discrete mathematics. 6th edition. (Chapter 7 and corresponding exercises). Prentice Hall Inc., New York, New York, United States, 2005, ISBN 0-13-117686-2
  • —¤— Eric Lehman, F. Thomson Leighton, Albert R. Meyer. Mathematics for Computer Science. (Chapter V). 2017 (2 May). CC BY-SA. https://courses.csail.mit.edu/6.042/spring17/mcs.pdf
  • —¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Chapters 5 and 8 and corresponding exercises). McGraw-Hill, Nueva York, Nueva York, Estados Unidos, 2012, ISBN 978-0-07-338309-5
  • Wikibooks contributors. Discrete Mathematics/Recursion. Wikibooks. https://en.wikibooks.org/wiki/Discrete_Mathematics/Recursion

In Spanish:

Algebraic structures


To find out more:

  1. The Discrete Mathematics Portal
  2. And more:
    1. Symmetric group
    2. Multiplicative group of integers modulo n

Bibliography: theory and proposed and solved exercises

In English:

In Spanish:

  • —¤— Máximo Anzola and José Caruncho. Problemas de Álgebra. Tomo 1. Conjuntos-Grupos. 3rd edition. Primer Ciclo, Madrid, Spain. (Chapter 9 «Operaciones», 24 solved exercises; Chapter 10 «Grupos-Estructura», 154 solved exercises), 1981. ISBN: 84-300-4073-0.
  • —¤— Máximo Anzola and José Caruncho. Problemas de Álgebra. Tomo 2. Anillos - Polinomios - Ecuaciones. 3ªrd edition. Primer Ciclo, Madrid, Spain. (Chapter 1 «Estructura de anillo», 40 solved exercises; Chapter 4 «Estructura de cuerpo», 32 solved exercises), 1982. ISBN: 84-300-6417-6.
  • Department of Algebra, University of Seville. Álgebra básica. Notas de teoría. http://www.algebra.us.es/Documentos/AB_1011_Teoria
  • —¤— José García García and Manuel López Pellicer. Álgebra lineal y geometría. Curso teórico-práctico. 7th edition. Marfil, Alcoy, Spain. ISBN: 84-268-0269-9.
  • —¤— RTVE (): «La aventura del saber». Series: «Más por menos». Chapter: «La geometría se hace arte» (Script + presentation = Antonio Pérez) (Minute 5,22, la Alhambra, sus mosaicos y la teoría de grupos; recommendation: see entire chapter). © gratisOA. Available on: http://www.rtve.es/alacarta/videos/mas-por-menos/aventura-del-saber-serie-mas-menos-geometria-se-hace-arte/1291007/

Graphs, trees and networks


To find out more:

  1. The Discrete Mathematics Portal

Bibliography: theory and proposed and solved exercises

In English:

  • —¤— Kenneth A. Rosen. Discrete mathematics and its applications. 7th edition. (Chapters 10 and 11 and corresponding exercises). McGraw-Hill, New York, New York, United States, 2012, ISBN 978-0-07-338309-5

In Spanish:

  • —¤— Kenneth A. Rosen. Matemática discreta y sus aplicaciones. 5th edition. (Chapters 8 and 9 and corresponding exercises). McGraw-Hill/Interamericana de España, S.A.U., Aravaca (Madrid), Madrid, Spain, 2004, ISBN 84-481-4073-7
  • —¤— Universitat Politècnica de València (UPV). Aplicaciones de la teoría de grafos a la vida real. © gratis OA. https://www.youtube.com/playlist?list=PL6kQim6ljTJu44dsVeZifHHiuDC1MEZ7q

Complimentary knowledge pills

Conjectures, open problems and imagination

History

Paradoxes

Minihackatones (miniencuentros intensivos de aprendizaje en colaboración) / Minihackathons (intensive collaborative learning meetings)

Templates

The template {{learning project}} has to be added to the talk page of every article that has been created or changed on Epistemowikia as part of the learning project. When you move your articles to Wikipedia in English you have to change it to the {{Educational assignment}} template.

See also

External links