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

1
vote
1answer
30 views

Theory of definitions

I am reading "Introduction to Logic" by P Suppes at the moment. In the Chapter 8 - Theory of definitions of it, I 've some confusion, actually about the Conditional Definition. The brief explanation ...
0
votes
0answers
7 views

Solving a Recurrence Using Substitution

I am trying to understand an example of solving a recurrence using substitution (or unrolling it) in my book right now, but all of the steps do not seem clear to me. Here is the basic example: ...
0
votes
2answers
25 views

Discrete maths proving a random observation

Suppose you had 6 points. Each point can choose to either visit another point, or choose not to visit another point. However, it can't visit itself. In addition, visiting another point works in both ...
1
vote
2answers
29 views

How to get to $5^3 \geq n^3$ in the proof by contradiction?

This is the same problem asked here. - Next step to take to reach the contradiction? Here is it again. I understand the solution - how you want to get to the fact 100 divides n^2 and then go ...
0
votes
1answer
19 views

how to prove boolean identities

I'm working on 2 boolean proofs (¬p⊕q)=(p⊕¬q=¬(p⊕q) <- I assume its equality law i'm not sure how to do this problem(I verified using truth table but I need to do algebraically) ...
1
vote
0answers
16 views

Find all points on the line 9x-21y=6

For this equation we are suppose to use the Euclidean Algorithm. But I run into a problem For the GCD (9,-21)= i tried 9=(-21)(0)+9 -21=9(3)+6 9=6(1)+3 6=3(2) +0 which gives a gcd of 3 and the ...
0
votes
1answer
17 views

What is the probability that 13 cards drawn from a standard deck has at least one card from each suit?

I am currently trying to figure out why my answer is not correct for that following question. Q: What is the probability that 13 cards drawn from a standard deck has at least one card from each suit? ...
0
votes
1answer
25 views

standard deck and the probability of at least one card,exactly one void and two voids

The question is this: if 13 cards are dealt from a standard deck of 52, what is the probability that these 13 cards include a)at least 1 card from each suit b) exactly 1 void(e.g no clubs)? ...
0
votes
1answer
10 views

How can I add the following 32-bit IEEE floating-point numbers?

How can I add the following two 32-bit IEEE floating-point numbers in binary? FEDCBA98(base 16) + 89ABCDEF(base 16) = a 33-bit binary number. How can this be possible?
0
votes
1answer
13 views

How would you convert the following 32-bit IEEE floating-point to decimal form?

I have got -1.101 1100 1011 1010 1001 1000 * 2^(9) How can I convert this to decimal form?
2
votes
1answer
23 views

Convert the following decimal number into 32-bit IEEE floating-point form.

I am given a negative decimal -1234.875. I understand the normal process of solving a question like this, except I am uncertain about handling the negative. What I do is find the binary form of 1234 ...
-3
votes
0answers
41 views

Let a1,a2,…,an be real numbers satisfying ai ≥ 1 (for i = 1,2,…,n). [on hold]

Let $a_1,a_2,\ldots,a_n$ be real numbers satisfying $a_i\ge 1$ (for $i = 1,2,\ldots,n$). We want to choose as many partial sums of $a_i$’s, i.e., expressions of the form $a_{i_1} +\dots+a_{i_k}$, ...
0
votes
1answer
22 views

How many ways can you choose 4 non empty subsets from q 10 element set

How many ways can you divide the set $A=\{1,2,3,4,5,6,7,8,9,10\}$ into a 4 non empty subsets? Hint: there's a formula states that the number of all the functions from $A \to \{1,2,3,4\}$ that are ...
1
vote
1answer
37 views

How many bit strings oft length k have more than one 1?

The question seems rather simple, but I am not able to get a closed formula. e.g. for k=2 it is 1 (11), for k=3 it is 4 (111,101,110,011) I thought that it maybe could be $\frac{1}{2} \cdot 2^k $ ...
0
votes
0answers
16 views

How to prove the two relations to be equal?

If I have a relation $R$ defined on a set $A$ ,then when we calculate $R^n$ by performing cartesian product of $A^n$ ,then can we predict the value of $s$ and $t$ such that $R ^ s=R ^ t$. As we ...
0
votes
2answers
44 views

Show that there exists no integer $x$ such that $3x$ is congruent to 5 (modulo 6)

So far my approach was to rewrite the congruency to $5-3x=6t$ for some integer $t$. My problem is I get stuck in trying to show how $5-3x$ is never divisible by $6$.
0
votes
1answer
25 views

simple diving question in combinatorics

So the Discrete Math exam is on friday and i am still very confused with which formula should i was in cases that looks very simillar, there are these 4 question : a) Divide 30 students to 6 ...
3
votes
0answers
37 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
40 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
32 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
16 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
70 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
1answer
77 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
21 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$.
2
votes
0answers
22 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 ...
2
votes
0answers
18 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
15 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
16 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
57 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
31 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
74 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
17 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
14 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
36 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 ...
1
vote
0answers
29 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
28 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
17 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
9 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
31 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
27 views

Exclusive or (XOR) proof [duplicate]

The question is to prove: X'⊕ Y = X⊕Y' = (X⊕Y)' State laws used (' meaning negation) Thank You