Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

-2
votes
1answer
24 views

How true their claims are?

Your introductory Real Analysis textbook does not make complete sense and suddenly mathematics is so counterintuitive. The theory of mathematics is wrong and this book shows you exactly why. The empty ...
-1
votes
1answer
22 views

Probability of events having to deal with a string permutation question

I am studying for a discrete math exam tomorrow and this is one of the review questions. I am having trouble answering the question as of now. If you could provide guidance on how to solve one or more ...
0
votes
2answers
24 views

How do I prove this relation is symmetric? F = {(n,m)| (2n+3m) is divisible by 5}

The relation F on Z is defined by F = {(n,m)| (2n+3m) is divisible by 5} I need help proving this relation is symmetric. I know I should choose two members of Z and assume F(x,y). and I know I need ...
0
votes
0answers
11 views

Boolean Algebra: Demonstrate that the pentagon lattice is non-distributive

I just started learning Boolean Algebra and have this homework question Demonstrate that the pentagon lattice is non-distributive I know this is non-distributive because $b$ complements $a$ and ...
2
votes
2answers
18 views

determine maximum remaining teams in a round robin tournament

Let's say I have 10 teams competing in a round-robin tournament. Ties are not allowed, and only teams that have at least 7 wins can move on to a new tournament. How would I go about proving the ...
0
votes
1answer
15 views

Problem: How many 'timetables' can be created for visiting 8 different lectures without time clashes?

Apologies for the poorly worded question but it really requires more explanation than can be done with one line. I have a statistics problem, or rather, a timetabling problem that I feel can be solved ...
0
votes
1answer
34 views

Traffic light problem

A car moves from point A to point B at speed v meters per second. The action takes place on the X-axis. At the distance d meters from A there are traffic lights. Starting from time 0, for the first g ...
0
votes
1answer
31 views

Number of permutations differing in at least $d$ spots in pairwise comparisons

A friend and I were thinking about this problem today but we were unable to come up with a solution. Problem: Consider the the numbers $S=\{1,\ldots,n\}$. Given $2\le d \le n$ what is the ...
0
votes
1answer
14 views

Need help with relation properties using logical operators

I was wondering how should I proceed to determine what will be in the relation and what will not given these properties. Operating with integers: $R: \{(a, b)|(a= 0∧b= 0)∨ GCD(a, b) = 5\}$
0
votes
2answers
41 views

Understanding Big O notation - discrete math?

I have questions with the solutions below but I'm still having trouble understanding how to solve these problems? Like for a) I don't understand how 17$n^2$ + 4𝑛 got turned into 17$n^2$ + 4$n^2$. ...
0
votes
0answers
15 views

Poset and lattice

Define and verify on the set of positive divisors of 70 a poset,a lattice with its types,and a Boolean algebra. I have tried to do this question but I don't know the correct method
12
votes
2answers
1k views

Why aren't these two solutions equivalent? Combinatorics problem

I was given the following fact: there is a set $S$ of $11$ people, among which there are $4$ professors and $7$ students, $S=\{p_1, p_2, p_3,p_4, s_1, s_2,...,s_7\}$ We are requested to form from ...
1
vote
1answer
26 views

Prove G is non-planar by contradiction

$G=(V,E). |V| = 25; |E| = 50.$ For every vertex $v \in V$, the degree of that vertex $d(v)=4.$ I am given that the shortest cycles in $G$ are 4-cycles (i.e. with 4 vertices). For a contradiction I ...
0
votes
0answers
10 views

finding the most general unifier

i am trying to find the most general unifier of the following: 1)Daughter(Uncle(y),y), Daughter(Uncle(x),emily) 2)Loves(cat(x),x), Loves(y,y) what i think: 1)$\theta = [emily/y, x/y]$ 2)$\theta = ...
-2
votes
2answers
37 views

Show that the five digit number abcde is congruent (mod11) to $(a + c + e) - (b + d)$ [on hold]

Show that the five digit number $abcde$ is congruent (mod $11$) to $(a + c + e) - (b + d)$
-1
votes
3answers
48 views

Prove: $\gcd(b,a) = \gcd(b,c)$ if $c \equiv a \pmod{b}$ [duplicate]

$b$ is an integer where $b > 1$ and $a, c$ are integers. Prove: $\gcd(b,a) = \gcd(b,c)$ if $c \equiv a \pmod{b}$ I am completely stumped on where to start. Any help is appreciated.
1
vote
3answers
41 views

Discrete math - The ceiling of a real number x, denoted by$ ⌈𝑥⌉$, is the unique integer that satisfies the inequality

I have a discrete math question below with a solution written by my teacher. I'm really lost as to what answers I'm trying to find exactly. I don't understand how the teacher got 1 and -1 for the ...
-2
votes
1answer
67 views

how many integers between $1000$ and $9999$ is the sum of digits equal $11$ [on hold]

I have already known that all cases is $\binom{13}{3}$, but I don' know how to handle the bad cases, such like putting $10$ objects in the first box.
-2
votes
1answer
48 views

Suppose A = {1, 2, 3, 4, 5}. Mark the statement TRUE or FALSE. [on hold]

I got the first few, but im not sure about these: {2,4}⊂A×A. {∅} ∈ P(A). (1,1)∈A×A.
0
votes
1answer
31 views

Suppose G is a group, a, b ∈ G such that |b| = 2 and bab = a^4 . [on hold]

I know that answer is (2) |a| divides 15 but I'm not sure how they got the answer, any hints will be helpful thank you.
1
vote
0answers
24 views

Arrange the functions in a list so that each function is big-O of the next function.

If 2 functions each big $\mathcal O$ of each other, then place them on the same level. $x^2 + x^3, 3^x, x!, x \log(x), x^2 + 2^x, 2^{x \log(x)}, \log(x^2), 6 \log(x), 2^x, x(1+2+\dots+x)$ My answer ...
0
votes
4answers
42 views

Why does $x!$ grow faster than $(x/2)^{(x/2)}$ but slower than $x^x$?

I'm having trouble understanding this. I understand the reasoning about why $x!$ grows slower than $x^x$. However, I'm not sure how to show that $x!$ grows faster than $(x/2)^{(x/2)}$. I was ...
-1
votes
1answer
41 views

Let $f(n) = 5n^4 + 3n^3 − 5$. Show that $f(n)$ is $Θ(n^4)$.

How should this be proved? I know that $f(n)$ is $Θ(n)$ if and only if $f(n)$ is $O(g(n))$ and $f(n)$ is $Ω(g(n))$ and that If $f(n)=\theta(g(n))$ then $\lim_{n \to \infty}\frac{f(n)}{g(n)}$ will be ...
0
votes
2answers
25 views

Roots of unity divisibility.

Suppose $r | n$. Then $R:= e^{2i \pi k/r}$ is an $n$-th root of unity. Thus, there exists a unique $l \in \{0, \dots, n-1\}$ such that $R = e^{2\pi i l/n}$. Does it hold that $l |n$? I tried to ...
0
votes
0answers
40 views

I did not know how to Express in terms of a and b

The vectors a and b are the two vectors drawn from a vertex of a square to the two adjacent vertices. Express in terms of a and b the vector of the diagonal drawn from the same vertex.
0
votes
2answers
53 views

Proving $1+\sqrt2+\sqrt3$ is irrational [duplicate]

How can I prove that $1+\sqrt2+\sqrt3$ is an irrational number, without proving first $\sqrt2$ and $\sqrt3$ are irrational numbers? Please give some hints or suggestion to proceed with this proof. ...
1
vote
3answers
48 views

A coin is flipped 14 times. How many different outcomes have at most 10 heads?

I followed the pattern here but it still resulted in my problem being incorrect. How many outcomes of a coin being flipped 12 times have exactly 4 heads? (1 pt) A coin is tossed 14 times. d) How ...
1
vote
2answers
57 views

How many times does the binary digit $1$ appear in numbers $0$ to $255$?

I am trying to find an easy way to calculate the number of times that the digit "$1$" appears in numbers $0-255$ (in the binary system). I consider the answer must be a power of $2$ since $256 = 2^8$ ...
0
votes
0answers
30 views

Rewrite a cubic summation [on hold]

how do you write $$\left(\sum_{i=1}^{k}{ i^3}\right) + (k+1)^3$$ as a single summation?
0
votes
1answer
55 views

Is $2(2^{p} − 1)$ a divisor of $n$? How about $2^2(2^p − 1)$? Finish the proof. [on hold]

A positive integer is called perfect if it equals the sum of its positive divisors. Example: $6$ is perfect because the divisors of $6$ are $1,2$ and $3$ and $6=1+2+3$. Show that $28$ is perfect. ...
-1
votes
1answer
37 views

How do you find a defined relation?

So this may be a really simple obvious question, but this is something that kind of trips me up. I'm a beginner at this type of stuff, and still learning. In my past experience if I see the relation ...
0
votes
1answer
21 views

Is this the correct relation for a finite set?

Given a finite set S, let the relation R = {(S1, S2) | |S1| < |S2|, S1, S2 ⊆ S}. Show whether or not R is reflexive, symmetric, antisymmetric or transitive. So if S = {1,2} $R = \{(\emptyset,\...
2
votes
1answer
36 views

Is this the correct solution to find a number of one-to-one functions?

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x? If we take $A_{i}$ to be a set of one-to one ...
0
votes
1answer
51 views

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x?

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x? Alright so I did see this question, but it really ...
0
votes
3answers
19 views

How do I prove growth of functions with exponents?

Prove that $16 + 3^n=O(4^{n})$. I have tried to do this problem but cannot find a constant $c$ that I am supposed to find.
0
votes
2answers
44 views

How to prove there are unreachable states in this bit flipping algorithm only for lengths $n=3k+2$?

This is similar to Bit flipping algorithm, but the algorithm is a little different. Specifically, we have bit string of length $n$, and we can choose any bit to flip and then we flip also the two ...
0
votes
0answers
10 views

Given L, s and d, which are positive real number, what is the probability that there exist integer k and k', such that $kd\in [k'(L+s)-s, k'(L+s)]$

Given $L$, $s$ and $d$, which are positive real numbers, is there always a pair of integers k and k', such that $kd\in [k'(L+s)-s, k'(L+s)]$. It is like there is a line which is painted red of length $...
3
votes
1answer
35 views

fibonacci and lucas numbers induction

I'm having trouble proving by induction that this following Fibonacci-Lucas equation $$F_{2n+k} = F_n L_{n+k} + (-1)^n F_k \tag{*}$$ is true, given that $$F_{2n} = F_nL_n$$ and $$F_{2n+1} = ...
-1
votes
1answer
41 views

I need help with induction proof [on hold]

Prove by induction if Chicken McNuggets are sold in quantities of 6, 9, and 20, then the largest amount that cannot be purchased is 43.
0
votes
0answers
10 views

What is the cardinality of |S x I| for an elevator FSM that serves n floors? [on hold]

S = Set of states and I = Set of inputs. S = {Ground, first, second, n} I = {G, 1, 2, n}
0
votes
0answers
28 views

If more than half of the integers from $\{1, 2, \ldots, 2n\}$ are selected, then they must include two integers such that one divides the other [duplicate]

Pigeonhole Principle problem: If more than half of the integers from $\{1, 2, \ldots, 2n\}$ are selected, then there must exist two integers among the selected integers that have the property that ...
2
votes
0answers
41 views

Assigning people to jobs

We have $n$ people and $n$ jobs. Assume that each person is able to do $k$ jobs $0<k<n$ and each job can be done by $k$ people. Proof that each job can be done at the same time My try Ok, I ...
-1
votes
1answer
35 views

How to discretize and normalize an $n*n$ Gaussian kernel?

A 3x3 Gaussian kernel is usually shown as $$\frac{1}{16} \begin{bmatrix}1 & 2 & 1\\ 2 & 4 & 2\\ 1 & 2 & 1\end{bmatrix}$$ But where does that actually come from?
0
votes
1answer
24 views

How would you notate that something is not in the domain of discourse?

For example, saying that something is specifically not in the domain of integers (not sure how to write the 'N' symbol).
-1
votes
2answers
45 views

How do I prove this by induction? With the induction on n [on hold]

How do I prove this with mathematical induction, the entire problem is like a Putnam/coffin problem, where the solution is almost impossible.I proved the basis case with a_0. But after that, when I ...
0
votes
1answer
26 views

How to prove this fact about the discrete closure? [on hold]

The content is given two relationships: R₁ and R₂ prove that s(R₁ ∩ R₂)=s(R₁) ∩ s(R₂) My teacher has taught us the UNION versions in class, and I figure it's easy. Also I have already finished the ...
1
vote
1answer
57 views

Is there a way to classify all power-invariant graphs?

Suppose $G = (V, E)$ is a finite undirected simple graph. Let’s, define the $n$-th power of a graph (where $n \in \mathbb{N}$) as graph $G^n = (V, E_n)$, where $$E_n = \begin{cases} E & \quad n = ...
1
vote
0answers
32 views

Given a finite set S, let the relation R = {(S1, S2) | |S1| < |S2|, S1, S2 ⊆ S}. Is R reflexive, symmetric, antisymmetric or transitive.

Given a finite set S, let the relation R = {(S1, S2) | |S1| < |S2|, S1, S2 ⊆ S}. Show whether or not R is reflexive, symmetric, antisymmetric or transitive. I'm shaky on how to approach this ...
-1
votes
3answers
27 views

Explicit form of $ b_1= 2, b_k = b_{k-1} + 2\cdot 3^k$ for all integers $ k\ge 2 $ [closed]

As the title says, I need to find the explicit form of the recursive sequence defined above, and I am very stuck on this.
0
votes
0answers
56 views

Check my math - Number of one-to-one functions $f$ from $\{1, \ldots, n\}$ to $\{1, \ldots, 2n-1\}$ such that $f(x) \neq 2x - 1$ for all $x$

What is the number of one-to-one functions $f$ from the set $\{1, 2, \ldots, n\}$ to the set $\{1, 2, \ldots, 2n − 1\}$ so that $f(x) \neq 2x − 1$ for all $x$? I'm not sure if I did the question ...