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

0
votes
2answers
17 views

Compute the remainder of a division

Could you help me about this easy problem. I have to compute the remainder of the division of $9^{123456789} $ by 17 Thanks!
1
vote
1answer
17 views

Discrete Math Proof Method

Give a direct proof of the fact that $a^2-5a+6$ is even for any integer $a$. Suppose $a$ and $b$ are integers and $a^2-5b$ is even. Prove that $b^2-5a$ is even.
0
votes
0answers
9 views

Given number of vertices of a graph G, how do we calculate the number of connected graphs

I have this exercise question in Schaum's Discrete Maths 3rd Ed chapt8: 8.40. Find the number of connected graphs with four vertices....Draw them. I do not pretty understand this question. My basic ...
1
vote
2answers
31 views

Prove: $A \cap(B\cup C^*)=(A\cap B)\cup C^*$

How do you prove this mathematically, when $C^*$ is the complement of C? I know from drawing a Venn diagram that this equation should hold. $A \cap(B\cup C^*)=(A\cap B)\cup C^*$ Thanks!
1
vote
2answers
25 views

How to prove this $\theta$ notation

How do you prove that the folowing function is equal to $\theta(n^2)$? $$f(n)=\frac{n^3+n+1}{2n+\ln(n)}.$$ Then $f(n)=\theta(n^2)$. Thanks!
0
votes
1answer
14 views

Assume that A is a subset of some underlying universal set U.

Prove the domination laws in Table 1 by showing that a) A ∪ U = U. here is the answer but i have no idea how to come up with this answer and where does T come from?:O A ∪ U = {x | x ∈ A ∨ x ∈ ...
0
votes
1answer
23 views

How to tell if the following function is one to one

Let f:A→B where A = X∪Y with X∩Y=∅. If f|x and f|y are one-to-one, does it follow that f is one-to-one? I am unsure how to figure this out. I have gathered from the info provided that X and Y are ...
0
votes
0answers
15 views

$O(n\log^2(n))$ algorithm for finding closest pair of points between two sets.

For example, say that we are given a set of points where each point is labeled White or Black. How can we compute the pair of ...
0
votes
1answer
24 views

Proving property of congruence - help needed

Let $c,d,m,k ∈ \mathbb{Z}$ such that $m ≥ 2$ and $k$ is not zero. Let $f = \gcd(k,m)$. If $c \equiv d \pmod m $ and $k$ divides both $c$ and $d$, then $$ \frac{c}{k} \equiv \frac{d}{k} ...
0
votes
1answer
17 views

List the members of these sets.

List the members of these sets. a) {x | x is a real number such that x2 = 1} What does this symbol mean | ? the answer is (-1,1) but how do you find the answer? Thanks
0
votes
0answers
30 views

Taylor Series Expansion for Function of Two Variables (with Countable Discontinuities)

Given a real-valued function of two real variables, under certain conditions of smoothness in a closed ball about some point, we can obtain a Taylor series for the function about that point. I want ...
0
votes
1answer
16 views

Generalize discrete Lyapunov equation for n-th order linear dynamics system

My specific application is analysis of dynamic textures using linear dynamics systems of the form $$ I(t) = Cz(t) + w(t) \\ z(t + 1) = Az(t) + Bv(t), $$ where $I(t)$ is the original signal, $z(t)$ ...
1
vote
2answers
27 views

Dividing students into teams-combinatorics

In how many ways can $n$ number of students be divided into two teams such that each team has at least one student. This is what I did: Let $x_1$ be the number of students in the one team and $x_2$ ...
0
votes
0answers
17 views

Determine maximal, minimal, least and greatest elements.

R = {(0,0),(1,0),(2,0),(2,2),(3,0),(3,1),(3,2),(3,3)}. Is it 0 / \ ...
0
votes
0answers
19 views

Can you use chinese remainder theorum to convert hex to dec in your head?

At one time I was able to convert hex to decimal in my head, using a trick I learned in college. I have not used it in years, and forgot how. Does anyone remember how to use the Chinese remainder ...
1
vote
2answers
46 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
17 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
30 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
1answer
19 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
2answers
30 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
33 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
59 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
47 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
22 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
57 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
25 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
21 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
33 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
35 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
79 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
90 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
17 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$?
1
vote
2answers
45 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
24 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
28 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
31 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
19 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} = ...
2
votes
2answers
36 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
19 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 = ...
2
votes
1answer
16 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
62 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
32 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 ...