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.

learn more… | top users | synonyms

1
vote
2answers
45 views

6th Grade Problem

Here's a problem from a 6th Grade textbook: A project was carried out by a 3-man brigade working for 5 days and a 4-man brigade working for 4 days. $390 was paid for the whole project. How much was ...
-1
votes
0answers
15 views

Comparison between sum and big Theta

I have a problem, I don't know how is the way to resolve this question. Let $f(n) = \sum\limits_{i=2}^n \frac{1}{i \ln i}$. Show that $f(n)= \Theta(\log \log n)$. thank you for your help. Julien ...
0
votes
0answers
25 views

How to substitue a proof (algebra) [on hold]

$ak_1=b$ $ak_2=c$ Hello How do I substitute $ak_1$ for b in $ak_2=c$? I know the result, but I don't know how to get it.
1
vote
0answers
11 views

drawing diagram for binary relation

im working on the practice problem on unit about sets and relations The question is: Let a = {1,2,3,4} and R be a binary relation on A x A given by: ((a,b),(c,d)) ∈R if and only if a divides c and b ...
0
votes
1answer
21 views

Finding the subsets in a set that contains x or y but not z

Let S be a set of size 37, and let x, y, and z be three distinct elements of S. How many subsets of S are there that contain x or y, but do not contain z? $(a) 2^{36} − 2^{34}$ $(b) 2^{36} − 2^{35}$ ...
0
votes
0answers
12 views

Question about Anti Symmetricity

If there are no relations on the set R where (a,b) ∈ R and (b,a) ∈ R is it anti symmetrical because you can't evaluate if a = b or is it not anti-symmetrical because you can't evaluate if a = b? ex) ...
3
votes
2answers
27 views

How to count the amount of subsets within a set

Let S be a set of size 37, and let x, y, and z be three distinct elements of S. How many subsets of S are there that contain x and y, but do not contain z? (a) $2^{33}$ (b) $2^{34}$ (c) $2^{35}$ ...
1
vote
1answer
55 views

how to fnd if R is an order?

hello i have a upcoming quiz and I was solving practice problems that the instructor gave us. But Im not sure how to approach this problem the problem is: Let $A = \{1,2,3,4\}$, and $\mathcal{R}$ be ...
0
votes
1answer
40 views

Show that R is an equivalence relation, where $(a, b)R(c, d) \iff a − d = c − b$ [on hold]

Let $R$ be the relation on $\mathbb Z \times\mathbb Z$, that is elements of this relation are pairs of pairs of integers, such that $((a, b),(c, d)) \in R$ if and only if $a − d = c − b$. Show ...
0
votes
0answers
21 views

Discrete Structrue

I was stuck with the following problem. Two players A and B play a game where they take turns adding numbers from 1 through 10, and the first person who gets to the target of 100 wins. Assume A ...
2
votes
2answers
52 views

$\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$

Please help! I need help on my assignment for discrete mathematics! Prove the following identity: $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$ I need to ...
3
votes
2answers
24 views

Equivalence Relations on Set of Ordered Pairs

Let $\mathbb{R}$ be the relation on $\mathbb{Z} \times \mathbb{Z}$, that is elements of this relation are pairs of pairs of integers, such that $((a,b),(c,d)) \in \mathbb{R}$ if and only if $a-d = ...
0
votes
1answer
18 views

Make a list of pairs given sets of a relation

Make a list of pairs for the relation R from the set A = {0, 1, 2, 3, 4} to the set B = {0, 1, 2, 3} such that (a, b) ∈ R if and only if a - b < 1. How would "a - b < 1" play into determining ...
1
vote
0answers
28 views

Solving matrix equation of the form $(AX)^2+(BY)^2=D$

Is there any method that can solve the matrix equation of the form $(AX)^2+(BY)^2=D$? $A$ and $B$ are matrices, $X$, $Y$ and $D$ are column vectors. (Solve for $X$ and $Y$) I originally have two ...
1
vote
1answer
34 views

How to show if A (A△B)△C=A△(B△C) [duplicate]

im working on problem that asks me to show that for any set a,b,c (A△B)△C=A△(B△C) In my opinion, I can just use associative law of set theory and just conclude that left equals the right. But then ...
0
votes
1answer
72 views

How to show that R(binary relation on A x A) is an order?

im working on the practice problem on unit about sets and relations The question is: Let a = {1,2,3,4} and R be a binary relation on A x A given by: ((a,b),(c,d)) ∈R if and only if a divides c and b ...
0
votes
2answers
83 views

Relation that is only symmetric, reflexive, antisymmetric or transitive?

What could be a possible example of a relation that's symm, reflex, antisymm, transitive? I am working on practice problems on the unit about Sets and Relations. The question asks me to give a ...
1
vote
2answers
16 views

Solve for x when x is on both sides of modular equation

This question is purely out of curiosity. My little brother got a question for homework to find a rectangle where the Area = Outline. Both sides must also be integers, obviously. He found the square ...
0
votes
2answers
19 views

Proof involving greatest common divisor [on hold]

Suppose that $\text{gcd}\:(a, y) = 1$ and $\text{gcd}\:(b, y) = d$. How do I show that $\text{gcd}\:(ab, y) = d$?
0
votes
2answers
35 views

How many ways can 40 people be split into 10 quartets?

"A certain music school has 49 students, with 10 each studying violin, viola, cello, and string bass. The director of the school wishes to divide the class into 10 string quartets; the four students ...
1
vote
2answers
14 views

How can I prove that a graph with a required amount of edges per node is invalid?

For the following example I assume that no node may be connected to itself. Nodes: A, B, C, ...
1
vote
2answers
38 views

Suppose that$\ gcd(b, a) = 1$. Prove that $\gcd(b + a, b − a) \leq 2$

Suppose that $\gcd(b, a) = 1$. Prove that $\gcd(b + a, b − a) \leq 2$ I've been given a hint I should use divisor rules, so I have if $d \mid b+a$ and $d \mid b-a$, then $d \mid 2a$ and $d \mid 2b$, ...
0
votes
0answers
23 views

Prime number,Greatest and lowest common divisor

Let D be the number of ways in which B11 the cycle graph with 11 vertices can be coloured with 10 colours and let E be the number of ways B12 , the complete graph with 12 vertices, can be coloured ...
0
votes
1answer
26 views

Euclid algorithm greatest common factor

Let A be the greatest common factor of 9883529 and 759345 Find A using Euclid’s algorithm, and hence find integers x and y so that A = 9883529 x + 759345 y. how do you use Euclid's algorithm ?
0
votes
1answer
30 views

picking 8 cards from a usual deck of 52 playing cards.

choose 8 cards from a usual deck of 52 playing cards.how many ways can this be done (4) All 8 cards that have values between 2 and 8 inclusive. (5) All 8 cards and they all have different values ...
0
votes
1answer
25 views

How many bit strings containing exactly eight 0s and twelve 1s have either all the 0s consecutive, or all the 1s consecutive?

How many bit strings containing exactly eight 0s and twelve 1s have either all the 0s consecutive, or all the 1s consecutive? i try use tree diagram to do it but it doesn't work that well, is there ...
2
votes
1answer
27 views

Combinations from prime number of elements

Let $p$ be a prime and let $k$ be a natural number: Prove that for $k < p$, $\binom{p}{k}$ is divisible by $p$. My proof: The formula for $p$ choose $k$ is: $$\frac{p!}{k!(p-k)!}$$ Since the ...
0
votes
2answers
18 views

Combinatorics identity proof by induction

Prove the formula by induction on n and fixed r: $\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \ldots + \binom{n}{r} = \binom{n+1}{r+1}$ What I tried: Base: we take $n=r$ so $\binom{r}{r} = ...
1
vote
2answers
31 views

Anti-symmetric relation given by a matrix

Relation R is given by a matrix $$\begin{bmatrix} 1& 0& 0& 0\\ 1& 1& 0& 0 \\ 1& 0& 1& 0 \\ 1& 1& 1& 1 \end{bmatrix} $$ Is it anti-symmetric? I'm ...
0
votes
2answers
18 views

Proving Greatest Common Divisors

I have two questions I'm struggling with 1) Suppose that gcd(a, y) = 1 and gcd(b, y) = d. Prove that gcd(a · b, y) = d I have 1 = ua + vy and d = sb + ty, and I use linear combination to get d*1 = ...
1
vote
1answer
15 views

Zero divisors and inverstible elements

I have learned about $X_n = \mathbb{Z} / n\mathbb{Z}$. I understand that a zero divisor is an element $x\neq 0$ in $X_n$ such that $xy = 0$ for some $y\neq 0$. I understand that an element $x$ in ...
0
votes
2answers
23 views

how does $(p\to q)\lor r \lor s$ effect $(p\leftrightarrow q) \lor r \oplus s$

If we know that $\lnot p \lor q \lor r \lor s=\top$, then what is the value of: $(\lnot p \land \lnot q) \lor (p \land q) \lor(r \land \lnot s) \lor (\lnot r \land s)$ I tried doing it with a truth ...
1
vote
3answers
58 views

Finding all the values of n, such that $ \varphi (n) = 12 $ [duplicate]

I have not broken this down very far. I have come to the conclusion that there are infinitely many values for n where there exists 12 coprimes to n. Since there are infinitely many primes, and primes ...
1
vote
1answer
13 views

When to use Binomial or Neg Binomial?

I have a problem that I'm not sure which distribution to use: 12 Toll employees were let go for taking more than 25,000 dollars in tolls. Lets say that one of the people let go on one day collected ...
1
vote
2answers
31 views

Trouble understanding algebra in induction proof

I'm on hour 20 of studying for the discrete math midterm tomorrow, and I've got to be honest I'm a little panicked. In particular I'm having trouble with induction proofs, not because I don't ...
0
votes
2answers
44 views

What does the constant mean in Big O notation?

I have a big issue in understanding the real meaning of Big O notation. Classical definition: $f(x) = O(g(x))$ as $x\rightarrow k$ if there exist $\delta, C > 0$ such that $f(x) \leq Cg(x)$ ...
3
votes
1answer
23 views

Find maximum number of nodes in a regular graph of degree 4 and diameter 2

In $n$ nodes directed graph, every vertex has in-degree and out-degree equal to $4$. If every vertex is reachable from every other vertex directed by a path of length at most $2$. How can we find ...
0
votes
0answers
15 views

Construction proof Chinese remainder theorem?

Use the construction in the proof of the Chinese remainder theorem to find all solutions to the system of congruence's x is equivalent to 2 (mod 3), x is equivalent to (mod 4), and x is equivalent to ...
1
vote
2answers
29 views

For any integer a, if $6|(3−a)$, then $3| (a−2)$.

Prove: For any integer a, if $6|(3−a)$, then $3| (a−2)$. I've been trying to work this problem for a while, but missed a day of class and can't seem to work it out.
1
vote
2answers
38 views

Number of particles at time $t$

A following problem appears in my text book under the section of induction: At time $0$, a particle resides at the point $0$ on the real line. Within $1$ second, it divides into $2$ particles that ...
1
vote
1answer
99 views

Consider strings of length n taken from the restricted alphabet {a, b, c}.

Consider strings of length n taken from the restricted alphabet {a, b, c}. (a) How many such strings are there? (b) How many such strings are there with exactly two as? (c) How many such strings are ...
2
votes
2answers
25 views

Number of Symmetric Relations on a set A

I'm having trouble understanding their explanation. I follow everything up to "The Set $A_2$ contains $(1/2)(n^2 - n)$ subsets..." could someone please help explain this to me? Source: Discrete and ...
1
vote
1answer
44 views

Proving that all numbers between two numbers are composite

I am having trouble with this problem: Assume $p_1, p_2 \ldots p_{n+1}$ be the first $n+1$ primes in order. Prove that every number between $(p_1\cdot p_2 \cdot \ldots \cdot p_{n}) + 1$ (exclusive) ...
2
votes
3answers
47 views

Determining number of solutions to equation (Discrete math)

I was given this homework problem: How many solutions are there to the equation: x1 + x2 + x3 + x4 + x5 + x6 = 29 Where xi, i = 1,2,3,4,5,6, is a nonnegative integer such that xi > 1. I also have ...
1
vote
1answer
28 views

Is this proof correct (Cartesian Products and Subsets)?

I am trying to prove that if $A \times B$ is a subset of $A \times C$ then $B$ is a subset of $C$ given that $A$ is not empty. I've looked at this question on here and I'm aware it's been asked. My ...
-2
votes
1answer
24 views

Is this relation reflexive, symmetric, transitive, anti-symmetric? [on hold]

Determine if $\rho$ is reflexive, symmetric, transitive, anti-symmetric. In each case, if $\rho$ is an equivalence relation, describe the equivalence classes. $$\begin{align}& A = \mathbb Z × ...
-1
votes
1answer
24 views

finding reflexive, symmetric, transitive, anti-symmetric and equivalence classes

For each relation $p$ described below, determine if $p$ is reflexive, symmetric, transitive, anti-symmetric. In each case, if $p$ is an equivalence relation, describe the equivalence classes. a) $A = ...
-1
votes
0answers
17 views

solve discrete math qs [on hold]

determine if ρ is reflexive, symmetric, transitive, anti-symmetric. In each case, if ρ is an equivalence relation, describe the equivalence classes. Two sequences of real numbers (an) and (bn) are ...
1
vote
1answer
34 views

attack on RSA (factoring when knowing e and d)

This is the problem, I have to explain how works the algorithm on the image with modular arithmetic for a discrete math class., I tried to explain it, but I couldn´t. In the class, I have seen this ...
-1
votes
0answers
23 views

discrete math: properties of a relation [on hold]

determine if ρ is reflexive, symmetric, transitive, anti-symmetric. In each case, if ρ is an equivalence relation, describe the equivalence classes. A = P(Z) (the power set of Z). Let X ⊆ Z be a ...