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
0answers
30 views

Placing $4n$ non-attaking queens of in a $4n \times 4n$ chessboard.

Is it possible to place $4n$ non-attaking queens of in a $4n \times 4n$ chessboard?? I have found that it can be done for $4 \times 4$ chess board and trying to extend it to $8 \times 8$ chessboard ...
1
vote
2answers
38 views

Prove that $f$ is NOT surjective

Let $f: Z \times Z \to Z \times Z$ defined like this: $f(x,y) = (x+y, x-y)$ Prove that $f$ is injective, and not surjective. For injectivity I did that: Let $(a,b) \in Z\times Z$ and $(c,d) \in ...
0
votes
2answers
29 views

If $|B\times A| = 15$ ,evaluate: $|A\cap B|$

If $|B\times A| = 15$ and $|A\times B \backslash B \times B| = 12$. Evaluate: $|A\cap B|$ I tried for myself and got to the conclusion that $|A\times B \cap B \times B| = 3 $ I couldn't get by ...
0
votes
1answer
13 views

For the following number, state the base represented as t?

$1011 \textrm{(base }t) = 4931 \textrm{(base 10)}$ I have to find $t$, which is the base of 1011. I do the following: $4931 \textrm{(base 10)} = 4 \times 10^3 + 9 \times 10^2 + 3 \times 10^1 + 1 ...
1
vote
1answer
29 views

let s be a set with N elements and A1,…,A101 be 101 (possibly not disjoint) subsets of S

So the question I'm having problem with is the following: let s be a set with N elements and A1,...,A101 be 101 (possibly not disjoint) subsets of S with the following 5 properties: each elements ...
0
votes
0answers
10 views

how do you calculate lattice path with inclusion exclusion principle involved?

So this is lattice path question with inclusion exclusion hypothesis. # of paths from (0,0) to (10,10) which do not pass through any of the points (2,4), (5,3), (7,8)? so I assume I should use this ...
0
votes
1answer
21 views

How many lattice paths with step S and W are there that begin at (0,0), end at (-12,-12)

How many lattice paths with step $S$ and $W$ are there that begin at $(0,0)$, end at $(-12,-12)$ and do not go through any of the points $(-1,-4), \space (-5,-3), \space (-9,-11)$? I'm unsure of how ...
0
votes
1answer
19 views

Need help understanding onto function

Let function $g$ from $V = \{1,2,3,4\}$ into V be defined by: $g(n)=3$. I'm having trouble understanding why $g$ is not onto. I understand why it is not one-to-one but, since all the $y$ in $Y$, are ...
-1
votes
0answers
18 views

Min. color $N$ if every $4$ vertex subgraph has a $3$ degree vertex [duplicate]

If a graph has $N$ vertices and every $4$ vertex subgraph has a $3$ degree vertex then prove there is a vertex with degree $N-1$.
1
vote
0answers
17 views

Check if graphs are Eulerian

I've been checking whether these graphs are Eulerian; I've come to conclusion that all of them are Eulerian, because they're all connected and all the vertices are of even degree. However, when I ...
1
vote
0answers
17 views

How to combine possible permutations of two sets to find number of combined permutations

I hope the title accurately describes the question. I have a question that asks: There are 7 male swimmers and 5 female swimmers. If there is a gold, silver, and bronze medalist male swimmer, and a ...
1
vote
1answer
14 views

Determine whether each pair is $f(n) = O(g(n), f(n) = \Omega(g(n)), or f(n) = \Theta(g(n)).$

For the pair of functions, find whether it's $f(n) = O(g(n), f(n) = \Omega(g(n)), or f(n) = \Theta(g(n)):$ $a) f(n) = 12^n , g(n) = 7^n$ $b) f(n) = log_9(n^4), g(n) = log_9(n^5)$ I understand that: ...
0
votes
0answers
13 views

Practicing mathematical proofs in preparation for another course and could use some help [on hold]

I'm starting a course on Algorithms and the professor wants to test our induction and proof knowledge. Problem is, our prerequisite courses never focused on such material. I'm hoping someone could ...
1
vote
4answers
52 views

Show that if $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$.

Show that if $m$ and $n$ are integers such that $m^2 + n^2 $ is divisible by $4$, then $mn$ is also divisible by $4$. I am not sure where to begin.
0
votes
2answers
28 views

prove that 2 does not go into $n^2 – 2$ without a remainder for odd $n$.

Prove that $2$ does not go into $n^2 – 2$ without a remainder for odd $n$. How do I approach this?
0
votes
0answers
9 views

Pinning 2015 polygons on a grid

Given 2 square grids with areas of 2015 units sq, each. Each of the grids is divided into 2015 polygons with an area of 1 unit sq. The grids are not necessarily identical in their division. We ...
0
votes
3answers
72 views

Cannot follow proof that $n! \leq en(n/e)^n$

prove that $n! \leq en(n/e)^n$ skip proof for base (n=1)... Assume it holds for $n-1$, verify for $n$. We have $n! = n* (n-1)! \leq n * e(n-1)(\frac{n-1}{e})^{n-1} $ by inductive assumption. we ...
0
votes
1answer
16 views

Network/graph theory -acyclic problem [on hold]

Consider an acyclic directed network of n vertices, labeled $i=1...n$, and suppose that the labels are assigned such that all edges run from vertices with higher labels to vertices with lower. Show ...
2
votes
1answer
30 views

Remove minimal number of elements

Given the numbers $ 1,2,..,2n + 1 $ , $ n > 0$ , remove as few numbers as possible so that among the remaining numbers no number is equal to the sum of two other numbers. After removal of first ...
1
vote
0answers
6 views

prove Orthogonal Latin Squares

Suppose that $n$ is an odd positive integer with $n \geq 3$. Let $A$ be the $n \times n$ Latin square whose rows and columns are indexed by the elements of $\mathbb Z_n = \{0, 1, 2, \ldots, n ...
2
votes
1answer
27 views

Solving diophantine equation $6x+9y=1050$ where $x,y \in\mathbb{N}$

I have to solve this Diophantine equation: $6x+9y=1050$, where $x,y \in\mathbb{N}$. I am not sure as to how to solve this for only the whole numbers, but I think I'm doing it right. I used the ...
0
votes
1answer
29 views

Sum of divisor powers?

A given number is divisible by 2, 3, and 5, and has altogether 2013 divisors. The smallest such number is $2^N \cdot 3^M \cdot 5^p$ where $N + M + P=$? I would $N + M + P = 2012$ because by a ...
0
votes
0answers
13 views

Stick breaking point (discretized ODE)

I cannot find nontrivial solutions to the following problem. Let $x\in[0,1]$ and $y(x)$ be the deflection of the stick. Then this is described by the diff.eq.: $$\alpha^{-1} P y(x)+y(x)''=0 $$ where ...
-1
votes
1answer
23 views

Prove if the following statement is true or false: *If x is a real number with $x>0$, then $x^2>4$. Suppose $x\leq 2$. Then $x^2 \leq 4$*

Here I have another question related to rules of inference. It says: using the rules these rules of inference prove if the following statement is true or false: If x is a real number with ...
-2
votes
1answer
35 views

Functions : Injective, surjective or bijection? [on hold]

I have been asked a question in one of my test. Question : Consider the relation R is a subset of X * Y where X = [a, b] and Y = [c, d] defined by R = {(x,y): x^2 + y^2 = 1}. For each of the ...
1
vote
1answer
12 views

Proof via strong induction of a string output

I'm still new to the whole proof thing (first class of discrete mathematics and analysis right now). I could do general induction problems, but the fact that 'n' is the output here along with the ...
0
votes
0answers
27 views

Strict total ordering

I'm not able to understand how the below relation is example of "strict total order". Consider a set $X = 2^Y$ where $Y = \{1,2,3,4,5,6,7,8,9\}$. The expected order of $X$ is for all $x, y$ ...
0
votes
1answer
27 views

Prove: if the complementary graph is connected, then graph isn't necessarily unconnected.

I have such a question. There is a theorem related to graphs that says, that if a graph is disconnected then it's complementary graph is connected. But how can I prove that the inverse is not true, ...
0
votes
0answers
15 views

How many cases can draw diagonals that Applicable 2 above condition?

Imagine A $n$_regular polygon that vertex is named by $1$ to $n$. We know can draw $\frac{(n)(n+3)}{2}$ diagonals in $n$_regular polygon and also know if we want draw Maximum diagonals are not ...
0
votes
0answers
8 views

Scaling for Matlab fft operation?

I have a $N$ complex signal samples (QPSK) and I am creating an OFDM signal. When I am doing a IFFT operation in matlab, I use following command: $$Y=(dft/sqrt(N))*ifft(X),$$ where $X$ is the input ...
0
votes
2answers
19 views

discrete math use an element argument

Q)Let U be a universe.Use an element arguement to prove the following statement. For all sets A,B and B in P(U),(C-A) u (B-A)⊆ ( B U C) -A. Def : Z ⊆ W ={(z,w):x∈ X and y ∈ Y}. Proof: W=(C-A) U ...
2
votes
1answer
43 views

Upper limit for Big O notation isn't established?

We say that a function $f(x)=O(g(x))$ if $\exists x_0\in \mathbb{R}_+$ and $\exists C\in \mathbb{R}_+$ such that $\forall x\geq x_0$, $|f(x)|\leq C g(x)$. So with this definition, the function ...
1
vote
1answer
30 views

Easiest way of finding a root of permutation?

I've been searching extensively for the simplest way of finding a root of a permutation, but I can't understand half of the things that I've found. Let's say we have 2 permutations: $\alpha^2 = ...
-3
votes
1answer
25 views

Exclusive or (XOR) proof [duplicate]

The question is to prove: X'⊕ Y = X⊕Y' = (X⊕Y)' State laws used (' meaning negation) Thank You
3
votes
2answers
28 views

Difference between “necessary” and “necessary but not sufficient”?

This is from Discrete Mathematics and Its Applications: Let $p, q,$ and $r$ be the propositions: $\quad p:$ Grizzly bears have been seen in the area. $\quad q:$ Hiking is safe on the ...
0
votes
1answer
17 views

Is these Trees isomorphic or not?

Is these Trees isomorphic or not? They have same structure but they have different code. Because one of them is minimum code. Thank you for your answers in advance.
0
votes
1answer
23 views

Expressing the converse, contra-positive, and inverse of conditional statements

This problem is from Discrete Mathematics and its Applications Here is my book's definition on converse, contrapositive, and inverse And the common ways to express an implication For this ...
0
votes
1answer
51 views

Generating function $D(x) = (1 + x)(1+x^2)(1+x^3)\cdots$ [on hold]

Let $$D(x) = (1 + x)(1+x^2)(1+x^3)\cdots $$ 1) What is the inverse function of $D(x)$? 2) What sequence is generated by $D(x) $ Please don't vote down, the subject is complicated for me. Sorry ...
0
votes
1answer
25 views

Draw a 2-3 tree, insert and delete a key

Assume that at the nodes of a 2-3 tree, the following keys are saved (in an increasing order): $3,6,9,12,15,18,21,24, 27, 30, 33, 36$. It is also given that the root is a 2-node that contains the ...
1
vote
1answer
43 views

Discrete math - Prove that a tree with n nodes must have exactly n - 1 edges? [duplicate]

I'm new in discrete math. Can someone prove simply that a tree with $n$ nodes must have exactly $n - 1$ edges. I have researched the solution but I haven't founded yet. I know of course, a tree with n ...
0
votes
1answer
40 views

prove by mathematical induction

I've been trying to solve this but I'm having trouble in simplifying it, in order to match the right hand side. Could you solve this? $$\sum_{i=1}^{n+1} i\cdot 2^i = n\cdot 2^{n+2} +2 ,$$ for all ...
1
vote
4answers
69 views

Solve $3x \equiv 17 \pmod{2014}$

Solve $$3x \equiv 17 \pmod{2014}$$ So first I suppose $3^{-1} \pmod{2014}$ $2014 = 671(3) + 1 \implies 1 = 2014 - 671(3)$ But this gives $3^{-1} = 1 \pmod{2014}$ which is incorrect?
0
votes
2answers
37 views

Show that $R=\lbrace (a,b): 5\mid(a^2-b^2) \rbrace$ is an equivalence relation

How can I show that this is an equivalence relation ? $$R=\lbrace (a,b): 5\mid(a^2-b^2) \rbrace$$
0
votes
1answer
12 views

how many reflexive relations but not equivalence, are in a set with 4 elements?

I know that for reflexive relations on a set with n elements the formula is: $2^{(n^2-n)}$ So for a set with $4$ elements: $2^{(4^2-4)}$ = $2^{12}$ But I don't know how to find the relations that ...
0
votes
1answer
21 views

Which are the equivalence classes for the following relation?

Here I have such an exercises related to equivalence relations. Given R defined on $Z \times Z$, $$(a,b)R(c,d)$$ and $$a+d=b+c$$ Let set $A$ be: $$A=\lbrace{0,1,2} \rbrace$$ Which are the ...
0
votes
2answers
55 views

Can someone verify my assertion from this english sentence? [duplicate]

This is from Discrete Mathematics and its Applications This is the book means when mentions a list of common ways to express conditional statements After going through the list, I immediately ...
0
votes
1answer
34 views

how to prove $pr_i(\alpha \setminus \beta) \supseteq pr_i\alpha \setminus pr_i\beta$

For those who are not familiar with the syntax $pr_i \alpha = \{ pr_i(a,b) / a \alpha b \} \text{ for }\alpha \subseteq A \times B$ which is same as $\begin{cases} (x= pr_1 \alpha) \Leftrightarrow ...
0
votes
1answer
26 views

Need to prove that a conditional statement is a tautology

The conditional statement is $[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r)$ Here are the steps I took in an attempt to prove the above statement a tautology, but I ...
2
votes
4answers
58 views

Clarifying on how if p,q is logically equivalent to p only if q [duplicate]

Here is what my book says about the different ways implications are worded I am struggling with how "if p, then q" is logically equivalent to "p only if q" The example I came up with With "if ...
0
votes
1answer
28 views

How to tell the difference between interval and coordinate notation from context?

I am working on a practice problem with sets. (the answer key) At first I was confused by the notation Ai = (0,i), i is a natural number. I looked up the use of paranthesis and saw that they could ...