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
80 views

Combinatorial argument for divisibility

Let $A$ be a set of $11$ positive integers such that for all $x \in A$ we have $20 \nmid x$. Prove that there are two integers $a, b \in A$ such that $20|(a+b)$ or $20|(a-b)$. Any ideas, how to ...
2
votes
3answers
187 views

Permutation of integers

Let $n$ be a positive integer and let $(a_1,...,a_n)$ be a permutation of $\{1,2,...,n\}$. Define $$A_k = \{ a_i | a_i < a_k, i >k\} \\ B_k = \{a_i | a_i > a_k, i < k\}$$ for $1 \leq k \...
0
votes
1answer
57 views

Good transition books

I am finishing up a class on discrete mathematics and I am interested in skipping my schools transition courses in order to take a rigorous theory course next semester (topology, analysis, abstract ...
1
vote
2answers
33 views

Multiple modulis, trying to find 1 number

I won't quote here the full question, because it's irrelevant. ${x \in \mathbb{N}}$ ${x \le 250}$ ${x \mod 8 = 1}$ ${x \mod 7 = 2}$ ${x \mod 5 = 3}$ So my idea was to write down ever number that ...
0
votes
3answers
89 views

Showing that a set has equal number of even\odd numbered subsets

Let $M$ be a non-empty set. Show that $M$ has as many subsets with an odd number of elements as subsets with an even number of elements. I already found a solution which said to use the identity $\...
0
votes
3answers
75 views

How many ways can I list the letters?

In how many ways can the letters $a, a, b, b, c, d, e$ be listed such that the letter $c$ and $d$ are not in consecutive positions? My partial solution: So, because we have $7$ letters, we will ...
0
votes
1answer
69 views

Extended rule of sum/product

Prove that both, the sum and the product principle, can be extended to more than two sets, i.e. show that: Given finite sets $A_1, A_2, ..., A_n$ which are pairwise disjoint, then $|\bigcup^{n}_{...
0
votes
1answer
15 views

Probability of dealer having a same-value card as me in Black Jack

In a game of Black Jack, before any additional cards are given out (so everyone has exactly two cards), what are the chances that the dealer has, say, a King, given that one of my cards is a King ? ...
8
votes
5answers
245 views

How to distinguish between combination and permutation questions?

How do you distinguish combination and permutation question? An example of a combination question: Example: How many different committees of 4 students can be chosen from a group of 15? ...
2
votes
2answers
76 views

loop invariant for simple algorithms

The following is an algorithm which finds the maximum value in a list of integers, and I want to prove that it is correct by using a loop invariant. ...
2
votes
2answers
75 views

Number of ways to arrange $a,b,c,d$ such that $a$ is not followed immediately by $b$

Can someone explain this solution? The question is: How many ways are there to arrange the letters $a,b,c,d$ such that $a$ is not followed immediately by $b$? The solution is: $4! − 3! = 18$ I ...
2
votes
2answers
413 views

How many bit strings of length 10 either begin with three 0s or end with two 0s?

The question : How many bit strings of length 10 either begin with three $0$s or end with two $0$'s? My solution : $0$ $0$ $0$ X X X X X $0$ $0$ = $2^5 = 256$ editing** I noticed the word"or" so ...
0
votes
2answers
65 views

There are 12 children .Assuming there are 4 children’s bedrooms show that there are at least 3 children sleeping in at least one of them.

There are 12 children in the family Assuming there are 4 children’s bedrooms in the house, show that there are at least 3 children sleeping in at least one of them. My question is can I use ...
1
vote
1answer
22 views

Permutations of bit-sequence(discrete math)

How many bit-squences with length 8 has 1 as it's first bit and 00 as the two last bits(e.g $1011 1100$) I thought the solution to this problem would be $1 * 2 * 2 * 2 * 2 * 2 * 1 * 1 = 2^5$, but my ...
0
votes
3answers
27 views

Discrete Math: Proof by Induction

I need to prove $3^{4n+2} + 5^{2n+1}$ is divisible by $14$ for $n=0, 1, 2\dots$ I did the base case $n=0$ and everything checked out. Then I assumed $n=k$ and want to prove $k+1$. $3^{4k+6} + 5^{2k+...
0
votes
0answers
45 views

Queens on a 4x4 chessboard.

How many ways are there to place four queens on a 4 by 4 chessboard so that no two queens attack one another? I have tried to look for an algorithm but I didn't find anything specific.Also what would ...
1
vote
0answers
103 views

maximum matching to solve a path-packing problem

G=(V,E) is a directed graph. . A path packing of G is a collection of paths: $\cal{P}=\{ P_1,\dots P_k\}$ such that $V(P_i)\cap V(P_j)=\emptyset$ $\forall i,j$ s.t. $ 1<i<j<k$ where $V(P_i)$...
1
vote
0answers
40 views

Finding a Hamiltonian cycle for $Q_4$

A hyper cube $Q_n$ is a graph that have the length-n binary sequences as its vertices. Two vertices are adjacent if they differ in one entry. I found a Hamilton cycle for $Q_3$ as follows $$000 \to ...
1
vote
3answers
204 views

Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$.

Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$ using the Pigeonhole principle. I am supposed to identify the pigeons and the pigeonholes. ...
1
vote
1answer
29 views

Using Euler's theorem to calculate the number of edges in a graph

I want to use Euler’s theorem for planar graphs to proof that for a tree $T = (V, E)$ that $|V | = |E| + 1$. Now It's very obvious that a tree is a planar graph since it is connected and there is no ...
0
votes
0answers
111 views

Out of $513$ nine-digit numbers, there must be two with matching zero positions

Need help figuring this one out, came up in class and I have no idea how to write a proof for this. Prove: Given a collection of 513 Social Security numbers, there must be two that match zeros.
2
votes
1answer
362 views

The number of pendant vertices in a tree

Let $T$ be a tree with vertices $\{v_1, v_2, . . . , v_n \}$ for $n \geq 2$. Prove that the number of pendant vertices in $T$ is equal to $$\large{2 + \sum_{v_i,deg(v_i) \geq 3}\big( deg(v_i) - 2 \...
0
votes
2answers
21 views

Equivalence relations and classes

Let $S = [10]$ (the set containing the integers 1,...,10). Define an equivalence relation R on S by $xRy$ $iff$ $x^2 \equiv y^2$ (mod 5) is an equivalence relation and determine the equivalence ...
0
votes
4answers
190 views

Proving a set is Uncountable or Countable Using Cantor's Diagonalization Proof Method

I understand the idea that some infinities are "bigger" than other infinities. The example I understand is that all real numbers between 0 and 1 would not be able to "fit" on an infinite list. I have ...
3
votes
4answers
302 views

Proving a summation inequality with induction

The exact question: Prove: $\displaystyle\sum_{k=1}^n \frac{1}{\sqrt{k}}\gt2(\sqrt{n+1}-1)$ I have looked at similar problems but still don't understand how to prove this inequality by induction. ...
0
votes
3answers
43 views

Closed form solution for the recurrence

I am given the following recurrence and need to find a closed form solution for the recurrence. I have no idea on how to get started though and i need some help on leading me to solve this. $A_0=20, ...
0
votes
0answers
9 views

Arbitrary length in the sequence of primes? [duplicate]

Let p1, p2 . . . pn+1 be the first n+1 primes in order. Prove that every number between p1 · p2 · p3 · · · pn + 1 and p1 · p2 · p3 · · · pn + pn+1 − 1 (inclusive) is composite. How does this show that ...
0
votes
2answers
34 views

Prove that a linear integer combination of two values cannot lie in a given range

If I am given two values such as $x = 14$ and $y = 21 $ is there any reliable method to prove that the sum of combinations of these numbers can lie in the range $170-174$? I am assuming it has ...
3
votes
3answers
206 views

Prove by mathematical induction that $a^n$ is an irrational number.

Let $a$ be an irrational number where $a^2$ is a rational number. Prove by mathematical induction or generalized mathematical induction that $a^n$ is an irrational number for all odd integers $n ≥ 1$. ...
0
votes
2answers
60 views

Deduce formula for $\sum_{j=0}^m {m \choose j}(-1)^j j^{m+1}$

I am working on the following problem: For each $m$ we have found the values of $$\sum_{j=0}^m {m \choose j}(-1)^j p(j)$$ for polynomials of degree at most m. Use a combinatorial story to ...
1
vote
0answers
36 views

Can I get some help to make my answer more rigorous for this problem in the book Concrete Mathematics [duplicate]

I'm a freshman in college this semester without any previous experience in rigorous proofs or such, however I am interested in the learning more about mathematics and for that reason I picked up the ...
0
votes
1answer
810 views

Graph, vertex cover problem

Let $G=(V,E)$ be a graph, a set $T \subseteq V$ of nodes it's called vertex cover if every edge $e \in E$ has a vertex in $T$. The MVC Problem: Input: The graph $G=(V,E)$ with $n$ nodes. A number ...
0
votes
0answers
452 views

Directed graph, set of even nodes

Let D=(V,E) be a finite directed graph. We define a set of even nodes in D=(V,E) a not null set $S ⊆ V$ with property $$|v^+ ∩ S| ≡ 0 ( mod 2 ), ∀v ∈ V.$$ $$v^+ = \{w ∈ V |(v, w) ∈ E\}$$ Now, If D=(V,...
0
votes
2answers
32 views

Graph Generated by a Surjective Function

There are 2 non empty sets $A$ and $B$, such that $A \cap B = \emptyset $. And there is a function $f: A \rightarrow B$ which defines the undirected graph $G=(V,E)$ such that $V=A \cup B$ and $E= A \...
0
votes
2answers
68 views

Why is the constant term in any chromatic polynomial is always zero?

The chromatic polynomial $P(G,\lambda)$ is simply the number of different way in which we can colour a graph $G$ with at-most $\lambda$ different colours. Such that every pair of adjacent vertices ...
0
votes
2answers
39 views

For each $x,y∈\mathbb N$, if $x≤y$ and $y≤x$, then $x=y$ [duplicate]

Proof: For each $x,y∈\mathbb{N}$, if $x≤y$ and $y≤x$, then $x=y$ By definition of order, $x≤y$ if and only if $x<y$ or $x=y$ By definition of order, $x<y$ if there exist a $K∈\mathbb{N}$ such ...
0
votes
1answer
50 views

Show that T(n)=4×T(n−1)−T(n−2)

T(n) is the number of spanning trees for a n-ladder. Show that $ T(n)=4×T(n−1)−T(n−2) $ As a proof, I don't really know how to solve this. Any assistance would be appreciated. I tried to first ...
1
vote
0answers
29 views
0
votes
0answers
25 views

max cut estimation in a graph

I understand what a max cut is. But I'm little confused because in this exercise they ask whether the estimation is correct or not. This is one of the examples: For me, there is only one MAXCUT in ...
0
votes
1answer
28 views

definition clarification of some special type of graphs

I was going through some families of graph and got introduced to circulant graphs. Got the following link of circulant graphs, but I am unable to get it. What do they mean by the list. Kindly help me ...
2
votes
1answer
87 views

Looking for a quick “randomish” way to map 1..N to 1..N and back

This is related to a programming problem I have, but posted here because I think I'll get a better answer. I've got database records that have ID's 1,2,3,.... Assume I'll never have more than a ...
0
votes
1answer
41 views

Integrals of sum. FInd upper and lower bounds

Find the upper and lower bound using integrals. $$\sum_{k=1}^n (k^2 - 3k)$$ Please explain I actually want to understand it
-2
votes
2answers
35 views

How could i prove that the sum of a rational and a prime number is always rational?

I know integers are closed under addition, but im not 100% sure on how to prove this? Or is this a false statement as prime numbers are rational aswell? Any help ?
0
votes
1answer
53 views

If A and B are nonzero matrices such that det( A )and det( B )are nonzero, can AB be the zero matrix?

Can someone help me aproch the problem. I know that for this to work a1d1 can not equal b1c1 as well as a2d2 can not equal b2c2. But am utterly stuck on what do next.
1
vote
1answer
146 views

Induction on the number of equations

Let $L$ be a differential operator. $$$$ We suppose that $\phi: \displaystyle{\bigwedge_{j=1}^n L_j x=f_j}$ and we assume that $\phi$ can be written as $Lx=f \land \psi$, where $\psi$ doesn't ...
0
votes
3answers
36 views

To prove $g \circ f=I_U$ and $g$

I need to provde the proofs for the below :- (1) On a set $U$ two functions are defined as $f,g: U \rightarrow U $, Given is that $f \circ g=I_U$ and $g$ is surjective. Prove that $g \circ f=I_U$ (2)...
0
votes
4answers
30 views

Prove an inequality using induction

I have to prove that... $(1 +a)^n \ge 1+an$ for $ a > 0$ and $n \ge 1$ I've started with the following base case: Let $a = 1$ and $n = 1$. Then $(1 +1)^2 \ge 1+(1)(1)→ 4\ge 2$, which is true. ...
0
votes
1answer
31 views

Prove or disprove irrational numbers [duplicate]

If x^(1/3) is an irrational number, then x is also irrational. I tried using contrapositive, but it's not the right way.
0
votes
1answer
56 views

Proof writing involving propositional logic: (p∧ (¬q) ) ↔ ((¬p) ∧ q) ≡ p ↔ q

Prove by using propositional logic: (p∧ (¬q) ) ↔ ((¬p) ∧ q) ≡ p ↔ q Is this possible? I tried solving but i get stuck. LS: = (p∧ (¬q) ) ↔ ((¬p) ∧ q) = ((p∧ (¬q) ) → ((¬p) ∧ q) ) ∧ ( ((¬p) ∧ ...
1
vote
2answers
90 views

For all sets $A$ and $B$, $P(A \times B) = P(A) \times P(B)$

Prove each statement that is true and find a counterexample for each statement that is false. For all sets $A$ and $B$, $P(A × B) = P(A) × P(B)$. For all sets $A$ and $B$, $P(A ∩ B) = P(A) ∩ ...