Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

1
vote
3answers
158 views

Define a relation on the set of all real numbers $x,y \in \mathbb{R} $ as follows:

Define a relation on the set of all real numbers $x,y \in \Bbb{R} $ as follows: $x \sim y$ if and only if $x - y \in \Bbb{Z}$ Prove this is an equivalence relation and find the equivalence class of ...
1
vote
3answers
48 views

Find m and n in the given equation:

Sorry new to this forum and don't know how to format: If $m,n\in\Bbb N$ satisfy $6^{2m+2}\cdot 3^n=4^n\cdot 9^{m+3}$, then $n$ and $m$ must be ... what? This is for my discrete mathematics ...
2
votes
2answers
76 views

Is the following always True?

Let $a, b \in Z$ and $n \in N$ . Is the following necessarily true? If $a^3 ≡b^3$(mod n) then $a ≡ b$ (mod n) How do I do this? For the record, I do not think this is True.
0
votes
1answer
60 views

Ceiling and flooring proof

Prove or disprove : $ \left\lceil \frac { \left\lceil \frac { x }{ 2 } \right\rceil }{ 2 } \right\rceil =\left\lceil \frac { x }{ 4 } \right\rceil \quad for\quad all\quad real\quad numbers\quad x ...
2
votes
1answer
113 views

Discrete math, statements true or false

The universal set defined for the task is $\{2,3,4,5,\dots\}$. I've been tearing my hair out at this one for quite some time. I can make the top one true, as in my head you can always just select ...
1
vote
2answers
93 views

finding function such that $f(2x) = f(x) + 1$

Q1. How to find a function $f(x)$ satisfying the recurrence relation $$f(2x) = f(x) + 1$$ Q2. Also how to prove that the closed form for the recurrence relation $$f(n) = f \left( \left ...
1
vote
3answers
50 views

Why $(a,b)\mid a+b\le3$ is not reflexive and is symmetric?

Why $(a,b)\mid a+b\le3$ is not reflexive and is symmetric? I read because a€ Z so by counter example $(5,5)$, $5+5$ is not less than or equal to $3$ So it's not reflexive But why it's symmetric ? I ...
0
votes
1answer
58 views

What is the number of all possible relations/intersections of n non-empty sets?

The accepted answer given for What is the number of all possible relations/intersections of n sets? also counts cases when one or more sets are empty. For example, for $n=2$ there are $2^{2^n-1}=8$ ...
2
votes
1answer
179 views

Discrete Math Proof By Cases Confusion

I am currently finishing up my Discrete Math course, and I just wanted to clear something up that has confused me for the past few days. My teacher posts answer keys to assigned homework problems ...
1
vote
1answer
220 views

Why the divides relation on the set of positive integers antisymmetric

I'd like to know why the divides relation on the set of positive integers antisymmetric. The book says $a|b$ and $b|a$ then $a=b$. But I think if a|b and b not divides a for example $1|2$ but not ...
2
votes
2answers
72 views

Why $\{(a,b) | a\leq b\}$ is not symmetric?

I want to know why $$\{(a,b) \mid a\leq b\}$$ is not symmetric, when $$\{(a,b) \mid a\leq b\} =\{(a,b)| a<b \text{ or }a=b\}$$ So if a=b that means aRb and bRa so it is symmetric, right ? Thanks ...
0
votes
1answer
38 views

Clarification on a question

I have been reading this problem, Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100. That says, Prove that of any 52 integers, ...
0
votes
0answers
39 views

Why does this proof need another case?

A psuedograph (with at least two vertices) is Eulerian if and only if it is connected and every evertex is even. Proof: (-->) understood so let's move on. (<--) For the converse, suppose that G is ...
-1
votes
2answers
31 views

Set operations question

How can i solve this one ? $Find\quad \bigcap _{ i=1 }^{ \infty }{ A_{ i } } and\quad \bigcap _{ i=1 }^{ \infty }{ A_{ i } } if\quad for\quad every\quad positive\quad integer\quad i,\quad A_{ i ...
0
votes
2answers
31 views

negative binomial distribution problem

Find the probability that you find 2 defective tires before 4 good ones. There is a chance of a tire being defective at a rate of 5%. From my understanding with the negative binomial distribution we ...
0
votes
2answers
304 views

Big theta notation question

can someone please explain to me the big theta notation and big omega and also How i can show that $$ 3x+7\quad \text{is}\quad \Theta (x); $$ I don't really get how growth of functions works.
0
votes
1answer
40 views

Proving true or false based on discrete math

Discrete math practice problems prove whether true or false If $a^2$ divides $b^2$, then $a^3$ divides $b^4$ I think it is false because it is true that if $a^2$ divides $b^2$ then $a$ divides $b$ ...
1
vote
2answers
60 views

Is it possible to draw a graph that has an Euler Cycle but not a Hamilton Path?

Is it possible to draw a graph that has an Euler Cycle but not a Hamilton Path? It seems every Euler cycle I draw has a Hamilton Path.
1
vote
1answer
41 views

Is it possible to draw a graph with a Hamilton Path but not a Euler Cycle?

Is it possible to draw a graph with a Hamilton Path but not a Euler Cycle? It seems that every graph I draw has a Hamilton Path.
0
votes
4answers
75 views

$5$ movies up for $10$ awards, how many ways to distribute

There are $5$ movies up for $10$ awards, how many ways can we distribute these awards? My guess is $\left(\!\!{5\choose 10}\!\!\right)$. Is this correct?
0
votes
5answers
164 views

Prove that if $B-C$ $\subseteq$ $A^c$then $A \cap B \subseteq C$

Let A, B and C three sets. Prove that if $B-C$ $\subseteq$ $A^c$then $A \cap B \subseteq C$ Im trying to prove this with sheer logic and not making use of De Morgans laws etc. Let $y \in ...
1
vote
0answers
415 views

Recurrence relation question

A country uses as currency coins with values of 1 peso, 2pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. a) Find a recurrence relation for ...
0
votes
1answer
66 views

Let A, B, C and D be four sets:

Prove that if $A \cup B$ $\space\subseteq $ $\space C \cup D$, $A \cap B$=$\emptyset$ and $C\subseteq A$, then $B \subseteq D.$ I tried working around with this for a while and reached this ...
1
vote
1answer
34 views

In the following list of equivalence classes, find two classes which are equal

Consider the equivalence relation n $\Bbb R$ - {$0$}: $a$~$b$ if and only if $\dfrac {a}{b} \in \Bbb Q $ In the following list of equivalence classes, find two classes which are equal: [$\sqrt 3$] ...
2
votes
1answer
245 views

Recurrence relations question

A vending machine dispensing books of stamps accepts only one-dollar coins, $1 bills, and $5 bills. a) Find a recurrence relation for the number of ways to deposit $n$ dollars in the vending machine, ...
0
votes
3answers
455 views

Prove if $a \equiv c \pmod n$ and $b \equiv d \pmod n$ then $ab \equiv cd \pmod n$.

Prove if $a \equiv c \pmod n$ and $b \equiv d \pmod n$ then $ab \equiv cd pmod n$. I tried to use $(a-c)(b-d) = ab-ad-cb+cd$, but it seem doesn't work.
2
votes
2answers
40 views

Expansion Coefficient needed

This is probably something very easy, but wth... my mind is totally stuck right now. I need to find the coefficient of $x^{11}$ of the expansion $(x^2 + 2\frac yx)^{10}$ Well I know that the answer ...
0
votes
2answers
55 views

Prove that if p and q are positive distinct primes,then $\log_p(q)$ is irrational.

Prove that if p and q are positive distinct primes,then $\log_p(q)$ is irrational. Attempt: Proof by contradiction: Assume $\log_p(q)$ is rational. Suppose $\log_p(q) = \dfrac{m}{n}$ where $m,n ...
1
vote
6answers
281 views

Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.

Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers. I think I have to use the contrapositive to solve this. So I assume $\neg ...
0
votes
1answer
121 views

Consider such a homogeneous linear recurrence

$a_n$=3$a_{n-1}$+18$a_{n-2}$ with initial conditions $a_0$=1 and $a_1$=9. a). Use the algorithm to find a solution. b). Use induction to show that the solution that you found in a) is correct, be ...
0
votes
2answers
61 views

Kripke $S5$ system on game theory

My question is short, but reaching that point is going to take some time. Sorry about that in advance. Take $\Omega$ as finite and $K:2^{\Omega}\to 2^{\Omega}$ be an operator with following ...
3
votes
1answer
72 views

Sum of $N$ natural numbers is less than $N+2$, then each number is less than $3$.

Prove by contradiction: If the sum of $N$ natural numbers is less than $N + 2$ then each of these numbers is less than $3$. Attempt: I have to assume that the sum of $N$ natural numbers is greater ...
37
votes
6answers
4k views

Of any 52 integers, two can be found whose difference of squares is divisible by 100

Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100. I was thinking about using recurrence, but it seems like pigeonhole may also ...
2
votes
1answer
40 views

Discrete maths; graph theory on undirected graphs

Let G be an undirected graph of 4 vertices and no loops (i.e. arrows to itself). Which of the following statements are guaranteed to be true? 1) G has at least two vertices of the same degree 2) G ...
2
votes
3answers
257 views

Is this relation reflexive, symmetric and transitive?

Define a relation $R$ on the set of functions from $\mathbb{R}$ to $\mathbb{R}$ as follows: $(f, g) \in R $ if and only if $f(x) - g(x) \geq 0$ for all $x \in \mathbb{R}$ Is this relation ...
-3
votes
2answers
35 views

prove rigorously that following is not a binary tree [closed]

A single leaf node is a binary tree. If t1 and t2 are disjoint binary trees, then the result of joining them under a single node is a binary tree. Nothing else is a binary tree. Prove rigorously, ...
0
votes
3answers
96 views

Solve the recurrence $ T_{n + 1} = T_{n} + nT_{n - 1}$

Solve the recurrence $$ T_{n + 1} = T_{n} + nT_{n - 1}\,, \quad\mbox{for}\quad n \geq 1\quad \mbox{with initial conditions}\ T_{0} = T_{1} = 1 $$ by finding the exponential generating function and ...
1
vote
2answers
52 views

binary trees and rules for their creation

I am learning about binary trees. I was given following rules for their creation: A single leaf node is a binary tree. If t1 and t2 are binary trees, then the result of joining them under a single ...
0
votes
1answer
60 views

Ergodicity of this Markov Chain

I was recently involved in a debate with a friend over the following graph, and whether it is ergodic or not. In the following diagram, each edge has a strictly positive probability of being travelled ...
0
votes
1answer
44 views

Algorithm to partition a graph under constraints

What would be an algorithm to partition the vertex set of an undirected graph into 2 vertex disjoint subsets such that each vertex has at most $\left\lfloor\frac{d}{2} \right\rfloor$ no of its ...
2
votes
1answer
84 views

What is a power Delaunay triangulation, and how is it computed?

What is a power Delaunay triangulation? and how would I compute it in n-Dimension?
1
vote
1answer
62 views

What is the proof that $\sum \limits_{v \in V} deg(v) = 2|E|$?

My textbook gives $\sum \limits_{v \in V} deg(v) = 2|E|$ and has the proof If an edge is not a loop it gets counted twice b/c it's incident with 2 different vertices. If an edge is a loop, by ...
1
vote
5answers
98 views

Prove that if $7$ divides $6^n + 1$ then $n$ is odd

Prove that if $7$ divides $6^n + 1$ then $n$ is odd Attempt: We'll prove the contrapositive: $n$ is not odd if $7$ does not divide $6^n + 1$
0
votes
1answer
60 views

What is the minimum number that must share the same birthday (month & day) each year, given that one such birthday is February 29?

If there are 6,392 students at Stack Exchange College. What is the minimum number that must share the same birthday (month & day) each year, given that one such birthday is February 29?
0
votes
2answers
41 views

Can two overlapping disconnected graphs contain a Euler Circuit or Path? Hamilton Circuit or Path?

Can two overlapping disconnected graphs contain a Euler Circuit or Path? Hamilton Circuit or Path?
1
vote
1answer
84 views

Minimum number of rows in a mod 12 multiplication table

Minimum number of rows you would need to write out in a mod 12 multiplication table to guarantee you wrote out an element with an inverse? I would think this would be just one row as 1 is its own ...
1
vote
0answers
15 views

Looking for intuition for picking strategy on how many pages to flip

This question is going to sound more CS'y because that is my background. It also might be a bit vague but that is because I am not sure what the right thought process is in how to formulate it. I ...
1
vote
2answers
36 views

How many marbles must be placed in a square area of $16 in^2$ to ensure that two of the marbles are within $2 \sqrt{2}$ inches of each other?

How many marbles must be placed in a square area of $16 in^2$ to ensure that two of the marbles are within $2 \sqrt{2}$ inches of each other? Wouldn't even know how to begin this question.
3
votes
2answers
60 views

How many integers between $100$ and $500$ are divisibly by both $6$ and $12$, but not by $9$?

The numbers divisible by both $6$ and $12$ and just the numbers divisible by $12$, so: $12 \times 9 = 108$ $12 \times 41 = 492$ $\frac {492-108}{12} = 32 + 1 = 33$ numbers divisible by $12$, and in ...
2
votes
1answer
85 views

Graph isomorphism and existence of nontrivial automorphisms

Consider the following two algorithmic problems - one of determining whether two graphs are isomorphic and the other of determining if a graph has a nontrivial automorphism: (1) Decision problem: ...