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
1answer
73 views

Identities involving the floor function

Are either of these statements false? if so what is the counter example? $⌊x − 2⌋ = ⌊x⌋ − 2$ or for any odd integer n, $⌊(n^2/4) + 1⌋ = (n^2+3)/4$ also I'm struggling to make a proof of either if ...
0
votes
1answer
33 views

Proof for divisibility?

Prove either by contradiction or contraposition (using Fundamental Theorem of Arithmetic in either case) that: $$ ∀k ∈ \mathbb{Z}, [3|(k-2) → 3 |(k^2 - 1)] $$ Any help would be great! Thanks!
1
vote
5answers
82 views

Using Direct Proof. $1+2+3+\ldots+n = \frac{n(n + 1)}{2}$ [duplicate]

I need help proving this statement. Any help would be great!
1
vote
2answers
91 views

Finding a formula for $1+\sum_{j=1}^n(j!)\cdot j$ using induction

I need help with finding the formula and proving it by induction. Am stuck, but the professor says we should know this by now.
3
votes
1answer
345 views

Simplify a boolean algebra expression: xy + xz' + x'yz

I need to simplify xy + xz' + x'yz into xz' + yz. I know that these expressions are equal in truth value, but I'm not sure how ...
0
votes
1answer
48 views

Hanoi Algorithm With Different Nodes

http://en.wikipedia.org/wiki/Tower_of_Hanoi I need help developing a Hanoi algorithm which follows the same rules as the standard game, however the nodes that are transversed is different. In this ...
0
votes
2answers
67 views

Simplifying modulus expressions and an unknown expression? discrete math

I have a few questions below that I need help with a) I don't really understand what that symbol means and how to solve it b) How do u simplify this without a calculator c) I got 2^-r = 0, iss this ...
1
vote
3answers
65 views

Prove that $\forall k\in\mathbb{Z}$, $3|k-2$ implies $3|k^2-1$

I'm looking to answer this question Prove $\forall k\in\mathbb{Z}$, $3|k-2$ implies $3|k^2-1$. I'm not sure what to do. I'm trying to study but now I am getting stuck on these questions that don't ...
0
votes
1answer
24 views

∀a,b,c∈ Z, if a|b and a|c then a^2|(5b^2 + 7c^3)

My question is Prove the statement. ∀a,b,c∈ Z, if a|b and a|c then a^2|(5b^2 + 7c^3) I'm really stuck and have no idea where to start. any help would be great!
1
vote
0answers
10 views

Minimal vertex cover in bipartite graph question

How one can check for every vertex of bipartite graph whether it(vertex) belongs to every minimal vertex cover?
1
vote
1answer
76 views

Prove $1! + 2! + . . . + n! < (n + 1)!$ using mathematical induction [duplicate]

$1! + 2! + . . . + n! < (n + 1)!$ This question has left me stumped for quite some time. I am not sure how to approach it. (I am really bad at induction).
1
vote
3answers
66 views

Explanation for the number of partitions of $\{1,\dots,n\}$ into $k$ parts

A partition of the set $\{1, 2, . . . , n\}$ into $k$ parts is a way of writing the set as a disjoint union of $k$ subsets. For example $\{1, 2, 3, 4, 5\} = \{1, 4\} \cup\{2, 3\} \cup \{5\}$ is a ...
3
votes
3answers
109 views

How to find the sum of sequence $ 1+4+4^2+\cdots+4^{X+Y} $?

I see the following sequence and it's: $$h=1+4+4^2+\cdots+4^{X+Y}=\frac{4^{X+Y+1}-1}{4-1}$$ how we get this sequence? I know this is a primary question but I confused :)
3
votes
3answers
103 views

Domain and Function Relationship

This is a very basic question I guess, if I have something like f:A->B, should all the elements in set A be used for f to be a function?
0
votes
0answers
55 views

Every DPDA has an equivalent DPDA that always reads the entire input string

I am trying to understand the proof from Michael Sipser's Introduction to the Theory of Computation, page 132. I don't understand why if $q \in F′$ then $\delta(q,a,\$)$ is set to ...
-1
votes
2answers
120 views

Minimum cut in a graph does not change when the weight of all edges is increased by one

Suppose we have a Graph $G$ in which weight of all edges is $> 1$ (positive). If we increase weight of all edges by one, why does the minimum cut $(S, T)$ of $G$ into two graphs remain the same? ...
3
votes
4answers
65 views

Show $P\left(A-B\right)=P\left(A\right)-P\left(A \cap B \right)$

I'm trying to show that, given two events $A,B \in \Omega$ ($\Omega$ is a sample space): $$P\left(A-B\right)=P\left(A\right)-P\left(A \cap B \right)$$ I know $A-B = A \cap B^C$, but I don't know how ...
2
votes
0answers
62 views

Number of nonnegative solutions of linear diophantine inequality

Given inequality $Ax + By \le C$, where $A, B, C$ are integers, $A$ and $B$ are coprime and $C < AB$. I need to find number of non-negative integer solutions of it. Is there exists algorithm which ...
4
votes
0answers
89 views

An interesting math problem I created for an old-school RPG game.

The point of this is to try to have the best stats as possible at the beginning of the game and stay at level 1 before doing any quests. Starting group at creation menu: ...
2
votes
2answers
83 views

Solution of an equation involving even integers

If $x$ is any positive even integer $> 1$. I compute: $$ c = x + x! $$ Now assume instead $c$ (even integer) is given, and I want to get back the value $x$. Is it possible to find a simple ...
0
votes
1answer
87 views

Induction Problem Number of Tiles on Floor

I took a discrete math course about a year ago, and I recently decided to crack open my book again as a refresher on induction proofs and problems. I ran across this problem, which I didn't remember ...
6
votes
2answers
1k views

A number is a perfect square if and only if it has odd number of positive divisors

I believe I have the solution to this problem but post it anyway to get feedback and alternate solutions/angles for it. For all $n \in \mathrm {Z_+}$ prove $n$ is a perfect square if and only if $n$ ...
0
votes
0answers
53 views

Block design: derived designs

I am now study some theorems of block design. I have a question about the derived designs. Let $B$ be the oringinal design $t-(v,k, \lambda)$. Suppose we omit one of the points, say $P$, then we have ...
1
vote
1answer
21 views

How many boolean functions $F(x, y, z)$

Question:How many boolean functions $F(x, y, z)$ are there so that $F(\bar{x}, y, z) = F(x, \bar{y}, z) = F(x, y, \bar{z})$ for all values of the Boolean variables $x, y,$ and $z$? I'm at loss on ...
3
votes
2answers
55 views

A sum of difference of floors

I have the sum ( $M$ is any integer $> 1$ ): $$ \sum_{h = 1}^{M}\left(\,\left\lfloor\, 2M + 1 \over h\,\right\rfloor -\left\lfloor\, 2M \over h\,\right\rfloor\,\right) $$ and looking for a way to ...
1
vote
1answer
71 views

prime division problem

$a,b,c \in$ {0,1,2,...,9} with at least one of $a,b,c$ nonzero. Prove that the six-digit integer $abcabc$ is divisible by at least 3 distinct primes. My thinking is not to use induction as there is ...
1
vote
1answer
89 views

Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.
0
votes
0answers
18 views

Histogram Separation Energy Equation

I am working in level set method, specially Lankton method paper. I try to implement Histogram Separation (HS) Energy problem (Part III.C). It based on Bhattacharyya to control the evolution of ...
0
votes
1answer
72 views

Prove that $f: \Bbb R \setminus \{2 \} \to \Bbb R \setminus \{3 \}$ is bijective

I wanna know how can I have a formal proof for this one $$f: \Bbb R \setminus \{2 \} \to \Bbb R \setminus \{3 \}.$$ I understand that for functions like this $f(x)=2x+1$. I can know if its is ...
3
votes
0answers
46 views

A probability of a monochromatic cycle on a randomly colored lattice graph.

Let $G$ be an undirected $6 \times 6$ lattice graph. The $36$ vertices of $G$ are each randomly colored with one of $5$ colors with equal probability. Such a coloring is called "successful" if and ...
0
votes
0answers
17 views

discrete-time vs. continuous-time energy

Could any one please explain why the energy of a continuous pulse shape is larger than its discrete-time samples by a factor of bit period $T$? Thank you, Elnaz
0
votes
1answer
22 views

How many ways between 2000 and 5000 can be written from the digits 2,3,4,5,7 if: a. no digit is repeated b. digits must be repeated?

How many ways between 2000 and 5000 can be written from the digits 2,3,4,5,7if: a. no digit is repeated b. digits must be repeated?
1
vote
3answers
85 views

Finding the sum of $3+4\cdot 3+4^2\cdot 3+\dots +4^{\log n-1} \cdot 3$

I see this: $$A=3+4\cdot 3+4^2\cdot 3+\dots +4^{\log n-1} \cdot 3=3\cdot ([4^{\log n}-1]/3)=n^2-1$$ The base of logarithm is $2$, and $n$ is $2,4,8,\dots$ Anyone could describe me how this sum was ...
1
vote
3answers
96 views

Number of images from $\mathbb{N}$ to {0, 1}.

Are the number of images from $\mathbb{N}$ to {0, 1} countably infinite or uncountably infinite? I was thinking of counting in base 2 to make a bijection between $\mathbb{N}$ and {0, 1}. So, a ...
1
vote
0answers
40 views

Least power of $x$ so that $y$ divides $x$

How do I find the least $z$ to satisfy, $$y \mid x^z$$ I have tried keep dividing $y$ with the GCD($x$,$y$) until $y \mid x$ and adding $z$ by $1$ (starting from $1$), but turns out it's too slow.
0
votes
0answers
25 views

Prove identity involving alternating groups

Prove the following identity: where $I_{A_n}(x_1,...,x_n)$ is a cyclic index the natural action of the alternating group $A_n$ on the set ${1,...,N}$ (assuming that $I_{A_0} = 1$).
0
votes
2answers
39 views

Prove that $G$ is Hamiltonian.

Let $G=(V,E)$ be a connected graph which is not a tree. Prove that if for every cycle $C$ of the graph G and for any $v \in V(G)- V(C)$ there are more than $\frac{|C|}{2}$ edges from $v$ to $V(C)$ ...
1
vote
0answers
133 views

Is this function $f^n_b : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}^n$ a surjection?

In this text the fractional part of a real $x$ shall be denoted $\{x\}$, such that $x = \lfloor x \rfloor + \{x\}$. Let the set of functions $f^n_b : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}^n$ be ...
1
vote
1answer
37 views

Discretization of an integral

Given $f: [a,b] \to R $ and $K: [a,b]$ x $[a,b]$ $\to R$, we want to find a solution $\varphi:[a,b] \to R $ to the Fredholm integral equation: $$\varphi(x) = f(x)+\int _{ a }^{ b }{ K( x,t)\varphi ...
0
votes
0answers
20 views

Represent this differential equation as a set of n+1 equations w n+1 unknowns

Given the following differential equation: $$s''w'' + 2s'w''' + sw'''' = q$$ We use these approximations: $$w''''(x_i) \approx \frac { { w }_{ i+2 }-4{ w }_{ i+1 }+6{ w }_{ i }-4{ w }_{ i-1 }+{ w ...
1
vote
1answer
51 views

Divisibility problem ($p \leq \sqrt{n}$)

If $n \geq 2$ and $n$ is composite, then there exists a prime $p$ such that that $p \mid n$ and $p \leq \sqrt{n}$ As $n$ is composite, it follows that $n = ab$ for some $a, b \in \Bbb N$, where ...
0
votes
2answers
64 views

What does let $F$ denote the set of all functions from $\{1, 2, 3\}$ to $\{1, 2, 3\}$ mean?

Let $F$ denote the set of all functions from $\{1, 2, 3\}$ to $\{1, 2, 3\}$. I'm supposed to prove that this statement is true or false, $$∀f ∈ F, \;∃g ∈ F\tag i$$ so that $g(f(1)) = 2$ But I'm not ...
-1
votes
1answer
127 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
2
votes
1answer
34 views

Is this relation symmetric

$R = \{(X, Y) \in \mathscr{P}(A)^2| X \subset Y \text{ and }X \neq Y \}$ I know that $(X,Y) \in R$ holds true since $X \subset Y$. However I'm unsure if $(Y,X) \in R$ since if $Y \subset X$ then ...
1
vote
1answer
138 views

Is the subset relation on the powerset of a set, with qualification, reflexive?

I was wondering if the subset relation is reflexive? $R = \{(X, Y ) \in P(A)^2\mid X\subseteq Y \text{ and } X \neq Y \}$ I assumed they it was reflexive since for all $X \in P(A), X \subseteq X$ is ...
0
votes
2answers
60 views

fundamental theorem of arithmetic problem

Change machine contains n quarters, 2n nickels, 4n dimes, n positive integer. Find all values of n so that these coins total k dollars, k positive integer. My thinking is to reduce coins to prime ...
5
votes
4answers
208 views

How many ways can 5 dice produce a total of 20?

How many ways can $5$ dice produce a total of $20$? I set up the equation $x_1+x_2+x_3+x_4+x_5 = 20$. The total possible number of combinations is $\binom{19}4$. From there I subtracted the ...
0
votes
1answer
45 views

Translating to English: $\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$

$$\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$$ I'm trying to intuitively understand this idea by thinking about it in terms of English. The second half is easy. Where P ...
0
votes
0answers
41 views

Properties of $R$, $R^n$, $R$*

I was talking to a friend who mentioned that eventually, $R^n$ and $R$* are equivalent. This confuses me because I don't see how it's necessarily the case. But it does seem to hold, for instance: ...
2
votes
2answers
95 views

ZFC and apples described using only fundamental axioms (complete expanded reasoning)

Let's assume that I'm adding two numbers representing my count of objects I perceive (lets say a green and a blue apple that are consider to be of the same class) and I see them as a set of two apples ...