Explore Discrete Math Examples

A relation that is both an equivalence relation and a function.
The question is: "Suppose R on A is both an equivalence relation on A and a function from A to A. What is R?" I'm not entirely sure where to start, I'm not even sure I understand what a function from A to A represents, can anybody help with this?

How many odd 6 digit numbers can be formed by using the digits 1,2,3,4,5,6 which are divisible by 3?
I have found that we have $3\cdot <!--\; \cdot \; -->6^5$ odd numbers. I understand, that if number is divisible by 3, the sum of its digits also should be divisible by 3, but I don't know how to use this...

Problem of selection from overlapping sets
For a positive integer m, let $A_1,\dots <!--\; \dots \; -->,A_m$ be (not necessarily disjoint and potentially empty) finite sets and let $c_1,\dots <!--\; \dots \; -->,c_m$ be non-negative integers. Suppose that
- each set $A_i$ contains at least $c_i$ elements; and
- the union $\underset{i=1}{\overset{m}{\bigcup <!--\; \bigcup \; -->}}{A}_i$ contains precisely $\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}{c}_i$ elements.
Intuitively, it should be possible to choose precisely $c_i$ elements from each $A_i$ in such a way that no element is picked twice. Formally, what I want to prove is that there exist sets $(B_i{)}_{i=1}^m$ such that
- $B_i\subseteq <!--\; \subseteq \; -->A_i$ for each i;
- the cardinality of $B_i$ is precisely $c_i$ for each i; and
- $B_i\cap <!--\; \cap \; -->B_j=\mathrm{\varnothing <!--\; \varnothing \; -->}$ for $i\ne <!--\; \ne \; -->j$.
I tried induction on the number of sets. The case $m=2$ is pretty straightforward. (Assign $A_1\setminus <!--\; \setminus \; -->A_2$ to $B_1$, assign $A_2\setminus <!--\; \setminus \; -->A_1$ to $B_2$, and divvy up $A_1\cap <!--\; \cap \; -->A_2$ between $B_1$ and $B_2$; this can be done in the desired way, so that $\mathrm{\#<!--\; \#\; -->}{B}_1=c_1$ and $\mathrm{\#<!--\; \#\; -->}{B}_2=c_2$.) But then I got stuck with having the induction hypothesis carry over.
In particular, the main difficulty is that if $\underset{i=1}{\overset{m+1}{\bigcup <!--\; \bigcup \; -->}}{A}_i$ contains $\underset{i=1}{\overset{m+1}{\sum <!--\; \sum \; -->}}{c}_i$ elements, this does not necessarily imply that the smaller union $\underset{i=1}{\overset{m}{\bigcup <!--\; \bigcup \; -->}}{A}_i$ contains precisely $\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}{c}_i$ elements, as the sets are not necessarily disjoint. This makes the inductive proof more difficult, and a non-inductive proof (relying on, say, inclusion-exclusion) seems prohibitively complicated.
I am hoping that someone reading this may have an ingenious shortcut in mind as to how to make the induction hypothesis go through.

A vertex of a minimum vertex cut has a neighbor in every component
I'm trying to understand the solution for the following problem: Prove that ${\mathrm{\kappa <!--\; \kappa \; -->}}^{\prime }(G)=\mathrm{\kappa <!--\; \kappa \; -->}(G)$ when G is a simple graph with $\mathrm{\Delta <!--\; \Delta \; -->}(G)\le <!--\; \le \; -->3$.
The solution goes like this: Let S be the minimum vertex cut, $|S|=\mathrm{\kappa <!--\; \kappa \; -->}(G)$. Since $\mathrm{\kappa <!--\; \kappa \; -->}(G)\le <!--\; \le \; -->{\mathrm{\kappa <!--\; \kappa \; -->}}^{\prime }(G)$ always, we need only provide an edge cut of size |S|. Let $H_1$ and $H_2$ be two components of G-S. Since S is a minimum vertex cut, each $v\in <!--\; \in \; -->S$ has a neighbor in $H_1$ and a neighbor in $H_2$. The solution conntinues from here...I really have no clue why the part "Since S is a minimum vertex cut, each $v\in <!--\; \in \; -->S$ has a neighbor in $H_1$ and a neighbor in $H_2$." is true.
I tried to show it by contradiction but haven't gotten very far: Suppose otherwise; then there exists a vertex $v\in <!--\; \in \; -->S$ which doesn't have a neighbor in $H_1$. We can assume that G is connected, hence there is a path joining v with $u\in <!--\; \in \; -->V(H_1)$... and I'm stuck. How do I proceed from here? Or should I try to prove this in a completely different way?

Proving two integers are relatively prime using Bezout's Theorem.
If $\gcd <!--\; \; -->(a,b)=1,$, a and b are relatively prime and also if gcd(a,b) is equal to 1 there should be 2 integers k and m such that $ak+bm=1.$.
If we can find such integers k and m, is it a proof that a and b are relatively prime ?
What you think about that proof? Is it correct way?

How to prove $A+A^{\prime }B+A^{\prime }{B}^{\prime }C+A^{\prime }{B}^{\prime }{C}^{\prime }D=A+B+C+D$
Prove the above relationship by using the Boolean definition. I tried $A+A^{\prime }B=A+B$, but end up with $A+B+A^{\prime }{B}^{\prime }(C+D)$, how can I go next?

Does LCM have distributive property of multiplication?
Is statement $lcm(ax,ay)=a\ast <!--\; \ast \; -->lcm(x,y)$ true? (assuming all variables are positive integers)

Why does "Some student has asked every faculty member a question" translate to $\mathrm{\forall <!--\; \forall \; -->}y(F(y)\to <!--\; \to \; -->\mathrm{\exists <!--\; \exists \; -->}x(S(x)\vee <!--\; \vee \; -->A(x,y)))$ ?
Context: I'm in undergrad discrete math, this is a textbook question from Discrete Mathematics and its Applications 7th edition
Here's the question:
Let S(x) be the predicate "x is a student," F(x) the predicate "x is a faculty member," and A(x, y) the predicate "x has asked y a question," where the domain consists of all people associated with your school. Use quantifiers to express the following statement.
Some student has asked every faculty member a question.
This is what the textbook says is the correct answer:
$\mathrm{\forall <!--\; \forall \; -->}y(F(y)\to <!--\; \to \; -->\mathrm{\exists <!--\; \exists \; -->}x(S(x)\vee <!--\; \vee \; -->A(x,y)))$
I mostly understand how this is correct, but shouldn't it be $\wedge <!--\; \wedge \; -->$ instead of $\vee <!--\; \vee \; -->$?

Bounding the order of tournaments without transitive subtournaments of certain size.
A tournament of order N is a directed graph on [N] obtained by assigning a direction to each edge of $K_N$. A tournament D is transitive if for every triple $a,b,c\in <!--\; \in \; -->N$, $(a,b),(b,c)\in <!--\; \in \; -->E(D)$ implies that $(a,c)\in <!--\; \in \; -->E(D)$. For $n\in <!--\; \in \; -->\mathbb{N}$ let f(n) be the maximum integer such that there exists a tournament of order f(n) without a transitive sub-tournament of size n. Show that $f(n)>(1+o(1))2^{\frac{n-<!--\; -\; -->1}{2}}$.

Find the sequence $a_k$ for generating function ${\left(\frac{1-<!--\; -\; -->x^3}{1-<!--\; -\; -->x}\right)}^n$.
We know that $\frac{1}{(1-<!--\; -\; -->x{)}^n}=\underset{k=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{k+n-<!--\; -\; -->1}{n-<!--\; -\; -->1})x^k$
I also worked out $(1-<!--\; -\; -->x^3{)}^n$ using the binomial theorem and got $(1-<!--\; -\; -->x^3{)}^n=\underset{i=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^i(\genfrac{}{}{0ex}{}{n}{n-<!--\; -\; -->i})x^{3i}$.
I'm not sure what to do with these to get $a_k$ from $\underset{k=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{a}_k{x}^k$ or if these are even what I need to solve the problem

Probability or expected value of hirings the company will make?
A company is hiring for an open position and has n interviews set up, one per day. Each day, if the candidate is better than the current employee, the employee is fired and the candidate is hired. Otherwise, the current employee keeps the job. What is the expected number of hirings the company will make?
I got the answer of $\frac{1+(n-<!--\; -\; -->1)}{2}$. Is this correct? I used the probability of no new hires and all new hires.

The Relation between Sets
if I have a relation between $A\times <!--\; \times \; -->A$
if $A=\{1,2,3\}$
if $B=\{1,2,3\}$
$R=\{(1,1),(2,2),(3,3)\}$
can I say that the Relation R is Reflexive and also a Symmetric because I have (a,b) and (b,a) and also (a,a).

Partitions of n where every element of the partition is different from 1 is $p(n)-<!--\; -\; -->p(n-<!--\; -\; -->1)$
I am trying to prove that p(n| every element in the partition is different of $1)=p(n)-<!--\; -\; -->p(n-<!--\; -\; -->1)$, and I am quite lost... I have tried first giving a biyection between some sets, trying to draw an example in a Ferrers diagram and working on it... Nevertheless, I have not obtained significant results. Then, I have thought about generating functions; we know that the generating function of $\{p(n){\}}_{n\in <!--\; \in \; -->\mathbb{N}}$ is $\underset{i=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\prod <!--\; \prod \; -->}}\frac{1}{1-<!--\; -\; -->x^i}$, so $\{p(n-<!--\; -\; -->1){\}}_{n\in <!--\; \in \; -->\mathbb{N}}$ will have $\underset{i=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\prod <!--\; \prod \; -->}}\frac{x}{1-<!--\; -\; -->x^i}$ as generating function. So, what we have to prove is that $\underset{i=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\prod <!--\; \prod \; -->}}\frac{1}{1-<!--\; -\; -->x^i}-<!--\; -\; -->\underset{i=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\prod <!--\; \prod \; -->}}\frac{x}{1-<!--\; -\; -->x^i}=(1-<!--\; -\; -->$-x). $\underset{i=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\prod <!--\; \prod \; -->}}\frac{1}{1-<!--\; -\; -->x^i}$ is the generating function of p(n|every element in the partition is different of 1)... but i'm am not seeing why! Any help or hint will be appreciate it!

The random variable X has homogeneous distrigution
I have a problem with exercise:
The random variable X has a homogeneous distribution in the interval [0,1]. Random variable $Y=max(X,1/2)$. Please find the expected value of a random variable Y. I need to do this for discrete variables and also for continuous variable

There is a subset $T\subset <!--\; \subset \; -->S$ with $|T|=k+1$ such that for every $a,b\in <!--\; \in \; -->T$, the number $a^2-<!--\; -\; -->b^2$ is divisible by 10.
Let $k\ge <!--\; \ge \; -->1$ be an integer.
If S is a set of positive integers with $|S|=N$, then there is a subset $T\subset <!--\; \subset \; -->S$ with $|T|=k+1$ such that for every $a,b\in <!--\; \in \; -->T$, the number $a^2-<!--\; -\; -->b^2$ is divisible by 10.
What is the smallest value of N as a function of k so that the above statement is true?
Step 2
I have observed that perfect squares end with 0,1,4,5,6 and 9. If we have two perfect squares that end with the same as one of 0,1,4,5,6 and 9, then we are done.
I think by PHP we should have $\lceil \frac{N}{k}\rceil =6$

Discrete Mathematics what exactly does from A to B mean?
Like if there's some relation R from a set A to a set B what exactly does this mean?
I know it's just a subset of the Cartesian product $A\times <!--\; \times \; -->B,$, but what exactly does from A to B mean..? Like obviously from B to A is different so can anyone explain what the FROM really means here?

Proof that $\lfloor -<!--\; -\; -->x\rfloor =-<!--\; -\; -->\lceil x\rceil$
I wanted to ask if this kind of reasoning for proving the result in the title could be considered correct:
We know that: $\lceil x\rceil =n$ if and only if $n-<!--\; -\; -->1<x\le <!--\; \le \; -->n$
Then $-<!--\; -\; -->\lceil x\rceil =-<!--\; -\; -->n$ if and only if $-<!--\; -\; -->n-<!--\; -\; -->1<x\le <!--\; \le \; -->-<!--\; -\; -->n$
Then multiplying by -1 the formula $-<!--\; -\; -->n-<!--\; -\; -->1<x\le <!--\; \le \; -->-<!--\; -\; -->n$ we get $n+1>-<!--\; -\; -->x\ge <!--\; \ge \; -->n$, inverting the sign.
But $n+1>-<!--\; -\; -->x\ge <!--\; \ge \; -->n$ is equivalent to $n\le <!--\; \le \; -->-<!--\; -\; -->x<n+1$.
We know that $\lfloor x\rfloor =n$ if and only if $n\le <!--\; \le \; -->x<n+1$.
So from $n\le <!--\; \le \; -->-<!--\; -\; -->x<n+1$ we can infer that $\lfloor -<!--\; -\; -->x\rfloor =$ $n=-<!--\; -\; -->\lceil x\rceil$

Find all complex numbers z such as z and 2/z have both real and imaginary part integers
I am really struggling to solve this one. I feel like I am missing the key part of the solution, so I would like to see how it's done.
Find all complex numbers $z=x+yi$ such as z and $2z^{-<!--\; -\; -->1}$ have both real and imaginary part integers
This is what I thought:
$2z^{-<!--\; -\; -->1}=\frac{2}{z}=\frac{2}{x+yi}=\frac{2}{x+yi}\cdot <!--\; \cdot \; -->\frac{x-<!--\; -\; -->yi}{x-<!--\; -\; -->yi}=\frac{2x-<!--\; -\; -->2yi}{x^2+y^2}.$.
In order to $2z^{-<!--\; -\; -->1}$ have its imaginary part $\in <!--\; \in \; -->\mathbb{Z}$, we should equal 2y to 0
$2y=0\Rightarrow <!--\; \Rightarrow \; -->y=0$
$yi=0$ is an integer.
x must also be an integer. We simply assume $x\in <!--\; \in \; -->\mathbb{Z}$ (no matter what value x has, as long as it's an integer, we are good).
We do the same for z and find out the same values $yi=0$ and $x\in <!--\; \in \; -->\mathbb{Z}$.
Therefore, the set $A=\{(x,y)\in <!--\; \in \; -->\mathbb{C}|x\in <!--\; \in \; -->\mathbb{Z}\text{ and }y=0\}$ is the set of all complex numbers whose real and imaginary part are integers.

Given $f:E\to <!--\; \to \; -->E$ and $f\circ <!--\; \circ \; -->f=f$. Prove that if f is surjective or injective then $f=I{d}_E$.

A box contains 20 green balls and 25 red balls. Two balls are chosen at random, one after the other, without replacement?
i. What is the probability that both balls are red?
ii. What is the probability that the second ball is red but the first ball is not?
iii. What is the probability that the second ball is green?