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
34 views

Calculating invariant for T shape tetrominos on rectangular board

The question is from Roland Backhouse Algorithmic Problem Solving. Suppose a rectangular board can be covered with T-tetrominoes. Show that the number of squares is a multiple of 8. The ...
2
votes
1answer
22 views

Prove Arrow's Theorem is not true when there are two candidates

I'm trying to prove the Arrow's Theorem is not true when there are two candidates, however I'm having trouble trying to prove that there is no dictator. I have suggested that in a majority rules ...
4
votes
1answer
19 views

Bipartite Graph and Matches of Graph

We know that one match from $G=(V,E)$ be a subset of edges $M \subset_= E $ in such a way non two edges of M hasn't a common vertex. Matches M is Maximal if M not a proper subset of any other matches ...
1
vote
1answer
38 views

Coconuts problem

I am trying to solve the following problem and I would appreciate any help on where I am wrong Problem Five men crash-land their airplane on a deserted island in the South Pacific. On their ...
6
votes
1answer
145 views

permutation and f(n) challenge

Suppose $f(n)$ be the number of permutation from set ${1,2,..,n}$ such that for each $ 1 \leq i \leq n$ we have: $ | \pi(i)-i| \leq 1 $. meaning of $ \pi(i)$ is an elements whose in place $i$ of ...
2
votes
1answer
34 views

Can you easily simplify large exponents without Fermat's Little Theorem?

I am asked to check if $x = 19$ is a solution to the following congruence: $$ x^{30034} ≡ 2 \pmod{18}$$ How can I do this? And in general, is there an easy/fast way to solve these types of problems ...
0
votes
0answers
33 views

Do I have to prove it by induction with respect to $n$ or to $k$?

I want to prove by induction, that the solution of the recurrence relation $T(n)=2T \left ( \frac{n}{2} \right )+n^2, n>1 \text{ and } T(1)=1$ is $n(2n-1)$. We have to suppose that $n=2^k, k \geq ...
0
votes
1answer
36 views

Finding $a_n$ if $a_0=a_1=1,a_{n+1}=n(a_n+a_{n-1})\ \ (n\ge 1).$

The problem states: Suppose $a_0,a_1,a_2,...$ is a sequence such that $$a_0=a_1=1,\ \ \ a_{n+1}=n(a_n+a_{n-1})\ \ \ (n\ge 1).$$ Guess a formula for $a_n$, valid for $n\ge 1$, and use mathematical ...
0
votes
1answer
176 views

Show that there exists a map which is invertible

Let $A_1$ and $A_2$ be sets. Let X be any set, given with maps $p_1:X\rightarrow A_1$ , $p_2:X\rightarrow A_2$ such that for any set T and any maps $f_1: T \rightarrow A_1$ , $f_2 : T\rightarrow ...
-1
votes
2answers
13 views

Closed operations on regular languages

Let x be a language over an alphabet, INSERT(x) is the set of all strings obtained by adding exactly one more character into any one of the strings in x. INSERT(x) = { azb : a,b ∈ ∑* and ab ∈ L and ...
1
vote
1answer
44 views

Need help proving a mathematical induction problem

I am having a bit of trouble proving assumption a & b, specifically b though. Could you guys walk me through the solutions for part a & b? Thanks.
2
votes
1answer
23 views

equivalence Relation problem with some conditions

If A be a set with $|A|=n$. if R be a equivalence Relation on A and $|R|=r$, why $r-n$ always be even ?
0
votes
0answers
22 views

Determine whether $f$ is a valid function if $f$ (a bit string) is defined as a sequence of $0$ or more bits.

Determine if $f$ is valid from the set of all bit strings to the set of integers if $ f(S) $ is defined as the number of $0$ bits in S. I don't understand where to start. I thought of saying that ...
0
votes
1answer
11 views

Suppose $R$ and $S$ are relations. Define $R \cap S$ as $a(R \cap S)b \iff aRb$ and $aSb$

Question asks is $R \cap S$ transitive given $R$ and $S$ are transitive. Not quite sure how to show this but I know it is definitely transitive. I have a idea but don't know where to go with it if ...
1
vote
4answers
51 views

Show that $4$ does not divide $12x+3$ for any $x$ in the integers.

I'm not exactly sure where to start on this one. Any help would be greatly appreciated. Show that $4$ does not divide $12x+3$ for any $x$ in the integers. Here's what I have so far: There exist c ...
0
votes
0answers
35 views

Solving a linear recurrence with unknown changing coefficient.

I'm stuck on how to solve this recurrence (if it can be solved?) Any help or tips would be greatly appreciated. \begin{equation} x_n=a_nx_{n-1}-x_{n-2} \end{equation} with $x_1=-1$ and $x_2=-a_2$ ...
0
votes
1answer
16 views

Determining the Cartesian product of a set

I have a question for one of my practice assignments and I'm not sure how to solve it; For the set A = {1,2,3}, let U = $A^2$ = A x A be the Universal Set. For B = {1,2}, determine $\overline{B ...
-4
votes
1answer
60 views

Is 6m(2m +10) divisible by 4? [closed]

Is $6m(2m +10)$ divisible by $4$? What is the reason for this, assuming all variables are integers?
-2
votes
1answer
50 views

How can this be proved? [closed]

How can this statement be proved? For all rational numbers $r$ and $s$, if $s$ does not equal $0$ then $\frac rs$ is rational.
-1
votes
2answers
175 views

Why is this a rational number? [closed]

Assume that m and n are both integers and that n does not equal 0. Explain why (5m +12n)/(4n) must be a rational number.
0
votes
0answers
33 views

cardinality of maximum antichains in power set posets

Let $\mathcal{P}(S)$ be the power set of a non empty set $S$. Consider the poset $\succ$ for the inclusion relation over the elements of $\mathcal{P}(S)$ (which is equivalently represented by a single ...
0
votes
1answer
16 views

How to express the number of subjects in a proposition by using predicates?

Let F(x,y) be the statement "x can fool y," where the domain consists of all people in the world. ...
0
votes
0answers
10 views

Estimate size of frequency table

I have a frequency table of the top 500 elements, e.g. category1 215,903 category2 152,393 category3 135,404 Additionally, I know the total count of all ...
2
votes
2answers
33 views

2 element subsets of n elements?

the question is as follows: Give a recursive definition for the number of $2$-element subsets of $n$ elements. We started working this out in class and here is where we got too: -if $n = 0$, then ...
2
votes
1answer
63 views

Do we have to claim it? If so, at which point?

I have to solve the recurrence relation $$T(n)=\left\{\begin{matrix} 3T\left (\frac{n}{4} \right)+n & , n>1\\ 1 &, n=1 \end{matrix}\right.$$ and prove by induction that the solution I ...
0
votes
1answer
31 views

Finding formulas for sequences, as well as boolean products.

I'm working on an assignment, and am not sure if I'm going about solving my problems the right way. Two of the problems are regarding sequences. ...
0
votes
0answers
22 views

Is there a discrete relationship shared between patterns and series or sequences?

Maybe to clarify a little, I feel that patterns are related to sequences and series, in that a series or sequence can define a pattern. However I have yet to find any reference to such being the case ...
0
votes
2answers
151 views

the strings of five decimal digitis

My question is : Consider strings of five decimal digits, such as 00147, or 99999. In each case below, what is the number of such strings satisfying the given property? (a) The string has no repeated ...
0
votes
0answers
27 views

Did I do these trig problems correctly?

1) Find the area of a sector formed by central angle theta = 2.4 in a circle of radius r = 3cm. I got 10.8cm^2 2) a) sin 217degrees = -0.6018 b) tan -114 degrees = -2.2460 c) csc 7pi/4 = ...
0
votes
1answer
10 views

Calculating interrelate results

Given these data : In a search system, when search was first performed under condition A, there were rA search results. When further narrowed down with condition ...
2
votes
0answers
42 views

Number or regions formed when $n$ points on a circle are joined

The maximum number $R_{n}$ of regions formed when $n$ points on a circle are joined in pairs is $\frac{1}{24}\left(n^{4}-6n^{3}+23n^{2}-18n+24\right)$. This is a fact that I have read in several ...
-2
votes
1answer
62 views

Find an example of a function satisfying certain condition [closed]

Find an example of a function $f: A \rightarrow B$ and two sets $C,D \subseteq A$, for which $f(C-D) \neq f(C) - f(D)$.
0
votes
1answer
51 views

How to check field axioms given addition and multiplication tables

I need help with this question, i want to know the exact method of doing it with explanation. i am not able to get around with the logic of it.
0
votes
1answer
35 views

$3\times 3$ seats need to be taken this way.

Suppose we have 9 seats named like this: Seats $b_i$ can be taken if $a_i$’s are already taken. And $c_i$’s can be taken if $b_i$’s are taken. The question is in how many ways can 9 individuals ...
0
votes
0answers
53 views

arranging people into seats in a row

Suppose there are 100 people in a line and they are to be arranged into 100 chairs in a row. Each of them has already selected one number $x_i$ from $1$ to $100$ randomly (i.e. all numbers with equal ...
2
votes
1answer
48 views

Prove that at least three students are registered for all four courses

Out of 40 incoming freshmen, 25 are registered for CS 110, 30 are registered for CS 160, 35 are registered for Math 254, and 33 are registered for Econ 101. Prove that at least three students are ...
0
votes
2answers
31 views

Which statements hold true for modular arithmetic?

I'm given a multiple choice problem with 4 statements that could be each true or false. To help determining which ones are true or false I did some example problems which I will list here. I have made ...
1
vote
1answer
57 views

Find the mistake in this proof.

I need help with finding the mistake in this proof. Statement: All natural numbers are divisible by 3. Proof: Suppose, for the sake of contradiction, the statement were false. Let X be the set of ...
0
votes
3answers
36 views

Need help with combinatorics problem

How can I find the number of solutions to the following problem: $x_1+x_2+x_3+x_4+x_5=21 $ where $x_i$, $i = 1, 2, 3, 4, 5$, is a nonnegative integer such that $0\le x_1\le 3, 1\le x_2 < 4, ...
0
votes
0answers
10 views

Discrete Analoge Methods for solving difference equations

For solving non-linear first order differential equations we can use separation of variables (sometimes) or an integrating factor to convert a DE to an exact DE. Are there any analog methods for ...
1
vote
3answers
49 views

Number of bit strings with exactly eight zeros and ten ones, where every zero is followed by one

Q: How many bit strings contain exactly eight $ 0$s and ten $1$s if every $0$ is either immediately followed by a $1$, or this $0$ is the last symbol in the string? Instructor said the answer was ...
0
votes
0answers
13 views

Integer multiplication in 5T(n/3) [duplicate]

x and y has n bits x=x0*(10^2n/3)+x1*10^n/3+x2 y=y0*(10^2n/3)+y1*10^n/3+y2 x*y=x2y2+(x2y1+x1y2)10^n/3+(x2y0+x1y1+x0y2)10^2n/3+(x1y0+x0y1)10^n+x0y0*10^4n/3 now 9 multiplication of n/3 bit numbers ...
3
votes
3answers
54 views

Finding all solutions for to the equation $x^3 = 0\ {\rm mod}\ 9$

How do I go about finding the solutions to: $$ x^3 = 0\mod 9 $$ Any help is greatly appreciated thank you
1
vote
1answer
19 views

Greatest Common Divisor of $2$ Numbers in The Integers

How do I find the numbers s and t in The Integers ${\mathbb Z}$ such that: $$21s + 8t = {\rm gcd}(21,8) $$
0
votes
0answers
15 views

How do I compute the following residue

Not really sure how to tackle this problem. Compute the following residue: 3^3 + 2 mod 5 Any hints in the right direction would be appreciated.
0
votes
1answer
30 views

Prove for all $x \in \mathbb{R}$, there is some $y \in [0,1)$ such that $x \equiv y \mod \mathbb{Z}$

So my logic is as such choose any $x$ say $99.05$. Then I can find $y \in [0,1)$ such that $99.05-y \in \mathbb{Z}$ doesn't $y$ have to be $0.05$? Congruences are a little more difficult when you let ...
0
votes
1answer
22 views

Statistics on discrete probability with error?

I need help with this question, am pretty confused on what to do with the error, I can't see how to use it.
0
votes
0answers
22 views

How to prove Ǝx(P(x) ⊕ Q(x)) and (ƎxP(x)) ⊕ (ƎxQ(x)) are not logically equivalent

Hey how would I prove using a counter example that these two following equations are not equivalent? Ǝx(P(x) ⊕ Q(x)) and (ƎxP(x)) ⊕ (ƎxQ(x)). I realize that in the first statement x is the same for ...
0
votes
3answers
45 views

Permutations (arrangement with alternating restrictions) [closed]

In how many ways can eight 6’s and six 9’s be arranged in a row so that the 9’s are always apart?
0
votes
1answer
19 views

Prove a complement of a union and intersection of two sets?

So our teacher asked us to prove that $(A\cup B) \setminus (A \cap B)$ = $(A \cap \overline{B}) \cup (\overline{A} \cap B)$ Obviously the statement makes sense when I look at it, but actually ...