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.

1
vote
1answer
27 views

Question regarding partially ordered sets

I have encountered few questions while reading the book 'Modern Algebra'. Let $\mathbb Q$ be the set of rational numbers. Let $B = \{ x : x\in\mathbb Q,\sqrt2 < x < \sqrt3 \}$. How it can ...
0
votes
0answers
16 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 ...
1
vote
1answer
878 views

Finding n in equivalence between two permutations

Find the value(s) of n: 2P(n, 2)+50 = P(2n, 2) For 2P(n, 2)+50 I simplified to 2(n)(n-1)+50. For P(2n, 2) I can't get any simpler than $2n\times(2n-1)\times...\times(n+1)\times n\times(n-1)$ and I'm ...
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
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:...
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
2answers
1k views

Number of students and how many are taking X class (Discrete Structures)

So I have my first quiz tomorrow and want to get off on the good foot, but I'm studying some problems and this one is particularly confusing... There are a group of 191 students, of which 10 are ...
0
votes
2answers
22 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
32 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)$ ...
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, ...
-3
votes
1answer
25 views
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 ...
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 ...
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
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 ...
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
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
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
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,...
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 ...
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$. ...
0
votes
1answer
42 views

Difference between 'Only' and 'Every' Keyword in Mathematical logic

Represent these two statement in first order logic: A) Only Alligators eat humans B) Every Alligator eats humans Is Every represents ≡∃ and Only represents ≡∀ ?? Can we differentiate it with ...
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
31 views

Show that the following two expressions to find $n \times n$ matrix determinant are equivalent [on hold]

I'm currently working in the following excercise: Let $A = [a_{i,j}]_{i,j ≤ n}$ be a $n \times n$ matrix. The determinant of $A$ is defined as: $$\sum_{\rho}^n i^2 \Biggr( \operatorname{sgn}(\...
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 ...
1
vote
0answers
22 views
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 ...
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: ...
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
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 ...
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 ...
0
votes
2answers
148 views

Argument for the diameter of these 2 graphs…

I believe G1 has a diameter of 2 & G2 has a diameter of 4. However, is there a formal way to prove / argue for these given diameters? I'd like to see an argument without having to list all the ...
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
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 ...
3
votes
3answers
983 views

N marbles puzzle: find the heaviest among them.

Suppose there are $N$ marbles and a two-pan balance used to compare the weight of 2 things. All of the marbles weigh the same except for one, which is heavier than all of the others. How would you ...
4
votes
3answers
798 views

Mod of numbers with large exponents [duplicate]

I've read about Fermat's little theorem and generally how congruence works. But I can't figure out how to work out these two: $13^{100} \bmod 7$ $7^{100} \bmod 13$ I've also heard of this formula: $...
2
votes
3answers
129 views

For all sets $A, B, C$, If $A \Delta B = A \Delta C$, then $B \subseteq C$

I get the general reason as to why this is True. I'm just having trouble trying to formulate this into a logically correct proof. My approach was: (1) Assume $A \Delta B = A\Delta C $ (2) Let $x$ be ...
0
votes
1answer
31 views

probabilility point closer to distance circle

the probability that the point is closer to the distance to the center of the circle than to the circumference is $\frac{1}{4}$ find probability: (A) When several points are selected sequentially ...
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 ...
5
votes
2answers
9k views

Proof that the sum of all degrees is equal to twice the number of edges

We want to proof $2|E| = \sum \limits_{v \in V} deg(v)$ for a simple graph (no loops). For our proof we assume $n$ to be the number of edges in a simple graph $G(E, V)$. We proceed our proof by ...
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
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 ...
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 ...
1
vote
1answer
36 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 ...