Explore Discrete Math Examples

Working out if a given relation is reflexive, symmetric or transitive (or all 3?)
On the set of integers, let 𝑥 be related to 𝑦 precisely when $x\ne y$
On the set of integers, let 𝑥 be related to 𝑦 precisely when $x\ne y$
1. Is this Reflexive?
2. Is this Symmetric?
3. Is this Transitive?
I'm also wondering if it can be multiple? I assume it can maybe be two but maybe not all 3.
To my understanding:
Reflexive is when each element is related to itself, I am not sure how to apply that to $x\ne y$? (Edit: If $x=3$ and $y=3$, then $x\ne y$, so it can't be reflexive as it would be an incorrect statement, so for not equals to it can never be reflexive from what I studied going back over notes)
Symmetric is when x is related to y, it implies that y is related to x (which may be fitting here as x is related to y when they don't equal each other?)
Transitive: When x is related to y, and y is related to z, then x is related to z (Not applicable here? Unsure)
I'm not sure if it's reflex as $x\in Z$ and $y\in Z$ (both are related to the set of integers), it could be symmetric as they are related when $x\ne y$ is the same as being related when $y\ne x$, then I'm not sure of transitive.

How do I formally express that a statement is true only if 3 propositions are true?
I have a rule: Action(A, B, C).
I want to say Action(A, B, C) is true only if:
1 - S is a member of set X.
2 - D is a member of set Y.
3 - T is a member of set Z.
I phrasing it at:
Action(A, B, C) only if 1, 2, and 3.
Is that correct and is there a more formal way to phrase this.

Determine all n-vertex simple graphs G such that every induced subgraph of G with 3 vertices has either 1 or 2 edges.
Let $n\ge <!--\; \ge \; -->5$. Determine all n-vertex simple graphs G such that every induced subgraph of G with 3 vertices has either 1 or 2 edges.
One thing I could understand is that there is no triangle in the graph.

The difference between universal and existential quantifiers in set abstractions
I'm finding it difficult to differentiate between
$\{(x,y)\mid <!--\; \mid \; -->\mathrm{\forall <!--\; \forall \; -->}z((x,z)\in <!--\; \in \; -->R\vee <!--\; \vee \; -->(z,y)\in <!--\; \in \; -->S)\}$
and $\{(x,y)\mid <!--\; \mid \; -->\mathrm{\exists <!--\; \exists \; -->}z((x,z)\in <!--\; \in \; -->R\vee <!--\; \vee \; -->(z,y)\in <!--\; \in \; -->S)\}$
where $R,S\subseteq <!--\; \subseteq \; -->A\times <!--\; \times \; -->A$ are binary relations on a set A.
Could someone please give a simple example which clearly differentiates these?
Under what conditions are these sets identical, and is it always the case that R and S are subsets of both of them?

Number of ways 10 men and 4 women can sit at a round table so there is no block of 3 consecutive women
In how many ways can 10 men and 4 women sit at a round table so that there is no block of 3 consecutive women?
Since there is no restriction on men, I thought they should sit first. Since the table is round, I fixed one seat for 1 in 10 men and placed the rest of them 9! ways and then we have 10 gaps in which we can place 4 women, at most 2 in each. I think these are the possibilities:
1. One woman in each gap: we can choose those gaps in $(\genfrac{}{}{0ex}{}{10}{4})$ ways and then place women in 4! different ways.
2. 2 women in 1 gap and the remaining 2 in each of their own. We need 3 gaps altogether, which can be chosen in $(\genfrac{}{}{0ex}{}{10}{3})$ ways. Since women are different entities, I believe we should be able to place them in, again 4! ways.
3. 2 women in 2 gaps: 2 in each. We can choose 2 gaps in $(\genfrac{}{}{0ex}{}{10}{2})$ ways and again, if I'm not wrong, place them in 4! ways.
Therefore, my answer to the number of possible ways is:
$9!\cdot <!--\; \cdot \; -->4!((\genfrac{}{}{0ex}{}{10}{4})+(\genfrac{}{}{0ex}{}{10}{3})+(\genfrac{}{}{0ex}{}{10}{2})).$.

DTFT of this signal
How can I calculate the DTFT of the following signal with properties? I suspect I would obtain a pulse, but I can not figure out how to calculate it.
x[n] for $n=0,\mathrm{1...},9$
Elsewhere $x[n]=0$
A step-by-step solution would be helpful.

Is my understanding of anti-symmetry and symmetry correct?
I'm struggling with understanding relations on equations, especially symmetric and anti-symmetric.
Here's my understanding, please let me know if it's correct or not:
The relation R:
- is reflexive iff $(a,a)\in R$
- is symmetric iff (a,b) and $(b,a)\in R$
- is anti-symmetric if $(a,b)\in R$ and (b,a) NOT in $\in R$.
- is transitive if $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)\in R$.
Example for symmetric and anti-symmetric:
Symmetric: (1,1), (2,1), (1,2)
Anti-symmetric: (1,2), (2,3), (4,3) (would it be anti-symmetric if I included ex. (2,2)?)

What is the contradiction (no I do not mean negation) of this statement: "The sum of ANY two positive integers is positive"
I believe that it can be rewritten in the form: "If two integers are positive then their sum is positive.". i.e. $A\to <!--\; \to \; -->B$.
My math teacher believes that the contradiction is: "There exists two positive integers whose sum is nonpositive.".
But I believe that it is: "The sum of any two positive integers is nonpositive.".
Please note the main difference between my answer and his is the difference between "there exists and any". i.e. $\mathrm{\exists <!--\; \exists \; -->}$ and $\mathrm{\forall <!--\; \forall \; -->}$

An urn contains 10 balls numbered from 1 to 10. Three balls are drawn without replacement. What is the probability that the drawn balls have numbers greater than 5?
I thought for the first ball, (6,7,8,9,10). The probability is 5/10. We took one, and for the second it is 4/9. And for the third one it is 3/8. Then we multiply these, and it is 1/12.
But I am not sure for this solution. I am confused.

Combinatorics, Hall's marriage theorem for bipartite graphs, where 2 vertices cannot be connected to more than one common vertex from the other side
I have a problem I'm trying to solve. the problem is: given Bipartite graph $G=(A\cup <!--\; \cup \; -->B,E)$, where $|A|=|B|=n>100$. and all edges are from A to B (all edges are symmetric), additionaly, lets assume that $\mathrm{\forall <!--\; \forall \; -->}{a}_1\ne <!--\; \ne \; -->a_2$ in A, $|\{b\in <!--\; \in \; -->B:\{a_1,b\},\{a_2,b\}\in <!--\; \in \; -->E\}|\le <!--\; \le \; -->1.$.
(in the original problem I had to prove it, which I actually did, So its a given now, you can also assume that the same applies with 2 vertices of B and one vertex from A if you need, just like the topic mentions ). Furthermore, the degree of every vertex in A is at least $\frac{n}{4}$, prove that there is a perfect matching in the graph. any hints or solutions would be great, thanks in advance!. edit: Hey, I might've done a mistake by not telling an important information, the original question included the following assumption: assume that for each $a_1\ne <!--\; \ne \; -->a_2$ in A and for each $b_1\ne <!--\; \ne \; -->b_2$ in B at least one of the pairs $\{a_1,b_1\},\{a_1,b_2\},\{a_2,b_1\},\{a_2,b_2\}$ isn't an edge in the graph.

Translating English statements into quantifiers and predicates.
Consider the following statement: "All your friends are perfect." This can be translated into quantifiers and predicates as follows : Let P (x) be “x is perfect” and let F (x) be “x is your friend” and let the domain be all people. So the statement can be written as: $\forall x(F(x)\to P(x))$. However, consider the statement: At least one of your friends is perfect. The answer is $\exists x(F(x)\wedge P(x))$, but why it is not $\exists x(F(x)\to P(x))$?

Compute gradient of discretized energy function
Given the following discretized energy problem, I'd like to compute the gradient with respect to u[i]:
$\underset{u}{min}\underset{i=1}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}|u[i+1]-<!--\; -\; -->u[i]|+\frac{\mathrm{\lambda <!--\; \lambda \; -->}}{2}\underset{i=1}{\overset{N}{\sum <!--\; \sum \; -->}}(u[i]-<!--\; -\; -->f[i]{)}^2$
I have the following solution but I can't come up with it myself.
$\mathrm{\nabla <!--\; \nabla \; -->}E[i]=\mathrm{sign}<!--\; \; -->(u[i]-<!--\; -\; -->u[i-<!--\; -\; -->1])-<!--\; -\; -->\mathrm{sign}<!--\; \; -->(u[i+1]-<!--\; -\; -->u[i])+\mathrm{\lambda <!--\; \lambda \; -->}(u[i]-<!--\; -\; -->f[i])\mathrm{\forall <!--\; \forall \; -->}1<i\le <!--\; \le \; -->N-<!--\; -\; -->1$
I understand that the derivative of the |x| function is sign(x) but I don't see why there are two sign terms. Basically, my calculation is:
$$\begin{gathered} \frac{d}{du[i]}|u[i+1]-<!--\; -\; -->u[i]| \\ =\mathrm{sign}<!--\; \; -->(u[i+1]-<!--\; -\; -->u[i])\ast <!--\; \ast \; -->\frac{d}{du[i]}(u[i+1]-<!--\; -\; -->u[i]) \\ =\mathrm{sign}<!--\; \; -->(u[i]-<!--\; -\; -->u[i-<!--\; -\; -->1])\ast <!--\; \ast \; -->\frac{d}{du[i-<!--\; -\; -->1]}(u[i]-<!--\; -\; -->u[i-<!--\; -\; -->1]) \\ =\mathrm{sign}<!--\; \; -->(u[i]-<!--\; -\; -->u[i-<!--\; -\; -->1])\ast <!--\; \ast \; -->(\frac{d}{du[i-<!--\; -\; -->1]}u[i]-<!--\; -\; -->1) \end{gathered}$$
This is where I get stuck and can't come up with the provided solution.

Deriving variance of a branching process with generating functions
In lecture today my professor introduced the notion of branching processes, and left the derivation of $\text{Var}(X_{n+1})$ to the students as an exercise. He said that we should try solving the problem through generating functions. For notation, let $\mathrm{\mu <!--\; \mu \; -->}$ denote the average of the offspring distribution, and let ${\mathrm{\sigma <!--\; \sigma \; -->}}^2$ denote its variance. $X_n$ denotes the number of offspring present at time n, and it is assumed that $X_0=1$.
I began this by first deriving the recursive formula for $\text{Var}(X_{n+1})$, which goes as follows:
$\text{Var}(X_{n+1})={\mathrm{\mu <!--\; \mu \; -->}}^2\text{Var}(X_n)+{\mathrm{\mu <!--\; \mu \; -->}}^n{\mathrm{\sigma <!--\; \sigma \; -->}}^2$
We can then define a generating function f(x) as follows:
$\text{Var}(X_{n+1})=c_{n+1},f(x)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{c}_n{x}^n=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{c}_{n+1}{x}^{n+1}$
So we have:
$\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{c}_{n+1}{x}^{n+1}=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}({\mathrm{\mu <!--\; \mu \; -->}}^2{c}_n{x}^{n+1})+\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{\mathrm{\mu <!--\; \mu \; -->}}^n{\mathrm{\sigma <!--\; \sigma \; -->}}^2{x}^{n+1}$
I eventually simplify this down to the form of:
$f(x)={\mathrm{\sigma <!--\; \sigma \; -->}}^{2}x\times <!--\; \times \; -->\frac{1}{1-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->}x}\times <!--\; \times \; -->\frac{1}{1-<!--\; -\; -->{\mathrm{\mu <!--\; \mu \; -->}}^{2}x}$
I'm new to generating functions, and don't have much experience with working with them. How do I pull out and isolate $c_{n+1}$ from the left-hand side of this expression? How would you guys finish this problem?

The largest number of intersection points we can obtain from 10 distinct points on a circle.
Suppose we pick 10 distinct points on a circle and connect all pairs of points with line segments, what is the largest number of intersection points we can obtain?
I have tried with 4 points and got 1 intersection point.
Next, I have tried with 5 points and got 5 intersection points.
Finally, I have tried with 6 points and got 15 intersection points.
After that I am lost. Can someone give an argument how to find it?

$S=\{a,a+d,a+2d,...\}$
where a,d are natural numbers. Show that there are infinitely many composite numbers in S.
It is easy to prove when $a>1$. Each element in this set is of the form $a+nd$. Whenever n is a multiple of a, then $n=ak$, thus $a+nd=a+ak=a(1+k)$. Thus n is composite. But the difficulty comes when $a=1$. I cannot find a way. Any hint will be much appreciated.

Existence of an edge that is contained in at least two cycles
Let G be a graph with n vertices and $\ge <!--\; \ge \; -->\frac{3n}{2}$ edges. Prove that there exists an edge in G that is contained in at least two different cycles.
My approach: Consider G. Pick a random edge. Let X(e) be the number of cycles that contain e. Somehow show that $E[X]>1$. Then there exists an e such that $X(e)\ge <!--\; \ge \; -->2$.
Does this probabilistic method approach work?
Edit: I would like to add that for a graph G with n vertices and m edges, one can find an edge that is present in multiple cycles, or identify if there is none, in $O(m^2(m+n))$ time with multiple DFS's.

Atleast two balls identical in 5 bags
There are five bags each containing identical sets of ten distinct chocolates. One chocolate is picked from each bag.
The probability that at least two chocolates are identical is?
I know the solution can be arrived by using 1-(none ball is picked is same) like this P(No two chocolates are identical) $10\cdot <!--\; \cdot \; -->9\cdot <!--\; \cdot \; -->8\cdot <!--\; \cdot \; -->7\cdot <!--\; \cdot \; -->6=30240$ so P(no two chocolates are identical) $={\displaystyle \frac{30240}{100000}}=0.3024$
P(At least two chocolates are identical) $=1-<!--\; -\; -->P$ (No two chocolates are identical)
$=1–0.3024=0.6976$
But I used this approach probability at least 2 bags have identical chocolates is equal to = probability of two exactly two bag having same chocolates + probability of exactly three bag having same chocolates +probability of exactly four bags having same chocolates + probability of five bags have identical chocolates.
Now I have calculated two bag having same chocolates is calculate as
No. of ways of choosing two bags C(5,2) and the these two bags have same chocolates rest have different chocolates so each C(5,2) will have $10\cdot <!--\; \cdot \; -->9\cdot <!--\; \cdot \; -->8\cdot <!--\; \cdot \; -->7$ (basically reducing number of bags having distinct chocolates to 4 by grouping pair )
So number of bags having exactly two identical chocolates is ${\displaystyle (\genfrac{}{}{0ex}{}{5}{2})\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->9\cdot <!--\; \cdot \; -->8\cdot <!--\; \cdot \; -->7=50400}$
Similarly number of bags having exactly three identical chocolates ${\displaystyle (\genfrac{}{}{0ex}{}{5}{3})\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->9\cdot <!--\; \cdot \; -->8=7200}$
Similarly number of bags having exactly four identical chocolates ${\displaystyle (\genfrac{}{}{0ex}{}{5}{3})\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->9=450}$
Similarly number of bags having exactly five identical chocolates =${\displaystyle (\genfrac{}{}{0ex}{}{5}{5})\cdot <!--\; \cdot \; -->10=10}$
Total 58060 out of total configuration $10\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->10\cdot <!--\; \cdot \; -->10=100000$
So answer becomes ${\displaystyle \frac{58060}{100000}}=0.5806$

F floors and p passengers problem
There exists an elevator which starts off containing p passengers.
There are F floors.
$\mathrm{\forall <!--\; \forall \; -->}i:P_i=$ (i. passenger exists on any of the floors) =$1/F$.
The passengers exit independently.
What's the probability that the elevator door opens on all floors?
Reasonable assumption: elevator stops on at least one of the floors.
Number of all configurations: $F^p$.
It arises as the implication that any of the passengers can exit on any of the floors.
Number of favorable configurations will be the difference between the number of all configurations and the number of ways that at least one of the floors are skipped.
Therefore the probability in accordance with the principle of inclusion-exclusion:
$\frac{F^p-<!--\; -\; -->(\genfrac{}{}{0ex}{}{F}{1})\cdot <!--\; \cdot \; -->{(F-<!--\; -\; -->1)}^p+(\genfrac{}{}{0ex}{}{F}{2})\cdot <!--\; \cdot \; -->{(F-<!--\; -\; -->2)}^p-<!--\; -\; -->...+(\genfrac{}{}{0ex}{}{F}{F-<!--\; -\; -->1})\cdot <!--\; \cdot \; -->1^p}{F^p}$
Now how to proceed from this point?

Pigeonhole principle problem - avoiding a sum in consecutive sets.
We have 48 golf balls and 30 golf holes, the holes are labeled from 1 to 30. Prove whether or not it is possible to distribute these balls into the holes while satisfying the following conditions:
1.) There must be at least one ball in each hole.
2.) The sum of balls in any number of consecutive holes cannot be 11 nor 18. (So if the fourth hole had 5 balls, fifth hole 3 balls, and sixth hole 3 balls, this would not satisfy the rule.)
I tried many different approaches (and I think that it is not possible to distribute the balls that way). First, I realized that I only need to distribute 18 balls as the 30 mandatory balls are already determined to be in the their respective holes. If I distributed 18 balls each into a different hole, at least 12 of the 30 holes would only have one ball inside. That means that in any case, there will be at least 12 holes with one ball only. But this is where I got stuck. I am not asking you to solve this problem, but I think I need a nudge towards the right way.

Arrangements of a standard deck of 52 playing cards if the denominations of the cards are ignored, so that only the suits are distinguished?
I am struggling to see why my solution is wrong for this question.
My solution:
Number of arrangements of length k is $4^k$ and, since the maximum length is 52 we have that the total possible ways is $4^1+\dots <!--\; \dots \; -->+4^{52}$.