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
1answer
66 views

$M_{R^n}$; how to derive $n$ for transitive closure?

When finding the transitive closure of a relation $R$, I convert $R$ into a boolean matrix $M_R$, and find the union between $M_R$ and its powers up to $n$. $$M_{R^*} = M_{R^1} \lor M_{R^2} \lor ...
1
vote
1answer
31 views

Definition of a lattice point being primitve

I was reading an article and came across the following definition: a lattice point is called $\it{primitive}$ if it is part of a basis of the lattice. Suppose I have a lattice $\Lambda$ in ...
1
vote
1answer
66 views

Easy generating functions task from concrete mathematics book

This question might seem very novice, but i'm not sure about the solution. We have domino puzzle of size $2 \times\ n$ and we get 4 points for every vertical block and 1 point for horizontal block, ...
1
vote
1answer
89 views

How to prove if two propositions are always true

Let P1 and P2 denote the following propositions: P1="CS is difficult or not many students like CS". P2="If math is easy, then CS is not difficult". Suppose that both P1 and P2 are true, determine if ...
1
vote
2answers
25 views

Question over recursive definitions

Let $E$ be the set of even integers. Then the Base Case: $0\in E$ And the constructor case would be If $n \in E$ then so are $n+2$ and $-n$. This makes sense. But would the Base case and constructor ...
1
vote
2answers
26 views

Modeling properties of a graph?

There is an undirected graph modeling highways in Texas, the vertices are cities and the edges are highways. How would you model the property. "Even if you shut down one highway, you can get from any ...
1
vote
3answers
227 views

How to identify an inverse of 101 modulo 4620

I use Euclidean Algorithm: 4620 = 101 * 45 + 75. long story short. I get 3 = 2 * 1 + 1. After that 2 = 1 * 2 + 0. gcd(101,4620) = 1. So I use back substitution. 1 = 3 - 1 * 2. Long story short, I ...
1
vote
1answer
942 views

Another proof by strong induction problem

I am trying to solve the following problem using proof by strong induction. the problem is: Assume that a chocolate bar consists of n squares arranged in a rectangular pattern. The entire bar, or any ...
1
vote
1answer
19 views

Finding a parameter for two solutions in a field

For what values of parameter $m$ does the equation have two solutions in field $Z_{13}$? $$mx^2+2mx+(m+1)=0$$ So my guess for such problem would be to calculate the delta so that we get $\Delta = 4m$ ...
1
vote
1answer
67 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. ...
1
vote
5answers
151 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 ...
1
vote
1answer
704 views

In how many ways can you arrange the alphabet so that A and B are always next to one another (In either order)

Ok, so I have no idea where to begin on this question. Do I treat A and B as one letter? 25 choose n?
1
vote
2answers
208 views

An example of a function whose domain is the set of positive integers and range is the set of integers?

I was browsing through one of my old pre-calc books, and I feel a bit ashamed to say I can't think of a simple answer. It intuitively feels impossible, as there are half as many points in the domain ...
1
vote
2answers
52 views

Find a recurrence for in , the number of integer compositions of n which only have 1s and 2s as parts.

Find a recurrence for $$i_n$$ the number of integer compositions of $n$ which only have $1$s and $2$s as parts. How do you approach this problem?
1
vote
2answers
53 views

finding boolean function truth table

Can anyone explain this $P \rightarrow Q$ and how do we get true,false,true,true from the truth table in the third column? I know the first two colums but i am confused how to get the third row.can ...
1
vote
1answer
123 views

Use mathematical induction to prove that a function F defined by specifying F (0) and a rule for obtaining F (n+1) from F (n)is well defined.

Im just not sure what the question is asking me to prove, or how to prove it with induction.
1
vote
1answer
48 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...
1
vote
2answers
57 views

Is $\sum_{x=1}^n (3x^2+x+1) = n^3+2n^2+3n$?

I wanna check if the following equation involving a sum is true or false? How do I solve this? Please help me. $$ \sum_{x=1}^n (3x^2+x+1) = n^3+2n^2+3n$$ for all $n \in \{0,1,2,3, \dots\}$.
1
vote
1answer
167 views

Mathematical Induction for greedy algorithm problem?

Suppose you want to place towers along a straight road, so that every building on the road receives cellular service. Assume that a building receives cellular service if it is within one mile of a ...
1
vote
2answers
238 views

Pizza Topping combinations

I run a pizza joint in Seattle, USA, and would love to know how many different combinations of pie we can create. We have: 23 toppings 12 "house" pizzas 2 sizes (medium and large) two different ...
1
vote
1answer
41 views

Discrete Mathematics Proof odd degree

Show that for a graph letting r be the number of vertices with odd degree( with an odd number of edges) show that r is even. Is that about Euler's criterion or is there any other solution?
1
vote
1answer
390 views

what is the cardinality of each of these sets?

I am confused on these questions I feel like that are too easy. I just need to find the cardinality of each of the 3 problems. I believe that the first one and third one is a zero with a slash through ...
1
vote
3answers
295 views

Prove or disprove that if one root of a quadratic equation is rational, then the other root must be rational as well.

I'm taking an introduction to discrete math course and I'm having some trouble with this homework problem. I think we're supposed to assume that the coefficients are integers based on other examples ...
1
vote
2answers
38 views

Intersections/Reunions of power sets

Let $P_i$ be the power set of $A_i=\{1,2,3,\cdots ,i\}$. What is: $$\bigcap_{i=1}^{n}(P_{i+1} - P_{i})$$ $$\bigcup_{i=1}^{n}(P_{i+1} - P_{i})$$ The problem asks you to find those two sets ...
1
vote
1answer
45 views

Constructing sets involving predicates. Let $P(x),Q(x)$ be predicates over a set $X$?

Let $X$ be a set and $P(x),Q(x)$ be predicates over $X$. Consider the sets $$Y = \{y\in X\mid P(y)\}$$ $$Z = \{z\in X\mid Q(z)\}$$ Complete the following sentences with quantified propositional ...
1
vote
1answer
54 views

How to express this truth set?

How would you express this truth set in mathematical terms? $4 < x^2 \le 9, X \in \mathbb{R}$
1
vote
2answers
265 views

Upper bound of Euclidean norm on vectors in $\mathbb{R}^n$

Show that for any vectors $v_1,\ldots,v_n \in \{-1,1\}^n \subset \mathbb{R}^n$, there exist $\epsilon_1,\ldots,\epsilon_n \in \{-1,1\}$ such that the Euclidean norm of $v=\sum_{i=1}^n \epsilon_i v_i$ ...
1
vote
1answer
76 views

The Mysterious Discrete Math Operator

I am working on some discrete mathematics and came across this strange operator on two sets. $R \circ S$ I have only seen this circle operator with function compositions, so is this "Set ...
1
vote
2answers
192 views

How can I find the number of solutions to integer inequalities with multiple unknowns?

I've just learned how to find the number of integer solutions of this kind of inequations, $$x_1 + x_2 + \dots + x_k = n, \qquad(x_i\geq0)$$ which is $\binom{n+k-1}{k-1}$. But I have no idea about ...
1
vote
1answer
112 views

Set notation & Identities (Proof)

The following questions require a true/false statement as well as a supporting claim. I'm having a hard time understanding set notation as well as their identities. This is my understanding ...
1
vote
1answer
179 views

Functions that are sets of all function - proofs

I'm going through the book Proofs and fundamentals, by Bloch, and it doesn't include a solution manual for it's examples. It doesn't have many examples on notation and proof strategy for certain ...
1
vote
1answer
40 views

Are the following two definitions of Borda winner equivalent?

The Borda count is a method used to determine the winner object where people rank objects. For instance, imagine each person ranking 3 objects. The highest ranked object gets 2 points, the second gets ...
1
vote
1answer
47 views

Calculate $\sum_{A,B \subset X} |A \cup B|$ for $|X|=n$

I need to calculate the sum $\sum_{A,B \subset X} |A \cup B|$ for $|X|=n$ Well I guess we can think of $X=\{1,...,n\}$. Well, in my opinion this is basically this. $\sum_{k=1}^n ...
1
vote
1answer
64 views

Creating Recurrence

If I have an integer $n \geq1$, and I had to draw $n$ straight lines, so that no two of them are parallel as well as no three of them intersect in one single point. These lines divide the plane into ...
1
vote
2answers
57 views

Finding a real number c for polynomial (proof)

The question is to find a real number c for which $ x\ge c%+$ implies $$x^4-4x^3+7x-9 \ge1000$$. I was given the hint that $x>10$, then $4x^3<0.4x^4$, so $x^4-4x^3>0.6x^4$. Problem is, I'm ...
1
vote
1answer
55 views

Largest K-multiple free set out of a fully ordered set

i'm struggling conceptually with this problem, i don´t know how to approach it in a clever way (without a computer, or at least without a brilliant algorithm). Mathematicians defined a k-multiple set ...
1
vote
2answers
150 views

Finding the coefficient in the expansion

I need help finding the coefficient of $x^7y^2$ in the expansion of $(2x-y)^9$ if you could give me a hint
1
vote
1answer
65 views

Number of Contiguous Arrangements of Four Books out of Twelve

Twelve distinct books are lined up on a shelf. If four of the books are blue, how many arrangements of the books, have all four blue books together? I don't know if my answer is right but is it 8 ...
1
vote
1answer
33 views

Compute number of points having same property

I have been given a cuboid which has either green or red color for each point (integer coordinates) in it. I am also given another cuboid whose lower left corner is (x1, y1, z1) and upper right corner ...
1
vote
1answer
120 views

Discrete Math- Four different dice are rolled

Four different dice are rolled. a) In how many outcomes will at least one five appear? b) In how many outcomes will the highest die be a five? I think i figured out the answer for how many outcomes ...
1
vote
1answer
156 views

Simplification of a Boolean Expression

I want to simplify this expression: ACD' + E(A+C)(A'+D') + A'C . The result must be a product of sums, where every sum should be consisted of just two variables. For example (A+B)(C+A)(Z+Y) ... ...
1
vote
3answers
112 views

Suppose x and y are coprime integers and z is a natural number. Prove that If xy is a zth power then x and y are both zth powers. [duplicate]

I'm supposed to use a prime factorization somewhere, and that the fundamental theorem of arithmetic is to be applied as well.
1
vote
1answer
1k views

The 100 Coins Puzzle

There are 10 sets of 10 coins. You know how much the coins should weigh. You know all the coins in one set of ten are exactly a hundredth of an ounce off, making the entire set of ten coins a tenth of ...
1
vote
3answers
41 views

Proof on equivalence relations help

If $a,b\in\mathbb Z$, define a relation $\sim$ on $\mathbb Z$ by $a\sim b$ iff $ab ≥ 0$. Is $\sim$ an equivalence relation on $\mathbb Z$? Proof: Reflexive: Suppose $a\in\mathbb Z$. Then ...
1
vote
2answers
53 views

Are those rings fields?

Let $f(x) = x^4+x^2+1 \in Z_{2}$ and $A = Z_{2}/f(x)$ Is $A$ a field? Let $f(x) = x^4-x^2+1 \in Z_{7}$ and $B = Z_{7}/f(x)$ Is $B$ a field? I know that a ring $A = Z_{n}/f(x)$ is a field ...
1
vote
1answer
89 views

How much is modulus( 3214020402^43424492897 , 308 )?

Let $$B=3214020402$$ $$E=43424492897$$ $$A=B^E$$ How much is modulus( A , 308 ) ? My try: $$[A]_{308} \to ([B]_4^E,[B]_7^E,[B]_{11}^E) = ([2]_4^E,[5]_7^E,[10]_{11}^E)$$ Applying ...
1
vote
2answers
334 views

Examples of transitive and not negatively transitive binary relations

Example of a binary relation that is transitive and not negatively transitive: My try: $1\neq 2$ and $2\neq 1$ does not imply $1\neq 1$ Not neg transitive. But if $1=2$ and $2=1$ then $1=1$ by ...
1
vote
1answer
384 views

Why is it called 'discrete' mathematics?

I understand why you would refer to mathematics which concerns itself with all of the numbers on the number line as 'continuous' but why would you refer to countable or finite mathematics as ...
1
vote
1answer
202 views

Generalized geography in a directed graph with a perfect matching

Greography is a game where players take turns naming cities. Each city chosen must begin with the same letter that ended the previous city. The game begins with any starting city and ends when a ...
1
vote
1answer
132 views

Different arrangements of the word PHILOSOPHY

I want to figure out the number of different arrangements using all the letters in PHILOSOPHY such that the letters H,I,S,Y always stick together. The way I solved this is given below ; Selecting a H ...