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
2answers
24 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
28 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
18 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
15 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
16 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
24 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
9 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
12 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
35 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
15 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
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.