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

0
votes
1answer
22 views

Probability - Random viarbles

A notepad manufacturer requires that 90% of the production is of sufficient quality. To check this, 12 computers are chosen at random every day and tested thoroughly. The day's production is deemed ...
-1
votes
1answer
18 views

does an explicit formula for GCD exist?

i was trying to put GCD(a,b) into the form of f(a,b) = a +5b. i know the euclidean algorithm finds the GCD, so I was trying to put that concept into a recursive formula but its getting way too ...
1
vote
3answers
69 views

If $x^2$ is divisible by $4$ then $x$ is even?

I am studying discrete mathematics as course and I have to prove this "If $x^2$ is divisible by $4$ then $x$ is even". I am wondering how to prove it using the contrapositive of this ...
0
votes
1answer
19 views

Concrete mathematics: 2.5: expand and contract [on hold]

So I'm reading on methods on solving sums. I don't understand this. The book says $$\sum_{1 \le k \le n} k^2 = \sum_{ 1 \le j \le k \le n} k$$ I don't understand what the authors did.
0
votes
2answers
26 views

recurrence problem for number of words

Let $w_n$ be the number of words (strings) of length $n$ that can be made using the digits {0,1,2,3} with an odd number of twos. Find a recurrence relation for $w_n$ and solve the recurrence. The ...
1
vote
1answer
26 views

Strange Absorption Behavior in Discrete Math

I'm studying for my discrete math exam and I'm looking over the professors' examples. I have a question about one of them and I was hoping someone could help me out. Here is the example: ...
1
vote
1answer
24 views

How does one find/list equivalence classes?

Can someone explain how I would find/list the equivalence classes (And number of equivalence classes) of these two examples? Example 1: A is the set of all possible strings of 3 or 4 letters in ...
1
vote
1answer
29 views

Probability involing percentages (Bernoulli?)

Assume that about 56% of population belong to group type of O. A) What is the probability that it will need to take a blood test from exactly three individuals in order to find a person with O-type ...
1
vote
2answers
32 views

How to formalize proofs

I'm struggling a bit with my discrete maths course and I was wondering if anyone could help me with my assignment. The question I'm working on is, Prove that if a and b are positive integers, then ...
0
votes
1answer
27 views

How would I draw the diagram for this relation?

The question I am trying to solve is below. I have proven it is an order but am unsure how to draw the diagram for it. Can someone point me in the right direction? Let A = {1, 2, 3, 4}, and let R be ...
0
votes
1answer
29 views

How to prove this equivalence relation?

How would one go about proving this is an equivalence relation? I have no idea where to start. $\cal R$ is the relation on $\Bbb Z \times \Bbb Z$, such that $((a, b),(c, d)) \in \cal R$ if and only ...
0
votes
2answers
59 views

Showing that ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ ∀x ∈ S (∃y ∈ E Q(x, y)) → R(x)

Q(x, y) := “Student x did exercise y in the book” R(x) := “Student x gets an A in the class” So my goal is to show that the following equivalency holds: ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ ∀x ∈ S ...
0
votes
0answers
23 views

Prove $(p\implies q)\lor (p\implies r)\implies(q\lor r)\equiv p\lor q\lor r$ with out using the truth table [duplicate]

prove with out using the truth table $$(p\implies q)\lor (p\implies r)\implies(q\lor r)\equiv p\lor q\lor r$$
1
vote
1answer
18 views

distributing r distinct objects into n-distinct boxes when repetition is allowed

Suppose there are 5 students and we are trying to create 3 distinct commissions which every student must be in at least one commission and every commission must have at least 2 members. what is the ...
0
votes
2answers
32 views

What is the number of nonnegative solutions of a linear equation?

What is the number of solutions of a linear equation? for example look at this equation: $X_1+X_2+...+X_n=r$ The number of solutions is the following formula, because the way of choosing $r$ objects ...
0
votes
1answer
48 views

Expected value of $\sin^2(0.01n)$ for discrete $n$

Is it possible to calculate the expected value of $\sin^2(0.01n)$, with $n$ taking non-negative integer values? Normally, when we wish to find the expected value of the sine function, we integrate ...
-2
votes
1answer
30 views

Conjecture about the units digit of 9^n where n is a positive integer [on hold]

Compute 9^0,9^1,9^2,9^3,9^4,9^5. Any1 can tell me what is the conjecture? I have been thinking~!appreciate ur help!
0
votes
0answers
20 views

Distribute Chocolates among m children Non Uniformly

Suppose person B has N chocolates,He has to distribute these chocolates non-uniformly among M children. Suppose child mi has weight Wi and the total weight is Wt. One way to do so is to distribute ...
0
votes
1answer
26 views

What rule of logic is this?

I was reading a proof on proving associative law for XOR operator and came across these steps. = (AB'C'+A'BC')+(A'+B)(A+B')C = (AB'C'+A'BC')+(A'(A+B')+B(A+B'))C = (AB'C'+A'BC')+(A'B' + AB)C I ...
0
votes
0answers
13 views

Understanding graph classification 1

I am reading a paper on graph classification and the author states In graph classification the goal is to learn a decision rule from training examples {${G_{i},y_{i}}$} where $i$=1, $G_{i}$ is a ...
1
vote
1answer
28 views

Math programms with floating point, how to calculate more digits? [closed]

How do programms like wolfram are able to calculate so many digits? ...
-2
votes
0answers
22 views

how do we negate “No cash no balance, no balance no cash” symbolically [duplicate]

how do we negate "No cash no balance, no balance no cash" symbolically my attempt statement: if no cash then no balance and if no balance then no cash (~p → q) ∧ (~q → ~p) negation: if there is cash ...
2
votes
1answer
184 views

two $\gcd$s that are coprime

Let $a, b$ and $c$ be integers. Prove that if $\gcd(a, b)$ and $\gcd(a, c)$ are coprime, then $\gcd(a, bc)$ = $\gcd(a, b) · \gcd(a, c)$ I am stumped in this problem. Can anybody clarify me what ...
1
vote
1answer
30 views

Using Extended Euclidean Algorithm

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$. I have ...
-1
votes
2answers
32 views

prove the equivalence of the following statements: 2x-1 is irrational; x/3 is irrational

I am stumped. I really have no idea how to solve this problem. Can someone please help me through this? THE TWO EQUATIONS ARE SEPERATE
2
votes
1answer
28 views

Gossip problem proof by induction

Question Suppose there are $n$ people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they ...
1
vote
1answer
24 views

How to generate a single instance of multichoose (stars and bars)

So we know that if I have $k$ balls and $n$ buckets, I have $\binom{n+k-1}{k}$ unique ways to allocate the balls. Let's say $n=4$ and $k=2$ then I have $\binom{5}{2}=10$ ways. All possible allocations ...
5
votes
2answers
81 views
+50

Graph and in-Degree and Drawing

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
4
votes
1answer
57 views

How many integers could be in such a way that any digits is not bigger than the left digits?

How many 4-digits integers could be in such a way that any digits is not bigger than it's left digits? I Try it with simulation, i get 714. anyone could describe a formula for me? My try:
1
vote
2answers
25 views

Getting the cumulative distribution function for Sqrt(X) from the cumulative distribution function for X

I've a data set X which consists of randomly generated numbers. My aim is to plot the cumulative distribution function for square root of X without generating data set for square root of X. I'm using ...
0
votes
1answer
3 views

Discrete algebra and exponents (See body text)

Let $a,b\in\mathbb{Z}^+$. If $a \equiv b\bmod 49$, and $\gcd(a,49) = 1$. How can I find any positive integer $n > 1$, so that $b^n\equiv a\bmod 49$? I'm completely stumped by this. I've been ...
0
votes
1answer
36 views

negation how do we negate “No cash no balance, no balance no cash” symbolically [closed]

how do we negate "No cash no balance, no balance no cash" symbolically my attempt statement: if no cash then no balance and if no balance then no cash (~p → q) ∧ (~q → ~p) negation: if ...
2
votes
4answers
47 views

Closed Form for Factorial Sum

I came across this question in some extracurricular problem sets my professor gave me: what is the closed form notation for the following sum: $$S_n = 1\cdot1!+2\cdot2!+ ...+n \cdot n!$$ I tried ...
0
votes
1answer
32 views

Decorate Tables

You have $r$ red, $g$ green and $b$ blue balloons. To decorate a single table for the banquet you need exactly three balloons. Three balloons attached to some table shouldn't have the same color. What ...
1
vote
0answers
13 views

Topology of the intersection of toric arrangement

Hope someone will help me in the solution of the following question. I'm working on some topological problem involving the topology of the intersection of some characters of the torus. I want ot find ...
1
vote
3answers
38 views

Prove the equivalence of the following 3 statements. [closed]

a) x is irrational b) 2x − 1 is irrational c) x/3 is irrational I am lost in this class I have no idea what to do.
1
vote
1answer
23 views

Proof for the number of perfect matchings in complete graph.

I'm working on a question: Let $P_n$ be the number of perfect matchings in $K_{2n}$. Prove by mathematical induction that for each integer $n\geq1$, $P_n$ is the product of odd integers from $1$ to ...
-4
votes
0answers
20 views

Equivalence Relations: Prove x E ~x [closed]

Using only the fact that congruency m is an equivalence relation on Z (integers). Prove that for all x in Z: x element of ~x (equivalence class x)
1
vote
1answer
12 views

License plate combination

California's license plate is made up for a number, followed by 3 letters, and 3 more numbers. If you cannot have the word BOB then how many license plate can be made in total? I'm guessing it's ...
1
vote
3answers
44 views

show that every rational number has one and only one multiplicative inverse

I am stumped and have no idea on how I prove this. I don't know what else to say. I am beyond lost.
5
votes
1answer
56 views

How many natural numbers less than 1,000,000,000 are multiples of 5 or 7?

I used the Inclusion-Exclusion Principle and I got $200,000,000$ (multiples of $5$ less than $10^9$, obtained by $10^9 / 5$) + $124,857,142$ ( multiples of $7$ less than $10^9$, obtained by $10^9 / 7$ ...
1
vote
1answer
43 views

How to solve this knights and knaves problem using CNF?

There are 5 natives A-E, each is either a knight or knave. Let a be the statement “A is a knight” and ¬a be “A is a knave”. Same format for the other four natives. Let T be “tautology” and F be ...
0
votes
1answer
42 views

Trouble understanding case analysis (proof by cases)

I've got a discrete math test coming up, and I've been studying religiously for the past week. Proof styles still frighten me though, I find it hard to wrap my head around them. Right now I am ...
0
votes
2answers
31 views

combinatorics: even numbers

There are given 6 numbers: 1,2,4,6,7,8. I need to find out how many 5 number combinations are there ($A_6^5$=720) and how many of those combinations are even numbers. The numbers can't recur. The book ...
0
votes
2answers
27 views

Determining if statement is even or odd.

When referencing the following page (http://geneseo.edu/~heap/courses/239/activity3.pdf) which uses the definition of... an integer $n$ is even if there exists an integer $k$ such that $n = 2k$ If ...
0
votes
0answers
11 views

Hyperplane arrangements and matroids

I'm studying some topics related to hyperplane arrangements and matroids. I've some problem in finding some practical example. Here's my question: Let $\mathbb{K}$ be a field (suppose of ...
1
vote
3answers
69 views

Discrete mathematics proof that I have been stuck on

So I have been working on these proofs for a while and finished 13 of 14 of them but I was never able to figure this one out so I thought I would ask for help on how it would be done:S Here is the ...
2
votes
1answer
36 views

Solving recurrence -varying coefficient

How can one find a closed form for the following recurrence? $$r_n=a\cdot r_{n-1}+b\cdot (n-1)\cdot r_{n-2}\tag 1$$ (where $a,b,A_0,A_1$ are constants and $r_0=A_0,r_1=A_1$) If the $(n-1)$ was not ...
0
votes
1answer
26 views

abstract machine, what language does M accecpt?

What language does M accept? 1: {a}3 ∪ {b}3 ∪ {λ} 2: {a}3 ∪ {b}3 3: {a, b}3 ∪ {λ} 4: {a, b}3 ∪ {λ} I'm not completely sure just yet which one would work. I would appreciate it if ...
1
vote
3answers
52 views

Hard Mathematical Induction [duplicate]

I have a mathematical induction question and I know what I need to do just not how to do it. The question is: Prove the equality of: $$(1 + 2 + . . . + n)^2 = 1^3 + 2^3 . . . + n^3$$ Base ...