# Tagged Questions

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.

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 ...
187 views

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 ...
69 views

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 ...
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)$...
40 views

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 ...
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 ...
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. ...
43 views

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 ...
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 ...
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 ...
29 views

...
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 ...
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 ...
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 ...
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
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 ?
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.
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 ...
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)...
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. ...
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.
### 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) ∩ ...