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

32
votes
9answers
66k views

Maximum board position in 2048 game

A game called 2048 is making rounds on social media. I am trying to determine the maximum score attainable for this game. Let's assume WLOG that only 2s are returned (if 4s are possible the max score ...
1
vote
1answer
284 views

Find an inverse of a modulo m for each of these pairs of relatively prime integers

a) a = 2, m = 17 17 = 2 * 8 + 1 2 = 1 * 2 + 0 1 = 17 - 8 * 2 <-How do I know which one is the inverse by using back substitution?
2
votes
1answer
36 views

Finding a Closed Form of a Two Dimensional Recurrence

In a problem I'm working on, the following two-index sequence keeps popping up: $a(1,m) = 1$ for all $m$. $a(n,m) = 1$ if $n = m$. $a(n,m) = n(a(n,m-1) + a(n-1,m-1))$, $1 < n < m$. And if $n ...
1
vote
2answers
130 views

In how many ways can you divide bonuses between employees?

How many ways are there to divide 33 000 USD between 22 employees of a company (including 1 president, 1 vice-chairman and 20 normal employees), if a normal employee can get 1000 or 1500 USD, whereas ...
2
votes
4answers
75 views

What is the coefficient of $x^{50}$ in $\left(x + \frac1x\right )^{100}$?

I know I should use the Binomial Theorem, but I'm just having some trouble figuring this out. thanks!
0
votes
1answer
151 views

Bipartite Graphs and Trees Questions

Which of the claims below is not equivalent to the rest? 1) Every cycle in a graph "B" has an even length 2) Graph "B" is bipartite 3) Graph "B" has two components that are connected. 4) Graph "B" ...
0
votes
3answers
87 views

Discrete math on Paths and Connectivity

Can someone describe the following question for me? a) Describe a 5-regular simple graph with 12 vertices which is not connected. b) Let G be a 6-regular graph with 12 vertices. For any pair of ...
1
vote
2answers
34 views

Discrete Math on Cycles and Circuits

I'm not sure how to show that the graph G contains a cycle if the minimum degree delta ≥ 2 for the following question Show that if G is a graph with minimum degree ≥ 2, then G contains a cycle.
0
votes
1answer
32 views

Discrete Math on Isomorphic Graphs

I'm not sure how to show or draw that no self-complementary graphs can exist or not for the following question. Show that no self-complementary graphs with 6 or 7 vertices can exist.
0
votes
1answer
270 views

Derive that 937 is an inverse of 13 modulo 2436

Use the Euclidean Algorithm to see if an inverse exists. 1) 2436 = 13 * 187 + 5 2) 13 = 5 * 2 + 3 3) 5 = 3 * 1 + 2 4) 3 = 2 * 1 + 1 5) 2 = 1 * 2 + 0 gcd(13,2436) = 1 Find the Bezout coefficients ...
0
votes
1answer
33 views

Can an element hood test be converted into an existential statement?

I'm just curious whether it makes sense to convert a statement of the form: $$ y\in \{x\in A : \phi(x) \} \;\; \text{into the form} \;\; \exists x(\,...) $$ It's just that in the book I'm reading the ...
1
vote
2answers
435 views

How is Pascal's Triangle Important?

Question: What are the uses of Pascal's Triangle? What are some interesting properties of Pascal's Triangle? I know that Pascal's Triangle has many uses, but I only know a few of them. I know ...
0
votes
1answer
32 views

Finding Bezout coefficients

$$3 − 1 · (23 − 7 · 3) = −1 · 23 + 8 · 3$$ How does one get the left side to become the right side? Is it algebra? My discrete math textbook just wrote this but never explained a step by step process ...
0
votes
3answers
53 views

Prove that a function is one to one without graphing

I know that you can prove a function is one to one by graphing it and using the horizontal line test. But in my notes it showed another way to prove a function is one to one but I am not sure if I am ...
1
vote
0answers
94 views

How do you justify the PigeonHole principle?

I am working on the problem below and just have two questions pertaining to my answers. 1) Am I clearly and correctly justfying my answers, anything I can improve on or explain better? 2) Are my ...
1
vote
1answer
38 views

how can i prove: $|P(\Bbb R)\times \Bbb R|=|P(\Bbb R)|$?

How can I prove that $|P(\Bbb R)\times \Bbb R|=|P(\Bbb R)|$? I can use the following statements: $$|A|<|P(A)| $$$$ |P(\Bbb N)|=|\Bbb R|$$$$ |\Bbb R\times\Bbb R|=|\Bbb R|$$$$ |\Bbb Z\times\Bbb ...
0
votes
1answer
106 views

Convert modulo 65 into modulo 26.

Is there anyway to convert x ≡ 9 (mod 65) into x ≡ something (mod 26)? Generally is there a way to convet one modulo into some other modulo?
0
votes
0answers
72 views

How many divisions are required to find gcd (34, 55) using the Euclidean Algorithm

1) $55 = 34 \cdot 1 + 21 $ 2) $34 = 21 \cdot 1 + 13$ 3) $21 = 13 \cdot 1 + 8$ 4) $13 = 8 \cdot 1 + 5$ 5) $8 = 5 \cdot 1 + 3$ 6) $5 = 3 \cdot 1 + 2$ 7) $3 = 2 \cdot 1 + ...
2
votes
2answers
69 views

May a bipartite graph have self-loops?

By definition I think no, but I'm not so sure. Thanks in advance
0
votes
0answers
74 views

Show these integers in each of these sets are pairwise relatively prime

My thought process: the integers are pairwise relatively prime if all the gcd of that set of integers listed below are 1. a) $\{31, 34, 55\}$ $\gcd(31,34) = 1$, $\gcd(31,55) = 1$, $\gcd(34,55) = 1$. ...
1
vote
1answer
66 views

Difference between $A\to B\to C$ and $A\to(B\to C)$

As the title says, what is the difference between $A\to B\to C$ and $A\to(B\to C)$? I have tried to reduce these expressions into $A\to B === (A\text{ OR } \text{NOT} B)$ form but didn't get anywhere. ...
2
votes
2answers
82 views

Find $\max_{\sigma \in S_n}\sum_{i=1}^n|\sigma(i)-i|$ where $S_n$ is the group of permutations on $n$ letters (Greedy algorithm shows up?)

Find $\max_{\sigma \in S_n}\sum_{i=1}^n|\sigma(i)-i|$, where $S_n$ is the symmetric group of permutations of $n$ symbols. So, the story goes like this: When I first saw the problem, I thought the ...
14
votes
2answers
372 views

Minimum number of operations (divide by 2/3 or subtract 1) to reduce $n$ to $1$

This question is inspired by a Stack Overflow question which involves the task to find an algorithm to solve the following problem: Given a natural number $n$, what is the least number of moves ...
0
votes
1answer
51 views

“Homotopy theory” on finite topological spaces?

My question concerns finite sets carrying a not-necessarily-discrete topology. I'm wondering if there's an analogue for homotopy theory where the role of $S^n$ is played by some other, finite set. (My ...
0
votes
1answer
46 views

the source and the sink have a maximum capacity

Consider a variant of max-flow networks in which all vertices different from the source and the sink have a maximum capacity. As we know, Such a network can be transformed into a usual max-flow ...
0
votes
0answers
25 views

proving a recurrence relation

I'm trying to prove that the recurrence $T(n) = T(\alpha n)+T((1-\alpha)n)+n$, where $0<\alpha<\frac{1}{2}$, has an order of growth $T(n)= an$ log $n$ $\in \Theta(nlog(n))$ where $a$ is a ...
0
votes
1answer
79 views

Prove or disprove for any real number

Prove or disprove for any real number $x^2 < x$ , considering $0.5^2 = 0.25, 0.25 < 0.5$
1
vote
1answer
69 views

Proving very basic statements.

I'm just talking about (b), (c) and (d) in this question. The way I see it, (b) is asking to prove that: $$n \mod m = n \mod m$$which is like asking to prove that $1 = 1$. (c) is also asking to ...
-1
votes
4answers
286 views

Prove that if n is an odd positive integer , then $n^2\equiv1\mod8$

Prove that if n is an odd positive integer , then $n^2\equiv1\mod8$. Can I prove by counter example by inserting several odd numbers? My work: I insert 1 into n. $8\mid(1^2 - 1) \implies 8\mid0$ I ...
0
votes
0answers
41 views

Division Algorithm

Evaluate these quantities. 1) -17 mod 2 Answer: 1 = -17 mod 2 2) 144 mod 7 Answer: 4 = 144 mod 7 3) -101 mod 13 Answer: 3 = -101 mod 13 4) 199 mod 19 Answer: 9 = 199 mod 19. May someone ...
1
vote
2answers
37 views

mean for the amount of money won for flipping a coin n times and winning m dollars on the m-th flip if it is tails

I am flipping a coin n times. if it lands on heads, i win nothing but if it lands on tails on the m-th flip, i get m dollars. how much money can i expect to you at the end of the game. I looked at ...
0
votes
2answers
90 views

recursive algorithm for fibonacci numbers?

Trying to figure out if I would use a recursive algorithm for fibonacci numbers. My problem is "Devise a recursive algorithm to find the n-th term of the function defined by $f(0)=0, f(1)=1, f(n+1)= ...
0
votes
1answer
53 views

Mathematical Induction proof that $\sum\limits_{i=1}^n \frac{1}{i^2} < 2 - \frac1n$ [duplicate]

I am to use mathematical induction to prove: $$\sum_{i=1}^n\frac{1}{i^2}<2 - \frac{1}{n}$$ my base case is n = 3: LHS: $\frac{1}{1}+\frac{1}{4}+\frac{1}{9}= \frac{49}{36}$ RHS: ...
1
vote
5answers
148 views

Proofs using Mathematical Induction

I have two problems that I am trying to solve using mathematical Induction but am confused on how to know when process to use. 1) Prove by mathematical induction that ...
0
votes
1answer
92 views

What's the difference between a permutation and a combination with repetition?

My understanding is that a permutation is used to find the number of rearrangements of different elements, taking into account possible orders. A combination is used to find the number of ...
0
votes
1answer
44 views

Help with understanding Induction proofs

From my understanding, to prove induction problems, we must: Find a base case Assume n=k holds true Prove n=k+1 with the assumption However I am looking at the proof of a problem and they don't ...
1
vote
0answers
21 views

Help with Calculating amount in pages by 2 working days

I need help with the following, I think I got this right, but wanted to pass it by the gurus/experts first: ...
2
votes
1answer
117 views

Possible marks in a MCQ test

Just out of curiosity(we have a similar test) not homework : A multiple choice questions test has $100$ questions. The marking scheme is $+4$ for correct answer, $-1$ for wrong answer and $0$ marks ...
1
vote
2answers
56 views

GCD of pairs of integers

So I think I am just psyching myself out right now and this is way to easy but I am running on no sleep in the past few days so forgive me please. The question is what are the greatest common divisors ...
0
votes
3answers
107 views

Derive Closed form sum of N^2

Can anyone explain to me how you would derive this ? I have this question asked in a CS class and can't figure out how to derive it. it has to be derived as you would with sum of N ex ...
0
votes
0answers
39 views

An independent set of vertices $\times$ the chromatic number $\ge$ the number of vertices

$A$ is a graph. By definition an independent set $S$ is a group of vertices (could be 0 vertices, or could be all vertices) of $A$ where there are no two vertices from $S$ that are adjacent in graph ...
1
vote
1answer
78 views

Determining number of solutions with inclusion-exclusion

NOTE: I know there are similar questions to this, but the ones on this website are much more complex, and I'd like to get a basic understanding before moving on to them. Please do not mark this as a ...
0
votes
3answers
78 views
0
votes
1answer
48 views

Number of binary operations on $S$

Given a set S, a function $f : S \times S \to S$ is called a binary operation on $S$. If $S$ is a finite set, then how many different binary operations on S are possible?
0
votes
1answer
93 views

Understanding a proof that $\gcd(a, b) = 1$ if $sa + tb = 21$ and $ua + vb = 10$

I am studying the solution to a problem: Suppose $a, b, s, t, u, v$ are integers such that $sa + tb = 21$ and $ua + vb = 10$. Show that $\gcd(a; b) = 1$. ...
0
votes
1answer
50 views

Finding the number of onto maps from $A = \{1,2,3,4,5\}$ to $B = \{a,b,c\}$

I'm trying to catch up in my discrete math class right now and I came across a practice question: Use inclusion-exclusion to find the number of onto maps from $A = \{1,2,3,4,5\}$ to $B = ...
0
votes
0answers
81 views

for n∈N A(n)={x∈N | 0<= x <= n}, prove the following statements

please help me improve this proofes, or find a more formal mathematical version of them. N is the set of natural numbers N = {0,1,2,...,} for all $n∈N$, there is $A(n) = \{x∈N | 0\le x \le n\}$ ...
1
vote
2answers
63 views

transitive property in a binary relation

I'm looking at a True or False question in my book and it is very close to identical to the definition of the transitive property in the book, though this answer is False. If someone could explain to ...
1
vote
2answers
77 views

understanding reflexive transitive closure

Suppose I have the following relation $$R = \{(1,1), (2,3), (3,1)\}$$ To make it reflexive we add the following missing pairs: $$ \{(2,2), (3,3)\}$$ Now I wonder how to find the reflexive transitive ...
1
vote
0answers
39 views

Solve recurrence $a[n,k]=(2m-2k)\;a[n-1,k+1]+k\;a[n-1,k]$

I'm trying to count how many vectors of size $n$ there are, given that the elements of the vector are integers from the range $\{-m,m\}-\{0\}$ (zero is excluded), and there are no pair of elements ...