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

3
votes
1answer
14 views

Find All Solutions to System of Congruence

$$ \begin{cases} x\equiv 2 \pmod{3}\\ x\equiv 1 \pmod{4}\\ x\equiv 3 \pmod{5} \end{cases} $$ $ n_1=3\\ n_2=4\\ n_3=5\\ N=n_1 * n_2 * n_3 =60\\ m_1 = 60/3 = 20\\ m_2 = 60/4 = 15\\ m_3 = 60/5 = 12\\ ...
4
votes
2answers
32 views

Simultaneusly solving $2x \equiv 11 \pmod{15}$ and $3x \equiv 6 \pmod 8$

Find the smallest positive integer $x$ that solves the following simultaneously. Note: I haven't been taught the Chinese Remainder Theorem, and have had trouble trying to apply it. $$ \begin{cases} ...
0
votes
0answers
25 views

calculating the average of updating memory on Interview questions? [on hold]

We ran into a problem that mentioned in an Interview. How can help us with any idea or hint? n persons randomly enter to a room . we want to find i'th tallest ...
2
votes
2answers
61 views

Complicated factorial expression simplification

I have $$\binom{n}{k}\binom{n-k}{j}\binom{n-k-j}{i}$$ I have it now simplified to $$\frac{n!}{i!j!k!(n-k-j-i)!}$$ I was under the impression that the multinomial number was ...
0
votes
1answer
22 views

Solving number divisibility problem using cardinal number of sets!

How many natural numbers $n<10^6$ are divisible by $7$ but not with $10,12$ and $25$? Theorem: Let $n,k\in \mathbb{N}$ and $k\leq n$, then in the set $\{1,2,...,n\}$ we have exactly $\left \lfloor ...
1
vote
0answers
18 views

Recurence with multiple variables and functions

Is there an easy way to solve a recurrence given with two variables and three different functions? Actually I'm looking for the solution of: $$A(n,k)=A(n-2,k-1)+A(n-3,k-1)+R(n-2,k-1)+L(n-2,k-1) $$ ...
0
votes
0answers
20 views

Let P(n) denote some predicate. Suppose we prove the following premises:

Discrete math Let P(n) denote some predicate. Suppose we prove the following premises: P(0) P(1) P(n)-->P(n + 2) for n>=0. For what values of n can we conclude P(n) is true? I found this under ...
-5
votes
0answers
28 views

Discrete math prove by element method [on hold]

For all subsets $A$, $B$ and $C$. If $$A \cap B = B \cap C = A \cap C = \varnothing$$ then $$A \cap B \cap C = \varnothing$$
0
votes
3answers
28 views

Let $a, b, c, d$ be integers s.t $a|bc$ and $d=gcd(a,b)$. Prove $a|cd$.

From the assumption I was able to gather the following: $bc= ak_1$. Let $p=gcd(a,b)$ thus $p=dk_2$. Well since $p|a$ and $p|b$ I have the following, $a= pr_1$ and $b=pr_2$. I have been trying to ...
2
votes
2answers
72 views

Can I cancel out factorials in proofs?

I encountered the following question in a discrete math course: Prove that $ \binom{2n}{k-1} < \binom{2n}{k} $ for $k = 1, 2, \ldots , n$. Hint: This should be a very cleanly written ...
0
votes
2answers
14 views

Discrete Mathematics- Counting Bit Strings

So I'm a little bit stuck on how to continue about this problem. "How many bit strings of length eight do not contain six consecutive 0s?" So what I did first is I found the total amount of bit ...
2
votes
0answers
27 views

Maximum number of points you can put on grid $ n\times m$ with no equidistant?

Assume we have a grid of $n\times m$ points. and the distance between two rows or two columns is 1 ( unit ). I have a couple of questions related to this grid:- What is the list of possible length ...
1
vote
0answers
23 views

Chinese remainder - Error in my solution

I have the following congruence system: $x \equiv 1 \mod 5 \\ x \equiv 2 \mod 7 \\ x \equiv 0 \mod 8 \\ x \equiv 3 \mod 11$ I used the Chinese Remainder Theorem to get a solution, but it only ...
-2
votes
2answers
78 views

What's the formula for this series of 1, 2, 1, 2, 1, 2? [on hold]

$u_{k} = u_{k−2} \cdot u_{k−1}$, for all integers $k \geq 2$, $u_{0} = u_{1} = 2$. What's the formula for this series of 1, 2, 1, 2, 1, 2?
0
votes
0answers
20 views

Modifying Kruskal's algorithm for Maximum Spanning Tree

So in our class, we did a proof on Kruskal's algorithm for finding Minimum Spanning Tree. Now, based on that, I have to modify it to find me a Maximum Spanning Tree. I know the idea, taking ...
2
votes
1answer
30 views

How many subgraphs does a $4$-cycle have?

Question: How many subgraphs does a $4$-cycle have? I am trying to discover how many subgraphs a $4$-cycle has. I know that there will be $2^4=16$ subgraphs with no edges, but I am not sure how to ...
2
votes
2answers
32 views

How much knowledge of math do I need before taking bachelor of software engineering ?

I asked this question before, but now I knew who to form it correctly after doing some research for months. It always puzzles me what someone need to know before enrolling in bachelor of software ...
1
vote
2answers
26 views

Proof related to maximum degree of node in a graph

So I'm given this problem - Prove that in every graph with 25 vertices, in which holds that in every 3-subset of vertices, at least two of them are connected, there exists a node of degree at least ...
0
votes
1answer
66 views

Markov Chains Question

Markov chains are widely used in modeling several natural and social processes. Consider the following three-state Markov chain modeling the daily weather in Boston. Each day can be sunny, partly ...
1
vote
1answer
42 views

Tree-related problem, counting leafs

I am studying Graph Theory right now, and I have solved tons of problems so far. However, I got a tree-related problem, where it asks me to prove that a tree, in which maximum node degree is 6, the ...
1
vote
1answer
31 views

covering number and compactness

The following picture is what I extracted from the end of page 7 in http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf My confusion is on the blue part: in 1-dimensional ...
-2
votes
2answers
66 views

What is the algorithm to add 2 binary with boolean operations? [on hold]

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be ...
0
votes
3answers
28 views

Decrypt the following message that was encrypted using: Caesar’s cipher: WHVWWRGDB

Decrypt the following message that was encrypted using: (a) Caesar’s cipher: WHVWWRGDB I'm told to decrypt the message using Ceasar's cipher but they don't tell me the key shift so how in the world ...
0
votes
1answer
22 views

Changing the subject of a formula involving the floor.

I'm trying to prove if $3\left\lfloor \frac{x+1}{2}\right\rfloor$ is onto. But I cannot seem to be able to change the subject of my formula to $x$ from $y=3\left\lfloor \frac{x+1}{2}\right\rfloor$. I ...
-5
votes
1answer
37 views

what is the smallest possible value for N? Discrete-mathematic. [on hold]

There are N students in a class. Their exam scores ranged between 27 and 94. All possible scores were achieved by at least on student except for the scores 29, 38, and 55 (none of the students got ...
1
vote
3answers
35 views

Total number of functions $f\colon S\to S$ where $S=\{1,2,3,4\}$

I missed a lecture on this topic and I'm having a hard time figuring out how this discrete function works. I'm given $S=\{1,2,3,4\}$ and $F =$ all functions from $S$ to $S$. What does this mean? I ...
1
vote
3answers
51 views

Modular Arithmetic with large exponents!

Decide whether each of the following is true or false without using a calculator: The problem is: $$11^{99}\equiv 1\pmod{5}$$ Now I know I can break the $11$ into $(10+1)^{99}$ and maybe rewrite it ...
1
vote
3answers
40 views

For $f: A \to B$ with $S, T \subset A $, show that $f(S \cap T) \subset f(S) \cap f(T) $.

Let $f:A\mapsto B$ be given and let $S\subseteq A$ and $T\subseteq A$. Show that, $$f(S\cap T)\subseteq f(S)\cap f(T)$$
1
vote
1answer
15 views

Problem with nonhomogeneous recurrence relations

I studying Discrete maths during this semester and I need your help. I have been trying to solve one non-homogeneous recurrence relation and read many-many guides how to do this, but I haven't found ...
1
vote
2answers
31 views

If a, b, q, r $\in Z$ s.t $a= bq + r$. Prove $gcd(a,b) = gcd(b, r).$

Here's what I have so far, I let $d_1$ divide $a$ and $b$ so I could write $a$ and $b$ as $a= d_1k$ and $b=d_1j$. After manipulation, I was able to achieve that $d_1|r$ after substituting values for ...
0
votes
1answer
42 views

connectivity relation to find the transitive closure

Hello I am having difficulties with this question: Use connectivity relation to find the transitive closure of relation $R = \{(a, e),(b, a),(b, d),(c, d),(d, a),(d, c),(e, a),(e, b),(e, c),(e, e)\}$ ...
1
vote
1answer
37 views

Find the worst case time complexity of the selection sort algorithm

So, i haven't seen a question like this before, and my answer is one i got from a bunch of different sources online. Could someone verify that it is correct and explain how to answer similar ...
1
vote
1answer
46 views

discrete math-Complexity of algorithms

The best and worst case time complexity of an algorithm we are using is O(n \log_2 n) For an input of size n = 1000$ the algorithm ran in 25 seconds. Approximately how long should the algorithm run ...
6
votes
1answer
44 views

On an $h \times h$ square lattice, count all the paths from $(0,a)$ to $(h-1,b)$, $a,b \in [0,h-1]$, with diagonal moves allowed

Consider an $h \times h$ upright square lattice, where a point is defined by $(x,y)$, $x,y \in [0,h-1]$. A valid path starts from the left boundary, $(0,a)$, $ a \in [0,h-1]$ and ends to the right ...
0
votes
1answer
33 views

Quotient and Remainder of Numbers

May I ask what is the logic behind the quotient and remainder for numbers in such situation. ...
-1
votes
0answers
42 views

Generating function for $a_0=0,$ $a_n=\frac{1 \times 5 \times … \times (4n-3) }{1 \times 2 \times … \times n}$

What is the generating function for the sequence $\{a_n\}_{n \geq 0}$, defined by $a_0=0$ and $a_n=\frac{1 \times 5 \times ... \times (4n-3)}{1 \times 2 \times ... \times n}$ for $n \geq 1$. ...
0
votes
1answer
32 views

Algorithm to generate a biased random bit

You find a fair coin in your pocket: This coin comes up heads (H) with probability 1/2 and tails (T) with probability 1/2. Show that this coin can be used to generate a biased random bit.Consider the ...
0
votes
0answers
8 views

Transforming continuous domain optimal problem to the one with discrete domain

I am now in the field of some algorithms which can be used to solve the problem with discrete domain. However, I want to apply these algorithms into the problem with continuous domain. I wonder which ...
-1
votes
0answers
11 views

The Tree-Doubling Algorithm [on hold]

The Tree-Doubling Algorithm, starting the Euler tour and the Hamilton cycle at the vertex a and resolving any ties alphabetically.Show all relevant steps of the procedure. Can anyone help with this. ...
-1
votes
1answer
20 views

Discrete MATH - RELATIONS- Show that R is an Equivalence [on hold]

This is a Homework problem I completely don't understand. Help would be appreciated. THANKS :) LET R be a relation on Z defined as ∀a,b ∈ Z :aRb ⇔ 2a+3b ≡ 0 (mod 5) Show that R is an Equivalence.
0
votes
1answer
29 views

Performing one digit operation to compute the result.

Suppose we have $a_i, b_i, c_i \in \{0, 1, \dots , 9\}$ and $A=a_2a_1a_0, B=b_2b_1b_0, C=c_1c_0$. We want to perform the following operations with the restriction that only one digit operation is ...
0
votes
3answers
41 views

How do i evaluate a nested summation with fraction?

i have to evaluate this expression, but im not sure how to begin. $$\sum^{4}_{i=1}\sum^{5-i}_{j=2} \frac{(j+1)^2}{(2i-1)}$$
3
votes
1answer
20 views

Constructing a recursive definition.

I know a recursive definition is a function or procedure that is defined in terms of itself, for instance $f(n) = f(n - 1) + n$ or $f(n + 1) = f(n) + n + 1$. This makes sense to me in terms of ...
2
votes
1answer
55 views

Principle of mathematical induction

In his book “Introduction to Mathematical Philosophy” Bertrand Russell seems to reach the conclusion that mathematical induction is a definition and not a principle. In essence he states that ...
1
vote
3answers
23 views

How many different equivalence relations S on A are there for with R ⊆ S?

Suppose R is an equivalence relation on a set A, with four equivalence classes. How many different equivalence relations S on A are there for with R ⊆ S? I'm not too sure how to approach this ...
0
votes
2answers
35 views

Prove that relationship is symmetric and transitive

Prove that $xRy$ iff $4|(x+3y)$ is symmetric and transitive? The relation is defined on $\mathbb{Z}$. Symmetry Need to prove $4|(y+3x)$ \begin{align*} x + 3y & = 4k\\ y + 3x & = 4k - 2y + ...
-4
votes
1answer
29 views

Use induction to prove a couple of questions [on hold]

(a) Let f(x) = e^(-1/x^2), x > 0. Use mathematical induction to prove that, for every n ≥ 1, the n’th derivative f^(n)(x) is of the form Pn(1/x)· e^(-1/x^2) for some polynomial Pn (depending on n) b) ...
1
vote
1answer
37 views

Solving Log equation using master theorem

I`m studying Master Theorem, and I got stuck in the case 3. The example is : T(n) = 3T(n/4) + nlogn. I have no idea how my teacher got the final value, c = 3/4, based on the equation below : 3*[n/4 ...
2
votes
1answer
20 views

Find the five different equivalence relations on the set {a,b,c}

What is the best way and easiest way to approach this problem? My first relation is going to be defined as such R = {(a,a), (b,b), (c,c)} which is reflexive, symmetric, and vacuously transitive. My ...
2
votes
4answers
77 views

proving that for every integer $x$, if $x$ is odd, then $x + 1$ is even (induction)

So I have to write a proof that "for every integer $x$, if $x$ is odd, then $x + 1$ is even". I understand what I have to do but I always get stuck at the last step which is prove that it's true for ...