Explore Discrete Math Examples

How many permutations of {1,2,...,n}.
How many permutations of {1,2,...,n} where $n\ge <!--\; \ge \; -->5$ are there such that none of {1,2,3} are adjacent to one another?
Example: the permutation (5,3,1,4,2) does not meet the condition described in the problem because 1 and 3 are in two adjacent places and the permutation (2,5,3,4,1) as well as (1,6,2,5,3,4) meets this condition.

What is the highest grade that Roma can get?
30 students took part in the Mathematics Olympiad. They were offered 8 problems. First, the jury checked the participants' work, giving each problem a "solved" or "not solved" grade. Then, for each task, its cost is determined - a natural number, which is equal to the number of participants who did not solve it. The total cost of solved problems by a student makes up his overall grade. It turned out that the boy Roma received a grade lower than everyone else. What is the highest grade he could get?
I got 55; 4 problems, from 13 to 17 points. Found this number by brute force. Is it correct?

Post's criterion for a single operation
Let $f:\{0,1{\}}^n\to <!--\; \to \; -->\{0,1\}$ be a logical function. Show that the signature ⟨f⟩ is complete if and only if f does not lie in $T_0,T_1$ and S.
The arrow from the left to the right is evident due to Post's criterion. From the right to the left is harder: I could deduced if $f(0,...,0)=1$ and $f(1,..,1)=0$ then f is not monotonous. It would be enough to prove that f is not in L but I don't know how.

Concrete mathematics: Computing the value of certain infinite sums example
In Concrete Mathematics (Graham, Knuth, Patashnik), on page 58, there is the below example of calculating the value of an infinite sum:
$$\begin{array}{rl}\underset{k\ge <!--\; \ge \; -->0}{\sum <!--\; \sum \; -->}\frac{1}{(k+1)(k+2)}& =\underset{k\ge <!--\; \ge \; -->0}{\sum <!--\; \sum \; -->}{k}^{\underset{\_<!--\; \_\; -->}{-<!--\; -\; -->2}}\\ & =\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}{k}^{-<!--\; -\; -->2}=\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{k^{\underset{\_<!--\; \_\; -->}{-<!--\; -\; -->1}}}{-<!--\; -\; -->1}{|}_0^n=1\end{array}$$
For that last part I don't understand how it is 1 and not -1. To start with, at 0, the summation property gives us 0:
$$\frac{0^{\underset{\_<!--\; \_\; -->}{-<!--\; -\; -->1}}}{-<!--\; -\; -->1}=\frac{\frac{0}{0+1}}{-<!--\; -\; -->1}=0$$
Then 1 is
$$\frac{1^{\underset{\_<!--\; \_\; -->}{-<!--\; -\; -->1}}}{-<!--\; -\; -->1}=\frac{\frac{1}{1+1}}{-<!--\; -\; -->1}=-<!--\; -\; -->\frac{1}{2}$$
and 2 is
$$\frac{2^{\underset{\_<!--\; \_\; -->}{-<!--\; -\; -->1}}}{-<!--\; -\; -->1}=\frac{\frac{1}{2+1}}{-<!--\; -\; -->1}=-<!--\; -\; -->\frac{1}{3}$$
And so on tending towards -1 for larger n. As I understand it (the subtraction vertical bar notation) if n is, say, 2 (a long way from infinity to be sure) then we'd get $-<!--\; -\; -->\frac{1}{3}-<!--\; -\; -->0=-<!--\; -\; -->\frac{1}{3}$. And so on getting closer to -1 as best I can tell.

Let $X=\{3^n|n>0\}andY=\{3n|n>0\}$. Prove that $X\subseteq <!--\; \subseteq \; -->Y$.
I know this should be a simple question to solve but I am stuck.
$3^n=3n$
$3\cdot <!--\; \cdot \; -->3n=3n$
How do I write this out further?

Determine whether the statement or its negation is true.
$\mathrm{\exists <!--\; \exists \; -->}a,b\in <!--\; \in \; -->{\mathbb{Z}}^{+}$ such that $\mathrm{\forall <!--\; \forall \; -->}c,d\in <!--\; \in \; -->{\mathbb{Z}}^{+},a/b=c/d$. Negation: $\mathrm{\forall <!--\; \forall \; -->}a,b\in <!--\; \in \; -->{\mathbb{Z}}^{+},\mathrm{\exists <!--\; \exists \; -->}c,d\in <!--\; \in \; -->{\mathbb{Z}}^{+}$ such that $a/b\ne <!--\; \ne \; -->c/d$.

A simple permutation question - discrete math
There are five distinct computer science books, three distinct mathematics books, and two distinct art books. In how many ways can these books be arranged on a shelf if one of the art books is to the left of all the computer science books, and the other art book is to the right of all the computer science books?
For my answer I was thinking since there are 10 books total and 5 are computer science books, then I could place an art book on the first, second, third, fourth slot ... but I do not know how to finish it, I am sure it has something to do with rule of sum. Any advice appreciated.

Discrete Math Graph Theory Independent sets
An independent set is a set of vertices in a graph, no two of which are adjacent. Let G be a graph with n vertices and with the maximal degree equal to ∆. Show that, G contains an independent set of size at least $n/(\mathrm{△<!--\; △\; -->}+1)$.

Uniqueness Proof, Discrete Math Help
While reading I came across Uniqueness Proofs. Where a theorem asserts the existence of a unique element with a particular property. In order to prove this two steps are needed, Prove existence and Prove Uniqueness. The example given is Show that if a and b are real numbers and $a\ne 0$, then there is a unique real number r such that $ar+b=0$.
I could do the existence portion. $r=-<!--\; -\; -->\frac{b}{a}$. I would like some clarification on proving the uniqueness part.
Suppose that s is a real number such that $as+b=0$. Then $ar+b=as+b$, where $r=-<!--\; -\; -->\frac{b}{a}$. You subtract b from both sides and divide both sides by a to get $r=s$. Then it says that this means if $s\ne r$ then $as+b\ne 0$ and that this establishes uniqueness.
I guess my issue is how exactly does this prove uniqueness? When would placing some random variable in the same spot as the previous not end with the two variables being the same? One example I thought of where it wouldn't be unique I wasn't able to follow the same steps to disprove. Consider this $n^2=4$
following the previous example suppose that s is another real number such that $s^2=4$
$⟹<!--\; ⟹\; -->n^2=s^2$
square root both sides $n=s$
now in the other one they just jumped to the conclusion that this means if $s\ne n$ then $s^2\ne 4$
however... -2 and 2 could fill meaning this example does not have a unique solution. Could someone please give some clarification so I can better understand uniqueness proofs.

Set of Integers with a Given Abundancy Index
Let $\mathrm{\sigma <!--\; \sigma \; -->}(n)$ be the sum of divisors of n. Define the abundancy index of n to be $I(n)=\frac{\mathrm{\sigma <!--\; \sigma \; -->}(n)}{n}=\frac{a}{b}$ with a,b coprime integers. For a given limit L and coprime integers a,b, I want to find the set of all integers $n\le <!--\; \le \; -->L$ with $I(n)=\frac{a}{b}$.
So far I've learnt that:
1. Integers that belong to the same set are called "friendly numbers"
2. Integers that are the only ones with a given index are called "solitary"
3. An index for which no solutions exist is called "abundancy outlaw"
But I am not sure if that's any helpful. Is there any clever approach to this (which doesn't involve factoring all numbers)? Perhaps reducing the problem into factoring only some integers which are better candidates? I assume a and b to be arbitrary, but I would like to hear if an assumption on either of them yields an effective approach for that specific case.

Discrete math question using PigeonHole
There are 30 students in the class where Jane is studying. In a Mathematics Test, Jane made 13 mistakes, any other student in the class made fewer mistakes. Use the generalized pigeonhole principle to determine at least how many students made the same number of mistakes as each other.
ANd i answer the question this way, am i right ?
ANS:
Since any other students made fewer mistakes, hence their number of mistakes ranging from 0 to 12 (inclusively). There are 13 values (0 to 12), hence according to Pigeonhole principle, there are
$29/13+1=3$
students having the same number of mistakes.

Let p be a real number with $0<p<1$. When and have a child, this child is a boy with probability p and a girl with probability $1-p$, independent of the gender of previous children. Lindsay and Simon stop having children as soon as they have a child that has the same gender as their first child.

Confusion in taking negation in nested statement
It is given that
$\mathrm{\forall <!--\; \forall \; -->}x\mathrm{\forall <!--\; \forall \; -->}y[(x<y)\to <!--\; \to \; -->\mathrm{\exists <!--\; \exists \; -->}z(x<z<y)]$
It is wanted to find the negation of given structure.
The answer is $\mathrm{\exists <!--\; \exists \; -->}x\mathrm{\exists <!--\; \exists \; -->}y[(x<y)\wedge <!--\; \wedge \; -->\mathrm{\forall <!--\; \forall \; -->}z(x\ge <!--\; \ge \; -->z\vee <!--\; \vee \; -->z\ge <!--\; \ge \; -->y)]$. Where i stuck in is $(x\ge <!--\; \ge \; -->z\vee <!--\; \vee \; -->z\ge <!--\; \ge \; -->y)$, i see that because of $(x<z\wedge <!--\; \wedge \; -->z<y)$, when we take the negation of $(x<z\wedge <!--\; \wedge \; -->z<y)$, we obtain $(x\ge <!--\; \ge \; -->z\vee <!--\; \vee \; -->z\ge <!--\; \ge \; -->y)$. I want to ask that can we write $(x\ge <!--\; \ge \; -->z\ge <!--\; \ge \; -->y)$ instead of $(x\ge <!--\; \ge \; -->z\vee <!--\; \vee \; -->z\ge <!--\; \ge \; -->y)$.
If so , can we write $(x\ge <!--\; \ge \; -->z\ge <!--\; \ge \; -->y)$ as $(x\ge <!--\; \ge \; -->z\wedge <!--\; \wedge \; -->z\ge <!--\; \ge \; -->y)$, because we wrote $(x<z<y)$ as $(x<z\wedge <!--\; \wedge \; -->z<y)$.

Tips for forming countability proofs?
I'm new to writing proofs, and I'm having a really hard time enumerating sets. I'm struggling to construct functions which convert positive integers into the desired set and which is bijective. For instance, one of these sets is the list of all real numbers with decimal representations consisting of 1's.
I have no idea how to approach this question. I'm not even sure if it's countable or not.
Another example which illustrates something which I am having trouble with is whether the set of all integers divisible by 5 but not divisible by 7 is countable. Obviously it is countable, but I don't know how to prove that it is countable.
I got f: $\mathbb{N}\to <!--\; \to \; -->\mathit{G}$
$f(x)=\frac{5x}{5}$ where x is divisble by 5
$\frac{-<!--\; -\; -->5(x-<!--\; -\; -->1)}{5}$ where $(x-<!--\; -\; -->1)$ is divisble by 5
$\frac{35(n-<!--\; -\; -->2)}{5}-<!--\; -\; -->\frac{35(n-<!--\; -\; -->2)}{5}$ where $(x-<!--\; -\; -->2)$ is divisible by 5
At which point I felt as if I wasn't going in the right direction and stopped.
Any and all advice would be appreciated.

Discrete math logic / proof question
Is this statement logically equivalent: $$\mathrm{\exists <!--\; \exists \; -->}𝑥(𝑃(𝑥)\to 𝑄(𝑥))$$ and $$\mathrm{\forall <!--\; \forall \; -->}𝑥𝑃(𝑥)\to <!--\; \to \; -->\mathrm{\exists <!--\; \exists \; -->}𝑥𝑄(𝑥)$$? Why? (I'm not sure how to proceed with this. I have to use the "universe of discourse" and not formal proof.)

Operator precedence - Discrete Math
Can someone please give me a hint as to how these two statements are different? Thank you!
$\mathrm{\forall <!--\; \forall \; -->}x\in <!--\; \in \; -->S,\mathrm{\exists <!--\; \exists \; -->}y\in <!--\; \in \; -->T,P(x,y)\Rightarrow <!--\; \Rightarrow \; -->Q(x)$ (Statement 1)
$$\mathrm{\forall <!--\; \forall \; -->}x\in <!--\; \in \; -->S,(\mathrm{\exists <!--\; \exists \; -->}y\in <!--\; \in \; -->T,P(x,y))\Rightarrow <!--\; \Rightarrow \; -->Q(x)$$ (Statement 2)

Discrete math(Divisors and primes)
Is the following statement true or false?Explain. There are integers x,y, and z such that 14 divides $2^x\times 3^y\times 5^z$.
My guess is false but I don't know how to explain it? Does it have anything to do with the fundamental theorem of arithmetic?

Prove that n edges can connect at most $n+1$ vertices not by induction.
Prove that n edges can connect at most $n+1$ vertices. Our professor solved this via induction but I feel I can prove it much more easily using the contrapositive statement. Am I going wrong somewhere?
Proof by contrapositive: n edges cannot connect $\ge <!--\; \ge \; -->n+2$ vertices.
name the vertices $v_1,v_2,\dots <!--\; \dots \; -->,v_{n+2}$
pair them up: $(v_1,v_2),(v_2,v_3),\dots <!--\; \dots \; -->,(v_{n+1},v_{n+2})$
we have now n edges, to be placed in these $n+1$ holes, no hole can have more than 1 edge, since multiple edges not allowed in simple graphs. So we will have at least 1 hole empty. Thus this empty hole makes our graph disconnected. thus proved. Now we show by construction that n edges can connect $n+1$ vertices, consider vertices, $v_1,v_2,\dots <!--\; \dots \; -->,v_{n+1}$ we have an edge between $v_1$ and all other vertices $\ge <!--\; \ge \; -->$ total n edges, and graph is connected.

A palindrome number is a number that is inverted, but the number remains the same. A four-digit palindrome number is 6226. Suppose, you subtract another four-digit palindrome number from such a four-digit palindrome. Subtraction is also a four-digit palindrome number. For how many four-digit palindrome numbers can that happen?

Prove the following by contradiction: for any $n\in <!--\; \in \; -->\mathbb{Z}$ we have $9\nmid <!--\; \nmid \; -->(n^2+3)$
I understand that I need to derive false from $\mathrm{\neg <!--\; \neg \; -->}(9\nmid <!--\; \nmid \; -->(n^2+3))$, or $9\mid <!--\; \mid \; -->n^2+3$. To do this, I attempted to say $n^2+3=9k$ for some $k\in <!--\; \in \; -->\mathbb{Z}$. Then I tried something like $3=-<!--\; -\; -->n^2=-<!--\; -\; -->3(k-<!--\; -\; -->1)$, but $-<!--\; -\; -->3\mid <!--\; \mid \; -->3$. That doesn't contradict the statement.