MATH1081 Discrete Maths (1 Viewer)

[InteGrand]

Re: Discrete Maths Sem 2 2016

Hello, I'm on a mission to understand proofs. It's going to be tricky for me but hopefully some people can help me out here.


My first question is about a proof (by contradiction) regarding log6(11) being irrational.

So the proof assumes p, q > 0 ... then fast forward and finds 11^q = 6^p, then says "which is a contradiction, as the LHS is always odd and RHS is always even".

Why is the LHS and RHS being odd/even make it a contradiction? Thanks.

Because that says an even number is equal to an odd number, which we know is impossible.

 

[kawaiipotato]

Re: Discrete Maths Sem 2 2016

Hello, I'm on a mission to understand proofs. It's going to be tricky for me but hopefully some people can help me out here.


My first question is about a proof (by contradiction) regarding log6(11) being irrational.

So the proof assumes p, q > 0 ... then fast forward and finds 11^q = 6^p, then says "which is a contradiction, as the LHS is always odd and RHS is always even".

Why is the LHS and RHS being odd/even make it a contradiction? Thanks.

 

[Flop21]

Re: Discrete Maths Sem 2 2016

Part of a proof has "2p^2 = 3q^2". It then goes on to say "Clearly, the LHS is even" I get this, since it's a multiple of 2... "and so q^2 must be even also. This implies that q is even".

Why does the LHS being even make the q^2 even too?

 

[kawaiipotato]

Re: Discrete Maths Sem 2 2016

Part of a proof has "2p^2 = 3q^2". It then goes on to say "Clearly, the LHS is even" I get this, since it's a multiple of 2... "and so q^2 must be even also. This implies that q is even".

Why does the LHS being even make the q^2 even too?

Since 3q^2 is even, then 3q^2 = 2K for some integer K.
then K = (3q^2)/2
but K is an integer, then 2 must divide q^2 (since 2 doesn't divide 3), so q^2 is even.

 

[Flop21]

Re: Discrete Maths Sem 2 2016

Where did the highlighted parts come from, I'm confused why they are there and how.

Thanks

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

Where did the highlighted parts come from, I'm confused why they are there and how.

Thanks

 

[Flop21]

Re: Discrete Maths Sem 2 2016

Thanks for your help, I did better in the class test.

Now onto the next topic,

"A set of eight Scrabble tiles can be arranged to form the word SATURDAY. How many three-letter 'words' can be formed with these tiles if no tile is to be used more than once".

No tile being used more than once = permutation right, so P(8,3) = 56.

The answers say 228, where are they getting this from?

Thanks.

 

[Flop21]

Re: Discrete Maths Sem 2 2016

Also I can recall this:

"If a choice can be made in m different ways altogether, but n of these are
not permitted for a particular problem, then the number of permissible ways
to make the choice is m − n."

which I'm guessing is what they use for the following question...

"How many 8 letter words constructed from the English alphabet have, at least two Ls"

answer is 26^8 - 25^8 - 8 * 25^7.

Can someone explain that answer in words?

Because my thought would be that m is 26^8, then n is the number of ways of one L which is 8.

 

[leehuan]

Re: Discrete Maths Sem 2 2016

Thanks for your help, I did better in the class test.

Now onto the next topic,

"A set of eight Scrabble tiles can be arranged to form the word SATURDAY. How many three-letter 'words' can be formed with these tiles if no tile is to be used more than once".

No tile being used more than once = permutation right, so P(8,3) = 56.

The answers say 228, where are they getting this from?

Thanks.

P(8,3) = 336; you put C(8,3) into your calculator. If you wanted to use C(8,3), then you'd only choose the letters themselves, and still have to arrange them later. So if your answer was correct, it should've been C(8,3) * 3!

However, the question is not that simple. The letter Y is repeated. You need to watch out for double counting in one Y being present v.s. 2 Y's being present.

I'm not exactly sure what might be the most optimal solution here. Listing out the cases helps, but I'm not sure if there's a way of killing it by just inclusion-exclusion.

 

[leehuan]

Re: Discrete Maths Sem 2 2016

Also I can recall this:

"If a choice can be made in m different ways altogether, but n of these are
not permitted for a particular problem, then the number of permissible ways
to make the choice is m − n."

which I'm guessing is what they use for the following question...

"How many 8 letter words constructed from the English alphabet have, at least two Ls"

answer is 26^8 - 25^8 - 8 * 25^7.

Can someone explain that answer in words?

Because my thought would be that m is 26^8, then n is the number of ways of one L which is 8.

You forgot to consider the possibility that the word may have zero L's as well for your n.

 

[Flop21]

Re: Discrete Maths Sem 2 2016

Thanks!

Can someone help me out with this, I would like an example so I can do the rest by myself.

A hand of 13 cards is dealt from a shuffled pack. Find the probability of: the hand has at least four cards in the same suit.



So the number of different ways you can get those 13 cards = C(52,13) right, then we need to find the number of ways of getting 4 cards in the same suit... 5, 6, 7, 8, 9, 10, 11, 12, 13. So would this be C(13,4) + C(13,5) ... etc. ?

 

[Flop21]

Re: Discrete Maths Sem 2 2016

How would I prove that this is NOT one-one (or is) ?

f : R -> Z f(x) = x (ceiling).


So I suppose f(a) = f(b) for some arb. a, b which are elements of Z.

a (ceiling) = b (ceiling)


... now what?

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

How would I prove that this is NOT one-one (or is) ?

f : R -> Z f(x) = x (ceiling).


So I suppose f(a) = f(b) for some arb. a, b which are elements of Z.

a (ceiling) = b (ceiling)


... now what?

The ceiling function ƒ is not one-to-one, because there are two distinct values in the domain that get mapped to the same value by ƒ.

For example, 1.2 ≠ 1.3, but ƒ(1.2) = ƒ(1.3) (= 2).

(Remember, saying a function is not one-to-one is equivalent to saying there exist two distinct values in its domain that get mapped to the same value by the function.)

 

[Flop21]

Re: Discrete Maths Sem 2 2016

Could someone please do this question, so I can do the rest:

I know how to do the change of sum index, but confused how i turn it into something with N.

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

Could someone please do this question, so I can do the rest:

I know how to do the change of sum index, but confused how i turn it into something with N.

Once you change the summation index, you should see a lot of terms are in common so cancel. Only some of the terms are the start and end won't cancel. The terms at the end will leave you with something involving N.

 

[Flop21]

Re: Discrete Maths Sem 2 2016

|P(A) - P(B)|, with A = {m,a,t,h} B = {1,0,8}.

Why do they in the answers go, |P(A) - P(B)| = |P(A)| - 1. Where does this 1 come from?

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

|P(A) - P(B)|, with A = {m,a,t,h} B = {1,0,8}.

Why do they in the answers go, |P(A) - P(B)| = |P(A)| - 1. Where does this 1 come from?

The empty set.

 

[Flop21]

Re: Discrete Maths Sem 2 2016

How do I find the number of subgraphs in a graph given? E.g. a simple graph with 4 vertices and 3 edges.

 

[Flop21]

Re: Discrete Maths Sem 2 2016

How do I find the number of subgraphs in a graph given? E.g. a simple graph with 4 vertices and 3 edges.

help pls is there a trick

 

[leehuan]

Re: Discrete Maths Sem 2 2016

It depends on what the graph looks like. The way you described it is quite arbitrary, because all 3 edges could just be joining two vertices. Or even, all three edges are loops on one single vertex.