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

2
votes
3answers
141 views

A combinatorial task I just can't solve

Suppose you have $7$ apples, $3$ banana, $5$ lemons. How many options to form $3$ equal in size baskets ($5$ fruits in each) are exist? At first I wrote: $\displaystyle \frac{15!}{7!3!5!} $ But its ...
0
votes
1answer
26 views

Graph theory 27 cube cheese and mouse problem [duplicate]

A cubic cheese consists of 27 smaller cubes of cheeses (3x3x3). A mouse will eat the first cheese cube and then eat an adjacent cheese cube (no diagonal eating allowed). Show that the mouse can't end ...
0
votes
1answer
20 views

How to find the function that is computed from a recursive algorithm? [closed]

The following is a recursive algorithm : Procedure unknown(n belongs to N) If n=0 then return 0 else return unknown (n-1)+5 The function that is computed from ...
0
votes
0answers
22 views

On discrete log calculation - safe primes need

Given a prime $r$ consider $g^z=h\bmod r$ where $z$ is unique mod $r-1$ where $r-1=2pq$ for primes $p,q$. Does this help simplify the discrete logarithm problem?
0
votes
0answers
24 views

what will be closed form of $P_vP_{2n-v-1}-P_{v-1}P_{2n-v}?$

Let $$P_0=1,$$ $$P_1=x,$$ $$P_n(x)=xP_{n-1}-P_{n-2}.$$ For some $v∈\{1,2,…,n+1\} $, what will be closed form of $$P_vP_{2n-v-1}-P_{v-1}P_{2n-v}?$$ I want a close form like ...
0
votes
3answers
34 views

What does the algorithm s = s + k * k do?

I just finished an exam in my math class and I did well except for one question that I just can't get out of my head, it seems simple but I just can't figure it out: PROBLEM: ...
0
votes
0answers
20 views

Discrete Math - RSA Encryption problem

I am doing practice problems for my upcoming final exam, and am having trouble with this RSA encryption problem. If any one could check to see if i did these correctly, it would be greatly ...
0
votes
0answers
14 views

Show there are 2 distinct paths that connect two foreign subsets of a 2-connected graph

Let $G$ be a simple 2-connected graph with at least 4 vertices. If $V(G)$ the set of vertices, let $U,W$ be subsets of $V$, with no common elements, with $|U|=|W|=2$. Show that there are 2 distinct ...
0
votes
1answer
29 views

Show there is a subgraph of G with minimum degree k

Let $G$ be a simple, connected graph with $n\ge k+1$ vertices and $m\ge (k-1)(n-k-1)+{k+1 \choose 2}$ edges. Show there is a subgraph of $G$ with minimum degree at least $k$. (Not necessarily ...
1
vote
2answers
11 views

function relations anti symmetric

I have the following relation $(x,y) \in R$ iff $x=y^2$. The book says it is anti-symmetric but it doesn't show the proof. Can you help me out by showing how to prove it?
2
votes
1answer
22 views

Need help proving this set identity

I need some help with this question for Discrete Math... It says: Let $A$, $B$ and $C$ be sets. Establish the identity: $A\cap(B-C) = B\cap(A-C)$ Now I've worded what I have, but just let me ...
-1
votes
3answers
49 views

How many numbers from 1 to 99,999 contain exactly one of each of the digits 2,3,4,5? [closed]

How many numbers from 1 to 99,999 (in their ordinary decimal representations) contain exactly one of each of the digits 2,3,4,5? I'm trying to solve this problem using rules of ...
0
votes
1answer
31 views

big theta question,not sure is book mistake or my misunderstand…

I have $\Theta$-notation question from my new book example solution... the example question is: Find $\Theta$ bound for $$f(n)={n^2\over 2} - {n\over 2}$$ and the book solution is : $\displaystyle ...
0
votes
2answers
15 views

How is this base conversion property explained?

converting $(7)_9$ to base 3 = 21, converting $(77)_9$ to base 3 = 2121 and so on. I am curious as to what exactly makes this true. I am guessing it has something to do with the relation of powers as ...
-1
votes
0answers
70 views

Find $A^n$ for n=0,1, and 3: Languages and FSM

I am having trouble trying to work out this finite state machine and languages question. Let $A=\{11,00\}$. Find $A^n$ for $n=0,1, 3$. Where would I begin?
16
votes
4answers
6k views

What is the smallest number of people in a group, so that it is guaranteed that at least three of them will have their birthday in the same month?

How should I begin solving this? I know that for months, there are 12, and 3 people from a small group suppose to have birthdays in the same month. Do I just multiply $12\times 3 = 36$ people? Or ...
1
vote
5answers
44 views

Stuck : Using inverses to solve linear congruences?

Question : What are the solutions of the linear congruence 3x ≡ 4 (mod 7)? Step 1 - We know that −2 is an inverse of 3 modulo 7. Step 2 - Multiplying both sides of the congruence by −2 shows that ...
1
vote
2answers
31 views

Problem in proof of: Show that inverse of 'a' modulo 'm' exist if 'a' and 'm' are relative primes and 'm'>1?

From K Rosen's Discrete Maths, Theorem: If a and m are relatively prime integers and m > 1, then an inverse of a modulo m exists. Furthermore, this inverse is unique modulo m. (That is, there is a ...
1
vote
3answers
207 views

How many numbers need to be selected to guarantee that at least one pair of these numbers add up to 80?

Suppose someone is randomly selecting numbers from the set: $\{2x-1 | 1\leq x \leq 40\} = \{1, 3, 5,...,75,77,79\}$ without repetition. How many numbers need to be selected to guarantee that at ...
0
votes
1answer
22 views

How many valid passwords can be formed using the following rules?

(i) Passwords must be 2 characters long, and (ii) each character must be a lower-case letter(a-z) or a digit(0-9). (iii) Each password must contain at least one letter. Letter: 26, Digits: 10 ...
2
votes
1answer
19 views

Find nondeterminstic finite state automata

Using the constructions described in the proof of Kleene’s theorem, find nondeterminstic finite state automata of: a) 01∗ b) ...
0
votes
1answer
43 views

What are the differences between empty set, zero set and null set?

What are the differences between empty set, zero set and null set? If i'm right empty set and null set is the same which is {} but zero set is {0} ?
1
vote
5answers
88 views

Showing that $n! > n^2$ for $n\geq4$ by induction

My attempt: Prove $ n! > n^2 $ for $ n \geq 4 $ Base Case: $P(4) = 24 > 16$ Inductive Hypothesis $P(k) : k! > k^2 $ $P(k+1) : (k+1)! > (k+1)^2 $ $ (k + 1)! - (k+1)^2 > 0 $ $ ...
0
votes
2answers
35 views

Are the following propositions tautologies?…

Are the following propositions tautologies?... 1.) $[\neg p \wedge (p \vee q)] \rightarrow q$ 2.) $[p \wedge (p \rightarrow q)] \rightarrow q$ I'm not sure if I have done a right truth table for ...
3
votes
1answer
55 views

Is this proof valid? The claim is $2^{k} < (k+1)!$ for $k \geq 2$

Hey guys so I think I have completed this proof but I'm not sure if its valid. Here it is: Prove that $ 2^n < (n+1)! \quad\text{for}\quad n >= 2 $ Here is my proof: Base Case P(2) = $ 4 < ...
0
votes
0answers
27 views

Let $f(n) = 3n^{2} + 7n + 12$ and $g(n) = n^{3}$. Want to understand this..

Let $f(n) = 3n^{2} + 7n + 12$ and $g(n) = n^{3}$. Which one of the following is a correct statement? A) $f(n) = O(g(n)).$ B) $f(n) = \Omega (g(n))$. C) $f(n) = \Theta (g(n))$. D) All of the ...
1
vote
2answers
25 views

Better/correct approach to solve arithmetic modulo problem

Suppose that a and b are integers, a ≡ 4 (mod 13) and b ≡ 9 (mod 13). Find the integer c with 0 ≤ c ≤ 12 such that a) c ≡ 9a (mod 13) I'm trying to solve the first part, few approaches I've tried, ...
0
votes
0answers
54 views

Yale College's Housing Draw Problem — Convex optimization techniques on a modified stable marriage problem?

I'd like to run various optimization techniques on this variation of the stable marriage problem I formulated. Ideally, I'd be able to convert the problem I constructed into one that is more ...
1
vote
2answers
28 views

Determining injective, surjective, and bijective? $\mathbb{Z} \to \mathbb{Z}$ and $\mathbb{N} \to \mathbb{N}$

I need to grasp these concepts of injective, surjective, and bijective. I have grasped the idea behind it, but when it comes to determining it with functions, I get confused and lost. For example this ...
1
vote
2answers
36 views

Minimizing the intersection of three sets

Let the sets $A,B,C$ which are all subsets of a larger set $N$. If $N(A), N(B), N(C), N$ are the populations respectively, then i need to find the minimum value of the population of their intersection ...
0
votes
1answer
12 views

For a positive integer $k$, let $B_{k}=\{\,x \in \Bbb Z \mid x \leq 2k\,\}$

I need a simple explanation on what the answer is to $B_{k}=\{\,x \in \Bbb Z \mid x \leq 2k\,\}$. Question asks: Determine $\bigcup_{k=1}^{2016} B_{k} =?$ I understand the it will go on like ...
1
vote
1answer
27 views

Expected sum value of permutaion

We have a set(A) of N elements. Let's assume elements are e1,e2,e3..etc. Value of each element can be 0 or 1. Another set of N elements(set B) are given, ...
0
votes
2answers
45 views

Maximize $\ S=Max{(\sum_{i=1}^{n-1} |f(i+1)-f(i)|)}$

Let $\ f: \{1,2,...n\} → \{1,2,...n\} \quad bijection$ What I want to know is $\ S=Max{(\sum_{i=1}^{n-1} |f(i+1)-f(i)|)}$ Furthermore, Is there a way to know 'when' does S would be maximized? I ...
1
vote
1answer
68 views

Luis Suarez goalscoring record.

Problem: The $2013-14$ season was a short-lived ray of hope in an otherwise long dark night for the world’s greatest football team. The team played $38$ league games and the main contributing ...
1
vote
1answer
42 views

Let $p$ be a prime. Then for every integer $a$ there is an integer $x$ such that $x^3 \equiv a \pmod p$

Let $p$ be a prime. Then for every integer $a$ there is an integer $x$ such that $x^3 \equiv a \pmod p$. I prove it using a Fermat little’s theorem but I want help with counterexample. We know that ...
1
vote
0answers
32 views

Under what conditions can I split a power of a binomial sum into two products?

I was reading a paper and came across a section that claimed that if $y \in \mathbb{N}$, and if $x \in [0,1]$, then for the expression: $$ \left(\frac{1}{2}+ \frac{x}{4}\right)^y $$ there exists a ...
-1
votes
0answers
22 views

if p and q are distinct primes and n=p q then there is a primitive root mod n [duplicate]

if p and q are distinct primes and n=p q then there is a primitive root mod n could you help me with counterexample I prove it and I find this statement is false , I try many example and all of them ...
1
vote
3answers
33 views

Use generating functions to determine the number of ways

Use generating functions to determine the number of different ways $12$ identical action figures can be given to $5$ children so that each child receives at most $3$ action figures So far I have come ...
1
vote
0answers
22 views

If p>2 is prime and r is primitive root mod p then r^((p-1)/2) == -1 (mod p)

If p>2 is prime and r is primitive root mod p then r^((p-1)/2) == -1 (mod p) Could you help me this statement is true or false ? I do it by fermat little theorem and I find it equal + - 1(mod p) I ...
1
vote
1answer
63 views

Mathematical induction proof problem: $\sum_{i=1}^{n-1} i(i+1) = \frac{n(n+1)(n-1)}3$

I am having difficulty proving the inductive hypothesis $(k+1)$ for the following statement: $$\sum_{i=1}^{n-1} (i(i+1)) = \frac{(n)(n+1)(n-1)}{3}$$ This is what I have so far: $$(Step \ 1) ...
-1
votes
1answer
29 views

If $a$ is odd then$(a^2)^n \equiv1$ (mod $2^{n+1}$) for all $n \geq 1$

If $a$ is odd then $(a^2)^n \equiv 1 (mod 2^{n+1})$ for all $n \geq 1$ I know it is false statement when I prove it by induction but could you help me give me counterexample show it is false I try ...
1
vote
1answer
35 views

Is the following statement true of false? Prove or provide counterexample

Is the following statement true of false? Prove or provide a counterexample $\forall m\in \mathbb{Z}\;\; \exists n \in \mathbb{Z}\;\; (2mn < m + n)$ Do I just plug in two random two random ...
0
votes
4answers
53 views

Prove or disprove the statement: “The number $1+n+n^2$ is odd for every integer $n$” [closed]

Stuck of this. Do I create statements and a truth table? Please help
0
votes
2answers
24 views

List all values $ p, q, r$ for which the statement $(p\to q) \to(q \lor r)$ is False

List all values $p$, $q$, $r$ for which the statement $(p\to q) \to(q \lor r)$ is False Confused about this. I created a truth table and don't understand the question.
0
votes
2answers
35 views

Find the sequence defined by the recurrence equation $x_{n+1} = 4x_n − x_{n−1}, (n ≥ 1)$

Find the sequence defined by the recurrence equation $x_{n+1} = 4x_n − x_{n−1}, (n ≥ 1)$ with $x_0 = 1$ and $x_1=2$. Find an odd prime factor of $x_{2015}$. I've found the characteristic equation to ...
0
votes
1answer
18 views

How to develop a formula for a function?

What are the general tips and techniques to define an explicit formula for a function when the mapping of that function is known. Say f: N to Z (N is natural numbers and Z is integers). In this ...
1
vote
3answers
43 views

Find a close form expression for $f(x)$

Here is the problem I am currently having trouble with. I have a pretty decent basis on how to do recurrence relations, but the $\frac{1}{n!}$ has got me in a rut. I tried multiplying the right side ...
-2
votes
1answer
56 views

Do the $2$ modulus $3$ can be $-1$ or just $2$?

I need to calculate $2$ modulus $3$ as $2<3$ then the answer should be $2$ but instead in a math problem they use it as $-1$. Is this possible? thanks
0
votes
2answers
47 views

Is there a graph that has 7 vertices and each vertex has a degree of $2,2,3,5,5,5,6$?

Is there a graph that has 7 vertices and each vertex has a degree of $2,2,3,5,5,5,6$? Any ideas on how to solve this one?
3
votes
4answers
41 views

Show that the $C_n \geq 4^{n-1}/2^{n}$ where $C_n$ is the Catalan number

I write $C_n=\frac{1}{n+1} {2n\choose n}$ and try to prove this claim by induction. But it didn't quite work out. Any idea how to do this without much computation?