Questions tagged [discrete-mathematics]

The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

Filter by
Sorted by
Tagged with
0
votes
0answers
14 views

Use the index calculus with factor base {2, 3} to solve $3^x \equiv 11 \pmod{37}$

I know the answer is x = 15 but I don't know how to reach that conclusion using index calculus. Please any help is greatly appreciated.
-1
votes
0answers
19 views

Finding the set of all equivalence classes for $\mathbb Z\times \mathbb Z$ on a relation

Consider the following relation $R$ on $\mathbb Z\times \mathbb Z$, $(x,y)R(z,w)$ if $2\mid (x-z)$ and $2|(y-w)$. Prove $R$ is an equivalence class and find $(\mathbb Z\times \mathbb Z)/R$. I am so ...
0
votes
0answers
14 views

Maximal number of edges

Given a simple graph on 15 vertices consists of several (more than one) isomorphic connected components. What is the maximal possible number of edges in this graph? I tried by using the bipartite ...
0
votes
1answer
10 views

Logarithmic functions complex

Are logarithmic functions not defined for negative real numbers? Since either part of a complex number (real and imaginary) can be 0 then isn't the above statement false and hence they are defined for ...
0
votes
0answers
21 views

proving the inequality related to Poisson probability

Suppose $X \sim Pois(\lambda)$. I want to show that, $$\left(P(a-1\leq X\leq b-1) \right)^2 \geq P(a\leq X \leq b)\, P(a-2 \leq X \leq b-2)$$ where $a,b \in \mathbb{N}$ and $a<b$ In other words, $$...
0
votes
2answers
30 views

how do I calculate the Thue-Morse-Sequence over the alphabet {0,1} for $\left(w_{2021}\right)_{2} \bmod 19$?

We define the Thue-Morse-Sequence over the alphabet $\Sigma:=\{0,1\}$ as follows: we set $w_{0}:=0$, and for $n \in \mathbb{N}$ we define $w_{n+1}:=w_{n} \overline{w_{n}}$, where $\bar{w}$ is the unit ...
0
votes
0answers
14 views

If $\delta (G) \geq \max \lbrace\frac{n+2}{3},\beta(G)\rbrace$ then G is Hamiltonian.

Iโ€™m trying to prove: Let $G$ be a $2$-connected graph of order $n$, independence number $\beta (G)$ and minimum degree $\delta (G)$. If $\delta (G) \geq \max \lbrace\frac{n+2}{3},\beta(G)\rbrace$ then ...
-5
votes
0answers
21 views

Proof of recursive function using induction [duplicate]

In this task Mathematical Induction has to be used
0
votes
0answers
28 views

Show that for all integers 𝑛: b) If 𝑛 | 58, then 𝑛+7 and 𝑛^2+9 are coprime.

Part a) stated : If ๐‘‘ is an integer such that ๐‘‘|๐‘›+7 and ๐‘‘|๐‘›2+9, then ๐‘‘|58. The next part (part b) is what i need help with. I thought I'd state this here for context. Working out: In order to ...
3
votes
0answers
36 views

Show that for all integers 𝑛: If 𝑑 is an integer such that 𝑑|𝑛+7 and 𝑑|𝑛2+9, then 𝑑|58.

This is the working out I have so far. Any checks to see if it is sufficient would be highly appreciated! Since $๐‘‘|๐‘›+7$, $๐‘‘| (n+7)^2= n^2+14n+49.$ By adding $(n^2+9)$, we get: $n^2+14n+49 +(n^2+9)$ ...
0
votes
1answer
48 views

How do I write equations for this Fibonacci sequence

The Fibonacci sequence can be defined using the recurrence relations: $n \in \mathbb{N} \colon F_0 = 0, F_1=1, F_{n} = F_{n-1} + F_{n-2}~~$ for $n \geq 2~~~$ (1) $n \in \mathbb{N} \colon F_0 = 0, F_1=...
0
votes
0answers
9 views

How to express a random variable as a function, given the PMF?

The problem statement of quiz 2.7 from Yates and Goodman says: The number of memory chips M needed in a personal computer depends on how many application programs, A, the owner wants to run ...
2
votes
1answer
38 views

$\forall\delta, \sigma \in F$ where $\delta \land \sigma$ are contrad., $\exists\theta$ so that $\delta\land\neg\theta$ & $\sigma\land\theta$ contrad.

I'm in my first logic class ever and I'm trying to wrap my head around this obscure question... Show that for all pairs $\delta, \sigma \in F$, where $\delta, \sigma$ contradict themselves there ...
0
votes
2answers
14 views

For $G_1$, $G_2$, $G_3$ simple undirected graphs on the same vertices with disjoint edge sets, if $G_1\cup(G_2\cap G_3)=G_2$, then $G_1=G_2$

If $G_1, G_2$ and $G_3$ are simple undirected graphs on the same set of vertices with disjoint edge sets. If we have a graph equation $$G_1\cup(G_2\cap G_3)=G_2$$ Then we have to show that $G_1=G_2,$ ...
0
votes
0answers
16 views

Write the statement using these predicates and any needed quantifiers.

Are my answers correct? In the questions below suppose the variable x represents people, F(x): x is friendly T(x): x is tall A(x): x is angry. Write the statement using these predicates and any needed ...
-1
votes
0answers
17 views

Construct an argument using rules of inference to show that the hypotheses

I practice a lot but am always confused. Can someone solve this? and if possible please explain it? this will help a lot. Construct an argument using rules of inference to show that the hypotheses. a) ...
2
votes
2answers
44 views

Generalized Understanding of “Switch” Problem

Lets assume you have a room of 10 switches that are all turned off. You also have 10 robots named 1-10. Starting with robot #1, it goes over and flips all of the switches divisible by its name. When I ...
0
votes
1answer
30 views

Determine if the relation is an equivalence relation.

I need help determining if this is an equivalence relation for my homework Given the following relation S on Z ร— Z where Z = {a, b, c, d, e}: S = {(a, a),(b, b),(a, b),(b, a),(c, c),(d, d),(e, e),(c, ...
1
vote
2answers
23 views

Relations on $\mathbb{R}^2$

I am asked to define a relation $R$ on $\mathbb{R}^2$ by $(x,y)R(u,v)$ iff $x^2+y^2=u^2+v^2$. How do I show that $R$ is an equivalence relation? The notation here is confusing me. To show reflexivity, ...
0
votes
1answer
16 views

Proving a bijection with the use of residue classes

I was given this challenge problem on an assignment and am having a difficult time understanding how to work with residue classes (denoted [n]): Prove that f : Z3->Z3 defined by f([n]) = [2n] is a ...
0
votes
0answers
29 views

Understanding Equivalence relation on a universal set

I was giving this following problem as a challenge problem, and am having a hard time understanding where to begin. Let R be the relation on a universal set U defined by A R B if, and only if, Aโˆ†B=โˆ…. ...
2
votes
1answer
41 views

How to prove that “$\forall x(P(x)\vee Q(x))$โ€ and ”$\forall xP(x)\vee\forall xQ(x)$โ€ are not equivalent?

How to prove that $โ€\forall x (P(x)\lor Q(x))โ€$ and $โ€\forall xP(x)\lor\forall xQ(x)โ€$ are not equivalent? How to prove it? I don't even know how to start.
0
votes
1answer
21 views
1
vote
0answers
27 views

Let $ G $ be a tree and $ V_0 = \left \lbrace v \in V(G) | deg (v) = 1 \right \rbrace $. Show that $ G \setminus V_0 $ is a tree.

Let $ G $ be a tree and $ V_0 = \left \lbrace v \in V(G) | deg (v) = 1 \right \rbrace $. Show that $ G \setminus V_0 $ is a tree. To see that this is true, to demonstrate: $ G \setminus V_0 $ is ...
0
votes
1answer
25 views

How to prove this is a partial order?

A relation is defined by: $x\leq y$ if and only if there exists $๐‘˜\in \mathbb{N}$ such that $y= x+5k$. Prove that $\leq$ is a partial order. I have no idea how to do this question. I've tried my best ...
3
votes
1answer
50 views

Combinatorial Necklaces & Strips of $n$ Beads and $k$ Colours

Say I have $n$ indistinguishable beads and $k$ different colours. Suppose here and for the rest of the writeup that $k \mid n$ unless otherwise stated. I want to colour all the $n$ beads using exactly ...
0
votes
1answer
29 views

Repeating an event until the actual mean equals the expected value (within a suitable degree of accuracy). How many times?

If I had a spinner, where each probability and value is known, how many times would I have to spin it to say that there is a 99% chance that my accumulated winnings' mean is within $0.01 of the ...
1
vote
0answers
18 views

contradiction in the definition of exponents of congruence class in modular arithmatics

I know that if $a\equiv b\pmod n $ ,then $a^k\equiv b^k\pmod n$ where $k \in Z^{\geq0}$.However , i saw a general definition in Discrete mathematics and applications by Sussanna 's book. It says that ...
1
vote
2answers
20 views

How to find PMF of max(X,Y) and (X|Y=1)

The joint PMF of X and Y is: I found the marginal PMF's: $$P_X(x)=\begin{cases} 0.6 & , x = 0\\ 0.4 & , x =1 & \\0 &, \text{otherwise} \end{cases}$$ $$P_Y(y)=\begin{cases} 0.3 & ...
3
votes
1answer
29 views

If $B \subsetneq A$ and $ f : A \rightarrow B $ is injective, then $ f[B] \subsetneq B $

Problem: Let $ A,B $ be sets such that if $B \subsetneq A$ and $ f : A \rightarrow B $ is injective, then $ f[B] \subsetneq B $. Attempt: Suppose $B \subsetneq A$ and $ f \in A \rightarrow B $ is ...
0
votes
2answers
50 views

Square free proof on if $b|a^2$ then $b|a$

We say that b is square-free if $b$ can be written as the product of distinct prime factors. That is, $b = p_1 \dotsm p_n$ for $p_1$ does not equal $p_2$ which does not equal $\dotsc p_n$ Let $a, b \...
0
votes
3answers
106 views

Prove $\sqrt {92}$ is an irrational number

Prove $\sqrt {92}$ is an irrational number is the question. I know how to do questions like root $4$ etc., however I do not know how to go about this any help is appreciated! This is what I have so ...
0
votes
1answer
38 views

Sample space for 3 cards chosen from a deck containing 3 red, 3 blue, 3 green, and 3 black ones.

Three non-replaced cards are randomly selected from a deck containing $3$ red, $3$ blue, $3$ green, and $3$ black cards. Specify a sample space for this experiment I think there are $220$ combinations....
2
votes
2answers
45 views

Need to calculate the probability

In an office, after having a very busy day, the secretary is just leaving the seat when the boss calls her and hands over the drafts for four letters with addresses. The secretary types the letters ...
0
votes
0answers
24 views

Let $R$ be binary relation on $\mathbb{N}$ defined by $xRy$ iff $x\leq y\leq 2x$ . Is $R$ reflexive? Is $R$ (anti)symmetric? Is $R$ transitive?

Hi I'm not sure about this question, can anybody help me out? Let $R$ be binary relation on $\mathbb{N}$ defined by $xRy$ if and only if $x\leq y\leq 2x$. Is $R$ reflexive? Is $R$ symmetric? Is $R$ ...
0
votes
1answer
26 views

Question about partial orders in set theory

$A,B$ are members of $\mathcal{P}({1,2,3,4})$. The relation $S$ is defined by $ASB$ if and only if: $A\cup\{1,2\}$ is contained in $B\cup\{1,2\}$. Find the minimal and maximal elements of $ASB$. So it ...
0
votes
1answer
11 views

How to show that the difference of two Gumbel distributed random variables makes a Logistic distribution?

How to show that, for two random variables XโˆผGumbel[a,b] and YโˆผGumbel[c,b], Xโˆ’YโˆผLogistic[a-c,b]? Can anyone show step by step how to make solution? Thank you!
-1
votes
0answers
16 views

Reducing ((x + y) โ‡’ (y + z)) โŠ• xw to conjunctive normal form (CNF)

How can I reduce this boolean function to conjunctive normal form? $$((x + y) โ‡’ (y + z)) โŠ• xw$$ It may be possible to do using truth tables, but I am not sure. I was able to get $(w * y) + (z * ! z * !...
0
votes
3answers
51 views

How do i prove a recursion with $ a_n = 3 \cdot 2^{(n-1)} + 2(-1)^n $ so that for all $ n \in \mathbb{N} $ it is true?

I am pretty new when it comes to recursion together with induction. I would appreciate if somebody could show me how to approach this kind of problem: $$ a_n = \begin{cases} ...
0
votes
1answer
15 views

How to find marginal CDF from joint PMF?

If I have the joint PMF: $$P_{X,Y}(x,y)=\begin{cases} 0.01, & x,y=1,2,3,\ldots,10 \\ 0, & \text{otherwise} \end{cases}$$ How would I proceed if I want to find $F_X(x)$ from here? I now this ...
0
votes
1answer
27 views

Reduce ((y โŠ• z) โ‡’ (x + y)) โ‡’ yz to disjunctive normal form (DNF)

How can I reduce this boolean function to disjunctive normal form? $$((y โŠ• z) โ‡’ (x + y)) โ‡’ yz$$ It may be possible to do using truth tables, but I am not sure. If it's possible to give examples with ...
0
votes
1answer
12 views

How to find conditional joint CDF, given an event and a function?

Random variables X and Y have the joint PDF: $$f(x,y)=\begin{cases} xy\over4000 & , 1\leq x\leq 3; 40\leq y\leq 60\\ 0 & , \text{otherwise} \end{cases}$$ For random variable $W = XY$, we ...
0
votes
1answer
38 views

Sets having the same cardinality

I am asked to think of an example of cardinality being the same between two sets X and Y such that the function from X to Y is one to one but it is not onto. I am so confused about this one because I ...
2
votes
3answers
56 views

If $w$, $x$, $y$, and $z$ are real numbers with $w < x$ and $y < z$, is the cardinality of the closed interval $[w,x]$ the same as that of $[y,z]$? [duplicate]

My reasoning is yes. I tried to draw a few example functions and based on my workings, think that the answer should be yes but I couldn't figure out how exactly I should mathematically prove the fact. ...
0
votes
0answers
29 views

Probability of choosing the same letter

Suppose you are choosing a letter at random from the word DISCRETE and your friend chooses a letter at random from the word ALGEBRA. What is the probability that you choose the same letter? This is my ...
0
votes
1answer
39 views

How to prove that for all odd $ n \in \mathbb{N} $ can be displayed as the difference of two square numbers?

I need guidance / correction for my proof. It's a little bit longer, but we really have to consider everything. If you find some issues / mistakes or have suggestions to improve it, please let me know!...
3
votes
1answer
79 views

What does $[n=1]$ mean?

Studying recurrence relations I stumbled upon this expression in a solution to the problem of finding a closed formula to this: $a_n = 5a_{n-1} - 6a_{n-2}; a_0 = 0, a_1 = 1$ To start the solution, the ...
0
votes
1answer
33 views

In an $8\times 8$ square, what's the min number of dots to be placed so that there's always a pair with distance apart at most $\sqrt8$?

By the Pigeon Hole Principle (PHP), we know that when we are to place $17$ dots in an $8 \times 8$ square, then there will always be a pair with distance $< \sqrt8$. However, does PHP actually ...
0
votes
1answer
21 views

count equivalence relations on a set with 6 members including and excluding certain pairs

I want to count the equivalence relations on the set ${\{1,2,3,4,5,6}\}$ with the conditions that the relation includes the tuples ${(1,2)}$ and ${(2,3)}$ but it does not include the tuple ${(3,4)}$ I ...
0
votes
0answers
5 views

Define several atomic formulas to determine whether a graph is a Hamiltonian graph

how to define several atomic formulas to determine whether a graph is a Hamiltonian graph? It seems that Hamiltonian graph is a very hard problem. I know that a graph is a Hamiltonian graph if the sum ...

1
2 3 4 5
โ€ฆ
574