Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-mathematics]

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.

0
votes
0answers
14 views

Number of eulerian paths in an undirected connected graph between two given vertices?

Given a undirected connected graph G(V, E). Provide an optimal algorithm, which finds the number of eulerian paths between vertex 1 and vertex |V|. I was thinking about matrix multiplication, but I ...
0
votes
1answer
20 views

Cardinal number of a set comprised of the multiplication of 2 other sets.

I have the following question in my assignment: Find the cardinal number of the following set: $\{a \cdot b \mid a \in \{1, 2, 3\}, b \in \{1, 2, 3\} \}$ I am wondering if this is asking for the ...
0
votes
1answer
39 views

Pigeonhole Principle: Showing that there are at least two holes with the distance between their centres less than $10\sqrt{2}~\text{cm}$

I'm having trouble regarding the application of the Pigeonhole Principle. I understand $f:A \to B$ but I don't know how to apply it in questions that require it. Example: Ten bullets are all shot on ...
0
votes
0answers
21 views

Polynomials in the Pancake problem

I noticed something interesting in this table. The columns can be expressed by polynomials of order k. I can't check if it is still a polynom for $k=7$. $$k=0: 1$$ $$k=1: n-1$$ $$k=2: n^2-3n+2$$ $$k=3:...
1
vote
6answers
85 views

Show that $2 - \sqrt{2}$ is irrational

I suppose $2 - \sqrt{2} $ is rational. so $$2- \sqrt{2} = {a/b} $$ where a,b are integers and gcd(a,b) = 1. $$\text{Step 1. } 2 = (a/b)^2 \text{ //squared both sides }$$ $$\text{Step 2. } 2b^2 = a^2 \...
0
votes
2answers
20 views

Uniform discrete distribution - time to draw

I have a question about the basic definition of discrete normal distribution. Let's assume I have a machine that draws a number ranging from 1 to 3 from a uniform discrete distribution (the ...
0
votes
0answers
30 views

Prove that every planar graph is the union of at most $5$ acyclic graphs.

Prove that every planar graph is the union of at most $5$ acyclic graphs. Reminder: As union of two graphs $G_1(V_1, E_1)$ and $G_2(V_2, E_2)$ we consider the graph $G(V_1\cup V_2,E_1\cup E_2)$ ...
-3
votes
1answer
25 views

Help! How to solve the problem [on hold]

Have no clue how to solve this
0
votes
1answer
26 views

Counting combinations for specified requirement

i want to know the regular way to count something like this assuming i have 2 of Xs and 2 of Ys. I want to know the total number of combination for these input. For this example it should be xxyy ...
1
vote
2answers
30 views

$ S = \{(x,y) \in B \times B | (\exists a,b \in A)[f(a)=x, f(b)=y, (a,b) \in R ] \} $ with R transitive, is S transitive?

Be the funtion $ f: A \to B $ and $ R \subseteq A \times A $ a transitive relation. Be the relation $ S \subseteq B \times B $ defined as: $ S = \{ (x,y) \in B \times B | (\exists a,b \in A)[f(a)=x, ...
0
votes
0answers
27 views

Cartesian product of R2 x R2 [on hold]

I need to work with a relation on $\mathbb{R}^2$ defined by $(x_1,y_1)R(x_2,y_2)$ with some condition. So far I've only done relations and Cartesian Products with single-dimension data (e.g., a ...
0
votes
0answers
26 views

Collection of subsets with more than $n\choose n/2$ elements must have set contained in another

I have a set $A$ of size $n$. I have a collection of subsets of $A$ that contains $k>{n\choose n/2} $ elements. I want to prove that there are two sets $B, C$ in this collection such that $B\subset ...
0
votes
3answers
21 views

Countability of set of binary strings of finite length

So I was thinking about the countability of the set of binary strings of finite length. I approached using two ways. The worst thing is I am getting different answers in both approaches. Here is the ...
0
votes
1answer
29 views

Show that the second player can always achieve a draw in the defined game

currently at it working on my discrete mathematics assignment, where I now have one assignment, that I just can't crack. I feel like I am very close, but miss something critical to it. So, I have the ...
0
votes
0answers
37 views

How do we solve this disassembled rainbow bagel puzzle? [on hold]

https://www.janestreet.com/puzzles/disassembled-rainbow-bagel/ I have been trying to solve this vehemently but to no avail.
0
votes
1answer
34 views

We have a sequencing problem

We have a competition with $9$ different teams (team $1$ to team $9$). They are competing in a round robin contest using $2$ different (venues $A$ and $B$). So every team will play the others once. ...
0
votes
0answers
13 views

Discretizing a function with 0 indexing

I have already asked this question and got it answered : Discretizing a mathematical equation. Now i want to adjust the indexes, i.e originally it was asked for natural numbers correspondence i.e $\{x,...
1
vote
0answers
22 views

What units is my mean squared error if I center and scale my training data?

I have a KNN model that I used to predict the close price on houses. ...
0
votes
1answer
22 views

Show that if A is a Subset of B, then A is dominated by B

Definition of A is dominated by B: There is an injective function from a to B. Remark: For finite sets A,B A is dominated by b is equivalent to the cardinality of A is less than or equal to B Proof: ...
7
votes
1answer
54 views

Graph with the condition that every vertex is connected to at least n other vertices.

Problem: (Adrian Tang) $G$ is a graph with $2n+1$ vertices. In $G$, for every set $S$ of at most $n$ vertices, there is one vertex outside of $S$ that is adjacent to every vertex in $S$. ...
2
votes
3answers
98 views

Prove that $\sqrt{5521}-1$ is an irrational number

I'm stuck on a textbook problem where I'm asked to prove that $\sqrt{5521} − 1$ is an irrational number by contradiction and prime factorization. I tried following steps the teacher did in her class ...
1
vote
4answers
67 views

Mathematical induction proof $n^4-1$ is divisible by $16$ for all odd integers $n$

I'm stuck towards the end of proving this, here's my attempt: $P(3) = 80/16 = 5$, True $P(k) = k^4-1$ $P(k+1)= (k+1)^4-1$ Expanded $= k^4+4k^3+6k^2+4k+1-1$ This is where I am stuck at. Sorry for ...
2
votes
1answer
44 views

Optimal Strategy in a money compounding model where one's interest is only consolidated at a fee

Say I have my main account with $ \$ 10000$ that gains interest at a rate of .1% a day. The interest collects in a separate account and I have to pay a certain fee, say $\$1$, to consolidate this ...
1
vote
2answers
53 views

Elegant Proof that $m | xn \implies \frac{m}{(m,n)} | x$ [duplicate]

I have a proof that shows $m | xn \implies \frac{m}{(m,n)} | x$ which leans heavily on prime factorizations. Is there a more straightforward proof? Edit With this question, I was looking for a proof ...
0
votes
2answers
25 views

Do I need to prove both directions of this if and only if statement for sets?

I need to show that $S{1} = S{2}$ iff $$(S1 \cap \bar{S2}) \cup(\bar{S1} \cap S2) = \emptyset$$ Ok So I'll show that $1.$ if $S{1} = S{2}$ then $(S1 \cap \bar{S2}) \cup(\bar{S1} \cap S2) = \emptyset$...
0
votes
0answers
20 views

laws of logic - having issues with identifying if some propositions and what law is used

(~q∨q)∧r⇔(q∨~q)∧r (q∨~q)∧r⇔r∧(q∨~q) To me looking over all the laws the only one that I think that makes sense to me is the Commutative law. Unless I am just way ...
0
votes
0answers
37 views

Proof of Leibniz formula for determinants [on hold]

im trying to understand the following proof but it is not very clear for me, can someone walk me through it? Proof Thank you in advance
1
vote
3answers
45 views

Prove that a NxN grid can be colored using n colors such that each color appear once each row and column

Just like a simpler Sudoku game, given n, show that nxn grid can be colored using n colors so that each color appears once for each row/column. I see that each row/column forms a complete graph so ...
0
votes
0answers
28 views

Can someone explain how should i solve a multi variable chinese remainder equation

I have the following equations. $15x + 7y \equiv 46 \pmod {53}$ $ 34x - 10y \equiv 11 \pmod {67} $ $ x\equiv y\equiv0 \pmod 7$ I have no idea how to solve this, I have only solved one variable ...
0
votes
0answers
6 views

Way of predicting change in gradient of line following matrix transformation?

I recently learnt about dominant and repulsive eigenvectors. I noticed that the farther a line is initially from the dominant (though still closer than to the repulsive eigenvector), the more dramatic ...
0
votes
1answer
27 views

Directed Graphs

I'm currently struggling with directed graphs. What does it mean when an allocated graph has a minimal vertex of p E P? What's a minimal element? What does it mean if something is acyclic and has a ...
3
votes
2answers
105 views

For $(a + b + c + d)^{10}$, how many terms have coefficients that aren't divisible by $5$?

$(a + b + c + d)^{10}$ how many terms have coefficients that aren't divisible by $5$? I know that each of the following $a^{10}, b^{10}, c^{10}, d^{10} $, their coefficient is 1, which isn't ...
0
votes
1answer
27 views

Find the time gap between two vehicle based on km/h of the vehicle

I am currently researching on VANET for identifying the road capacity based on vehicle moving speed. Below is my question, If a car moving on 8km/h and distance to the next car is 15 meters, what ...
0
votes
2answers
29 views

Permutation from left to right of $140$ objects

I've been stuck on this problem for quite some time now, I can't seem to find a video or such where it references permutations in a specific order of left to right. I have no idea how to set this ...
3
votes
2answers
47 views

Finding the equivalence classes of the relation R

Find the equivalence classes of the relation R = {(0, 0),(1, 1),(1, 2),(2, 2),(2, 1),(3, 3),(3, 4),(4, 3),(4, 4)} on the set A = {0, 1, 2, 3, 4}. How do i solve this question. I'm attempting to ...
1
vote
0answers
38 views

Build up a matroid using a “rank-like” function

It is not hard to show that given a matroid ($E, L$) and a defined rank function, $L$ is exactly those subsets whose rank is equal to the size. The following question is about how to build up a ...
2
votes
1answer
30 views

Construct a rank-3 matroid using rank-2 flat

Let $E$ be a finite set with size bigger or equal to 3. Let $L$ be a collection of subsets of $E$ such that: $2 \leq |A| < |E|$ for any $A \in L$ $|A \cap B| \leq 1$ for any $A, B \in L$ Now show ...
0
votes
1answer
31 views

Simple percentage problem driving me crazy

Ok, so lets say to board a cruise ship it would usually take $60$ to $90$ minutes. Now it takes only $10$ minutes. In percentages this is: $60-10 = \frac{50}{60} = 83.3\%$ reduction (ie. from $60$ ...
0
votes
1answer
10 views

Proof - Possibility to transform all vertex’s value to 1

A big equilateral triangle is made up of smaller equilateral triangles. The relation is for n order of the bigger triangle, the number of inner triangles are n^2. Example of such a triangle with n = ...
1
vote
1answer
35 views

Expected value of the number of different numbers drawn in 37 rounds of roulette?

I need help with this problem. What is the expected value of the number of different numbers drawn in 37 rounds of roulette? Is this possible to interpret as the number of records? So the expected ...
1
vote
2answers
31 views

Logical Equivalences with English Statements

Showing two statements $p$ and $q$ are logically equivalent is to show $p \Longleftrightarrow q$. I understand this, however I think when looking at english statements showing whether or not they are ...
0
votes
1answer
21 views

Parity check matrix H given; justify that C can correct one error, does a word belong to C and correct an error. [on hold]

I'm trying to learn about error correcting codes, and I have this question from a previous exam. Now I'm a little bit confused because I can't seem to wrap my head around this one, could I please get ...
1
vote
1answer
38 views

Balls between boxes equation

I have a practice question I don't know how to answer past part (a) Consider nonnegative integer solutions of the equation $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 26$ (a) How many different ...
0
votes
0answers
18 views

Placing books on shelves using generating functions of recursive relation

Let $t_n$ be the number of ways to arrange $n$ books on two bookshelves such that each shelf contains at least one book. Assume books are distinguishable and order matters. Find a recursion ...
1
vote
5answers
59 views

Prove that if $A \cap C \subseteq B \cap C$ and $A \cup C \subseteq B \cup C$ then $A \subseteq B$

I'm having trouble figuring out what to do in this problem. I know that if $A \subseteq B$ then $A \cup B = B$ and $A \cap B = A$, but I can't wrap my head around on what to do with the given ...
0
votes
1answer
38 views

What kind of math should I learn before I tackle policy search PEGASUS research paper by Andrew Ng?

I provided the link below https://ai.stanford.edu/~ang/papers/uai00-pegasus.pdf the paper was referenced in the AI: Modern Approach book, and I would like to dive in depth into it. But my math is ...
1
vote
1answer
29 views

Logical statements with multiple quantifiers - discrete math

So I have some questions below that I don't understand because I'm struggling with solving questions that involve multiple quantifiers. I was wondering if someone could walk me through how to do these?...
0
votes
1answer
29 views

Prove these differently written de morgan laws

We define $$\overline{\bigcup_{p\in P} Sp} =\bigcap_{p\in P} \overline{Sp}$$ and $$\overline{\bigcap_{p\in P} Sp} =\bigcup_{p\in P} \overline{Sp}$$ Which are just another way to write de morgans laws....
0
votes
5answers
43 views

Simplify (p v (r v q)) ∧ ~(~q ∧ ~r)

I understand that ~(~q ∧ ~r) simplifies down to (q v r), but I don't understand how the answer to this question is ...