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
3answers
19 views

(14^2014)^2014 mod 60 without a calculator

Calculate without a calculator: $\left (14^{2014} \right )^{2014} \mod 60$ I was trying to solve this with Euler's Theorem, but it turned out that the gcd of a and m wasn't 1. This was my ...
0
votes
0answers
5 views

How to use mobius-inversion to solve this problem?

Currently, I'm trying to solve this problem using mobius-inversion. the function f(d) means the number of (i, j, k) equals d, and function g(d) means the numbers that satisfying: d | (i, j, k). Then ...
-1
votes
3answers
76 views

Use mathematical induction to prove a statement [on hold]

Use mathematical induction to prove that: $$A\cap\left(\bigcup_{i=1}^nB_i\right) = \bigcup_{i=1}^n\left(A\cap B_i\right)$$
3
votes
2answers
364 views

The number of palindromic 6 letter sequences.

The genetic code can be viewed as a sequence of four letters T, A, G, and C. There were two parts to the question: (a) How many 6-letter sequences are there? I just said $\binom{4}{1}^6$, or ...
0
votes
1answer
14 views

Find $x$ for $[809x] = [214]$ in $\mathbb Z_n$ where $n= 5124$ s.t $0 \le x < 5124$.

The following is dealing with equal classes under congruence modulo $n$. I was told to use my answer for $[809x] = [1]$ in $\mathbb Z_n$ where $n=5124$ s.t $0 \le x < 5124$, so basically it's ...
1
vote
1answer
12 views

When can you not do a mapping composition?

Suppose I have $\alpha:\mathbb R^3 \to \mathbb R$ and $\beta:\mathbb R \to \mathbb R^+$. Looking over my notes, it says $\alpha \circ \beta$ can not be done but $\beta \circ \alpha$ can. What is the ...
-1
votes
0answers
33 views

Prove multivariable function is injective?

I am a little confused on how to prove a multivariable function is injective(one to one). I know the process for single variables but got stuck sadly. The function $f: \mathbb N \to \mathbb N$ such ...
0
votes
1answer
18 views

Find transitive closure of the relation, given its matrix [closed]

Find transitive closure of relation $R$ described by the matrix $M_R$: $$M_R = \begin{bmatrix}1 & 0 &0 \\0 & 1 & 1 \\1 & 0 & 1 \end{bmatrix}$$ I tried doing it like this ...
1
vote
2answers
12 views

Are they using Vandermonde's Identity here?

Consider a set of $5$ men and $7$ women. Then there are $\binom 53 \binom 72$ groups consisting of $3$ men and $2$ women. What they are doing looks very much like this identity: $\binom {m + n}{k} = ...
0
votes
1answer
7 views

Choosing subsets out of a set by using lists

Suppose we need to choose sets of size $2$ out of $\{A, B, C\}.$ The answer is given by $\frac {n!}{ (n - k)! k!}$. So, $n! = \{\text {ABC ACB BCA BAC CAB CBA}\}.$ What lists do $(n - k)!$ and $k!$ ...
0
votes
1answer
24 views

Infinite Decision Problems [on hold]

How can I prove that there are infinitely many decision problems of natural numbers that cannot be soved?
1
vote
1answer
14 views

proving property of polynomial that is composite

Show that $a^m+1$ is composite if $a$ and $m$ are integers greater than 1 and $m$ is odd. [$Hint:$ Show that $x+1$ is a factor of the polynomial $x^m+1$] So I tried doing it and got a result which ...
0
votes
2answers
39 views

Prove by induction that for a natural number a there exists integers $x, y$ where $a = 7x + 2y?$

I am trying to get my head around induction at the moment and found this problem in a textbook. I think that I should be doing induction on a, but I can't even see where to start the proof.
0
votes
1answer
42 views

Prove there exists a 2x2 entirely black or white square.

Given a 200x200 board containing black and white squares prove there exists a 2x2 sub square that is entirely black or entirely white. The total # of squares is 40000, there are 199x199 squares of ...
3
votes
5answers
42 views

Sets $A,B,C$ with $B\subseteq C$, prove that $(A-B)-C=A-C$

Ran across this and couldn't figure out how you would give a formal proof. It seems intuitive, in that $(A-B)-C$ is the elements in $A$ but not in $B$, and then also remove the elements from $(A-B)$ ...
0
votes
2answers
27 views

Find the probability that an integer selected between 1 and 5000 is divisible by at least one of 3, 5 and 7

I'm having a hard time finding the solution. I can find integers that are divisible by only one of them, but there are many that are divisible by two of them. That's the problem. Find the probability ...
2
votes
0answers
19 views

Hasse Diagram Correct?

I've had to make Hasse Diagrams before, but they've always been, for lack of a better word, pretty. The lines haven't had any complicated back and forth or the like. The jump that 4 and 6 have to do ...
1
vote
1answer
24 views

Prove that there exists a 2 by 2 sub square with odd number of white cells (i.e. 1 black, 3 white cells). [on hold]

I had previously asked a question similar to this but was told the question had an error, so this is the modification. Given a 200 by 200 board containing black and white squares prove there exists ...
2
votes
3answers
74 views

Inductive Proof that $k!<k^k$, for $k\geq 2$.

Call $P(k): k!<k^k$, for $k\geq 2$ Test it out with 2, and it's true ($2<4$). Assume that $P(k)$ is true for some $k\geq2$. Then show that $P(k+1)$ is true. $P(k+1): (k+1)!<(k+1)^{k+1}$ ...
6
votes
1answer
46 views
0
votes
1answer
30 views

Cardinality multiplication in counting problems

Multiplying things seems to be my weakest point, so I am trying to understand as much as possible. Consider $\sum^k_{j = 0} \binom mj \binom n{k - j}$. It's the answer to the question: "from a class ...
-2
votes
2answers
32 views

Hamiltonian cycle from adjacency matrix [on hold]

I'm finding it quite hard to answer this question I found; any help would be great. Find a Hamiltonian cycle in the graph G whose adjacency matrix is $$\begin{bmatrix} ...
1
vote
2answers
21 views

Are Cartesian Product and Multiplication (kind of) equivalent?

Example(not trying to prove anything): $|\{X, Y, Z\}| \times |\{A, B\}| = |\{XA, XB, YA, YB, ZA, ZB\}| = 3 \cdot 2 = 6.$
2
votes
1answer
41 views

Number of hairs of inhabitants and the population of a city

There is a town T where the population is greater than the number of hairs of each inhabitant. That is, if we count the number of hairs on the head of any inhabitant of the town, the amount will be ...
2
votes
1answer
38 views

Discrete Mathematics

I am having great difficulty trying to understand a question I have found and am keen to finding the solution and would appreciate any help. "Suppose that ten computer programs have been submitted ...
0
votes
1answer
17 views

Discrete Mathematics Sets Help

Hi i'm having difficulties working this question out I found, any help would be appreciated :) Let $A = \{1,2,4\}$ and $B = \{1,2,3\}$. Define the function $f: A\to B$ by the rule. What is the ...
3
votes
4answers
146 views

Four 6-sided dice are rolled. What is the probability that at least two dice show the same number?

Am I doing this right? I split the problem up into the cases of 2 same, 3 same, 4 same, but I feel like something special has to be done for 2 of the same, because what if there are 2 pairs (like two ...
3
votes
1answer
44 views

Euler's theorem: [3]^2014^2014 mod 98

Calculate without a calculator: $$\left [ 3 \right ]^{2014^{2014}}\mod 98$$ I know I have to use Euler's Theorem. As a hint it says I might need to use the Chinese Remainder theorem too. I know ...
2
votes
2answers
44 views

Experiment: Roll three 6-sided dice.

Are the following probabilities correct? I'm not very confident with probabilities and would just like these double checked please. Thank you. Experiment: Roll three 6-sided dice. a) Find the ...
0
votes
1answer
12 views

Bijection between lists and sets

Multiplication Principle as given in my textbook: Consider two element lists for which there are $n$ choices for the first element, and for each choice of the first element there are $m$ choices ...
0
votes
2answers
14 views

Lattice orders and number of elements in a set

My discrete mathematics lecture notes give the following definition of a lattice order: A 'Partial order R is a lattice order if the set of lower bounds for any two elements $x, y ∈ X$ has the ...
3
votes
2answers
34 views

14 pencils handed out to 6 people. Each person has at least 1 pencil. Person 6 no more than 3 pencils.

We have 14 indistinguishable pencils and we want to hand out all of the pencils to 6 people and we want everyone to get at least one pencil. However, we do not want person 6 to get more than 3 ...
-5
votes
1answer
19 views

Finding a solution to a recurrence relation [on hold]

Here is the setting of my problem $(a_k)$ is a sequence of numbers verifying : $a_k=4a_{k-1}+5$ for all integers k greater than or equal to 1. Initial condition: $a_0=2$. I need to find a close ...
1
vote
3answers
36 views

Suppose $k$ is even and $4 \nmid k$, please explain why $k/2$ is odd

Assume integer $k$ is even and $k>2$. In order for $k/2$ to be odd, $k$ cannot be divisible by $4$. Can someone please explain why this is true, or point me in the right direction? I don't need to ...
0
votes
0answers
5 views

Find minimum number of uniformely colored rectangles in a colored grid

I have an MxN grid. In each square of the grid there is color taken from a set of color C. I can describe the whole grid with MxN statements that say something like: the square (Mi,Nj) has the color ...
1
vote
2answers
38 views

How many different ways can 14 pencils be passed out to 6 different people? Some people are allowed no pencils.

There are 2 questions that are very similar and I have the same answer to both but I don't think that's correct. Can you help me see the difference between the 2 questions. We have 14 ...
2
votes
2answers
23 views

Equivalence Classes Output

I understand that an equivalence relation is a set that is reflexsive, symmetric, and transitive. I don't quite understand equivalence classes though. For example: What would the equivalence class be ...
-3
votes
1answer
53 views

Prove by induction $\frac{a_{1} + a_{2} + a_{3} +…+ a_{n}}{n} \geq \sqrt[n]{a_1 \cdot a_2 \cdot a_3 \cdot …a_n}$. [duplicate]

Let $a_1$ $a_2$,..., $a_n$ be positive numbers. Prove that $\frac{a_{1} + a_{2} + a_{3} +...+ a_{n}}{n} \geq \sqrt[n]{a_1 \cdot a_2 \cdot a_3 \cdot ....a_n}$. Mine is about trying to understand how ...
0
votes
0answers
37 views

Proof by induction [duplicate]

$\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} +\cdots+\frac{1}{n^2} < 2 - \frac{1}{n}$. Proof: Let $p(n)$ be a proposition. $$p(n):\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} ...
0
votes
2answers
24 views

How to create a moment generating function for $Y$?

Consider a discrete random variable defined as follows: When $X=0$, $P(X=x) = .25$. When $X=1, P(X=x) =.4$. When $X=2, P(X=x) = .35$. The moment generating function for $X$ will be: $$Mx(t) = .25 + ...
1
vote
2answers
25 views

Making sense of a combinatorial answer

$\frac {\sum^n_{k= 0}k\binom nk}{2^n}$ is the average size of a subset of $\{1, 2, \ldots, n\}$. We add up the sizes of all subsets and divide by the total number of subsets. Why is the $i$th term ...
0
votes
1answer
16 views

Computing the Value of a minimax tree

I am asked to compute the value of a minimax tree, which each node labeled with its initial value. I am just unsure how to do it. I know that it is a minimax tree if: the root is a min node, the ...
2
votes
3answers
109 views

Proof verification for proving $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ by induction

Prove by mathematical induction: $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ Basis Step: (We want to show, $P(2)$, which is 1 + ...
0
votes
2answers
35 views

How many elements in $X$ are of the form $3k + 1$ for some integer $k$?

Consider the set $X={300,301,302,...,29999,30000}$ (the set of all integers from $300$ to $30,000$ inclusive.) You do not need to simplify the numeric answers. How many elements in $X$ are of the ...
0
votes
0answers
14 views

Recursive and Primitive recursive functions

According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows: The constant, projection, and successor functions are all $\mu-$recursive. If $g_1, ...
0
votes
1answer
26 views

Permutation and combination.

I have started learning permutation and combination. I am looking at the question below. It has given the answers also but I didn't understand how? I have looked at many examples online it just made ...
0
votes
0answers
30 views

Probability With 52 Playing Cards

I am trying to answer the following questions as practice, however I am unsure on whether this is correct! 1) Probability of first card is $Heart$ is $13/52$ 2) Is the probability of getting a King ...
0
votes
3answers
41 views

determining which graphs are bitpartite/2-colorable and which are not

I am having trouble understanding bipartite/$2$-colorable graphs. I was hoping someone can guide me through this question. For the graphs given above, either prove that they are bipartite by showing ...
1
vote
1answer
35 views

Graph Theory - How many regions of an n-sided polygon with all chords added?

The question: Consider an $m-sided$ polygon with all of its chords added, and assume that no more than two of these chords cross at any one intersection point. Make the figure into a planar graph by ...
20
votes
3answers
579 views

A (probably trivial) Induction Problem: $\sum_2^nk^{-2}\lt1$

So I'm a bit stuck on the following problem I'm attempting. Essentially, I'm required to prove that $\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 1$ for all $n$. I've been toiling with some ...