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

Am I doing the Cartesian product of sets correctly?

Question in the image and how I attempt to solve it. Did I do it correctly? And is that the right answer?
-3
votes
0answers
35 views

Proving that $x’y’ + yz’ + x’z’ = yz’ + x’y’$ using the laws of Boolean algebra. [on hold]

I'm trying to prove the following identity using the laws of Boolean algebra. $$x’y’ + yz’ + x’z’ = yz’ + x’y’$$ Here's what I've tried: [insert attempt here]
0
votes
0answers
18 views

Clique cycles structure

I am currently going through the paper "Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles" by Peter Allen (http://www.ime.usp.br/~allen/twocycle.pdf) and I have some ...
0
votes
1answer
14 views

The drawer has M different colored socks. What is the least amount of socks I that I need to draw to guarntee N pairs

So in my discrete math class, we all know that if the drawer has 2 different colored socks, you need to pull out 3 socks to ensure a pair. However, I am puzzled after there are more different ...
1
vote
1answer
41 views

What does it mean for a function to be $\Omega(1)$?

I am having a lot of trouble understanding this. Could someone put this in a context I might understand?
1
vote
3answers
36 views

Arranging a word

This is the question : In how many ways you can arrange the word AAABBCDEFG so that the first letter is A or E ? I'm not sure if im doing this right. My plan is to take all the arrangments and ...
0
votes
1answer
22 views

Diving students into teams

So this is the question : Count the number of ways in which you can divide a group of 33 sudents into 3 soccer teams (each team has 11 studends, them have no names). I know that i shouldn't use the ...
0
votes
0answers
2 views

Multinomial Coefficients proof?

prove that if n and m are positive integers, then ∑ (n )*(−1)^(k2+k4+...+k2l) (k1,...,km) k1+...+km is equal to 0 if m =2l, and is equal to 1 if m = 2l + 1. Please ...
1
vote
1answer
45 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
13 views

Proving 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
32 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
50 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
22 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
18 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
23 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
29 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
20 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
14 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
25 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
42 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
23 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
44 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
17 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
46 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 ...
4
votes
0answers
40 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
42 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
35 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
17 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
82 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
89 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
22 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
20 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
17 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
18 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
61 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
39 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
10 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
30 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
37 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 ...