Discrete Maths Last Minute questions (1 Viewer)

Drsoccerball · Nov 4, 2016

Thanks mainly Integrand for saving me from dropping out of my degree by helping me in maths 1B but I need everyone's help just a bit longer for discrete maths.

$1) For B $ = $ { $ \varnothing,0,{1} $ } , are the following statements true or false?$

$a) \varnothing \subset $ B. Why ?$$

$b) {\varnothing} \in $ B. Why ?$$

$2) You can give a one word answer for this: Does A x B = all possible subsets of combinations of 1 element of A and 1 element of B?$

$3) Does the fundamental theorem of arithmetic also deduce that two numbers when written as a product of their primes if different then the original numbers are different? Eg: $ n_1 = p_1^{\alpha_1}p^_2{\alpha_2}...p_n^{\alpha_n} $ and $ n_2 = q_1^{\beta_1}q_2^{\beta_2}...q_n^{\beta_n} \therefore n_1 \neq n_2 $ Since $ n_1 $ and $ n_2 $ have different prime factorizations.?$

$$ 4) a,b,q and r are integers such that $ a= qb + r $ where $ a, b $ are non-zero. Prove that $ gcd(a,b) = gcd(b,r)$

Drsoccerball · Nov 4, 2016

I think LaTeX is screwing up today...

InteGrand · Nov 5, 2016

Drsoccerball said:
Thanks mainly Integrand for saving me from dropping out of my degree by helping me in maths 1B but I need everyone's help just a bit longer for discrete maths.

$1) For B $ = { \varnothing,0,{1} } $ , are the following statements true or false?$

$a) \varnothing \subset $ B. Why ?$$

$b) {\varnothing} \in $ B. Why ?$$

$2) You can give a one word answer for this: Does A x B = all possible subsets of combinations of 1 element of A and 1 element of B?$

$3) Does the fundamental theorem of arithmetic also deduce that two numbers when written as a product of their primes if different then the original numbers are different? Eg: $ n_1 = p_1^{\alpha_1}p^_2{\alpha_2}...p_n^{\alpha_n} $ and $ n_2 = q_1^{\beta_1}q_2^{\beta_2}...q_n^{\beta_n} \therefore n_1 \neq n_2 $ Since $ n_1 $ and $ n_2 $ have different prime factorizations.?$

$$ 4) a,b,q and r are integers such that $ a= qb + r $ where $ a, b $ are non-zero. Prove that $ gcd(a,b) = gcd(b,r)$

3), Yeah, prime factorisation is unique. So every positive integer has only one prime factorisation. So if n_1 and n_2 have different prime factorisations, they cannot be the same number.

Drsoccerball · Nov 5, 2016

$Prove if true or give a counter example if false:$

$$ For all sets A, B and C, $ A \times (B \cup C) = (A \times B) \cup (A \times C)$

lel LaTeX isn't working.

seanieg89 · Nov 5, 2016

Drsoccerball said:
$Prove if true or give a counter example if false:$

$$ For all sets A, B and C, $ A \times (B \cup C) = (A \times B) \cup (A \times C)$

lel LaTeX isn't working.

Claim:
A x (B u C) = (A x B) u (A x C)

If (x,y) is in the LHS then by definition x is in A and y is in either B or C.
If y is in B, then by definition (x,y) is in AxB. Similarly if y is in C then (x,y) is in AxC.
Hence LHS c RHS.

If (x,y) is in the RHS then either x is in A and y is in B, or x is in A and y is in C.
In either of these cases, x is in A and y is in BuC. Hence RHS c Ax(BuC) = LHS.

Hence LHS=RHS.

Drsoccerball · Nov 5, 2016

InteGrand · Nov 5, 2016

Drsoccerball said:
$$ If $ a \cong b $ (mod m) $ then gcd(a,m) = gcd(b,m)$

Suppose a and b are congruent mod m, then we can write a = b + km for some integer k. Now, let d1 = gcd(a,m), and let d2 = gcd(b,m). Since d2 | b and d2 | m, we have d2 | (b + km), so d2 | a. So d2 divides both a and m, so d2 ≤ d1. A similar argument shows d1 ≤ d2 (since b = a + Km, where K = -k). So d1 = d2, as required.

Drsoccerball · Nov 9, 2016

Need help for these thanks

InteGrand · Nov 9, 2016

Drsoccerball said:
Need help for these thanks

View attachment 33575

View attachment 33576

View attachment 33577

$\noindent Q3) Suppose $p > n^{\frac{1}{3}}$. Assume for the purposes of contradiction that $m$ is not prime. Then the number $m$ (which has a prime factorisation (fundamental theorem of algebra)) can be written as $m = q_{1}l$, for some integer $l >1$, where $q_{1}$ is prime. (Note if $l$ were to equal $1$, then $m$ would be prime, contradicting our assumption.) Since $l > 1$, we can write $l = q_{2}k$, where $q_{2}$ is prime and $k$ is a positive integer. Note that $q_1,q_2$ are also prime factors of $n$.$

$\noindent Since $p$ is the smallest prime factor of $n$, we have $q_{1}, q_{2} \geq p$. Therefore, we have $n = pm = pq_{1}q_{2}k \ge p^{3}k \geq p^3 > n$ (as $p> n^{\frac{1}{3}}$). So $n > n$, contradiction.$

Drsoccerball · Nov 10, 2016

Don't worry about the first question but the second is messed up

nvm got it.

Drsoccerball · Nov 11, 2016

A security agency sends messages using 12 letter code words, made up using the 26 letters of the English alphabet.

How many words contain at least one X and at least one Y and at least one Z?

I had :

$26^{12} - 3 \cdot \binom{12}{1} \cdot 25^{11} + 3\binom{12}{2} 2! \cdot 24^{10}$

Answer: $26^{12} - 3\cdot 25^{12} + 3\cdot 24^{12} -23^{12}$

InteGrand · Nov 11, 2016

Drsoccerball said:
A security agency sends messages using 12 letter code words, made up using the 26 letters of the English alphabet.

How many words contain at least one X and at least one Y and at least one Z?

I had :

$26^{12} - 3 \cdot \binom{12}{1} \cdot 25^{11} + 3\binom{12}{2} 2! \cdot 24^{10}$

Answer: $26^{12} - 3\cdot 25^{12} + 3\cdot 24^{12} -23^{12}$

What was the reasoning for your answer? You can use the inclusion/exclusion principle to get the answer.

Drsoccerball · Nov 11, 2016

InteGrand said:
What was the reasoning for your answer? You can use the inclusion/exclusion principle to get the answer.

That's what I did.

Unrestricted - (If 1 of the letters is in it) + (if pairs of the letters are in it)

Drsoccerball · Nov 11, 2016

Also I am doing past papers and circling questions I cant do Ill post them here after I finish all of em

Drsoccerball · Nov 12, 2016

$$ Question 1: Write down the general solution to $ 1039x +2013y = 4.$

$Question 2: In regards to Kuratowski's theorem I havn't been able to see which lines to delete is there an approach to take?$

$$ Question 3: Give an example of a function $ f: X \rightarrow Y $ and two subsets A, B of X such that: $ \\ \ \ \ \ \ \ \ \ f( A \cap B ) \neq f(A) \cap f(b)$

$$ Question 4: For all integers $ x $ and $ y $, prove that $ 3\mid(x^2 + y^2) $ iff $ 3\mid x $ and $ 3\mid y.$

$$ Question 5: Let f be a function from X to Y, and let A be a subset of X. Prove that if f is onto, then $ (f(A))^c \subseteq f(A^c)$

$Question 6: Let X and Y be finite sets of the same cardinality $ |X| = |Y| = n > 0 $ and let $ f: X \rightarrow Y $ be injective function from X to Y. Prove that $ |f(A)| = |A| \ \forall $ subests $ A \subseteq X $ and that f is bijective.$

leehuan · Nov 12, 2016

^Why is it that virtually all of them are from the past paper book lol

But in regards to Q2, I also have that problem.

$\text{Q3: }A=\{0\}, B=\{1\}\\ \text{and }f(0)=2, f(1)=3\text{ will suffice.}$

Drsoccerball · Nov 12, 2016

leehuan said:
^Why is it that virtually all of them are from the past paper book lol

Drsoccerball said:
Also I am doing past papers and circling questions I cant do Ill post them here after I finish all of em

But in regards to Q2, I also have that problem.

$\text{Q3: }A=\{0\}, B=\{1\}\\ \text{and }f(0)=2, f(1)=3\text{ will suffice.}$

How is this a necessary condition?

InteGrand · Nov 12, 2016

Drsoccerball said:
How is this a necessary condition?

What necessary condition? Q3 is just asking for an example.

An example would be f:R->R, f(x) = sin(x), with A = [0, 2*pi] and B = [2*pi, 4*pi].

Then f(A) = [-1,1] = f(B), but A∩B = {2*pi}. So f(A∩B) = {sin(2*pi)} = {0}, whereas f(A)∩f(B) = [-1,1].

leehuan · Nov 12, 2016

Drsoccerball said:
How is this a necessary condition?

Yeah as InteGrand said, what necessary condition?

He-Mann · Nov 12, 2016

Discrete Maths Last Minute questions (1 Viewer)

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Vexed?

Users Who Are Viewing This Thread (Users: 0, Guests: 1)