Discrete Math Question 1 | Mathematics | Page 1

red scrollBOT Apr 7, 2023, 6:46 AM

#

Wait patiently for a helper to come along.
Once someone helps you, say thank you and close the thread with: ```diff
+close

stable girder Apr 7, 2023, 7:41 AM

#

Well, if x is the number of relations a given topic has, then 0 <= x <= n - 1, right? Which is the same cardinality as the set of courses. However, it's not possible to have both a course with 0 relations and a course with n - 1 relations at the same time. Prove that, then you have your pigeonholes.

fleet slate Apr 7, 2023, 3:27 PM

#

Sure

#

Go ahead

#

Why would they all have the same importance?

#

That's not the claim being made

#

The claim is that at least 2 have the same importance

#

Which there are

#

B and C have the same importance (1) and D and E too (0)

#

?

#

D,E 0 no?

#

Then yeah

#

Do you want help with the problem? It's not a long solution

#

Okay

#

You're most welcome

#

Well it suffices to notice that if a subject has $n-1$ importance, no subjects have 0 importance, similarly if there exists a subject with 0 importance, no subjects have $n-1$ importance. So you have $n-1$ possible values and $n$ taking on those values, so you can apply pigeonhole easily.

safe cypressBOT Apr 7, 2023, 3:41 PM

#

Pyrodynamic

fleet slate Apr 7, 2023, 3:42 PM

#

Because if a subject has $n-1$ importance it means it is related to all of the other subjects

safe cypressBOT Apr 7, 2023, 3:42 PM

#

Pyrodynamic

fleet slate Apr 7, 2023, 3:43 PM

#

Basically what @stable girder said

fleet slate Apr 7, 2023, 4:18 PM

#

Yeah of course you apply the pigeonhole

#

And yes that's what I meant

#

Yeah just post it and I'll be back in a few minutes

#

Ok

#

I'll be gone for a little while like 30-40 minutes

#

I apologize

fleet slate Apr 7, 2023, 5:55 PM

#

The number of interesting words is $\frac{6!}{3!2!} \times \frac{9!}{3!2!}$.\
To have the substring BP, the last letter of the re-ordering of BANANA must be B, and the first letter of the re-ordering of PINEAPPLE must be P. We fix these two and count the number of ways to rearrange the rest i.e. $\frac{5!}{3!2!} \times \frac{8!}{2!2!}$.\
For (c) it's the same idea as before, we treat all 3 possibilities and sum them (Starts with A and does not end with E, starts with A and ends with E, ends with E and does not start with A).

safe cypressBOT Apr 7, 2023, 5:56 PM

#

Pyrodynamic

fleet slate Apr 7, 2023, 5:56 PM

#

@uneven hatch

#

I summarized so ask if you want more explanation

safe cypressBOT Apr 7, 2023, 7:01 PM

#

banned from 100+ servers

stable girder Apr 7, 2023, 9:03 PM

#

They don't all have to have the same importance. Two of them have to have the same importance.

#

I think you should prove why you can't have a topic with importance 0 and a topic with importance n - 1 simultaneously.

#

It's incomplete.

#

...yes... the thing I just told you you're missing.

#

You only proved half of the statement.

#

Honestly, you're not as rigorous as I would like.

#

Well, I would prove the statement both ways at once by contradiction. Suppose there exists a course P such that I(P) = n - 1 and a course Q such that I(Q) = 0. Q having an importance of 0 means it's not related to any other course. P having an importance of n - 1 means it's related to every course but one. Since it can't be related to itself, it must be related to every other course. This would mean P is related to Q while Q is not related to P, which is a contradiction, since relatedness is symmetrical.

#

... what do you think I'm proving?

#

...no.

#

Look at what I proved.

#

Yes.

#

...probably not.

#

I don't know.

#

How should I know?

#Discrete Math Question 1