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

1
vote
2answers
30 views

Four colored dots on a graph

How do you prove the following: Suppose that every point in the plane is colored either black, white, or violet. Prove that (no matter how the colors are distributed) I can draw a rectangle in the ...
0
votes
2answers
26 views

Floor and Ceiling function

prove that x is a real number then $\lfloor −x \rfloor = −\lceil x\rceil$ and $\lceil −x \rceil = −\lfloor x \rfloor$. If I were to put a real number say like $1$, wouldn't it be right? But if I put a ...
2
votes
2answers
11 views

Picking Unique Balls from a Bin

Problem: We have a bin with 5 red balls, 7 green balls, and 9 blue balls. We draw 3 balls out of the bin, without replacement. What is the probability that no two of the three balls have the ...
1
vote
1answer
29 views

Proof by induction: For all n>= 1; 1 - 1/2 + 1/3 - 1/4 + 1/5 -…+(-1)^(n+1) 1/n <=1

Proof by induction: For all n>= 1; 1 - 1/2 + 1/3 - 1/4 + 1/5 -...+(-1)^(n+1) * 1/n <=1 ...
1
vote
1answer
26 views

Proof by induction: Show that for every real number $x\geqslant -1$ and every positive integer $n$, $ (1+x)^n \geqslant 1+nx$

Show that for every real number $x\geqslant -1$ and every positive integer $n$, $(1+x)^n \geqslant 1+nx$. This is what i have so far ...
0
votes
2answers
20 views

By the binomial theorem, use this result to show with explanation that the number of subsets of a set $S$ is $2^{|S|}$

Given that $(1+1)^n = 2^n = \sum^n_{k=0} \binom{n}{k}$ by the binomial theorem use this result to show with explanation that the number of subsets of a set $S$ is $2^{|S|}$ I'm really confused. So ...
0
votes
2answers
41 views

There is a group made of 25 people made of 10 men and 15 women…

There is a group made of $25$ people made of $10$ men and $15$ women. How many committees of $2$ men and $3$ women ($5$ people total) can be chosen from this group? I know you are supposed to use ...
0
votes
0answers
24 views

How to arrange a permutation ordered pair?

Let $X = {1, 2, 3, 4}$. List all permutations of $X$ that contain the ordered pair $(1, 1)$, and draw the graph of each of these permutations. How does one use the formula $P(k) = n!/(n-k)!$; I know ...
0
votes
1answer
17 views

How many 5-permutations of Q are there? (No repetition of character within a string and order matters)

How many 5-permutations of Q are there? (No repetition of character within a string and order matters) Q = {A, B, C, D, E}. So I think i'm supposed to be using the formula $(^n_k) = ...
3
votes
0answers
17 views

Problem on distributive lattices

I'm trying to prove the following: Show that a lattice is distributive if and only if it does not contain a sublattice isomorphic to either of the two lattices below. I was able to prove that ...
-3
votes
0answers
27 views

Discrete mathematics halp!

A perfect square is an integer of the form $n^2$ where $n \in \mathbb Z$. What possible remainders do perfect squares leave when divided by $3$?
0
votes
0answers
16 views

Relating floor and ceiling functions [on hold]

Let x ∈ R. Prove That the ceiling of x = (the floor of (x)) + 1.
0
votes
0answers
32 views

Find all solutions a, b ∈ N to the equation $2^a = b^ 2 − 5$ [duplicate]

so I'm stuck on this question in my uni assignment for discrete math. I've worked out that a=2 and b=3 but the question also asks for us to prove that there are no other possible integers and I have ...
-2
votes
1answer
22 views

18 teams and you need to select correct order [on hold]

18 teams and you need to select correct finishing order how many permutations possible
0
votes
0answers
11 views

Maximizing volume of a regular hexagonal prism [on hold]

So my problem is as in the title above. I wanted to know how can I calculate the value of the side of the hexagon and the height of the prism given the total surface area does not exceed $330$, so ...
5
votes
1answer
74 views

How can I find the closed form of this recursive relationship: $a_{n}=(a_{n-1})^2+a_{n-1},a_{0}=1$

This comes up in OEIS as A007018. However the recursive form is useless to me, I need the closed form. I've been trying for several hours and I simply come up empty. Any advice? Thanks.
0
votes
0answers
20 views

determining the values for id(v) and od(v) in directed graph using counting flag method

I'm working on this problem: Let $G=(V,E)$ be a directed graph, where $|V|=n$ and $|E|=e$. What are the values for $\sum_{v\in V} id(v)$ and $\sum_{v\in V} od(v)$? This is a question that requires ...
1
vote
1answer
36 views

how to show that when an edge is removed from K5, the resluting subgraph is planar.

this question might be simple to others, but I'm stuck on this question. "prove that when I deleted an edge from $K5$, it has planar sub-graph . So, I know that G is planar if and only if G contains ...
2
votes
2answers
30 views

Finding a grammar for given language

So for this problem we are given a language and we have to find the grammar for that set. I am confused and what the constructors should be. The language in this problem is: $\{bb, bab, baab, ...
-2
votes
3answers
30 views

Give an example to a subset H of the group of integers (with respect to +) that is closed under the addition [on hold]

Give an example to a subset H of the group of integers (with respect to +) that is closed under the addition, but which is not a subgroup because the inverse takes us out of H.
1
vote
2answers
21 views

Prove $d = \gcd(a,b) \iff 1= \gcd (k_1, k_2)$. [duplicate]

This is the assumption they give me: Let $a, b$ be integers and $d$ a positive integer. Let $d|a$ and $d|b$ so there there exists $a=dk_1$ and $b=dk_2$. I can go the backwards direction but I'm ...
2
votes
1answer
62 views

How many students to award a prize? Combinations

Question: 80 tickets were sold to 50 engineering and 30 science students, one ticket per student. The tickets are entered in a prize draw. Five prizes are drawn: the Grand Prize, the Second Prize, ...
3
votes
5answers
54 views

Proving $(n+1)!>2^{n+3}$ for all $n\geq 5$ by induction

I am stuck writing the body a PMI I have been working on for quite some time. Theorem: $∀n∈N ≥ X$, $(n+1)!>2^{n+3}$ I will first verify that the hypothesis is true for at least one value of ...
0
votes
2answers
39 views

How many ways are there to sit 4 people from a group of 10 people around a circular table where two sittings are considered

How many ways are there to sit 4 people from a group of 10 people around a circular table where two sittings are considered the same when everyone has the same immediate left and immediate right ...
2
votes
1answer
31 views

How many binary bit strings of length 32 are there

How many binary bit strings of length 32 are there? I think I know the answer but I'm not sure...wouldn't it just be $2^5$ ?
0
votes
2answers
24 views

how to tabulate word transition function in discrete math?

The state transition table is $$ \begin{array}{c|cc} && f_a && f_b \\ \hline S_0 && S_1 && S_6 \\ S_1 && S_1 && S_4 \\ S_2 && S_3 && ...
-1
votes
0answers
17 views

Population of a host and parastite as a Discrete Dynamical System [on hold]

The population of a host and parasite is given by $h_t$ and $p_t$. Then the system of equations is: $$p_{t+1}=\alpha h_t (1-e^{-\beta p_t})$$ $$h_{t+1}=\alpha h_t e^{-\beta p_t}$$ where $h_0,p_0>0$ ...
2
votes
2answers
130 views

$a, b \in\Bbb N$, find all solutions to $2^a = b^2 - 5$ and prove there are no more solutions?

I am currently studying discrete mathematics at uni (in my computer science degree). We have an assignment due tomorrow, and i have been able to do most of it, but one question eludes me. I spoke to a ...
0
votes
1answer
14 views

What is the number of families that buy newspaper A only?

In a town of 10000 families it was found that 40% families buy newspaper A, 20% buy newspaper B, 10% buy newspaper C, 5% families buy both A and B, 3% families buy B and C, and 4 % buy A and C. If 2% ...
2
votes
3answers
49 views

Given LCM of three natural numbers, find the possibilities.

LCM of three natural numbers =150. How many sets of three numbers are possible? I know how to do this for two natural numbers.There is also a general formula for that. But for 3 numbers it is posing ...
0
votes
0answers
25 views

GCD and remainders

Can anyone please help me with a problem associated to GCD. Say we have 2 numbers 30 and 42. What is the largest integer which when divides these two numbers will produce the same remainder? The ...
3
votes
1answer
22 views

Number of Possible Pairs from Two Sets

The Question: We have 18 distinct gadgets and 22 distinct widgets. We want to pick five pairs, each with one gadget and with one widget. In how many different ways can the five pairs be ...
0
votes
2answers
14 views

How to calculate: (Number of sets in power set size n) - (Number of sets in power set size n that have less than or equal to m items)

I know that power set size is 2^n, but how may one find the size 2^n - f(m), where f(m) is the size of all sets less than or equal to m (in powerset 2^n). Example: when n = 4, m = 2; size = 5 ...
1
vote
1answer
25 views

Proving statements about ceiling and floor functions.

Prove or disprove the statements below. (a) For all positive real numbers x and y, $\lfloor x \cdot y\rfloor ≤ \lfloor x\rfloor \cdot \lfloor y\rfloor $. (b) For all positive real numbers x and y, ...
0
votes
1answer
17 views

Finding out how many distinct functions can be made.

The problem goes as follow: Let$ A = {1, 2, 3, 4, 5}.$ (a) How many total functions $f : A → A$ are there? (b) How many of the functions in (a) are one-to-one? I would say only one function can ...
1
vote
1answer
67 views

Searching Algorithm

A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. When looking up a customer’s record in the database, the good customers account for 60%. Two ...
4
votes
0answers
57 views

Complicated Multivariate Recurrence Relations For Generating Polynomials

I have the following multivariate recurrence relations all from the same system: First, suppose that $0\le k\le j\le m$, and let $N$ be an independent integer. Then we have for expressions $a(k,~ m,~ ...
0
votes
0answers
44 views

Proof of $(P \to R) \lor (Q \to R)\, is\,equivalent\, to\,(P \land Q) \to R$

I am working through Velleman’s ‘How to Prove It’. This is one of the problems where I am a bit stuck. $(P \to R) \lor (Q \to R)\, is\,equivalent\, to\,(P \land Q) \to R$ I use the Conditional ...
1
vote
0answers
5 views

Approximation for the minimal test cover / minimal group test problem

There are multiple approximation methods I find for the minimal test cover, where approximation is with respect to the size of the test set. However I am looking for approximation which starts with a ...
2
votes
2answers
42 views

Prove that $\frac{1}{(1-x)^k}$ is a generating function for $\binom{n-k-1}{k-1}$

On my discrete math lecture there was a fact that: $\frac{1}{(1-x)^k}$ is a generating function for $a_n=\binom{n-k-1}{k-1}$ I'm interested in combinatorial proof of this fact. Is there any simple ...
0
votes
1answer
40 views

Proof by contradiction or contrapositive sets help

so I'm having difficulties proving the following Theorem, through either proof by contradiction or contrapositive. Can someone please help me? The problem is as follows: Prove that for any two sets, ...
0
votes
0answers
21 views

Let F be a field and let a,b ∈ F with a not equal to b. Show that the polynomials f ( x ) = x + a and g ( x ) = x + b are relatively prime

Let F be a field and let $a,b ∈ F$ with $a$ is not equal to $b$ . Show that the polynomials $f ( x ) = x + a $ and $g ( x ) = x + b $ are relatively prime. Only things I know is : A commutative ring ...
0
votes
0answers
32 views

binary search worst case for a set database of entries some good some bad

A database has 10,000 sorted entries, 20% known to be good. When looking up a record in the database, the good entries account for 60%. Two design options are considered to store the data in the ...
1
vote
0answers
29 views

How many elements are in the following set?

The set is $$\{ x \in Q:x^2 =64/25 \} $$ I thought the answer was $\{ \frac{8}{5}, -\frac{8}{5} \}$ but I am told there are in fact 4 distinct elements: $$\{ \frac{8}{5}, \frac{8}{-5}, \frac{-8}{5}, ...
1
vote
1answer
30 views

Proof by Induction: Puzzle Pieces Problem

There's a thought puzzle I am struggling to understand that deals with the fundamentals of writing a proof involving the inductive assumption. A jigsaw puzzle is solved by putting its pieces ...
0
votes
0answers
13 views

Dealing with complicated sums - $\sum_{1\leq i < j \leq m}\sum_{1\leq k,l \leq n}\binom{n}{k}\binom{n-k}{l}(j-i-1)^{n-k-l}$

I'm preparing myself for discrete math exam, and I have no problem when dealing with simple sum, but when I see a monstrous one I totally don't know what to do. Here's an example: $$\sum_{1\leq i ...
1
vote
0answers
28 views

All non-isomorphic transitive actions of the Dihedral group

Consider the Dihedral group $D_n$ of order $2n$ as a permutation group. That is $$D_n = \langle (1,2,\ldots, n), (1)(2, n-1)(3,n-2) \cdots \rangle.$$ I would like to determine all faithful transitive ...
0
votes
0answers
77 views

Questions on Lewis Carroll Distance [on hold]

In 1879, Lewis Carroll proposed the following puzzle to the readers of Vanity Fair : transform one English word into another by going through a series of intermediate English words, where each word in ...
-4
votes
3answers
66 views

$n \equiv 1 \pmod{2m} \Rightarrow n \equiv 1 \pmod{m}$ but converse is false [on hold]

Prove if $n \equiv 1 \mod 16$, then $n \equiv 1 \mod 8$ BUT if $n \equiv 1 \mod 8$ then it is not necessarily true that $n \equiv 1 \mod 16$. Prove that if $n \equiv 1 \mod 2m$, then $n \equiv 1 \mod ...
1
vote
1answer
55 views

how to prove that the ceiling(x) = floor(x) + 1?

I was just wondering if someone could please explain how one would go about proving that the ceiling(x) = floor(x) + 1 ? I have never been very good with inequalities, and that seems to be the only ...