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

learn more… | top users | synonyms

1
vote
2answers
55 views

$\lfloor \sqrt{\lceil x \rceil} \rfloor = \lfloor \sqrt{x} \rfloor, \forall x \in \mathbb{R}$

Question: $\lfloor \sqrt{\lceil x \rceil} \rfloor = \lfloor \sqrt{x} \rfloor, \forall x \in \mathbb{R}$ My Attempt: Let $a = \lfloor \sqrt{\lceil x \rceil} \rfloor$ $$a \leq \sqrt{\lceil x \rceil} ...
1
vote
1answer
96 views

How can I divide 30 people into 6 different groups of 5 people in 6 ways so that no two groups share two people?

I have a group of 30 people that I need to divide into 6 groups of 5 people in 6 different ways, however I do not want the same people to be together twice. I already have 5 ways written down, but I ...
0
votes
2answers
40 views

Graph Theory, with algorithms like kruskal and something more

The new government of the archipelago of Sealand has decided to join six islands by bridges to connect them directly. The cost of building a bridge depends on the distance between the islands. This ...
1
vote
2answers
24 views

Discrete math and recursion problem.

I was recently reading up examples on recursion and how it relates to induction and there's this question I am not sure about. Q: Let $$b_1=3$$ $$b_n=n(n+2)$$ From that question I wanted to do the ...
0
votes
1answer
35 views

Maximum value of function involving factorials

Define $$g_{(k,j)} = \frac{a^{n-k}b^k(k+n)!x^{k+n-j}}{k!(n-k)!(k+n-j)!}$$, where $n,k,j \in \Bbb{N}$ are fixed such that $(0 \leq x \leq a/b ),(b<a),(0 \leq k \leq n ),(2 \leq j \leq 2n),(0 \leq ...
-1
votes
2answers
302 views

What is the efficient way to calculate number of divisors of N that are divisible by 2?. [closed]

For example if a number is given let say 8 then its factors are 1,2,4,8 hence total numbers of divisors which are divisible by 2 are (2,4,8) that is 3.
0
votes
1answer
24 views

Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance
1
vote
1answer
52 views

Stable Marriage - set of preferences such that every arrangement is stable?

This is a homework problem from the MIT OCW math for CS class, assignment 4, problem 5. Prove or disprove the following claim: for some n ≥ 3 (n boys and n girls, for a total of 2n people), there ...
6
votes
1answer
47 views

Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs?

Following on from this question: Q: Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs? or equivalently Q: Does there exist a $15 \times 15$ matrix ...
3
votes
2answers
50 views

Use a proof by cases to show that $\lfloor n/2 \rfloor$ * $\lceil n/2 \rceil$ = $\lfloor \frac{n^2}{4} \rfloor$ for all integers $n$.

Question Use a proof by cases to show that $\lfloor n/2 \rfloor$ * $\lceil n/2 \rceil$ = $\lfloor \frac{n^2}{4} \rfloor$ for all integers $n$. My Attempt: I can only think of two cases, $n/2 \in ...
1
vote
1answer
36 views

Mapping a range of real numbers to a range of integer numbers.

I have a set of real numbers within the range [-1.0, 1.0], and I want to map them to set of integers in [-2, 2]. What is the simplest mathematical formula to achieve this?
0
votes
2answers
46 views

Discrete math equation: True or False

Hello I am having an issue with this problem. it goes like this: There exists an n for all m such that m*n = n. I am confused on how to approach this problem. ...
0
votes
0answers
31 views

Reversible smoothing of a two dimensional function (or an image)

Smoothing of an image, or a two dimensional function is quite easy, there are many methods to achieve it, using average of near elements. But how to make it reversible? Maybe DCT (discrete cosine ...
1
vote
1answer
52 views

Film Festival, with intersections graphs

I encourage you to read this problem. I have a doubt, have films 1 and 2 the same type? I read the problem and I think that films {1,3,5}, {2,4,6}, {3,4} and {5,6} are grouped, but not is the case ...
1
vote
1answer
25 views

Draw a graphic only passing one time

I would like to know when I can draw a graph, without lifting the pencil and passing once for each edge? What theory is behind that? Thanks for your time
0
votes
0answers
18 views

What is correlation kernel and compare with gaussian kernel

I read a paper that said about correlation kernel that defined: $$W(x-y)=(α/1+d(|y − x|))$$ where $α =  (\int(1+d(y − x)dy)^{-1}$, $(d(|y − x|))$ is spatial Euclidean distance from the central ...
0
votes
1answer
45 views

Making a Graph having edges

V is the set of those two-letter words built over {w, x, y, z} whose first letter is y or z. The graph G = (V, A) is defined so that two words of V determine an edge of A if they differ in exactly one ...
2
votes
1answer
111 views

About $\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}$ . . .

Suppose $$\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}.$$ Which of the following is true? Explain your answer. For any $n$, $$\Sigma\cup\{p_n, \neg p_{n+1}\}$$ is complete and ...
2
votes
2answers
52 views

Binary relation, reflexive, symmetric and transitive

I have a question regarding an image. I'm currently studying binary relations and the following image confused me: What got me confused is that the page from which I got the link ...
-1
votes
1answer
60 views

Quick Truth Table in Logic Problem

Suppose We Have: How can quickly detect how many "1" are in the truth table of above formula? (without drawing Truth Table). i think by using some inference. any idea? we know there are 11 "1"s ...
5
votes
2answers
92 views

Does $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs?

Q: Does the complete bipartite graph $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs, where $I$ is a $1$-factor (i.e., a perfect matching)? The obvious necessary conditions work: $K_{12,12}$ ...
-1
votes
1answer
47 views

prenex equivalence problem

Suppose: $$\forall x\exists y \phi(x,y) \to \neg \exists x\psi(x) $$ which of the following formula are prenex normal equivalence with the above formula? i didn't any idea to explain it. it's a ...
1
vote
3answers
43 views

Functions for boolean operators, that return 1 or 0

Are there any purely mathematical expressions that are equivalent to boolean operators and return $1$ or $0$? For example: $a > b$ Is there any $f(a, b)$ for which if $a>b$, $f(a,b)=1$ and if ...
2
votes
1answer
31 views

The number of distinct multiples of composites greater than $n$ that can be factored into two naturals less than or equal to $n$

Given a list of composites between $n$ and $\lfloor \frac{n^2}{2} \rfloor$: What would be the most efficient way to count, for each composite, the number of its distinct multiples that can be ...
0
votes
1answer
47 views

Fibonacci Induction Proof

$\displaystyle F_{k-1} F_{k+1} - F_k^2 = (-1)^k$ I have done the base step for $k=1$ and it works. I realize we need to prove for $k+1$, so: $$F_k F_{k+2} - F_{k+1}^2 = (-1)^{k+1}$$ Could ...
0
votes
1answer
54 views

Sumatory formula

Anybody knows the formula for this, because I don't know how to write it from the basic formula of $$\frac{n(n+1)}{2}$$: $$\sum _{i=1}^{n}{ \sum _{j=1}^{ n}{ \sum _{ k=1 }^{ n }{ \sum _{ h=1 }^{ n ...
1
vote
3answers
87 views

Combination Problem Understanding

How many ways can a Doctor go to the Hospital on $5$ days of January (which has $31$ days) such that no two visits are on consecutive days? I think the solution is: $\displaystyle\binom{27}{5}$ But ...
0
votes
0answers
30 views

How to calculate the number of combinations of getting a pair in a deck of 52 cards?

I am confused over calculating the number of ways in which I can select a pair out of a deck of 52 cards, this is how I go about solving the problem, following the definition of a pair in card games, ...
4
votes
1answer
44 views

All $k$-regular subgraphs of $K_{n,n}$ have a perfect matching: a proof without Hall's Marriage Theorem?

There are several ways of describing this result: Theorem: For $k \in \{1,2,\ldots,n\}$, any $k$-regular subgraph of $K_{n,n}$ has a perfect matching (also known as a $1$-factor). I tend to ...
1
vote
1answer
44 views

Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
0
votes
1answer
99 views

Big Mathematics Challenge on Set and Summation? [closed]

please be aware that this is not homework. it's past PHD entrance Exam on 2011. Suppose: $$B=\{(A_1,A_2,A_3) \mid \forall i; 1\le i \le 3; A_i \subseteq \{1,\ldots,20\}\}$$ if we have: ...
0
votes
1answer
18 views

Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
1
vote
1answer
44 views

Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
1
vote
3answers
33 views

Problematic Permutation Problem

i see a problem without any definition. would you please help me? i want to calculate the number of permutations of 1,2,...,1392 that 696 numbers be in the natural positions (from all numbers, 696 ...
0
votes
2answers
43 views

How do I know if a function has x roots on x-axis?

I am currently studying Newton Raphson Method. Now I am kind of having a question that how I know if the function ever has a x-root or roots on x-axis? Please let me hear your advice. I am sorry if I ...
4
votes
1answer
40 views

Derive a procedure to select one of the 2 options with equal probability when we are not using a fair coin.

Derive a procedure to select one of the 2 options with equal probability when we are not using a fair coin. $P(\text{H}) = p$. $P(\text{T}) = 1 - p = q$. I came up with the following two-roll ...
0
votes
3answers
27 views

Equivalence Relation with multiples

How can I prove the equivalence of this relation, and how can I calculate the equivalence class of (4,8)? On the set the relation R is definded by (a,b)R(c,d) ⇔ ad=bc. Find out if this is an ...
4
votes
1answer
40 views

Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
0
votes
2answers
25 views

Reliability Probability problem

What is the Probability that at least one close path is formed from A to B where each switch has a Probability of close = p and each switch acts independent of the other Proposed Solution Let ...
0
votes
3answers
94 views

Proving that $aRb \iff a^2-b^2=a-b$ is an equivalence relation

Could you help me with that, I don't know how to prove if the relation is an equivalence and the class of 5? On the set of integers, the relationship is defined by $aRb \iff a^2-b^2=a-b$. Find out ...
0
votes
0answers
21 views

How to find a certain uppper bound (see details)?

What would be the most efficient way to find this upper bound? Given natural number n and a natural number d < n, find the ...
0
votes
2answers
53 views

Sets and Relations in Math

I have not knowledge about relations, could you help me to solve this excercise step by step, to use in futures excercices? Thanks for your time. Given the set $A = \{1, 2, 3, 4\}$ and $B = \{1, 3, ...
0
votes
0answers
25 views

Use the Chinese Remainder Theorem to show that an integer $a$, with $0 \leq a < m = m_1*m_2* \dots *m_n$, …

Question: Use the Chinese Remainder Theorem to show that an integer $a$, with $0 \leq a < m = m_1*m_2* \dots *m_n$, where the integers $m_1, m_2, \dots, m_n$ are pairwise relatively prime integers ...
1
vote
3answers
73 views

Counting valid tickets

I think my question is very easy but I need to understand. The problem is, I have a ticket with 2 numbers from 1 to 10. The first number cannot be greather than the second number. How many valid ...
1
vote
0answers
20 views

How do I prove this equality involving ceilings and max?

For all $T \in \mathbb{N}$ the following holds, with $k \in \mathbb{Z}$ and $m, n \in \mathbb{N}$: $$\left \lceil \frac{k \cdot m}{n} \right \rceil + T - 1 = \max_{0 \leq i < T} \left \{ i + T ...
0
votes
0answers
28 views

Mathematical Modeling for the Mapping Relationship

I have encountered a problem in my research and have no idea how to model the problem. To simplify the description, I tell a game with the same rule instead of the original problem. Consider two set ...
1
vote
1answer
27 views

Alternatives to absolute error?

Let me explain my scenario in which I need to calculate absolute error. Lets say the X is the actual value. And X' is the value of X with some error 'e'. So X' = X + e'. Lets say i = 1 to 10000. I ...
1
vote
0answers
26 views

Either or in compound statement

I think this might be a silly question, but I'm confused. Please help me to understand it. Statement is: Randy studies German on either Tuesday or Friday. How should I write this as compound ...
0
votes
2answers
51 views

Constructing a formule

Could you help me with that? \begin{align} 1 &= 1 \\ 1 - 4 &= -(1 + 2) \\ 1 - 4 + 9 &= (1 + 2 + 3) \\ 1 - 4 + ...
3
votes
5answers
591 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...