MATH1081 Discrete Maths (6 Viewers)

leehuan · Sep 18, 2016

Re: Discrete Maths Sem 2 2016

RenegadeMx said:
lol i remember that q, its surprisingly hard just give to tutor

Lol fair enough
_______________________

How do I create my sets for incl./excl.?

"What is the probability that a hand of eight cards dealt from a shuffled pack (w/o jokers) contains:
b) exactly three cards in at least one of the suits

Paradoxica · Sep 18, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Not sure if this is just a really tediously long question that I should give to my tutor, or if there's shortcuts.

Q: How many eight letter words can be formed from the letters of PARRAMATTA? (10 letters)

No shortcuts, you must exhaust all the cases.

InteGrand · Sep 18, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Lol fair enough
_______________________

How do I create my sets for incl./excl.?

"What is the probability that a hand of eight cards dealt from a shuffled pack (w/o jokers) contains:
b) exactly three cards in at least one of the suits

You could try letting Sj be the set of all hands such that there are exactly three cards from suit j. We want to find |S1 U S2 U S3 U S4|.

leehuan · Sep 19, 2016

Re: Discrete Maths Sem 2 2016

Same question

c) exactly three cards in exactly one suit

I can't interpret this hint they gave:
Find the number of ways in which five cards can be chosen from three suits, with none of the three represented by three cards.

Sent from my iPhone using Tapatalk

InteGrand · Sep 19, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Same question

c) exactly three cards in exactly one suit

I can't interpret this hint they gave:
Find the number of ways in which five cards can be chosen from three suits, with none of the three represented by three cards.

Sent from my iPhone using Tapatalk

Having the eight-card hand have exactly three cards in exactly one suit (say suit 1) means we have exactly three cards from 1, and so the remaining five cards in the hand do not contain anything from suit 1. So the remaining five cards come from the other suits (2,3,4). But they must come from here in such a way that none of these suits are represented by exactly three cards in these remaining five cards (if that happened, that'd violate the condition of having exactly one suit contain exactly three cards).

So the hint is referring to this (remaining five cards chosen in such a way that they come from cards from suits 2,3,4, and so that none of these three suits are represented by exactly three cards in this set of five cards).

leehuan · Sep 20, 2016

Re: Discrete Maths Sem 2 2016

I've mind blanked

What's the difference between "negation" and "converse"

He-Mann · Sep 20, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
I've mind blanked

What's the difference between "negation" and "converse"

Negation of p -> q is ~(p -> q)

Converse of p -> q is q -> p

leehuan · Sep 21, 2016

Re: Discrete Maths Sem 2 2016

Just want some checking on my reasoning.

Q: A hand of thirteen cards is dealt from a shuffled pack. Giving reasons for your answers, determine which of the following statements are definitely true and which are possibly false.

a) The hand has at least four cards in the same suit.
- Not sure if this meant all 4 suits. Cause if that were the case then well no but if it were 1 suit I could argue true.

c) The hand has at least five cards in some suit.
- Sounds more like any suit now, so i just said

$Definitely true - since there are 4 usits to draw out 13 cards from, by the pigeonhole principle there will be $\lceil \frac{13}{4}\rceil=5$ cards from some suit.$

InteGrand · Sep 21, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Just want some checking on my reasoning.

Q: A hand of thirteen cards is dealt from a shuffled pack. Giving reasons for your answers, determine which of the following statements are definitely true and which are possibly false.

a) The hand has at least four cards in the same suit.
- Not sure if this meant all 4 suits. Cause if that were the case then well no but if it were 1 suit I could argue true.

c) The hand has at least five cards in some suit.
- Sounds more like any suit now, so i just said

$Definitely true - since there are 4 usits to draw out 13 cards from, by the pigeonhole principle there will be $\lceil \frac{13}{4}\rceil=5$ cards from some suit.$

a) It means at least one suit, i.e. the hand has a suit with at least four cards from that suit. By the pigeonhole principle, this must be the case.

c) There need not be a suit with 5+ cards from it. Note ceil(13/4) = ceil(3.25) = 4 (not 5). So there must be a suit with 4+ cards, but need not be one with 5+ (e.g. imagine if the first three suits each had four cards and the last suit had one).

leehuan · Sep 21, 2016

Re: Discrete Maths Sem 2 2016

InteGrand said:
a) I'm pretty sure it means at least one suit, i.e. the hand has a suit with at least four cards from that suit. By the pigeonhole principle, this must be the case.

c) There need not be a suit with 5+ cards from it. Note ceil(13/4) = ceil(3.25) = 4 (not 5). So there must be a suit with 4+ cards, but need not be one with 5+ (e.g. imagine if the first three suits each had four cards and the last suit had one).

Ah damn, lost track of my arithmetic. That was probably why I doubted so for a).

leehuan · Sep 24, 2016

Re: Discrete Maths Sem 2 2016

Too lost in the wording.

Prove that there were two people in Australia yesterday who met exactly the same number of other people in Australia yesterday.

InteGrand · Sep 24, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Too lost in the wording.

Prove that there were two people in Australia yesterday who met exactly the same number of other people in Australia yesterday.

$\noindent Let $S$ be the set of all people in Australia yesterday (roughly, $|S| = 20 \text{ million}$). We can define a function $f \colon S \to \mathbb{N}$ by $f(p) = n$, where $n$ is the no. of members in $S-\left\{p\right\}$ that person $p$ met yesterday. We are asked to show there exist two distinct $p,q \in S$ such that $f(p) = f(q)$. (Note that if person $p$ met person $q$, where $p\neq q$, then person $q$ also met person $p$, i.e. ``met'' is ``symmetric''.)$

leehuan · Sep 24, 2016

Re: Discrete Maths Sem 2 2016

InteGrand said:
$\noindent Let $S$ be the set of all people in Australia yesterday (roughly, $|S| = 20 \text{ million}$). We can define a function $f \colon S \to \mathbb{N}$ by $f(p) = n$, where $n$ is the no. of members in $S-\left\{p\right\}$ that person $p$ met yesterday. We are asked to show there exist two distinct $p,q \in S$ such that $f(p) = f(q)$. (Note that if person $p$ met person $q$, where $p\neq q$, then person $q$ also met person $p$, i.e. ``met'' is ``symmetric''.)$

Sorry lol, the definitions make sense but I can't do the question now

InteGrand · Sep 24, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Sorry lol, the definitions make sense but I can't do the question now

You can try investigating what happens for small values of |S| (e.g. |S| = 2 or 3 etc.) before generalising to |S| = N for arbtitrary N.

leehuan · Sep 24, 2016

Re: Discrete Maths Sem 2 2016

InteGrand said:
You can try investigating what happens for small values of |S| (e.g. |S| = 2 or 3 etc.) before generalising to |S| = N for arbtitrary N.

Oh I see. The fact that it's symmetric matters a lot here it seems.

How would I communicate it for a generalised n though? Because taking |S|=5 and a,b,c,d,e in S, I'm not sure how to describe it in a way such that (for example) the following case is included

a meets b,c,d
b also meets e.
so f(c)=f(d)
___________________________

Also, I know how to do this but is this type of question really just stars and bars (lecturer didn't actually refer to the terminology)

"For non-negative integers x_j, find the number of solutions to x₁+...+x₆=40"

InteGrand · Sep 24, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Oh I see. The fact that it's symmetric matters a lot here it seems.

How would I communicate it for a generalised n though? Because taking |S|=5 and a,b,c,d,e in S, I'm not sure how to describe it in a way such that (for example) the following case is included

a meets b,c,d
b also meets e.
so f(c)=f(d)
___________________________

Also, I know how to do this but is this type of question really just stars and bars (lecturer didn't actually refer to the terminology)

"For non-negative integers x_j, find the number of solutions to x₁+...+x₆=40"

$\noindent (For the meeting people one) Let $|S| = N$, where $N$ is a positive integer at least $2$. Note that all we need to do is show that the function $f$ described earlier can't be one-to-one (injective). Observe that the range of $f$ is actually a subset of $X = \left\{0,1,2,\ldots, N-1\right\}$, because a person can meet at most $N-1$ others and at minimum $0$ others. Suppose by way of contradiction that $f$ is injective. Since the domain of $f$ has $N$ elements (as $|S| = N$), and the range is of size at most $|X| = N$, the only way to have injectivity is for the range to be exactly $X$, so that $f$ just describes a permutation of the elements of $X$ (otherwise the range would be proper subset of $X$, so have cardinality strictly less than $N$, which implies by pigeonhole principle we'd have to have two different elements of $S$ get mapped to the same number).$

$\noindent This means there is someone who met $0$ people and also someone who met $N-1$ people. This is a contradiction (why?).$

------------------------------
And yes, last one is just stars and bars.

leehuan · Sep 24, 2016

Re: Discrete Maths Sem 2 2016

InteGrand said:
$\noindent (For the meeting people one) Let $|S| = N$, where $N$ is a positive integer (note the claim is trivial if $N = 1$). Note that all we need to do is show that the function $f$ described earlier can't be one-to-one (injective). Observe that the range of $f$ is actually a subset of $X = \left\{0,1,2,\ldots, N-1\right\}$, because a person can meet at most $N-1$ others and at minimum $0$ others. Suppose by way of contradiction that $f$ is injective. Since the domain of $f$ has $N$ elements (as $|S| = N$), and the range is of size at most $|X| = N$, the only way to have injectivity is for the range to be exactly $X$, so that $f$ just describes a permutation of the elements of $X$ (otherwise the range would be proper subset of $X$, so have cardinality strictly less than $N$, which implies by pigeonhole principle we'd have to have two different elements of $S$ get mapped to the same number).$

$\noindent This means there is someone who met $0$ people and also someone who met $N-1$ people. This is a contradiction (why?).$

------------------------------
And yes, last one is just stars and bars.

Because it makes no sense for someone to meet nobody and someone else to meet everybody. Makes sense - I saw the link with the injectivity of a function as well but couldn't puzzle everything together. Thanks again

__________________________________

Possibly dumb, and last one for now. I got a) out because it's trivially 6^4 but I don't see what I'm doing for part b). Feels also like stars and bars but I just can't see it.

How many outcomes are possible from the roll of four dice
a) if the dice are distinguishable (for example, they are of different colours)
b) if the dice are not distinguishable

InteGrand · Sep 24, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Because it makes no sense for someone to meet nobody and someone else to meet everybody. Makes sense - I saw the link with the injectivity of a function as well but couldn't puzzle everything together. Thanks again
__________________________________

Possibly dumb, and last one for now. I got a) out because it's trivially 6^4 but I don't see what I'm doing for part b). Feels also like stars and bars but I just can't see it.

How many outcomes are possible from the roll of four dice
a) if the dice are distinguishable (for example, they are of different colours)
b) if the dice are not distinguishable

$\noindent b) Yeah it's stars and bars. Recall that stars and bars is basically placing identical (indistinguishable) dots into distinct boxes. Here, the `boxes' are the possible results of a die role: $1,2,3,4,5,6$. (So there's $6$ boxes, i.e. $5$ `bars' in the stars and bars picture.) Since we're rolling $4$ indistinguishable dice, the `stars' (or dots) will represent dice, since when we're placing $4$ indistinguishable dots among the boxes, this is equivalent to selecting the results of each die roll. E.g. The following corresponds to getting two $3$'s, one $4$, and one $6$:$

| | • • | • | | • .

So the answer is just found by finding the no. of ways to arrange the picture above (i.e. five bars and four dots).

leehuan · Oct 15, 2016

Re: Discrete Maths Sem 2 2016

A course has seven elective topics, and students must complete exactly three of them in order to pass the course. Show that if 200 students passed the course, at least six of them must have completed the same electives.

Please also provide your inspiration as to your train of thought... I'm getting way too lost with how to apply PHP with these problems for some reason...

seanieg89 · Oct 15, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
A course has seven elective topics, and students must complete exactly three of them in order to pass the course. Show that if 200 students passed the course, at least six of them must have completed the same electives.

Please also provide your inspiration as to your train of thought... I'm getting way too lost with how to apply PHP with these problems for some reason...

There are 7C3=35 elective combinations possible. There are 200 students.

200/35 > 5

=> At least one elective combination must be taken by more than 5 students. (I.e at least 6 students.)

Not much inspiration to give, just identify the pigeonholes based on what you are asked to prove (in this case elective combinations), count these pigeonholes, and then divide the total number of pigeons by the number of holes to obtain a rational number r. There must then exist a hole with at least ceil(r) pigeons.

MATH1081 Discrete Maths (6 Viewers)

Well-Known Member

-insert title here-

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Vexed?

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

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