discrete-math

[full grove]

i dont understand this question

[eternal thicket]

given a simple graph with 12 vertices and the degree of each vertex is 8. how to prove that it is possible to direct the edges of the graph so that the resulting graph has at least 2 * 10^9 directed eulerian cycles?

[coral parcel]

My first hope would be that it might be enough to pick an arbitrary Euler tour, direct the edges according to that, and then somehow prove we can always make 2 billion distinct variants starting from the original tour.

Actually ||that does in fact turn out to work.||

[coral parcel]

Hopefully your textbook or course material contains an explanation of what it means by "logical matrix representation". That's not a standard term -- or at least not standard enough that the question can be answered without looking up details that are not standard.
Presumably each of the 0 and 1 in the array encodes whether one of the 9 possible pairs is in the relation or not. But it's not obvious how "position in the array" corresponds to "which pair the number at that position tells you about". I can imagine at least two different principles that that would each make some sense.

[unreal plover]

Is any relation defined by some equality, like a ~ b if some function of a is equal to some function of b automatically an equivalence relation?

Because equality is always reflexive, symmetric and transitive?

[rigid oriole]

equality is generally an equivalence relation.

[humble storm]

Is there a definition for A^c is a subset of A union C, where C is a universal set

[faint sphinx]

What is A^c

[humble storm]

A complement

[rigid oriole]

[rigid oriole]

i dont understand what ur getting at

the universal set contains all elements ur working with

A u C is just C

and yes A' (and any other set under consideration) must be a subset of C

[humble storm]

So there's nothing special about that there's no definition like the definition of a proper subset

[rigid oriole]

im failing to parse what you're trying to say

[faint sphinx]

It's just that A union C is C, when it's our universal set. So yeah there's nothing really special about it since it's always true.

[rigid oriole]

The definition under consideration is that of the universal set

[humble storm]

Is the same true for intersections

[faint sphinx]

Well if you replace it with intersection, then again, since C is our universal set A intersect C is just A. So when is A complement a subset of A? Just when A is all of C (in which case A complement is empty)

[unreal plover]

Generally?

[rigid oriole]

well, equality under which set

is what you should consider

relations are defined on sets

unless uve generalised the defn somehow, etc, etc.

[latent epoch]

Hii guys , can you help me ? i have this argument "v∧p→s∧q,¬(v∧p)∴¬(s∧q)" and i think that this argument is true

You can use contra position so you get ¬(s∧q)→ ¬(v∧p) so you get ¬(s∧q)→V so this only holds if ¬(s∧q) otherwise the argument is invalid right ? , now lets think about the conclusion ¬(s∧q) , then you get ¬s v ¬q , s→¬q , so you can assume that s is true otherwise the statment is always true , so now you just need to conclude ¬q , so lets assume that "q" is false you get (s∧q) this is false therefore ¬(s∧q) is true so you get a valid argument , but if "q" was true , since "s" is also true ¬(s∧q) would be f , and you would get a false argument

This is my reasoning , is it correct ?

[rigid oriole]

answered in #proofs-and-logic there's no way u can have proven that, there's an error in the reasoning somewhere

[latent epoch]

Why it makes sense

[molten stirrup]

Hello, I'm a complete beginner at discrete mathematics but I have to dip my toes for a project

I have no clue how to describe what I want in words so I'll just use numbers

If I was to work under whatever this is, then is x^5 congruent to -x mod (x^4 + 1)?

(Ignoring the modulo 13)

[restive tartan]

I need help please, how I make this?

[tight hound]

Yes

[alpine basalt]

.

[faint sphinx]

<@&268886789983436800>

grow up.

[rigid oriole]

They only ever had 48 msgs yet reached Active

[hard stone]

Why are you reporting them for speaking the truth?

[rigid oriole]

concerning.

[urban berry]

hey is anyone able to help me with this induction proof

basically i have this expression ciel(log_2*n)

its for the famous stick cutting quesiton where u take a stick of size n and make the least amount of cuts possible to divide the stick into n peices

[thorny hollow]

Can someone help me please? The question is about "Are a) and b) logically equivalents?"

I am having trouble to covert the statements in each sentence into statement variables

Hm

Would it be alright if I convert sentece a) to "Bob and Ann have a math and a computer science major, but Ann is not both a math and a computer science major"

No, it is not

It doesnt make sense in my point of view

[regal dune]

Is this how the snaking argument would look?

And to visualise the uncountable sets part is it like

{{2.342323223,22.2939202030}, {2.34828392, 29.9190200202....}} U {{222.342323223,1.2939202030}, {59.34828392, 89.9190200202....}}

which is a set of uncountable sets which is countable since there are 2 sets?

correction of the snaking

[warm quest]

That looks good, the main mistake with snaking arguments is either looping or missing elements.

If you ever need to reference this again, I think the hood classic snaking example is mapping the integers to the rationals.

[regal dune]

got you, is this right?

It's a set of set of real numbers, the real numbers aren't countable but the sets of them are

[thorny hollow]

Would they be equivalent?

I didn't used a truth table, as it is meant to do from the exercise, I used the definitions of the use of "both" and "and"

[thorny hollow]

Help

[molten stirrup]

Thanks

And would x^9 be congruent to x mod (x^4 + 1)?

[brave rock]

Yes

[sour scarab]

(11-3/3*9-3)^69

[bronze gorge]

how would you calculate the number of possible suit distributions?

[vital dew]

Slim Reaper

[obtuse lance]

looks like you need +1/2 in there to use floor from wikipedia:

[neon jewel]

Oh alright, thanks

[vital dew]

Slim Reaper

[neon jewel]

I stopped the series at selecting 3 isolated vertices since if 3 vertices are isolated, the 4th will be isolated by default and you don't need another case for that, is there a mistake in that?

[unreal plover]

basically the Q im doing is define an equiv relation on R that partitions R into intervals of length 1

so i said x ~ y if floor(x) = floor(y)

so my question on the equality thing, is that if you are defining the requirement for x ~ y based on some f(x) = f(y), is it always automatically an equivalence relation?

i guess cause the "=" automatically makes the equivalence relation properties true

[sterile flame]

Hi there could anyone help me understand this definition? I don't get how is the sequence defined by induction but backwards (???) like $a_m=\phi(a_{m'})$ ($n'=n\cup {n}$) . Is the book wrong on this or am I just stupid?

[vital dew]

davide

[pastel coral]

This wasn't really your question, but if you want to prove that Q is countable, the way i'd like to do it is by using an x and y axis, where on the x axis you represent the numerator, and on the y axis you represent the denominator. So for each coordinate (where x and y are integers only) you can label it with a positive integer. So let's start by (0,0), you can label it as 0, (1,0) as 1, (1,1) as 2, (0,1) as 3, (-1,1) as 4 and so on, if you draw it it'll become clear, like this it's very clear a bijection exist between Q and N which implies that Q is countable.

[fallow dune]

(the only part is c for hw)

is the sufficient and necessary condition that n can only be divisible by d if floor(n | d) is an integer

or is it floor(d/n)

[fallow dune]

i believe its the second answer

[faint sphinx]

Definitionally, floor(x) is always an integer

Look at what parts (a) and (b) say. Can you use that as motivation for a necessary and sufficient condition?

[fallow dune]

damn that is true

ngl ima j leave this joint blank

my head hurts too much after working right after school

[rare river]

Hey guys

I have a question

is the word, "nor" logically equivalent to the word "and" ?

because to me nor seems like the negation of "or"

[fossil mural]

well i'm not entirely certain what the word "nor" actually means

but also i wouldn't say that "and" is the negation of "or"

it is true that "P and Q" is equivalent to "not (not P or not Q)" but that's a very specific pattern of three negations, if you negate something else you generally don't get something equivalent to "and"

[rare river]

I agree

[fossil mural]

...so uh, what does "nor" mean?

[rare river]

oxford languages:

Nor: used before the second or further of two or more alternatives (the first being introduced by a negative such as “neither” or “not”) to indicate that they are each untrue or each do not happen.

whatever the heck that means

[fossil mural]

ok so that sounds like it's basically "not (P or Q)", or equivalently "not P and not Q"

or wait

[rare river]

a Boolean operator which gives the value one if and only if all operands have a value of zero and otherwise has a value of zero.

another definition

it sounds like the opposite of and

[fossil mural]

ok i think those are defining slightly different things

but yeah both of them seem to be basically "not (P or Q)"

[rare river]

oh my goodness

discrete math sounds like the study of how to become more manipulative

[fossil mural]

although from what i understand here, something like "it is raining nor i am a wasp" would actually be grammatically incorrect, and saying "it is not raining nor am i a wasp" would be equivalent to "not (it is raining or i am a wasp)"
but the entire construction of "not P nor Q" is equivalent to "not (P or Q)" / "not P and not Q"

[fossil mural]

?

[rare river]

we have to be very precise in our use of words

one misinterpretation seems to collapse everything from my understanding

[rare river]

Yeah I think you are right here

[fossil mural]

that's... kind of just maths in general

in theory it would be everything but in most topics you have some kind of intuition and also a language that's reasonably well-suited to the topic so being precise with words doesn't matter

your brain will just fill in the details that aren't explicitly said because they're obvious

if you say "this sphere won't fit in the box because it's too big" nobody's going to think you're saying the box is too big because that's just obviously not how it works if you have any experience with space

[rare river]

yes of course

[neat meadow]

Hello is anyone able to help me with this Discrete probability? I think I did 6 correct, but im unsure of how to do 7 (homework). I included some notes from class.

[verbal lichen]

help

@shut finch

[snow sleet]

Curious to know what ur answer for 6 and 7 are. In percentages

[humble storm]

Hello, i don't know if you remember me but 3 days ago you tested me on a mini quiz on sets and you said the rest would be another time

[snow sleet]

oh shoot I completely forgot! We covered intersections, unions, and complements. Now let's do some about relations/functions and partitions

[humble storm]

Would I be ready for that

[snow sleet]

I've been swamped with some group theory hw so it slipped my mind my bad

[snow sleet]

possibly? Let's start with cartesian products.

[humble storm]

Would that be the form R cross R

[snow sleet]

Given A={a,b,c} and B={a,b,c} and C={a,b} determine |AxBxC| and then determine AxBxC. Do it in that order. That way you know if you've written all ordered triplets, when writing AxBxC.

[humble storm]

Or am I mistaking that with something else

[snow sleet]

this is right

[snow sleet]

For 6, I'm getting ||26.49%|| is that what you got? Problem 7 is quite similar using P.I.E., although counting the complement using a generating function is way easier.

[humble storm]

If I remember from a video, doing the Cartesian product makes it to an ordered pair

[snow sleet]

yes

[humble storm]

Is this first part right

[snow sleet]

yup

[humble storm]

If I cross it with set C, would it be in form of (x, y, z)

[snow sleet]

yes

[vital dew]

logician

[humble storm]

Kind of got stuck

My first term was (a, a, a)

[snow sleet]

for each of these ordered pairs here, add a on the right. Then write all of these ordered pairs down again and then write b on the right

so (a,a,a), (a,b,a), (a,c,a)...based on what you have on ur board

[humble storm]

And then you start from b so ill have (b, b, b) as one of them right

[snow sleet]

yes

[snow sleet]

you should know the cardinality of this set^

[humble storm]

Took forever

[snow sleet]

looks good

and you know you haven't missed any

because 3x3x2=18

[snow sleet]

^

A had size 3, B had size 3, C had size 2

So 3 choices for the left part of the triplet, 3 choices for the middle part of that same triplet, and 2 choices for the right part of the triplet

[humble storm]

Is this the total cardinality of A×B×C

[snow sleet]

hence 3x3x2

yes

[humble storm]

To find the cardinality of the power set it would be 2^18 power

[snow sleet]

yes the power set of AxBxC would have that size

[humble storm]

Im ready for the next exercise

[snow sleet]

Now if G={a,b,c,d}. Find all partitions of G. Challenge problem: See if you can determine how many partitions you should have before you write them all out

[humble storm]

To be honest I don't know what a partition is

[snow sleet]

A partition of a set G is a set of nonempty subsets of G such that the union of all of these subsets gives G and the subsets are pairwise disjoint (meaning no two subsets share an element)

[humble storm]

Maybe we should talk about what it means for a set to be disjoint I don't know that yet

[snow sleet]

it means their intersection is nonempty

they share no elements

for instance

[humble storm]

so A intersect B has atleast one element for example

[snow sleet]

A={a,b,c} and B={b,e,f} are not disjoint since A intersect B contains b.

[snow sleet]

yes if A intersect B has at least one element, then A and B are not disjoint

[humble storm]

Wouldn't a intersect b be the empty set in this example

[snow sleet]

A intersect B would not be empty

both sets share b

[humble storm]

You right my bad

[snow sleet]

So remember:

$A\cap B={x\ :\ x\in A,\ x\in B}$

[vital dew]

logician

[humble storm]

So if A intersects B is empty set is it disjoint

[snow sleet]

yes

[humble storm]

Could you give an example with finite sets on a partition

Like the usual 1 2 3

[snow sleet]

Let A={1,2,3}, then partitions of the set are the following 5 sets....{A}, {{1},{2},{3}}, {{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}} . Notice each set is a set of sets and none of those sets in the set are empty and no two sets within the same set share an element

{{1},{2},{3}} for instance...union all of the sets in this one. Then you get precisely A. None of the subsets are empty, and no two sets share an element

[humble storm]

Is this different from power set

[snow sleet]

yes every element of a partition must be an element of P(A). but partitions are essentially a way we can break up a set into pieces.

For instance consider the set of integers

we can break that up into evens and odds

{{even integers},{odd integers}}

none of those two sets are empty and they don't share any element. Furthermore, their union is the set of all integers

[humble storm]

Is there notation to show a partition

[snow sleet]

I can't rememember if there is, but I know it should be a set of subsets.

like {1,2,3} has a partition that looks like {{1,2},{3}}

{1,2} and {3} are subsets of {1,2,3}. {1,2} and {3} don't share any elements (so they're disjoint). {1,2} union {3} gives {1,2,3} so we're good

[humble storm]

Would this be an example of a partition

[snow sleet]

{{b},{b,c}} is not a partition since b is shared. I think you meant to write {{b},{a,c}}

everthing else looks good!

[humble storm]

Is partitions covered after unions sets intersections complements

[snow sleet]

yes definitely after unions and intersections since that's in the very definition of partitions

have you taken a discrete math course?

u should definitely take it. All of this will be covered in a class like that

this is all intro to discrete mathematics stuff

[humble storm]

In this part why is it disjoint I thought that was when intersection is empty

[humble storm]

No just curious on basics of sets

Nvm

[snow sleet]

{1,2} and {3} are disjoint sets. Because they share no elements so their intersection is empty

they don't share 1, 2, or 3, so we're good

[humble storm]

Did you mean this what you typed out

[snow sleet]

yes

looks good

a partition of a set A must satisfy 3 things: 1.) the union of all the cells (sets in the partition) must give the entire set A, 2.) None of the cells should be empty. 3.) No two cells share an element.

[humble storm]

How can I use this information to tackle a problem like this

[snow sleet]

That challenge problem requires some extensive counting experience

[humble storm]

I understand what you mean by union of the cells

[snow sleet]

but with your knowledge of partitions, you can write the partitions of G

[humble storm]

For this example one of the cells has a set with 2 elements in it, so for this other one can I have three elements in on set

Is that allowed

I tried

It should work because as You said earlier, if you take the union of each partition I get G back

[snow sleet]

everything you have so far looks good. There's more partitions

[snow sleet]

the union of all the cells in the same partition should give u all of G back

[humble storm]

But i thought order of a set doesn't matter

My guess is I can group two cells like {{b}, {a}}, {{c, d}}

[snow sleet]

order of the cells in the same partition doesn't matter

order within the cells of partitions doesn't matter either

I'm saying that if you give me a partition of G. Then for that partition, if I union all the cells in that same partition you gave me, the union of all of those cells must equal G

[snow sleet]

For 7, I'm getting ||1-[(.32)%]||

[humble storm]

The way I did it for the first picture of the partitions is I listed a, b, c, d and if I pick a i would have the cell b, c, d left over that was my strategy

Could I do, {{a, b}}, {c, d}}

[snow sleet]

yes {{a},{b,c,d}} is a valid partition. So is {{a,b},{c,d}}

You should have 15 partitions in total

u have 6 so far

on ur board

[humble storm]

One on top right is {{d, c}, {a, b}}

[snow sleet]

I see 13

[humble storm]

Might've done it wrong

[snow sleet]

don't forget you could have {{a},{b},{c,d}}

for instance

[humble storm]

Can we do one that wont take all the board. I only have limited space

Maybe do more union and intersections but include complements as well

Like A^c U B^c

[snow sleet]

I gotta go to bedddd

[humble storm]

I am feeling tired too

But at least I learned what it means for a set to be disjoint

[snow sleet]

Maybe I'll type up a pdf later tomorrow or the day after...and send it to you for you to work on. It will include terms like A intersect B, A union B, A complement, subsets, power sets, partitions, and cartesian products.

Tag me if I don't reply with a pdf by thursday.

[humble storm]

The pdf won't be rigorous math proofs right

Though, would like to learn how to prove A is a subset of B

In the future

[snow sleet]

rigorous...I mean I may ask you to prove something like show that n is odd if and only if n^i is odd for any integer i>0.

[snow sleet]

I will provide a sample proof for that for specific sets A and B

on the pdf

[humble storm]

The only "proof" I've done close to that if

m, n are odd then (mn) is also odd

[snow sleet]

gotcha gotcha

yea okay so I won't do anything too hard

[snow sleet]

this should be a walk in the park for you then^

[humble storm]

That one involves an exponent

[snow sleet]

yes

[humble storm]

Which I'm not too familiar with in context of proving something

[snow sleet]

if n=m, then you showed n^2=nm is odd when n is odd here

and taking n=n and m=n^2, you showed n^3=nm is odd

taking n=n and m=n^3, you showed n^4=nm is odd and so on

[humble storm]

If I had S={2k+1 | k is an integer} and I had to prove n^2 is odd could I start off by saying n^2 is an element of S or something

[snow sleet]

no because that's the very thing you need to show

you need to show n^2 is odd (meaning, you need to show n^2 is in S)

so no you can't start off with that without justification

[humble storm]

could I say n is an element of s

[snow sleet]

you could assume n is an element of S and then show n^2 is also (in other words, you would be assuming n is odd, to prove n^2 is odd)....

[humble storm]

Usually I see people go like

Suppose, n is an element of S and keep on going

[snow sleet]

yes that works fine

or you could say. "Suppose n is odd. Then n=2k+1 for some integer k"

Or you could say "Given an integer k, set n=2k+1."

[humble storm]

Does there exists proofs for showing odd numbers are in form of 2k+1, you could plug in any number yes, but can you show that with the more abstract idea, like that one example for the division algorithm for well ordering principle

[snow sleet]

See odd numbers are by definition of the form 2k+1

just like even numbers are by definition of the form 2j

[humble storm]

So it's sort of an axiom

[snow sleet]

definition yes

the division algorithm guarantees that any integer n yields remainder 1 or 0 after division by 2. If 2|n-1, then n is odd. If 2|n-0=n then n is even

[humble storm]

Do you think it's a good idea to learn basics of sets for a beginner wanting to learn more about these things

[snow sleet]

I have mixed feelings about that....it's great to be curious about upper division mathematics, but if you learn the material wrong, you're essentially doing more harm then good (it would be far wiser to take a discrete math class taught by a prof)...this is because it's harder to undo habits that are formed from learning something incorrectly. It's much easier to mold those learning habits correctly the first time when u take a discrete math class. In other words, old habits can be hard to undo. Definitely hard to teach someone to do something the right way when they've already learned it the wrong way and have that incorrect learning engrained in their mind.

Aight Imma head to bed but yea remind me about the pdf If I don't send one ur way by Thursday. I've written it down in my calendar so I shouldn't forget, but if I do u have my permission to ping/tag me to ask me about it.

@neat meadow ping me with ur answers for those problems....I've replied to them above^^

[regal gate]

why isnt this a counter example

like A and B know each other and have no common friends, but B has two friends and A has one friend. And the hypothesis is satisfied, because B is a common friend of C and A, who do not know each other

[faint sphinx]

Yeah that's seemingly just false for any n >= 3. Just say one person A knows all other n-1 people, and everyone else only A. Then picking A and one of the other people should be a counterexample I think. Unless we're both misreading it lol

[regal gate]

no, its wrong. The solution doesn't make any sense, see #math-discussion

[rare river]

@fossil mural I would like to say thank you for helping me with my interpretation of nor!

[safe spoke]

discrete math will be the end of me, more specifically logic
thanks for listening

[plucky wedge]

if B is only a superset of A if and only if every element of A is also a element of B doesn't the if and only if mean A must have all Elements of B and B must have all elements of A then that means when B has an element that is not an element of an A it can't be a superset right?

or am I getting something wrong

[vernal vigil]

Please can someone explain to me the handshaking lemma. I dont understand when a graph is or is not allowed to exist

[warm quest]

hi, so because the of the degree sum formula which states that there is always twice the number of edges as the degree of the vertices, there must necessarily be an even number of odd vertices because it needed to be an even number to be twice something, by definition.

So if there's an odd number of odd numbered vertices, it isn't a possible graph.

for example, for 4a) it fails the test because there are 3 odd degree vertices: 3, 3, 5

then 4c) passes as there is 4 odd degree vertices: 1, 1, 1, 1

@vernal vigil

[vernal vigil]

Im reading

[vernal vigil]

Im starting to understand, by any chance can you draw what it means when its an odd number of odd degree vertices please

But you are very helpful so far thanks

[warm quest]

I don't care to draw anything, review what vertices having degree means. It is in essence the number of edges connecting to it.

[vernal vigil]

Oh sorry

[warm quest]

If you have an odd number of edges connecting to a vertices, it is of an odd degree. If you have an odd number of those, it applies.

[vernal vigil]

So if I try to draw a graph that has an odd number of odd degree vertices that would be impossible?

@warm quest

AHHHHHHHHHHHHHH

i get it

Thank sm

[warm quest]

ye, for stuff like this make sure you remember your definitions and maybe check the wikipedia page. Helps a lot, the wikipedia articles on graph theory are unironically good

[vernal vigil]

Now I have one last questions

Question 6

Is that not a sum total of 4 for the degrees?

[warm quest]

sorry, 2 1 degree and 1 2 degree

this satisfies the lemma as 4 degrees is twice the number of edges (2)

[vernal vigil]

@warm quest

I dont understand what you are saying sorry

[unique dove]

I'm working with hasse diagrams and my book says that this poset is not a lattice and I don't get why

[rigid oriole]

agreed i have no idea

going off wiki defns at least.

[brave rock]

Yeah I can't see why it wouldn't be either, using the definition I know. Can you show us what the book says is a lattice, and perhaps if there is some explanation the book makes?

[vernal vigil]

They cant test people on Pòlya counting theory in an exam right?

[vernal vigil]

Yo are you south african?

[brave rock]

Holy shit someone noticed!!!!!!!!!

Yes @vernal vigil I was born there and although I moved at a young age, my grandma still calls me my Boytjie

[fathom olive]

isn't this no?bard saying yes

[rigid oriole]

Yeah, let a natural language model gaslight you in math...

[normal cedar]

oh u moved

now doxxing myself

[brave rock]

No this is complete nonsense. Never, ever – and I really mean never – trust a language model with math.

This is so wrong it's painful.

[brave rock]

I mean it's a big country lol

[normal cedar]

ye

[faint sphinx]

Average language model attempting math

[fathom olive]

is this right?

i have no tutor to teach me discrete so i gotta use chatgpt

[rigid oriole]

[rigid oriole]

of the gajillion resources out there, you decided to pick the worst one

#book-recommendations

literally wikipedia would serve you better

khan academy does elementary logic

[ivory badge]

Literally worse than nothing

[faint sphinx]

Negative benefit to using GPT for math. Just read a textbook or watch youtube series on discrete math, there are bound to be some decent ones

[brave rock]

I literally....... I literally just said............ did you not..........

[ivory badge]

https://tenor.com/view/catsad-gif-10975270751505630184

[unreal plover]

Pls tip for question b

[brave rock]

The statement of (B) is wrong as written.

I think perhaps the writer intended to add the assumption that supp(sigma) = supp(tau) for (B).

Also, deeply fucked up that they used \varepsilon instead of \in. For shame!

[unreal plover]

yeah

supp(sigma) = supp(tau) for B still

it doesnt seem too hard but im blanking tbh

[brave rock]

Since I don't know what in particular you're struggling with, I will simply say that you need to recall that sigma is a cycle.

[unreal plover]

so for the first part I understand that t = sigma^j(1) , u can eventually get to t by using sigma enough times, no matter where u start with

because ya its a cycle

im not really sure how if you have tau(1) = sigma^n(1), then applying sigma j more times gives you tau(t)

i feel like its just something obvious here that im not seeing

If someone helps out pls @ me

[unreal plover]

We’re trying to just show that tau = sigma^n, right?

[unreal plover]

Is that even true though

Isnt it not possible for (1,2,3,4) = (1,2,4,3)^n for any n?

Also, does anyone else get completely obsessive when theyre confused in math

[coral parcel]

Surely it is true at least for n=1?

[unreal plover]

(1,2,3,4) = (1,2,4,3)?

3 gets sent to 4 in the left but 3 gets sent to 1 in the right

[coral parcel]

Ah, I missed that.

[unreal plover]

Oh ok

[coral parcel]

Then I agree.

[unreal plover]

Ok cool

[unreal plover]

Any thoughts on B

Im stuck there

I thought for B we were eventually trying to show tau = sigma^n for some n, but i guess not cuz it turns out it isnt even true

Just cuz tau and sigma have same support doesnt mean tau = sigma^n

[coral parcel]

(1 2 3 4) and (1 2 4 3) are not a counterexample, because they are not commuting cycles.

[unreal plover]

Wait so in B we are assuming they commute ?

Then it becomes easy

I thought we were deriving conditions for them to commute so cant we not assume it commutes

We first showed supp(tau) = supp(sigma) is necessary but not sufficient

If sigma tau commutes then … sigma j (tau(1)) = sigma j n (1)

tau(sigma j n) = tau(t) = blah blah

Its just like an algebra thing

[coral parcel]

I agree the formulation is a bit unclear if you don't already know the answer, but I think what they are aiming for is "two cycles commute if and only if their supports are disjoint or one is a power of the other".

[unreal plover]

Yeah

So assuming they commute, we can get (kinda easily) that tau = sigma^n

Then later we prob gonna show that if tau = sigma^n, then they commute?

Later it says something about n and the order of sigma being coprime

[coral parcel]

Well, but that is easy enough that it might not be a separate exercise.
If tau = sigma^n, then tau·sigma = sigma^(n+1) = sigma·tau,

[unreal plover]

Ok

I guess ill try part C then now

Not sure if im 100% clear of the structure of all this yet but thx for the help ill try part C

[frozen tendon]

We can't ask questions related to discrete math here right?

[coral parcel]

What do you mean? This is the #discrete-math channel.

[unreal plover]

Tropo is this discrete math or abstract algebra

[frozen tendon]

Ik but can we asks questions here or can we only ask questions in the math help category?

[unreal plover]

Bruh obv u can ask questions here

Did u not just see what i was doing lmao

[frozen tendon]

I did but I wasn't sure if that was allowed or not

[unreal plover]

Fair

[frozen tendon]

how would i go about doing this?
Im fairly certain i need to use this formula https://cdn.discordapp.com/attachments/1018703193473024061/1159175256674668636/image.png?ex=651eed95&is=651d9c15&hm=bcfe31a7a553514b32defd9513531831a0c8c4723920c675d8332ac228c61d20&

[coral parcel]

It's more specifically #groups-rings-fields, but permutations figure often enough in "discrete math" courses that it would be a lost battle to try to forbid them here.

[coral parcel]

The formula you're quoting is more relevant when the same choice can appear multiple times. But here you're just being asked how many 11-element subsets of the original 19-element set there are.

[unreal plover]

Yeah im in an abstract algebra class rn thats what its from

But i figured it feels like discrete math too

[frozen tendon]

Oh tysm

[sage pelican]

im a bit dumb and not sure how to start this question

[plain hatch]

Do you understand the notation

If so think about if it’s true

If not I would think of truth assignments which make it false

Otherwise you have to use your “equivalence transformations”

[sage pelican]

i think i get it, i just dont know how to start writing it out

[coral parcel]

That's not a counterexample: setting p=true means that the assumption ¬p is not satisfied.

(More concretely, you've evaluates F and T to T, but it is F).

[sage pelican]

ah, i watched a youtube vid that said the way to find valid / invalid to set all to true

i think i left the counterexample in there from last time i did the problem

[plain hatch]

When trying to form a counter example for an implies statement consider the case where it’s vacuously true

[sage pelican]

okok, so if i say, when p= T and q = F, it is valid, therfor the original argument is invalid

[coral parcel]

Then neither of the original assumptions are satisfied ...

[weary tiger]

Is 1 not the correct value for X1 in this scenario?

[sage pelican]

ight, i think i get it

[rigid oriole]

,calc (65 + 937 - 1) / 67

[vital dew]

Result:

14.940298507463

[granite forge]

How would go on about solving this?

I can't come up with the perms and combs stuff straight away so I do it a bit differently
we know they must be distinct.
so the possibilites are
AABBB
AAABB
ABBBB
AAAAB
in the sense that it could have 2 same digits and 3 same digits.
or 3 same digits and 2 same digits and so on.
now lets say A is the one with 10 possibilites (0-9), this means B has only 9 posibilities
So we can calculate the number of ways we can arrange A (10 possibilties) in the different number of A:B ratios above.
for example
AABBB
How maany ways can we arrange A in here?
that is 5C2 (without repetition as we only have 2 As) = 10
now we do the same for AAABB
How many ways can we arrange A in here
that is also 5C2 = 10
and so on (5C1, and 5C4 for the rest) which both give 5
now we need to look at the possibility of numbers for each

for example AABBB
A has 10 possibilites
but that means the next A can only be 1.
and B has 9 possibilites. but the next one can only be 1.
so that 10x1x9x1x1

[haughty garden]

Pick two of the digits to be in your string: C(10, 2). Each slot in your five digit string has two choices, so you can make 2^5 many strings. However, exactly two of them will contain one digit. So you obtain C(10, 2) * (2^5 - 2) = 1350

(If we do not allow a string to start with a 0, then you can count all strings without a zero first and then count all strings with a zero separately)

[plucky wedge]

for A to be a subset of B, A and B must have the exact same values?

and when it doesn't it's a proper subset

want to make sure im understanding this right

so when A has all values of B but B has extra values we can't call A a subset but instead a proper subset, and we can't call B a superset but instead a proper superset??

thats what im understanding from this definition

because the definition says if and only if every element of A is also in B and if and only if would have to imply that every element B would also have to be in A but if it's not then that means it's not a superset?

so what im getting is that for any two sets to be a subset of each other they must be equal and that would also make them a superset and subset of each other

[fossil mural]

because the definition says if and only if every element of A is also in B and if and only if would have to imply that every element B would also have to be in A
no

it's not saying "a thing is in A if and only if it's in B", it's saying "A is a subset of B if and only if [...]"

so, "A is a subset of B" means the same thing as "every element of A is an element of B"

if A is {1, 2} and B is {1, 2, 3}, then every element of A is an element of B, therefore A is a subset of B

and also, if A is a subset of B, then every element of A is an element of B

[plucky wedge]

its not saying A is a subset of B if every element of A is in B and every element of B is in A?

[fossil mural]

it doesn't say anything about "every element of B is in A"

[plucky wedge]

p <-> q, (p -> q) and (q -> p) though

[fossil mural]

A is a subset of B if and only if every element of A is in B

if A is a subset of B, then every element of A is in B
if every element of A is in B, then A is a subset of B

[plucky wedge]

oh ok I think I see

ok yeah that makes sense

but A being a subset of B still means that A and B must be the same right

I think thats what this says
https://math.stackexchange.com/questions/218529/are-two-identical-sets-each-others-subsets-supersets#:~:text=Actually%2C two sets A and,subset and superset of B.&text=As others have pointed out,b and b⊂a.

[fossil mural]

...no it doesn't

like i said earlier, {1, 2} is a subset of {1, 2, 3}, and those aren't the same set

[plucky wedge]

isnt that a proper subset instead of a subset though

[fossil mural]

it is a proper subset, and it's also a subset

if A is a proper subset of B then A is a subset of B

[plucky wedge]

oh ok

[fossil mural]

although it is true that every set is a subset of itself

so if A and B are the same then A is a subset of B

(since clearly everything in A is in A)

[plucky wedge]

ok thanks

[radiant garden]

how would i prove that k^2/ p = 1 and that (1 + k^-1 / p) = (1+k)/p? cuz in my proof i think i just assume it, but now that im thinking about it, idk how to prove either lol.

[radiant garden]

<@&286206848099549185>

[opal needle]

#❓how-to-get-help

Refer to that please.

[vital dew]

yohan_wittgenstein

[unreal plover]

for sigma a permutation, doesnt sigma^n always commute with sigma

[coral parcel]

Yes, that's the point.

[unreal plover]

wait, look at this

i think my prof is just confusing tbh

C

“If n and order of sigma are coprime, then sigma^n commutes with sigma …”

Ok well sigma^n ALWAYS commutes with sigma so why r we caring about n and order(sigma) being coprime and all that

i am pretty confused with the logical flow of this question

[unreal plover]

@coral parcel any idea lol

[coral parcel]

sigma^n automatically commutes with sigma, but sigma^n is not automatically a cycle.

[unreal plover]

Ohhh interesting

So the point in C is that show that sigma^n is a CYCLE

[coral parcel]

E.g., (1 2 3 4)^2 is not "a cycle commuting with (1 2 3 4)".

[unreal plover]

So in B, we assume sig and tau commutes and that their supports are exactly the same. We then show that tau = sigma^n

Is that true?

[coral parcel]

Yes, there I think you need to show that they're cycles.

[charred dawn]

hi

[unreal plover]

In B?

[coral parcel]

Yes.

[unreal plover]

Why

[coral parcel]

It's not generally true that permutations that commute and have the same support are powers of each other. Consider (1 2)(3 4) vs (1 3)(2 4).

[unreal plover]

We already assume sigma and tau are cycles

We assume sigma and tau are cycles, they commute, and have same support. Then we show in B that tau = sigma^n

True?

Yea the question in general isnt talking about commuting perms, its just focusing on commuting cycles

Then in C, we show that n and ord(sigma) are coprime.

Then, we show that if n and ord(sigma) are coprime, sigma^n is a cycle (that obv commutes with sigma) i think this is showing the “sufficient” condition for cycles with same support to commute

[vernal vigil]

Whats the difference between Euler Path and Euler Trail?

Cause in my textbook it gives us the Euler Trail Theorem and then asks if a graph has a Euler Path

@warm quest

[warm quest]

i dont want to be tagged randomly w/ your questions

literally the first line of the wikipedia page

In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices).```

[weary tiger]

What is the cardinality of (0,1)? Like, I know if it was a set {0,1} it would =2, but how does it work here?

[meager prawn]

presumably, its cardinal would simply be its own. But you can prove it's in bijection with R so by definition of cardinal equality, it's of the same cardinal as R

that's how all the cardinal equalities written here work

[vestal bronze]

it's stars and bars
******|||||
we permute these 11 characters, and get all ways to add up to 6

the 7 just tells us there's enough branches, which we would assume anyway

if there wasn't enough, then this wouldn't work

[vital dew]

yohan_wittgenstein

[vestal bronze]

that's correct

[weary tiger]

Is f(x) = x + 1 surjective/onto for domain and co-domain = Z?

Z being all integers {...,-3,-2,-1,0,1,2,3..}

[haughty garden]

Yes

[flint hawk]

what should i anticipate for my course in discrete math?

[coral parcel]

Argh! I now see I mistyped -- I firmly intended to type "... there I think you need to assume they're cycles".

[unreal plover]

ahhh, yea makes more sense

was my shpeal there good?

[coral parcel]

I have nothing left to criticize, I think.

[unreal plover]

thanks a lot for the help bro

[odd pelican]

quick question: can i just say that for b, "for all comedians they are funny" and for d "there exists a comedian and they are funny"
or would i have to write "for all people, they are comedians and they are funny"?

[haughty garden]

For all people is a funny way to say everyone, but the second statement is more accurate to the FO formula

[shadow lion]

what do i do here?

[sage pelican]

for this, can i treat -> as seperate so i can do resolution law for p's and q's

[weary tiger]

A X B n C = {(a,b) | a ∈ A & b ∈ B n C}
(a,b) ∈ (A X B n C)
(a,b) ∈ A
(a,b) ∈ (B n C)
Is that last line correct? Or is it only
b ∈ (B n C)

[fallow dune]

any1 know what this is?

38

[unreal plover]

getting stuck on if sigma is a cycle and sigma^n is a cycle then n and length of support(sigma) are coprime

Im seeing some modular arithmetic stuff im so close

[compact bay]

can someone save my soul?

[cold finch]

I am not sure what the problem is asking

[snow sleet]

@humble storm Here's that quiz I typed up for you.

I have some questions there and some proof problems on there. Since I'm more of a proof person and since proofs are a large majority of a discrete math class, I've put more proofs on there than I originally intended. Exposure to proof problems will be helpful. Do your best on this quiz. Take you time with it, there's no deadline lol. Just ping me when you're finished with it and have ur answers to as many problems as you can. Try to attempt all the problems

[untold falcon]

hmm why in your for loop it is "a++" instead of "i++"

is that intentional?

[whole plover]

Heyo, y'all got any good book recommendations for discrete maths, for a beginner?
I'm sutdying computer science and minoring in math, and am quite interested ^-^

[untold falcon]

heard good things of this textbook https://courses.csail.mit.edu/6.042/spring18/mcs.pdf

[brave rock]

https://dontasktoask.com/

[granite tangle]

do you have to design the DFA in a programming language ?

[frozen tendon]

how would i go about solving this?

[vestal bronze]

you draw a venn diagram and fill it from inside out

except 4 sets are hard to draw

i guess that's not a good idea

[frozen tendon]

thers another way to solve it but idk how to do it

[vestal bronze]

i don;t get what they mean tbh

it seems like the very bottom needs to have negative 4

so we're like forced to draw it like this

[frozen tendon]

i see

but why dont u subtract 4 from 29?

[vestal bronze]

it doesn;t make sense

[frozen tendon]

to do that or the question?

[vestal bronze]

the question

[frozen tendon]

i see

its fine ill try to solve it myself, tysm for trying

[humble storm]

Thanks. I was asleep when you pinged me but I got school today but I will try these problems

[spring hound]

That's not correct for b, but for d, it would be clearer to state it as "there's at least one funny comedian".

[humble storm]

This the first exercise

[snow sleet]

Remember the first problem is asking u to prove n^i for any positive integer i. Not just for some i and not just for n^2

I’ve given you the lemma above it as well use the lemma since you prolly don’t know modular arithmetic yet

[humble storm]

Could you tell me what I did right if anything

@snow sleet

[compact bay]

i didnt notice that, thanks

it should be i++ indeed

but do you know if the solution makes any sense?

[untold falcon]

I didn't check the answer but in general u can prove ur answer by induction (considering it as a recursion problem and induct on recursion times)

[weary tiger]

How can I prove/disprove: for any k = positive int, log2(2k + 1) is irrational

[tight hound]

Assume it is rational and work towards a contradiction

[weary tiger]

log2(2k + 1) = a/b
2^ (a/b) = 2k + 1
2^a = (2k+1) ^b
uhh... am I headed in the right direction?

[tight hound]

Yes

[vernal vigil]

nice

How in the fuck am I supposed to do question 2???

[weary tiger]

2 = (2k+1)^(b/a)
Can I say if b = a, then
2 = 2k+1
2k = 1
k = 1/2
?

Which is rational?

[vernal vigil]

Heres the memo. Makes 0 sense to me

[snow sleet]

You showed that if n is odd, then n^2 is odd. Repeated application of that statement u proved is that if n is odd, n^{2^i} is odd for any integer i>0. However, this doesn’t account for things like n^3 since 3 is not a power of 2.

[humble storm]

It looks like a 2 but it's n^i

[snow sleet]

Oh well then the line after (2k+1)^i makes no sense.

[humble storm]

I just expanded the term

[snow sleet]

How do u know this is true for all integers i>0

?

The first equality holds, but the second one doesn’t necessarily hold

[humble storm]

So the expanded term doesn't make sense is what you're saying

I thought of it like expanding (a+b) ^2 =a^2 +2ab+b^2

[snow sleet]

Yes it’s true for i=2 but not necessarily for all positive integers i

[steel verge]

What is going on?

n^i if n is odd is odd as only odd numbers are being multiplied and hence no multiple of 2

[snow sleet]

We’re looking at his proof.

[humble storm]

Am i heading towards the right direction atleast

[snow sleet]

I would say not really because u can invoke the lemma I proved, but right now ur not using it and kind of tying ur hands behind ur back. Use the lemma to attack the problem!

[humble storm]

Could you give me a hint

[snow sleet]

The great thing about the lemma is that u don’t even have to prove if n is odd, then n^2 is odd

[snow sleet]

Yes use the lemma recursively…in other words repeated application of the lemma will give u the result

U know n is odd and n^2 is odd so their product n^3 is odd. U know n and n^3 is odd, so their product n^4 is odd, etc.

[humble storm]

In the beginning it says n is an integer, and says n is odd so I immediately thought n=2k+1, k is an integer

[steel verge]

You expand using the binomial theorem not like this

[snow sleet]

This is right.

[snow sleet]

We haven’t gotten to the binomial theorem yet, so we’re gonna not assume it

[humble storm]

So then it wants you to show n^i is odd so I subsituted 2k+1 in its place

[snow sleet]

But u don’t know what (2k+1)^i looks like yet

There’s nothing wrong with that substitution

[humble storm]

No, but since you said i is an integer i just pretended like it's a number

Unless you mean the ith term

[snow sleet]

No I mean i is a positive integer but u expanded it like it was 2! It could be 1500 we don’t know

[humble storm]

I get what you mean now

The only idea I have is it's 2k+1 multiplying infinite times or something

[humble storm]

I don't really use the binomial theorem but I did memorize the coefficients of Pascal triangle

[humble storm]

I did exercise 7 as well, can you check if it's right

[woven zealot]

Im not sure about cardinality when it comes to the third and fourth problems. I'm assuming {3,4} shouldn't be counted as its not an element in the integer power set?

[granite forge]

I don't understand this sorry.

I get the first part. picking 2 digits to be in our string. Then idk what you did

[vital dew]

Syl

[granite forge]

Is there something wrong with your C(10, 2) ?

Shouldn't the order matter?

because remember, if we chose 2, 3. XXYYY
is different to 3,2. XXXYYY

[snow sleet]

S union T and S x T both look good! S intersect T however, is not empty. S and T are not disjoint since they share an element, namely, s_2.

[humble storm]

If I had A={1,2,3} and B={4, 5,6} then they would be disjoint since they share no element right

[snow sleet]

yes

[spring hound]

What's the correct result for n = 4?

Check that against the result of your formula.

[snow sleet]

@granite forge , do you happen to know the answer to your problem? I'm getting 1095

[snow sleet]

yes there is something wrong with this because if we choose 0 and 1 for instance, we will not count 01111 or 00111 or 00011, etc. as a five digit number. 01111 would be counted as a four digit number.

I broke mine up into cases where 0 is in the set and where 0 is not in the string

[granite forge]

I don't have the answer sorry @snow sleet

but I can share my working and maybe you can spot a flaw?

we have similar working

[humble storm]

Figuring out a proof is hard to be honest

[snow sleet]

that's fine because I'm pretty sure mine is correct. I've done many counting problems before and assuming we cannot have 0 as the first digit, I know my answer is correct

[granite forge]

we can have 0

it's a string

what do you get if we can have 0

'00001' is still a string.

[snow sleet]

but it's not a five digit number

if we can have 0 as the first digit, then (10 choose 2)(2^5-2) is correct

If not, then 1095 is the answer

it all depends on whether or not we would allow 0 to be the left most digit. Since it says decimal digits, I can understand allowing 0. If we would say, a five digit number, then 0 can't be the leftmost digit

[snow sleet]

10P2 can't be right since it counts picking 1,2 as different from picking 2,1 when in fact those are the same to numbers we're constructing the binary string with.

[granite forge]

once again lol, it's a string

[snow sleet]

If we allow 0 to be the leftmost digit, then there are (10 choose 2) ways to select two distinct numbers from {0,1,2,...,9} with which we will contstruct our binary string. And for each of those pairs, there are (2^5-2) such strings. Thus (10 choose 2)*30 is the answer

[granite forge]

= 2700?

[granite forge]

oh idk abuot the p thing sorry.

I just wrote P because I thought order matters

[granite forge]

yes those are different tho, no?

actually hmm.

I see what you mean.

[snow sleet]

I've seen problems where some math profs would count a 5 digit number to mean 0 can't be in the left most digit. Again, it's open to interpretation, but what's more important is that you can count the number for each of those two interpretations rather than for just one.

[granite forge]

that's a number. the question says 'string'. but I know where you are getting at. understood 👍

[snow sleet]

nope not different

[snow sleet]

1350= (10 choose 2)(30)

[granite forge]

hm give me a second to process this

[snow sleet]

Once you complete this problem, challenge urself to count the 5 digit strings where 0 can't be the leftmost digit.

[granite forge]

that shouldn't be that hard I think

unless u mean with the same '2 distinct'

okay so

tell me if order matters here when picking 2

and if so, why?

[snow sleet]

yes with the same conditions of exactly two distinct numbers in the sequence

[granite forge]

im not saying your wrong btw. I'm trying to understand why i'm wrong.

cause im wrong most of the times when it comes to perms and comb

[snow sleet]

For this, there are 4 choose 2 ways we will select the two denominations. For each pair of denominations A,B we can have 3 ofA and 2 of B or vice versa. So the answer should be (4 choose 2)(2)(13 choose 3)(13 choose 2). By denomination, I'm assuming they mean suits.

[granite forge]

demonimation is Ace,2,3,4..

[snow sleet]

oh so denomination isn't spades for instance?

[granite forge]

yeah it's not.

it's the different 13 cards.

[snow sleet]

okay lol lemme rethink this then I answered a different question ahahaha

[granite forge]

okay.

the start is the same correct?

we want to pick 2 cards.

[snow sleet]

so ur saying 3 cards of one denomination means for instance the spades 1, diamonds 1, clubs 1?

[granite forge]

no

il give an example

we have 3 cards that are 1, 1, 1

oh

just read waht you said

yes. sorry.

so that's correct. spades 1, diamonds 1, clubs 1

and maybe spades 2, diamonds 2, hearts 2

[snow sleet]

not quite now

Right got it

so then here's my answer:

[granite forge]

in the sense that we have to pick 2 denominations

okay...

[snow sleet]

There are 13 choose 2 ways to choose the 2 denominations. There are 4 choose 3 ways to select 3 of the same denomination from the 4 suits. And there are 4 choose 2 ways to select the other denomination from the 4 suits. Again, if the denominations are 1,2, we could have 3 ones and 2 two's or vice versa. So we multiply our answer by 2. Our answer is then (13 choose 2)(4 choose 3)(4 choose 2)(2)

[granite forge]

So P(13,2)(4 choose 2)(4 choose 3)(4 choose 2)(2)

is that what you got

[snow sleet]

replace that P with a C or delete the 2 at the end. Do one or the other

[granite forge]

OH

P(13,2)(4 choose 2)(4 choose 3)(4 choose 2)

so this?

I can tell you that's correct.

[snow sleet]

yes. P(13,2)=C(13,2)*2 so yes

[granite forge]

and I am super confused.

wait

so shouldn't we be doing x 2 in our problem

[snow sleet]

look at this^

[granite forge]

yeah saw.

[snow sleet]

I wrote (13 choose 2) and had an extra factor of 2 so we're good

[granite forge]

I mean our original problem.

shouln't we be doing x 2

[snow sleet]

which problem lol

the 5 digit one

[granite forge]

yes

[snow sleet]

no

[granite forge]

i was tryna understand

[snow sleet]

because

[granite forge]

why order matters

and why it doesn't

im still as confused as before

if we are choosing 2 digits. why doesn't order matter.

[snow sleet]

because for that 5 digit one I'm choosing the two distinct numbers and then applying an ordering to them via the 2^5-2 bit. So I don't need to have them chosen with order (i.e., I don't need to count x,y as different from the pair y,x)

[granite forge]

UGHHH

😭

this topic is so confusing

then why does order matter in the cards

feel like crying

I get why order doesn't matter in the digit problem now.

[snow sleet]

only because 3 of one denomination (say 1's) and 2 of another (say, 2's) is different from having three 2's and two 1's

[granite forge]

but in this case can't it be like

2-3

3-2

1-4

4-1

[granite forge]

it's because we just want to pick which 2 cards are gonna be in our digit.
so if i first picked 2, then 5. or first 5 then 2. it shouldn't matter.

BUT
can't we say the same thing about the card problem?

[snow sleet]

yes this is why I multiplied (13 choose 2) by 2

[granite forge]

so what's your final ans

2700?

or

2700/2

[snow sleet]

for the second problem?

about cards

?

[granite forge]

digit problem

[snow sleet]

which problem lol u switching back and forth it's confusing

okay

[granite forge]

Digit Problem

[snow sleet]

uh no I said if we allow 0 to be a leftmost digit (10 choose 2)(2^5-2) is the answer, which is 1350

[granite forge]

so 2700/2. OUF

brain hurt.

okay I get why its 1350.

[snow sleet]

yes

[granite forge]

just don't understand why we can't apply the same logic to our cards now.

2 diff denominations

[snow sleet]

cards are a different problem. Most counting problem u can't just apply the exact same logic. Different problems tend to be unique in their own way

[granite forge]

pick any 2 cards

yeah

but that's the thing

idk when to apply what logic

[snow sleet]

look back at how I solved that card problem

[granite forge]

I saw

[snow sleet]

I choose the 2 cards

[granite forge]

yes.

[snow sleet]

then I determined if I needed to multiply my answer by 2

[granite forge]

and then u multiplied by 2 at the end

because u can have 2-3 then 3-2

[snow sleet]

yes

[granite forge]

understood.

but still confusing

[snow sleet]

about?

[granite forge]

i pick 2 cards.

[snow sleet]

right

[granite forge]

order doesn't matter

[snow sleet]

right

[granite forge]

one sec.

let me think of next step.

[snow sleet]

I highly recommend you choose two things and then determine if you need order

[granite forge]

choose 2 things?

wdym

okay I chose 2 denominations.
ace and king

we will have 3 aces and 2 kings

or 3 kings or 2 aces

okay.

5 digit problem:

pick 2 digits: 0 and 9

[snow sleet]

yes

[snow sleet]

right

for the digit problem it's different because we applied ordering by doing 2^5-2

[granite forge]

i can have one 0, four 9.
two 0, three 9
four 0, one 9.

[snow sleet]

2^5 counts all possible binary strings of length 5 with 0,9

[granite forge]

yes

[snow sleet]

so we don't need to choose the digits 0,9 with order

since we're ordering them later

[granite forge]

okay hm.

I see.

I think its confusing me cause we used 2 diff eq

for picking the cards and picking the digits.

digits was repeition allowed and order matters. n^k

cards was idek what that was

[snow sleet]

it's just something you have to get used to tbh

different problems almost always require different approaches

[granite forge]

can u epxlkain this part for teh card problem pls

[snow sleet]

yes I'm choosing 3 (1's for instance) from the four possible 1's in the card deck. Doing similar for the other denomination but only choosing 2

[granite forge]

okay I thought about it.

makes sense.

in the digit problem we look at order afterwards.

in the card problem we look at order first

Thanks mate @snow sleet appreciate it heaps.

[snow sleet]

I actually looked at it afterwards right? I choose 2 of the 13 denominations first then asked whether or not I need to multiply by 2 or not

[granite forge]

Oh yeah you did it like that.

[snow sleet]

Always choose without order first then decide whether or not you need to multiply by anything else

[granite forge]

so you are saying do it without order first?

and then see if we have to multiply? by anything.

[snow sleet]

yes

[granite forge]

okay il try implement that.

ty heaps

[spring hound]

XOR just means an odd number of propositions are true.

You have two things there, and they can both be true, meaning that an even number of them would make the whole thing true, so it's not XOR.

Well, if Cole loses, both could be true.

It says if Cole wins his first game, then .... That means that if Cole loses, that if-then statement would also be true.

If-then is either the first part being false or the second part being true.

Yes, that looks good.

Though you might want a W function for winning.

Like (W(S) ^ ~W(C)) v (W(C) -> ~W(J)).

Either one is fine, though.

No problem.

Hmm, wait.

I didn't notice the either.

That generally is XOR.

So, it would be (S ^ ~C) XOR (C -> ~J).

[snow sleet]

I'm gonna dm u my answers to the proof part of the pdf.

[humble storm]

Just for that one exercise?

[snow sleet]

no no for all of the first page

i just sent you a pdf

you can continue to attempt the problems and look back at the pdf I just dm'ed u if u get stuck

on the first page

@humble storm

[humble storm]

For the one I was stuck on, i was heading towards the right direction except never considered rewriting n^i by itself

[snow sleet]

I gave soo many hints about using the lemma. We even talked about that problem before I sent u the quiz yesterday!!

[humble storm]

is n^i-1 essentially indicating the previous term

[snow sleet]

yes

look how I got from n^2 is odd to n^3 is odd

[humble storm]

I wonder if you multiply by n an infinite amount of times will it still be odd

[snow sleet]

u mean like $n^\infty$

[vital dew]

logician

[snow sleet]

?

[snow sleet]

because if n is odd, then n^i being odd for any positive integer i essentially is saying that. n^(infinity) can't be necessarily odd or even since n^(infinity) would be just infinity which we don't know whether it's odd or even

so n^i is the only meaningful result

[humble storm]

Thinking about infinity is weird if it's the concept of never ending

[snow sleet]

true true

[humble storm]

If you don't mind me asking, what is a logician

[snow sleet]

someone versed in logic (for me mathematical proof theory is where my interests ly)

I'm still just a senior undergrad but I'm super into proof theory I kinda geek out on it

[humble storm]

Could a logician prove anything

[snow sleet]

with the right inspirations and with the right cleverness, I believe so

as far as mathematical things go

I can't prove for instance that all crows are black

[humble storm]

I still wonder why when completing the square it's ( b/2)^2 who comes up with that lol

[snow sleet]

I bet it's arose from a geometrical interpretation

hence where the term "square" came from

could be wrong bout that but it's a guess

[humble storm]

trinomials are sort of special because there's not many ways to solve one

[snow sleet]

yea I don't know if there's a way to find the roots of a cubic

[obtuse lance]

wdym by "find"

[snow sleet]

I mean an explicit formula for the roots of a cubic

[obtuse lance]

there is in terms of radicals up to 3rd and 4th degree polynomials

[snow sleet]

hmm interesting

[obtuse lance]

5th is where it runs out, but then again we could just define some new function and keep going forward to get an explicit expression

[humble storm]

Why would solving an equation of higher degree be important

[haughty garden]

The cubic formula is rather long and cumbersome

[obtuse lance]

that's a good question, I'd say it's probably not that important to have some fancy closed form solution unless you're doing some kind of pure math thing. You could always just approximate solutions to arbitrary accuracy for the most part

[fluid coyote]

hey all!

is there anything you'd recommend to watch to learn how to solve this type of thing? It doesn't seem to be that hard, but I need to see some kind of an algorythm of solving this🥴

[cerulean radish]

Is there anything wrong with this proof?

Let $f, g$ be Boolean functions such that $s \le f \vee g$ with $s = \bigwedge_{k=1}^n x_k$. Our claim is that $s \le f$ or $s \le g$.

If $x_k = 0$ for some $k \in { 1, \dots, n }$, then $s = 0$, making $s \le f$ and $s \le g$ automatically true.

If $x_k = 1$ for all $k \in { 1, \dots, n }$, then $s = 1$ and $f \vee g = 1$, meaning $f = 1$ or $g = 1$ and $s \le f$ or $s \le g$ respectively.

[vital dew]

A Lonely Bean

[cerulean radish]

The reason I am asking is that the exercise also states that f and g are monotone meanwhile I have not used that fact in the proof

[wide thorn]

that not proof

[cerulean radish]

Why?

[weary tiger]

I'm not sure how to approach b

[rose zinc]

guys I need a help in a very simple question ?

[oblique dragon]

Assume n is even. If you look at partitions of size 2, you'll have n / 2 of them. (For example, if n is 6, you have 3 + 3, 4 + 2, 5 + 1). None of these can be a refinement of the other, since you have to increase the number of terms in a partition when you're refining it. And if you prove it for even numbers, it's proved for odd numbers as well, since you can add 1 to the partitions of the preceding even number (For example, for 7, you have 3 + 3 + 1, 4 + 2 + 1, 5 + 1 + 1)

[weary tiger]

What about c with n >= 4

[blissful shell]

This is True right?

[white sundial]

it's not
for instance if A = {1,2}, then P(A) = {empty, {1}, {2}, {1,2}}
so {A} = {{1,2}} isn't an element of the power set

[blissful shell]

isnt {{1,2}} part of P(A)??

[white sundial]

{1,2} is in P(A)

but {{1,2}} is not

if you list out the elements of P(A) you have:
empty set
{1}
{2}
{1,2}

[blissful shell]

oh i think i get it now

[blissful shell]

thx!

[oblique dragon]

What have you tried so far?

[fallow dune]

this class really really bad for my mental tbh

every week we got 20+ proofs we have to do for hw

especially that i got work monday-thursday sat and sunday

💀

[vernal vigil]

Do they teach you at university how to apply Graph theory and Matrices to your code?

[lavish roost]

i need help with modular exponentiation

solve 23^65432 mod 101

i reached to 23^32 101

how to proceed further?

[faint sphinx]

It's a little bit tedious, but you can do 23^2, then reduce mod 101, then square that, then reduce mod 101, then ...
Should take only 5 steps

[lavish roost]

got it thanks

[granite forge]

How many non-negative integer solutions are there to the system x1 + x2 + x3 = 18 if 0 ≤ xi ≤ 9.

[orchid leaf]

Can anyone help with this

[weary tiger]

!status

[lofty cloud]

What step are you on?
1. I don't know where to begin
2. I have begun but got stuck midway
3. I got an answer but I'm told it's wrong
4. I got an answer and would like my work checked
5. I have a question about someone else's worked solution
6. None of the above

[orchid leaf]

1

[weary tiger]

1: Visualize the mappings

[orchid leaf]

b(0) maps to a(0)
b(1) maps to a(6)?

[weary tiger]

Sure

but

really

it maps to the number inside the ( )

[orchid leaf]

idgi

[oblique dragon]

One way is coefficient of x¹⁸ in (1 + x + x² + ... + x⁹)³ . But I think here it might be simpler to just count by hand.

[granite forge]

@oblique dragon

I don't think it's simpler to count by hand.

Without the restriction of 0 <= xi <= 9

there are 190 combinations of x + x2 + x3 such that = 18

I think we have to take the complement for this question

where we do Total without restriction (190) - (whatever the complement is)
but I don't know what the complement is

would it be the case where 1 is 10 ?

because that's how I did it

[oblique dragon]

Assume x1 = 0. Then count possible values of x2 and x3. Then assume x1 = 1, and so on.

[granite forge]

that we would have to do 9 times 10 times correct?

instead can we do the complement?

because I remember a similar q

and they just took 1 more than the restriction

[oblique dragon]

By complement you mean when you mean at least one xi ≥ 10 right

[granite forge]

that's what im confused about. it would be only 1 right?

cause 2 isn't possible?

[oblique dragon]

yep you're right

[granite forge]

but yes essentially that

but then with that, there's another confusion I have

[oblique dragon]

but I don't really see why taking the complement should make it any easier

[granite forge]

atleast 10, then would that mean I have to do cases where 1 is 10, 11, 12 ?

[oblique dragon]

Yes

[granite forge]

see that's what's confusing me

[oblique dragon]

and then multiply this by 3

[granite forge]

because I'm sure they want us to practice 'complements'

and I feel like here it is a usecase

also

[oblique dragon]

because it could have been x2 or x3 as well

[granite forge]

I know this is weird and hard to explain but

I remember my lecturer did a similar q

something about no more than 50 should pass in a test

then what he did for that was

he did all different ways - someone gets 51
he didn't do 52, 53 etc..

[oblique dragon]

I mean if there was like 12 instead of 18 on the RHS

Complement would make sense

[granite forge]

no read this

[oblique dragon]

But here 9 is halfway between 0 and 18

[granite forge]

he only did 51

let me get the example one sec

Here is the q

and look at Condition 3

See what he did?

The question was fewer than 50% of the students my pass.
this means atleast 50% should pass. Meaning 50% should fail (D)
He then takes the complement...
He makes it so that 51% fail
so allocates 51 to D

that's all he does.

he doesn't do 52 fails

53, 54, 55 and so on..

@oblique dragon are you here?

Is there anyone else that can help?

[oblique dragon]

I'll look at it

[granite forge]

Thanks

Even when I watched a lecture, I didn't understand why we don't allocate 52 to d, 53... so on

oh

actually nvm I still don't understand,

[oblique dragon]

Ah I see

What he did is

Assume A, B, C, D are people and you have to distribute apples among them such that A + B + C + D = 100, and D has ≤ 50 apples

To count the complement, you give D 51 apples first

and then count how you can distribute the remaining 49 apples

[granite forge]

but what about 52 apples to D?

[oblique dragon]

So then you're counting no. of solutions to A + B + C + D = 49

[granite forge]

yeah I got that.

[oblique dragon]

This is included

[granite forge]

how?

[oblique dragon]

We're giving at least 51 apples to D

Not just 51 apples

[granite forge]

hmm

[oblique dragon]

If D is 1 here

[granite forge]

so it doens't matter how many we give to them?

[oblique dragon]

It means D has 52 apples here

[granite forge]

OH

shittt

yeah

omg yeah he even explains that afterwards. im so dumb.

wait

so can I make it such that I can do

[oblique dragon]

It's like you had to ensure D has at least 51 apples

[granite forge]

give 10 to any X

and then we have 3 groups. and want to distribute 8 apples

so C(8 + 3 - 1, 3-1) = C(10, 2)

[oblique dragon]

yes, this works here

but wouldn't always have worked

Like this wouldn't have worked if you had 21 on the RHS