In the recent project, I encountered a puzzle, thought for several days, I simplified it. I will be very grateful for your help.
[Math] Tricky discrete math problems
discrete mathematicsmathematicaMATLABpython
Related Solutions
If you stick strictly with a direct proof (denoting two consecutive integers by $n$ and $n+1$, summing them to get $2n + 1$, therefore odd), you'll be fine.
For one thing, your assumed contradiction, the negation of "the sum of two consecutive numbers is always odd" is not correctly stated; its negation needs to be "it is not the case that that the sum of two consecutive numbers is always odd", which means, "there exists two consecutive integers whose sum is even."
Proof by contradiction here turns out to be much more work than simply using a direct proof.
Your teacher may have chosen to represent two cases, in the event some students designated the two consecutive integers as $(n - 1)$ and $n$, while others, like you, denoted these consecutive integers as $n$ and $(n+1).$
As you note, the proof proceeds the same, in either case, but given that your teacher was providing an answer key, he or she may have simply tried to cover all the bases: all the approaches students may have used.
But to answer your question, aside from this pedagogical concern your teacher may have had, the proof does not require a proof by cases. So I do not believe your teacher expected you or any other student to provide both cases. Doing so does not add any more information, is rather redundant, etc, save for the pedagogical concerns your teacher may have had.
First of all, you will need to understand how to interpret these matrices. They are Boolean matrices where entry $M_{ij}=1$ if $(i,j)$ is in the relation and $0$ otherwise. As an example, the relation $R$ is \begin{align*} R=\{(0,3),(2,1),(3,2)\}. \end{align*}
Question 1
For the inverse relation, try writing the the pairs contained in $R^{-1}$ and represent this in matrix form. How does this matrix relate to $M_R$?
It's the transposed matrix. We have $(a,b)\in R^{-1}$ if $(b,a)\in R$, which corresponds to transposing the matrix.
The intersection of the relations is defined such that $(a,b)\in R\cap S$ if both $(a,b)\in R$ and $(a,b)\in S$. How does this translate to matrices? Consider the entry $(i,j)$ in $M_{R\cap S}$: When it is $1$, what must be true about the entries $(i,j)$ in $M_R$ and $M_S$?
Both of the entries must be $1$. Thus, $M_{R\cap S}=0_{4\times 4}$ in this example.
To find the composition, it can be shown that this corresponds to the Boolean product of the matrices.
Question 2
First, you have to find the matrix $M_{R\cup S}$. In the case of the intersection the entries of both matrices $M_R$ and $M_S$ had to be $1$, since both relations should contain the pair. In the union, only one of the relations need to contain the pair. How does this translate to the matrices?
Entry $(i,j)$ in $M_{R\cup S}$ is $1$ if entry $(i,j)$ is $1$ in either $M_R$ or $M_S$.
For $n\times n$ matrices, Warshall's algorithm consist of $n$ steps. First, we fix $k=1$ and construct a matrix $W$ where $W_{ij}=M_{ij}\vee (M_{ik}\wedge M_{kj})$ (here $M$ denotes the matrix representation of the relation). Consider a small example:
\begin{align*} M=\left[\begin{array}{c c c} 1 & 0 & 0\\ 0 & 1 & 1\\ 1 & 0 & 0 \end{array}\right] \end{align*}
Fix $k=1$. We can transfer the first row and column immediately. Further, all $1$'s can be transferred. For the remaining entries, we check the corresponding entries in the $k$'th row and column -- here marked with a box. If these are both $1$, we write $1$, otherwise $0$. \begin{align*} W_1=\left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & 1\\ 1 & ? & ? \end{array}\right]=\left[\begin{array}{ccc} 1 & \boxed{0} & 0\\ 0 & 1 & 1\\ \boxed{1} & \mathbf{0} & ? \end{array}\right]=\left[\begin{array}{ccc} 1 & 0 & \boxed{0}\\ 0 & 1 & 1\\ \boxed{1} & 0 & \mathbf{0} \end{array}\right]. \end{align*}
Next, fix $k=2$ and repeat the process on $W_1$. Again transfer the $k$'th row and column and any entries containing $1$. \begin{align*} W_2=\left[\begin{array}{ccc} 1 & 0 & ?\\ 0 & 1 & 1\\ 1 & 0 & ? \end{array}\right]=\left[\begin{array}{ccc} 1 & \boxed{0} & \mathbf{0}\\ 0 & 1 & \boxed{1}\\ 1 & 0 & ? \end{array}\right]=\left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & \boxed{1}\\ 1 & \boxed{0} & \mathbf{0} \end{array}\right]. \end{align*}
Finally, fix $k=3$ to find the last entries. \begin{align*} W_3=\left[\begin{array}{ccc} 1 & ? & 0\\ ? & 1 & 1\\ 1 & 0 & 0 \end{array}\right]=\left[\begin{array}{ccc} 1 & \mathbf{0} & \boxed{0}\\ ? & 1 & 1\\ 1 & \boxed{0} & 0 \end{array}\right]=\left[\begin{array}{ccc} 1 & 0 & 0\\ \mathbf{1} & 1 & \boxed{1}\\ \boxed{1} & 0 & 0 \end{array}\right]. \end{align*}
This final matrix $W_3$ is the transitive closure.
Best Answer
A solution for $N=7$ with the smallest value for $\omega_N$ is this:
$$ W = \begin{bmatrix} 25 & 26 & 28 & 29 & 34 & 36 & 37 \end{bmatrix} $$
$$M = \begin{bmatrix} 0 & 24 & 22 & 21 & 16 & 14 & 13 \\ 27 & 0 & 24 & 23 & 18 & 16 & 15 \\ 31 & 30 & 0 & 27 & 22 & 20 & 19 \\ 33 & 32 & 30 & 0 & 24 & 22 & 21 \\ 43 & 42 & 40 & 39 & 0 & 32 & 31 \\ 47 & 46 & 44 & 43 & 38 & 0 & 35 \\ 49 & 48 & 46 & 45 & 40 & 38 & 0 \end{bmatrix}$$
This solution is generated by this z3py script: