discrete-math

[quartz hound]

(I was initially planning to use burnside's lemma to root out dupes)

[weary tiger]

is there anyone here who can help with formal logic? i.e. generalization and instantiation in proofs, using inference rules, etc.

please DM or reply if u can

[swift agate]

I have a problem to find the total node at depth d ...the formula can be recursive. I started the problem but I can't figure out the formula. Is anyone available to help?

[swift agate]

<@&286206848099549185>

[mystic moss]

@swift agate you can use T(d-2) in your solution too, right?

[swift agate]

yes

[mystic moss]

okay, then try to use both. (specifically, you can use them to get n_d.)

[swift agate]

I know I want to add all the nodes from previous depths which I called T(d-1) to all the nodes at depth d which I called n_d. And I was think n_d is a multiplication of 2 values. depth * number of nodes at that depth

i am still thinking about it

[mystic moss]

right. how can you find the number of nodes at a particular depth using T(d-1) and T(d-2)?

[swift agate]

right now I'm trying to think about what T(d-2) is and its stretching my brain

[mystic moss]

circle T(d-2) and T(d-1) on the same graph, it might help

[swift agate]

[(Td-1) - T(d-2) ] * depth

?

[mystic moss]

why do you think so?

[swift agate]

all the nodes at a particular depth = all the total nodes - all the nodes at the previous depth

[mystic moss]

yeah, exactly.

[swift agate]

okay thank you now I am testing it

thanks for your help

[plucky flicker]

Is anyone available to help me out on how to approach this question and find the errors?

[silk coyote]

I think it is related to the fact that you can't be sure what is going to happen when r^(-1), but I recommend you to wait for the help of someone who knows more about this. I am not exactly good at doing proofs. To put it better, you can't be sure that r^(-1) is going to be 1 at all, because your induction rules are very clear that they apply when k>=0, and there you are messing with a number outside that range.

[zinc swift]

hello, for part b. i understand that we could find out by A(total ways to place elements) - B(ways to place elements without 6). that gives us A-B = 100,000 - 9^5. but i was wondering if we need to deduct 1 because of the number 100,000

[grave lagoon]

Hi, I am not sure how I am supposed to solve this particular exercise.

[nimble cove]

@grave lagoon just get the probabilities, pi by dividing fi/n, where n is the total number

ie. sum of all the fi

from there the expected value and variance formulae can be applied

[grave lagoon]

@nimble cove thanks, a fellow student solved this problem this way and I thought something was off.

[nimble cove]

[vast mulch]

how do you read this?

[grave lagoon]

@vast mulch From what I remember from maths it's translated n doesn't exist

[vast mulch]

@grave lagoon what about this

[grave lagoon]

for every n

[weary tiger]

The first one might alternatively be read as "there does not exist a n such that [...]"

[grave lagoon]

The first one might alternatively be read as "there does not exist a n such that [...]"
@weary tiger yeah you're right. I wasn't entirely accurate

@nimble cove In this case I will compute expected value and variance this way?

[wise dawn]

Bruh I don't even know trigonometry and you guys are discussing crazy stuffs. Mad respect

[nimble cove]

@grave lagoon Yes

[rustic stratus]

this is some induction proof, does anyone know what they did at the very last step? im kind of confused

this appears to be the last step and im not sure how this really proves anything

[lyric pumice]

@zinc swift Use the principle of inclusion-exclusion.

[olive sun]

I gotta say Discrete Math is way harder than any of the Calculus. IDK how people can say that Calc II is the hardest math, not even close.

[fallow raft]

^^

Freshman in calc 3 & discrete and can easily say discrete is the hardest class Ive ever taken

and on that note, does anyone have any recommendations for YT channels or just videos online I can watch to get a bit more solid w/ discrete concepts?

[unique herald]

Could somebody guide me through this question?

I'm confused, how do I find the basis step, inductive hypothesis, etc

[fallow raft]

To find your base case youre going to set n equal to 1 and then show that the left hand side is equal to the right hand side @unique herald

And then work from there in regards to your IH and IS

[winter finch]

maybe this discord will carry me through this class

[vital dew]

Commander Vimes:

[last timber]

I SAW YOU

WHY ARE YOU HIDING

[weary tiger]

thanks 🙂

what is the name of this function?

sigma denotes summation

this looks like pi, what is the name of this?

[last timber]

ye, it is pi

[unique herald]

thanks!

[rapid lily]

is this transitive 😮

i cant decide

[unreal stump]

No

[rapid lily]

xRy as y is born 11 months after x
yRz as z is born 11 months after y
xRz is not true as z is born 22 months after x

because of that right ^

[unreal stump]

Yes

[weary tiger]

@fallow raft I did take logic and algorithm class similar to discrete but its more on computer science and watching theTrevTutor helped me a lot.

[unborn walrus]

Guys

Do u know the answer to these questions

[stray reef]

@unborn walrus we do not give out answers here.

[ivory creek]

lmao

wait are you askin for hw help lmao

[tacit sluice]

clarification question; proving disjoint sets using symmetric difference is contradictory no? i assume this is a trick question (simple yes or no can suffice)

<@&286206848099549185>

[honest barn]

What?

The statement given is true

What contradiction are you proposing exists?

[tacit sluice]

i corrected myself @honest barn

i read it as the intersection of A and B equaled the symmetric difference oops

[honest barn]

Lmfao

Yeah that would be kind of bad

[quartz hound]

can someone plz briefly explain the concept of multiset combination to me?

[hexed meteor]

Any one familar with Bayes' theorm and can explain it XD

[versed granite]

I am note sure what happenes to the summ when you square it?

[near prawn]

wdym @versed granite

[versed granite]

right side = (summ k)² is it = to summ k²?

[near prawn]

no

its [n(n+1)/2]^2

or n^2(n+1)^2/4

[versed granite]

and if you wanna say it with the summ symbol?

because how do i know, that this counts? its [n(n+1)/2]^2

first i would need to proof that, right? ^^

[shrewd spindle]

not sure if htis is the right place for this

but for this infinite series

in a problem that i'm doing, i use this summation

but, i dont want to include hte first term of k=1, and want to start the summation at k=2

i was wondering if doing so would simply make the rhs the same but just subtract 1

since i don't want the first term of 1. I'm thinking this doesn't work but let me know if i'm wrong.

[errant bear]

yes

[willow root]

For this question, should I let A = {1}? Im not sure how to prove this

So far, I let A⊆X. Thus f(A)=Y. That would men f-1(f(A)) = f-1(Y) = X

I proved that f-1(f(A)) = X but not the subset of X which is A

[mystic moss]

@willow root what exactly is the objective? to define a function f?

[willow root]

I have to identify the set A and determine f-1(f(A))

[mystic moss]

(also nice handwriting. do you usually underline/overline your sets?)

but you define f, right

[willow root]

Yeah I think

Thats my teachers hand writing lol

[mystic moss]

okay, so you just need a single element whose image doesn't map to itself then

[willow root]

yeah

[mystic moss]

so what do you want f to be?

[willow root]

I have no idea what he means define a function f, my professor hasnt done a problem like that

I assumed he wanted us to just find numbers in A that contradicts f-1(f(A)) = A that follows f: X -> Y

By defining the function, do I set Y?

[mystic moss]

yeah, i guess. this is a weird question to ask

[willow root]

So I just set Y = {1}

And since f: X -> Y, that would mean f(1)=f(2)=f(3) = 1 right?

[mystic moss]

yeah you can do that

what would be a valid A in this case

[willow root]

I know 2 would make f-1(f(A)) != A be true

[mystic moss]

yeah, {2}

[willow root]

So since A⊆X, f(A) = Y?

And that would mean f-1(f(A) = f-1(Y) cause i just take an inverse of both sides?

[mystic moss]

f(A) is {1}, which is also Y in this case, sure. (i'm kind of guessing at how the output of the function is defined on a set).

also, i kind of skipped over the part where you take the inverse of f

this particular function isn't invertible

[willow root]

oh okay

So how do I draw the conclusion that f-1(f(a)) is not equal to A?

[mystic moss]

no clue, actually. for any element x, it should be that f-inverse(f(x)) is x (by virtue of how the inverse is defined)

[turbid meadow]

just to confirm i got e) right {1,2,4,6}

it just that my professor sent the answers and it says {7}

which doesn't make sense for me

[lament nymph]

sorry im confused. im just learning set so i may be wrong but doesn't $\overline{C-A}$ mean that $x$ does not belong to $C$ but belongs to $A$. But since all elements of $A$ belongs to $C$, wouldnt $\overline{C-A} = \emptyset$? And since $\overline{C-A} \cap B$, wouldnt it mean its $\emptyset$?

[vital dew]

lohzna:

[willow root]

@mystic moss Can you only do inverse if f is one to one and onto or does that not matter?

[lament nymph]

ohh i see

[mystic moss]

how do you define the inverse?

if it has to be a function from Y to X, then yes

[willow root]

So for my previous question, would I need to choose different values of Y instead of Y={1}?

[mystic moss]

yeah

you can't have overlapping outputs if it's invertible

[willow root]

So if I choose X= {1,2,3}, Y={1,2,3} and f: X->Y, I could take the inverse?

[mystic moss]

yeah, you could

[willow root]

Now what 😭

[charred forge]

How do I solve this via induction

[versed ledge]

assume it for n then prove it for n+1

that is just induction

actually you don't really need induction here n+ 6. n(n+1)(2n+1) /6

[charred forge]

And the induction step is just changing i to k+1

Well for some reason my professor wants it broke. Down

Broken

[versed ledge]

no the induction hypothesis you will take it the summation of i from 0 to k

then prove it for i from 0 to k+1

Oh! sorry take i from 1 to k and then from 1 to k+1

take 0 and 1 as base case

[charred forge]

So base case

I would show it as

Just plugging in 0 and 1 to the equations

[errant bear]

yes

[pallid belfry]

h(x,y) = (f(x), g(y))
Can someone help me prove if this is 1-1 or not
and either onto or not

[novel spire]

So if anyone is interested, I need help coming up with some graphs to use for a problem for my class.

It's for my math-for-liberal-arts class, and we just started talking about games and probability. But we also have done graph coloring toward the beginning of the semester.

So, take the idea of Competitive Graph Coloring. Players take turns properly coloring vertices of a graph using some number of colors. The first player who can't make a valid move wins.

What would you suggest as simple graphs that could be analyzed by beginners?

[mystic moss]

triangles/paths/loops?

that sounds interesting. this can be done with any number of players, right

[novel spire]

I'm sticking with two players

[mystic moss]

have you come up with some already? just so i know what you mean by "simple"

you could have some that are always colorable (i.e. no one wins)

[novel spire]

Well so far I have a path of 3 vertices, and a cycle of 4 vertices

In the first case (the 3 vertex path), P1 can force a win just by choosing to color the middle vertex first

Oh I'm using two colors here btw, blue and red

In the second case (the 4 vertex cycle), P2 can force a win by choosing to color the opposite vertex P1 chooses first, and using the opposite color

[mystic moss]

does the first person who can't make a valid move win or lose?

[novel spire]

Lose.

The winner is the last person to make a valid move.

[last timber]

why not use salersperson variation?

[novel spire]

Either by coloring the last vertex or trapping the other player.

[last timber]

i mean problem statement is quite simple

[novel spire]

What's that @last timber ?

[last timber]

salesperson problem, haven't you heard about it?

[mystic moss]

you mean tsp?

[last timber]

ye

[mystic moss]

how does that relate...?

[last timber]

variation

oh wait

competitive graph coloring

sorry i am blind idiot

[mystic moss]

you can extend the path one to a triangle, in which the first person always loses

perhaps you can even do one with a 1-coloring

like a 4-vertex path, where the second person forces the win

actually the second person will win regardless of what happens

[novel spire]

I'd like one more graph that makes things "interesting"

I'm thinking of taking the square and adding a diagonal

Actually no that makes it easier

Maybe a pentagon?

[mystic moss]

can you generalize a strategy for cycles of odd/even length?

[last timber]

well, actually, as one pretty simple option you can do the following variation which is fairly simple:

take random simple graph 
first player chooses any vertex to be his initial one
second does the same
then on each move player can color any vertex which is adjacent to colored by him (or you can even make these conditions harsher) or skip the move
maybe we can add something like capture but this is superfluous ig
once all vertices are colored  one who colored more vertices wins

i see some possible exploits here, but i guess it is useful game to analyze graphs

do not punish me if this is too stupid

[mystic moss]

maybe instead of coloring all vertices the condition could be when no player can further color vertices instead

[novel spire]

It looks so far like P2 can win the cycles 😛

@mystic moss Yeah that's the strategy

Or the win condition

[last timber]

i guess Madeleine commented my variation

[novel spire]

Either you win if you've colored the last vertex, or you win if you've made it so the other player can't do anything

[mystic moss]

yeah, i was talking about the variation. incidentally, how does P2 win?

[novel spire]

Well at least I've gotten a way P2 can win the 3, 4, and 5 cycles

Who knows if it works in general ¯_(ツ)_/¯

But I think I've found what my other questions will be

Well I guess since these are finite games there's always SOME winning strategy, but I don't have to tell them that. 🙂

Thing is this is meant to be accessible to non-majors.

[last timber]

well many graph problems can be treated mainly by pure logical reasoning rather then heavy theoretical machinery

[mystic moss]

i think they can reach a conclusion fairly confidently by just playing it out themselves

[novel spire]

Yup! That's why I love graph theory

[last timber]

i mean if you want to find isomorphism algo you have to use heavy machinery

but for example for showing the graphs are not isomorphic it maybe enough pure reasoning

[mystic moss]

also for (c) and (d) they might just give you a vertex and an edge

is that a solution path you'd like?

[novel spire]

I mean if they think of it, then that's fine lol

[last timber]

i have another solution but universe is too small to contain it

[feral hearth]

If we proved that an NP-complete problem has no polynomial solution what does that mean for the relationship between P and NP?

Does that mean that P != NP?

[daring beacon]

can someone tell me how this person got 11 and 29?

[daring beacon]

nvm

[daring beacon]

can someone exlpain these answers for me?

[fervent briar]

Once the previous questions are answered, can anyone help explain this to me? I don't really know what's going on and I tried googling and watch the recommended video. None of those explain about rectangle problems like this one..

This is just a sketch that I don't even sure if it's 100% correct..

[feral hearth]

How can we polynomial time mapping reduce SUBSET-SUM into 0-1 KNAPSACK?

[mystic moss]

describe both?

@feral hearth

[mystic moss]

@feral hearth you set V and W to something intuitive. take a guess, maybe

[feral hearth]

S?

[mystic moss]

yeah, exactly. do you see why this works?

(what is v, and what is C?)

[feral hearth]

k?

[mystic moss]

yes.

how does this work?

[feral hearth]

I'm just not seeing how I can translate the equality from subset-sum to the inequalities for 01 knapsack

[mystic moss]

you set both v and C to k.

[feral hearth]

ohhhhhh I see

thanks

[karmic falcon]

Is this correct to these questions A) - F)?

A) R = {(1,1),(3,3),(5,5),(7,7),(1,3),(3,1),(5,7),(7,5)}

B) R = {(1,1),(3,3),(5,5),(7,7),(1,3),(3,5),(1,5)}

C) R = {(1,3),(3,1),(5,7),(7,5),(1,3),(3,5),(1,5)}

D) R = {(1,1),(3,3),(5,5),(7,7)}

E) R = {(1,3),(3,1),(5,7),(7,5)}

F) R = {(1,3),(3,5),(1,5)}

[rapid lily]

i have no idea what to do with -3/x^2 in

if anyone can kindly help, i'll appreciate it! ❤️

[gritty crescent]

@rapid lily Find the general term of the given expansion, simplifying x as far as possible. Then equate the exponent of x with 21 to find the value(s) of n, i.e., the term(s) for which the exponent of x is 21. Find their respective coefficients and add them(if there's more than 1).

[bronze wagon]

Could I have help with this problem please?

[last timber]

@bronze wagon what is SList L

[last timber]

👻

[abstract ravine]

lets say i have 2 binary strings, one is A and the other is B. How would i calculate (A n B)' ?
i know how to calculate A n B

[last timber]

n stands for AND?
and ' for complement?

[abstract ravine]

yes

[last timber]

then you can just calculate A n B and complement resulting string

[abstract ravine]

i meant n stands for intersect

[last timber]

or use De Morgan

[abstract ravine]

n stands for intersect

so (A intersect B)'

and wait i forgot Union was or operation?

and intersect was and operation?

right?

[last timber]

yes

[abstract ravine]

@last timber hey is this correct?

Btw is it ok if i ping you?

[last timber]

seems fine

[abstract ravine]

Ok wait

Last one

@last timber

[last timber]

ye

no need in U btw

U is assumed to be just string of 1's of max length

[abstract ravine]

Ye

[arctic orbit]

Guys i was thinking of taking a course on discrete math...is it going to be extremely hard and do you know what kinda topics they teach in that course?

[last sigil]

Discrete math proofs could be intimidating at first, so it's hard to say how hard it would be for you

Honestly, just practicing and getting used to examples makes discrete math really easy

[drifting sail]

well, they're intimidating if it's your first time doing proof-based math (which is the case for many)

[last sigil]

In terms of topics, it can be ridiculously broad, but in general, discrete math teaches: propositional logic, proof techniques (induction, etc.), basic graph theory, recursive sequences, combinatorics

these are all general things; it will be up to the prof to dcide what specifically

@arctic orbit see above comments

[arctic orbit]

Thanks

[raven sandal]

Anybody available to guide me through a problem? I have an issue with basic inequalities but I don't know how to pinpoint my issue in the proof to actually understand it.

Basically, using Well ordered Principle Technique, prove (2n choose n) <= 4^n

[drifting sail]

The Well Ordering Principle says that any non-empty subset of the positive integers has a minimum element. This can be used to prove things about the positive integers by contradiction.

So the first step would be to assume the set of integers for which the proposition is false, say A:={n≥1 | (2n choose n) > 4^n} is non-empty and let n be the minimum element in A. (Here we use the W.O.P.)

other than that, what have you tried thus far?

[raven sandal]

My issue isn't the concept of it.

It's the need to get to the fact (2x choose x) < 4^x given (2(x-1) choose (x-1)) < 4^(x-1)

After a lot of reordering and simplification I've led myself to (2x choose x) <= 4^x * [(2x-1)/2x]

Textbook says that [(2x-1)/2x] < 1 and thus it just becomes 4^x but I'm confused as to why that is so

Does that make sense? I'm really bad at explaining my confusion in math. LMK if there's more clarification needed

Ty for being patient with me

[drifting sail]

oh, it probably means you have
$$
\binom{2x}{x}\leq 4^x\dfrac{2x-1}{2x}< 4^x
$$
since $\dfrac{2x-1}{2x}<1$ for $x>0$

[vital dew]

derivada.schwarziana:

[raven sandal]

Oh, that makes sense. It's weird since the other questions with inequalities have a similar setup but the reason you get to reduce the inequality is different each time

This is what confuses me but I'll look into it more and the different methods.

Thanks so much derivada.schwarziana! You're awesome.

[reef jolt]

I have 8 containers and 12 items, I want to fill these with these items and I want to see how many possibilities there are to fill them, when 1 containers has to have at least 3 items inside it

I don't know how to calculate this 😮

[opal cedar]

what does the set Z sub 61 mean?

like this

[near prawn]

set of integers modulu 61

[opal cedar]

like for this, would the answer be all odd values?

[stark creek]

i cant tell if these graphs are plane or not

the one on the left looks like it could be as all its vertices have only 3 lines on them (i dont know the right words for this in english)

heres a clearer version

well its been 15 so <@&286206848099549185>? (sorry to bother)

[fervent briar]

#discrete-math message

Can anyone help?

[mystic moss]

@fervent briar check over your diagram again

[fervent briar]

Was my diagram correct?

<@&286206848099549185>

[mystic moss]

(no, check over it again.)

[fervent briar]

I would get something like this?

The vertical connection can honestly be anywhere.. from all the way to left to all the way to right. They just have to be at the same x coordinate..

For the horizontal connection, the same.. They can be as high or as low as they want. Just that the same y coordinate

[mystic moss]

you only glue together the opposite sides, not everything in between

[fervent briar]

So it looks like this? Like a prism?

Actually, it might even look like diamond depending on the x value..

[weary tiger]

Is it possible to change the dimension of a matrix?

I've played with data science and I remember being able to reshape matrices. I'm working on a practice set for my discrete class and we have a problem for adding matrices with different dimension. I'm just wondering if reshaping matrices exists outside of computing or should I just answer that it isn't possible?

Tried browsing but keeps ending up in matlab pages.

[stray reef]

youre gonna have to give some more context

[weary tiger]

Right, let me make it more simple.

Can you add a 2x2 matrix with a 1x4 matrix?

by potentially reshaping that 1x4 into a 2x2?

[stray reef]

if you reshape your 1 by 4 matrix you will no longer be adding the original 1 by 4 matrix to anything

you will be adding the reshaped version

[weary tiger]

So a 1x4 matrix of all 1 is not exactly equal to a 2x2 matrix of all 1?

[stray reef]

it's not "not exactly equal" it just isn't equal

these are two very obviously distinct objects

[weary tiger]

I see, thank you.

[weary tiger]

Please help with me on this question

[long bronze]

can someone help me with this question, I am trying to simplify this using the laws of set algebra

A-B'∪ B∩A (using Commutative and difference laws)```
after this I am not sure how to continue

[minor dagger]

(A∩B')∪(A∩B) -> A ∩ (B∪B') -> A ∩ u -> A

[long bronze]

thank you @minor dagger

[old hawk]

<@&286206848099549185>

dont get this at all

[fluid zealot]

Let's see if this helps.
https://www.math24.net/logic-set-notation/

[winter finch]

Does a probability of 1 guarantee an event

[minor dagger]

yeah

[raven sandal]

How would I go about proving 3^n = 2n+1

with well ordering

I got up to 3^x * (1/3) = 2x - 1 but I'm a bit confused on how to move on from there

[raven sandal]

(Solved)

[stray reef]

3^n = 2n+1??

[last timber]

3^n=2k+1 was meant

[stray reef]

you mean that 3^n is odd for all n??

[raven sandal]

Yeah that's what I meant. I solved it.

Do you mind checking my work for a problem?

It's different. It's on relations.

[stray reef]

ok sure

[raven sandal]

Basically, xRy if and only if 2x+5y = 0 mod 7.
So I got it's reflexive since 2x+5x = 7n and 7 divides 7x.
It's symmetric because if 7 goes into 2x+5y then it goes into -2x-5y as it's simply a switch of parity.
Then finally for transitive, it's transitive because if 2x+5y = 7n and 2y+5z = 7n then 7|2x+7y+5z. I'm not 100% on transitivity part

But I'm trying to prove it's an equivalence relation.

[stray reef]

oh boy your work has multiple issues

first off there isn't even any structure to speak of, this reads like a barely coherent string of consciousness

you'd have done better to start with:

i have this relation R defined as xRy iff 2x+5y = 0 mod 7, and i'm trying to prove this is an equivalence relation.

so that i, the reader, know what you're trying to achieve.

So I got it's reflexive since 2x+5x = 7n and 7 divides 7x.
2x + 5x = 7x, this n of yours came out of nowhere

[raven sandal]

Oh, my bad. I used the definition of division.

and the definition of conguence modulo

2x+5y - 0 = 7n

where n is a member of the set of integers

[stray reef]

you would've had to introduce n accordingly

right now it reads as if it came out of the blue

It's symmetric because if 7 goes into 2x+5y then it goes into -2x-5y as it's simply a switch of parity.
it's wrong to describe this as a "switch of parity", nothing here is switching between even and odd.
also this says nothing about whether or not 2y+5x is 0 mod 7, which is really what you need to address here.

[raven sandal]

Well, to prove it was symmetric (p --> q) I thought we assumed p is true initially.

[stray reef]

that's not the issue

you're missing my point

you stated xRy (albeit poorly) but then proceeded to say nothing of yRx

you do not even mention 2y+5x, let alone its being divisible by 7, in your single-sentence attempted proof of symmetry

do you understand what i'm trying to tell you here

[raven sandal]

Yeah, that my proof is really bad and is basically [a really bad word]. I should string my thoughts more coherently and logically by identifying the definitions.

I should establish definitions and basis of my proof before going through it to not be led astray.

[stray reef]

am i understanding correctly that you'll now attempt to redo your proof

[raven sandal]

Well, yeah but I asked because I noticed the symmetric and transitive part didn't make sense.

I just put down the wrong thought process I noticed I had to state this was my initial thinking.

[raven sandal]

@stray reef I'm still lost.

But I organized it better.

[stray reef]

okay this isnt much better content-wise

and replacing $\equiv$ with congruence modulo'' just feels weird. just write = instead if you don't have the fancy symbol, it's fine. you have the word mod'' there to disambiguate.

[vital dew]

Ann:

[stray reef]

if anything, $\equiv$ should be read as just ``congruent''

[vital dew]

Ann:

[stray reef]

or "congruent to"

anyway

yeah you didn't prove symmetry at all, and also more pressingly you used n for two different things in the symmetry section of your proof

which is bad

[vital dew]

용현진:

[raven sandal]

That's why I'm asking.

I tried defining x and y in terms of each other.

But I can't reorder the terms to get 2y+5x.

[stray reef]

mmmh

ok so like do you know the properties of modular arithmetic

[raven sandal]

Yeah, that it's an equivalence relation in of itself.

[stray reef]

no, not that

specifically, do you know that congruence modulo n preserves addition and multiplication? namely that if a = a' (mod n) and b = b' (mod n) then a+b = a'+b' (mod n) and a*b = a'*b' (mod n)

[raven sandal]

No, I did not.

[stray reef]

bruh

imean ok

you can write 2y + 5x as (7x+7y) - (2x+5y)

[raven sandal]

Oh, I do actually. I just didn't read it right.

[stray reef]

bruh

okay so there is a shortcut and a way to make this all significantly easier but i don't know how receptive you'll be to my attempts to share it

[raven sandal]

I actually just want to understand in depth.

Because as you probably noticed, I have trouble abstracting definitions to practice as shown just now with modulo.

[stray reef]

so do you want the non-shortcut or the shortcut

[raven sandal]

Both. Non-shortcut first though.

Is that ok?

[stray reef]

ok

[raven sandal]

Thank you!

[stray reef]

i will rephrase the definition of R as 7|(2x+5y) so as to make the subsequent work a little bit easier

and i'll make use of some properties of the divisibility relation which i will assume as known.

so now:

the relation R is defined as xRy <=> 7 | (2x+5y), for all x, y ∈ Z. our goal is to show that R is an equivalence relation.
to prove R is an equivalence relation, we will prove that R is reflextive, that R is symmetric, and that R is transitive.

to prove R is reflexive, we need to prove that xRx for all x ∈ Z.
by the definition of R, xRx <=> 7 | (2x+5x), or in other words xRx <=> 7 | 7x. since x is an integer, 7 | 7x is obvious.

to prove R is symmetric, we need to prove for every x, y ∈ Z that if xRy, then yRx.
by the definition of R, this amounts to proving that 7|(2x+5y) implies 7|(2y+5x).
notice that we can write 2y + 5x = 7(x+y) - (2x+5y), thereby expressing 2y+5x as the sum of 7(x+y) (a multiple of 7 directly from the definition of multiple) and -(2x+5y) (a multiple of 7 as follows directly from the assumption). since the sum of two multiples of 7 is again a multiple of 7, we get 7 | (2y+5x) as desired.

to prove R is transitive, we need to prove for every x, y, z ∈ Z that if xRy and yRz, then xRz.
by the definition of R, this amounts to proving that 7|(2x+5y) and 7|(2y+5z) implies 7|(2x+5z).
notice that we can write 2x+5z = (2x+5y) + (2y+5z) - 7y, thereby expressing 2x+5z as the sum of (2x+5y), (2y+5z) (both multiplse of 7 by assumption) and -7y (a multiple of 7 directly from the definition of multiple). since the sum of three multiples of 7 is again a multiple of 7, we get 7 | (2x+5z) as desired.

we have shown that R is reflexive, symmetric and transitive, and therefore R is an equivalence relation. this completes the proof.

this is wordy i know but proofs like this showcase so much detail because they're aimed at beginners

[raven sandal]

I never knew you could do 7(x+y) from 7|2y+5x

I mean I knew, but from definition of divsibility it wasn't clear to me.

[stray reef]

i'm not doing 7(x+y) "from" anything

you could instead see it as 7x+7y

and like, expressing 2y + 5x as (7-5)y + (7-2)x

and some reorganization

[raven sandal]

My thinking process was that I couldn't use yRx like you did to prove it since we're proving for it unless I'm still reading it wrong.

In my head from reading your proof, I'm thinking if P does imply Q, then this case happens. Since this case is mathematically true by the algebra I have shown, it does imply Q. That's how you approached it to me

[stray reef]

i didn't use yRx

i did algebra to the thing involved in yRx

[raven sandal]

Oh, I see. You didn't use yRx, you used two numbers being 2y and 5x.You got 7(x+y) comes from though because since 7|(2x+5y) and 7|(2y+5x), you add 2y+5x+2x+5y which is 7x+7y = 7(x+y).

[stray reef]

,,,, no

no, i would not describe it as that

how i came up with 7(x+y) has no bearing on the proof whatsoever

[raven sandal]

I got it.

I'm just really dumb.

Thank you for making such a detailed proof. I really did not see that. It's like stating 0 = 1-1.

[stray reef]

i can still give you the shortcut proof

[raven sandal]

Sure. Thank you so much again.

This helped out more than just this proof.

Really expanded the box for multiple problems I struggled on this assignment with.

[stray reef]

take 2x+5y = 0 (mod 7) and multiply both sides by 4 to get 8x + 20y = 0 (mod 7). notice that 8 = 1 and 20 = -1 mod 7, so this becomes x - y = 0 (mod 7) or just x = y (mod 7)

more formally: 2x + 5y = 0 (mod 7) <=> 8x + 20y = 0 (mod 7) <=> x - y = 0 (mod 7) <=> x = y (mod 7)

so our relation turns out to be the same as the relation of congruence mod 7 itself

[raven sandal]

I gasped.

That's really smooth.

Thanks again for breaking it down for me and helping me expand my critical thinking skills.

And being super patient.

[viral patio]

From

#❓how-to-get-help

Rule 4

If your question has not been answered for a minimum of 15 minutes, you may use the Helpers tag once. Please do not try to bump your question using this ping unnecessarily. Do not abuse this ping. Do not individually ping users with the Helpers tag without their express permission.

[normal dragon]

How to get started with this? I'm completely stuck

[unreal berry]

moved to questions-y

[unreal berry]

I think you delete the original question and use the tag in one of the channels below while providing context and what you know

[normal dragon]

Okay. Done
Thank you 🙂

[lethal sequoia]

Hi can someone help me with this question?

[stray reef]

is this graph theory

[lethal sequoia]

Yea

[stray reef]

what's a traceable graph

and what's S here, and for that matter what's minus

[lethal sequoia]

It’s a Hamiltonian path

[stray reef]

huh?

[lethal sequoia]

Sorry S is the subset of the vertices of a graph G

[stray reef]

do you mean a traceable graph is a graph that admits a hamiltonian path?

what's G - S? is it the graph you get by cutting out all vertices in S from G (and the edges incident to them)?

[lethal sequoia]

This is the question:

In this book, traceable is defined as a Hamiltonian path. Which is the path that spans all vertices in G

[stray reef]

as admitting a hamiltonian path

yes?

[lethal sequoia]

I don’t know what you mean by ‘admitting’

[stray reef]

it doesn't mean the graph consists of only a single path and nothing else

a traceable graph is a graph which has a hamiltonian path, yes?

[lethal sequoia]

Yes

[stray reef]

ok

great

would you like hints or would you like a proof sketch

[lethal sequoia]

I made examples and I see how it makes sense. I just don’t know how to prove it mathematically

[stray reef]

ok

[lethal sequoia]

I kind of made a proof but don’t think it’s rigorous enough

[stray reef]

ok, can you show?

[lethal sequoia]

I assume G is traceable and S subset of V(G), then deleting |S| vertices splits the path into at most |S|+1 paths => G-S has at most |S|+1 connected components

[stray reef]

the idea's fine but the last part is a bit of a leap of faith

[lethal sequoia]

Can you help me improve it?

[stray reef]

you might mention that if in a graph G there exists a family {A_1, A_2, ..., A_m} of pairwise disjoint connected subsets of V(G) then G has at most m connected components

which is pretty simple to show

and then back to your reasoning, deleting S from the path will split it into some number of smaller paths, say k - and you have that k ≤ |S| + 1 with equality iff no two vertices of S were adjacent along the path

and then applying that lemma i mentioned you'll have (# of connected comps of G) ≤ k ≤ |S|+1 and you're done

you can also be more explicit in saying exactly what vertex sets G gets split into

[lethal sequoia]

Ah okay thanks!

I’ll work on it

[mystic moss]

do y'all have any hints on how to prove that every graph on n vertices must have either a clique or anti-clique of size $\frac{\log_2{n}}{2}$? (wanted to ask here before reading the proof)

[vital dew]

Madeleine:

[primal python]

This is my own work/research. How do I get from the top statement to the bottom..

I kinda get why just from looking at it but have no idea how to explain it or write it in math formally.

If you answer and I don't repond soon, it's because I've gone to bed (2am for me 😦 ) but I will be very happy to chat during daytime tomorrow.

[zenith thorn]

are you guys familiar with the empty graph by any chance

[primal python]

I am not, sorry.

Actually, after googling it I understand the concept, I did a little graph theory.

[zenith thorn]

yah its basically an edgeless graph

anywho, my question is, are graph contractions possible on an empty graph?

cuz graph contractions are usually respective of edges

[primal python]

By that do you mean edge contractions? If so no because there are no edges.

I spent quite a while trying to find an example of something similar/and the exact proof but failed 😦

[zenith thorn]

thats what im saying lol

im doing a course on graph theory

and one of my assignments asks for performing an algorithm called the connection-contraction algorithm on the empty graph $E_4$

[primal python]

Oh I thought you were trying to abstractly help me out.

[vital dew]

Majez_tic:

[zenith thorn]

ohhhhhh shit. Im sorry dude. my bad

[primal python]

Haha its okay I'll post in a different channel.

[zenith thorn]

are you sure you're in the right chat for your research question tho?

[primal python]

Well, it is discrete math

This is literally called the discrete Fourier transform 😛

[zenith thorn]

ah i see. i wish i could help 😦 I havent done discrete math in 4 years and forgot everything about that fourier transform

[primal python]

im moving my post to a different channel

np!

[zenith thorn]

for sure for sure

good luck man

[primal python]

you too!

[zenith thorn]

thanks

[sleek island]

Does anyone know how to prove this yellow part?

If a graph has Hamiltonian cycle then it has a nowhere-zero 4 low

[stray reef]

what's a 4-flow

and what's a nowhere-zero flow

what's a flow, in general

[sleek island]

hi

this is the concept

https://www.ti.inf.ethz.ch/ew/courses/GA09/NZF.pdf

[stray reef]

ok, can you show the example graph on which you're trying to construct a 4-NZF?

[sleek island]

I'm trying to prove it in general.

the yellow one

[midnight skiff]

@sleek island what is a Hamiltionian cycle?

[minor dagger]

its a Hamiltonian path that is a cycle

[earnest comet]

Hi Guys can anyone help me with this problem

[quaint star]

What does ~ mean? @earnest comet

[earnest comet]

negation]

[quaint star]

Do you mean the complement? Or what is the negation of a set?

[near linden]

i think it's more to the negation of the set

[earnest comet]

i dont know how to prove it

but i think it's false

[quaint star]

Do you mean the complement? Or what is the negation of a set?
@quaint star

[earnest comet]

negation of a set

[quaint star]

What does that mean?

[earnest comet]

im confused man

hahahah

[quaint star]

So you don't know what ~Α is either?

[merry zephyr]

I don't think you can negate sets...

only statements can be negated

[quaint star]

Indeed

[quaint star]

So it meant the complement of

[earnest comet]

sorry man im so confused

im not doing well in discrete

hahaha

[quaint star]

The fact that your solution is in English tells me this is not a translation issue. SETS CANNOT BE NEGATED.

Sets have complements

[earnest comet]

im sorry man

[quaint star]

You don't have to keep apologizing, lol

I just want to know whether you understand what ~X means or not

[merry zephyr]

I mean

I see where he came from though

~P if P is a statement or ~C is C is a statement does mean the negation of P or C

[quaint star]

Yeah, but he is just not answering my questions and keeps apologizing so it's difficult to help

[merry zephyr]

yeah yeah gotcha

[opal crescent]

some (old) books denote implications with the inclusion symbol @quaint star

[quaint star]

Interesting, but here they specifically said A and B are sets

[opal crescent]

ah yeah lol

[quaint star]

I have never seen that though, so that is interesting

[opal crescent]

just a weird way to denote complement idk

[merry zephyr]

yeah, I'd just go with the notation that it means the complement of the sets

[opal crescent]

like A->B would be noted B \subseteq A, as in the conclusion (B) is included in the antecedent (A)

but yeah it's just sets here fuck @quaint star

[quaint star]

From the proof he said, it definitely means complement, even though no universal set was mentioned

[normal dragon]

Please help

I know how to find out number of solutions of x1 + x2 + ... + xk = n

But I'm not sure how to connect that to this

<@&286206848099549185>

[olive sun]

Can anyone help me with this?

[mystic moss]

@normal dragon still working on it?

[normal dragon]

Yes

I'm stuck :(

[mystic moss]

look at the combination and consider what it means

like do you have an idea of why it should work?

[normal dragon]

I do

I took some examples and saw why it comes
Also, I'm pretty sure it relates to the aforementioned "bars and stars" analogy

But I just don't know how they fit in here, or if they do at all

[mystic moss]

they do. what does the combination mean?

[normal dragon]

So, the sequence is an arithmetic progression.
We have to select all legal ones

2 or more

[mystic moss]

i mean the ${n - r + 1} \choose r$

[vital dew]

Madeleine:

[normal dragon]

Oh that. It's selecting r things from (n-r+1) things. We can do that in (n-r+1)!/(r!)(n-2r+1)! ways

[mystic moss]

okay, so what do the r and (n - r + 1) things represent in this case

[normal dragon]

sequences

As in, we're choosing positions to fill the sequences

[mystic moss]

okay, so why (n - r + 1)

[normal dragon]

I've got to be honest here. I don't know

how this formula comes

[mystic moss]

so i claim that we have n - r + 1 positions, and we choose r of them to be part of the sequence with no restrictions. how do we now fulfill the restrictions?

i.e. how many positions are we "missing", and how do we use them?

[normal dragon]

We miss n + 1 positions
And we fill them with the values not in the initial sequence i.e x+1 because the next term will be at least x+2

[mystic moss]

n+1?

[normal dragon]

Oh wait
Is it like

T(n+1) >= T(n) + 2

So we take all possible combinations and subtract it with {T(n+1) < T(n) + 2}?

But since it is a subsequence of {1,2,3,....,n} we can't have T(n+1) = T(n)

So we take away T(n+1) = T(n) + 1 ?

Is this a half-decent approach?

[mystic moss]

not entirely sure what you're doing there my guy

the problem is: i have n positions, choose r of them but they can't be next to each other

so what are we doing? take away r-1 positiions

choose r of the remaining

and then what?

[normal dragon]

Arrange them in such a way that T(n+1) is at least 2 more than T(n)?

Like, fill in the values

[mystic moss]

yeah, you squeeze one of the remaining r-1 positions in between each of the r positions you chose

now you're guaranteed to fulfill the restriction

[normal dragon]

Yeahh makes sense

But how would we justify the said property?

Does that get taken care in the selecting r positions part?

[mystic moss]

wdym said property?

[normal dragon]

We have to have sequences, where each term is at least 2 more than the previous term

And count number of those

[mystic moss]

yeah...

wdym "justify"

[normal dragon]

As in, our selection of these numbers and gaps will fulfil this requirement of the selection

[mystic moss]

the non-adjacent requirement is fulfilled by the insertion of the r-1 "spacers"

[normal dragon]

Yeah

And non-adjacent means at least 2!

As it's at least x+2 from x

Oh man

Awesome!

Thanks a lot m8

[errant bear]

yw

[lean shard]

Hi guys so I’m struggling with proving the periodicity of a sequence

So it’s basically the Fibonacci sequence but mod 5

I mean it’s pretty obvious that the sequence is repeating itself but how exactly do I prove it

[charred forge]

the answer to this would be 14 right? Prove by strong induction that any amount of postage can be made >= ________________ using any number of 5 and 9 cent stamps, along with possibly one 2 cent stamp. You should fill in the blank with the smallest whole number that works.

[weary tiger]

Hi can someone check if my answer to this question is correct?

[signal basin]

Seems ok to me.

[hushed wyvern]

Hey I was wondering if someone can help me with an induction proof...

[quasi finch]

wanna just give me a head start for letter c ? plz and ty. I just finished a and b but im a little confused for c

[urban scroll]

hey does anyone have any videos on mathematical inductions, methods of proofs and relations? these are very hard to me if anyone has any idea on what to do

[clear aspen]

Help how to do this

[minor dagger]

13C2 * 13C3 * 13C2 * 13C0

13C0 doesnt matter tho obviously theres only one way to choose zero cards

so 13C2 * 13C3 * 13C2

[minor wyvern]

How can I prove that in a connected graph, there is a path that goes through every edge exactly once with different starting and ending point iff there are exactly 2 odd-vertices ?

[sour arrow]

What does ~ mean haha

Note that f(n) = O(f(n)) for all f

@restive olive

[sour arrow]

@restive olive
What is equivalence here?

I don't think you're allowed to just make up what ~ means, haha. Odds are f ~ g means that they have the same end behavior. That is,
lim{x → inf} f(x)/g(x) = 1

Note that f(x) = O(g(x)) if this is the case

But I'm not certain of that, it might depend on context. Where's the question from?

It would be false

Again, f(x) = O(f(x)) for ANY function. As such, f and g can be anything

And so f ~ g isn't guaranteed

I believe that to be true, but I'm still a little iffy on what ~ is

Trying to look it up

Yeah actually I think I did get it, looking at it now

It's been a while bear with me

🐻

[neat holly]

Can someone help me understand this?

[last timber]

for a) monotone sequence theorem

[neat holly]

Let me try to get something off my textbook pertaining to that and them get some sort of start.

Would b) be Bolzano-Weierstrass?

[last timber]

nah, just continuing of a)

well prolly you can use bolzano there

but it is just a) finished

[neat holly]

I'll see what I can make of it! Thank you!

I'll have to review the monotone sequence theorem but I'll try to make a proof based on things from the book.

The book has an almost-similar function used to describe a bounded decreasing sequence

wait never mind

[unreal berry]

Question moved to question-y

[finite wren]

why can we not draw this without lifting up pen?

[minor dagger]

it is possible ^

[naive saffron]

euler proved it

[minor dagger]

yes its a euler path

[naive saffron]

so if you can draw the graph without lifting up your pen (the graph has an eulerian path) if and only if all the vertices have even degree or exactly 2 vertices have odd degree

[mystic moss]

*odd degree

[naive saffron]

yes

[weary tiger]

IS anyone good with proofs that is up atm?

[obtuse lance]

I think you're supposed to also not cross lines you made previously too but

[spiral cradle]

Shouldnt step 5 be Ez and not Ex

[weary tiger]

idk where to start

[weary tiger]

Does anyone know how to do group multiplication tables? I don't know how to start if im given this: {1,i,−1,−i}

Do I just make a table like so:
x | 1 i −1 −i
1 |
i |
-1 |
-i |

[coral raven]

yeah that's literally it

[weary tiger]

so i dont start with 0 first? bc I saw an example (Z / 7Z) where they go from 0-6

[coral raven]

0 is an element in z/7z but not in the group you're looking at, just multiply all the elements in the table

[weary tiger]

@coral raven do you mind checking this? I wanna make sure I didn't make any mistakes.

[coral raven]

it's fine

[zinc viper]

Is anyone good at pythagoras?

[stray reef]

@weary tiger can you please make your 1 and i more visually distinct this is kind of a pain to read rn

it all just blends together into a forest of sticks

[coral raven]

this is literally my handwriting and therefore i feel obligated to defend it

[stray reef]

the handwriting's shit when it comes to math

it does not take that much more energy to add a little swoosh to your i's

[coral raven]

pain

[errant bear]

lmao

[tawdry pasture]

can anyone help me with some proofs for big O, omega and theta?

[glacial flame]

@tawdry pasture Just put the question. YOu shouldnt "ask to ask"

I don't think that's discrete math though.

Perhaps it is, I don't know, but anyways, just throw the question 🙂

[glacial flame]

@tawdry pasture Any idea how to approach

[tawdry pasture]

i don't know what proof method to use

I understand graphically how the statements are true

but no idea how to put it into math

and when i asked my professor last week for a mathematical explanation she said we wouldn't have to do that in her class

then she gave us this exercise because people didn't understand graphically

[glacial flame]

I think you can take the thing in O and divide the left "function" with it. And then take the limes of n to +inf

So for the first example:
1/2n^2 - 3n
lim --------------
n->+inf n^2

Now, I think if this is a number bigger than 0 and not infinity, then it is proven equal. Otherwise it is not equal

I base that on this table from wikipedia:

rightmost column., says that for theta, both Big Oh and Big Omega must be true. The first says it must not be infinity, the other says it must be bigger than 0.

[weary tiger]

if i have a practice question

will anyone be able to help?

from a past paper

[glacial flame]

@weary tiger Don't ask to ask. Just ask, on the appropriate channel.

[weary tiger]

sorry just new to discord

dont know how this server and stuff works

Just need help with this

[tawdry pasture]

rightmost column., says that for theta, both Big Oh and Big Omega must be true. The first says it must not be infinity, the other says it must be bigger than 0.
@glacial flame thank you

[glacial flame]

@weary tiger I never saw something like this, but I guess (i) should be simple?

Just replace x and y with concrete values. and you get -1=1 which is false

(ii) is weirder. But it seems to me that it means: "for every y there exists x such that the statement x+y=1 is true"

[weary tiger]

yeah ii is confusing me so mucg

[glacial flame]

Which is obviously true. But the proof would say: "for any given y observe x=1-y. This is also an integer because 1-integer is an integer, and it satisfies the statement x+y=1. Thus (ii) is true."

Perhaps "proofs-and-logic" might be a better channel to ask.

@tawdry pasture There is slightly more traditional proof which involves the definition in the second to last column in the image I pasted.

Don't know which one your professor expects.

[signal rampart]

Do algorithn questions go here too? I'm learning algorithms in discrete math

Let's say before doing a loop
A=10
B=20
And inside the loop, theres:
A = A+B
B = B-A

In "B=B-A", is the "A" value the one found from "A=A+B" or the one before the loop (A=10)?

[errant bear]

the most recent

[signal rampart]

Ok so A= A+B -> A = 10+20 =30....so then B = B-A -> B = 20-30 and not 20-10? Just want to be 100% certain. Thanks

[karmic falcon]

How do I read/translate this problem?

a ≡ b(mod 3)

[last timber]

DO NOT MULTIPOST

but this is read as a = 3k+b where k is some integer

[neat holly]

Can anyone help me with 1b? I feel like I have the right theorems, but I'm not sure how to apply them.

[last timber]

haven't i already helped you with it

[neat holly]

Well, can I get some pointers with it?

I applied monotone convergence.

And in the book, it says something about how lim(xn) = sup(xn : n is element of natural numbers)

[last timber]

for 1a) it is just monotone sequence theorem

because v_m is obviously >= v_n whenever m <= n

[neat holly]

I got that part out of the way, yes. I managed to prove it was bounded and increasing, and that v_m+1 was also convergent.

[last timber]

yes nice

for b) you can just show that x_s is lower bound of S

and that for each eps > 0 there is subsequence that converges to something in ]x_s, x_s+eps[

like just push defn of infimum

[neat holly]

I was scrambling for theorems I could use and I ended up finding four that seemed relevant, but also redundant.

I think I ended up writing sup(v_m) = sup(inf(x_n : n >= m))

And wanted to follow up with an identity by grabbing from x*

[last timber]

well i would do it so: let L be any subsequential limit. then L obviously >= x_s by definition of convergent subsequences

then showing second parf of inf's definition is also not so hard

[neat holly]

There's a certain part in my book that I thought relevant for the next part of the proof and it was the following:

[last timber]

ok btw d) is just your statement

but with inf's

you can read its proof if you want

because compase c and your statement

[neat holly]

Wait, is it? I figured it couldn't work, but maybe it can if I look at the proof.

One sec

I see that in (d) they applied (b). I like it.

But that (d) implies (a). If we switch sup(x_n) to inf(x_n), it should still work.

[last timber]

i men look at c and what happens if in u_m you change sup by inf

this would be just v_m then

[neat holly]

Maybe I overthought it. So the statements are still equivalent even with infimum instead of supremum?

[last timber]

i meant your statement is just this theorem restated for lower limit

anyway, point is that you have to show that for every eps > 0 there is convergent subsequence with lim = L in ]x_s, x_s+eps[

[neat holly]

Oh! I think I can do that!

Also, if I may ask, what does the format ]x_s, x_s+eps[ represent?

[last timber]

well, once you show that x_s is lower bound for set of subsequential limit it will show that x_s is its inf

]a,b[ is just (a,b)

i prefer ][ notation for open interval to not mix it with ordered pair

[neat holly]

Oh! Never seen that before, but that clears a lot of doubts on ordered pairs and open interval.

Let me see if I can get some sort of proof going. Thank you so much, again!

[last timber]

yw

[stray reef]

@last timber you prefer to impale yourself on the loose ends of these brackets

[last timber]

yes i do

[signal rampart]

Lets say f(x) goes from N -> R
and g(x) goes from N -> R.

Am I right to say that we CAN'T do f°g (composition) since the end result of f(x) doesn't match the starting point of g(x) since is R and N respectively?

[stray reef]

in general yeah you cant do that

[signal rampart]

Thx :D

[karmic nymph]

just need to confirm my answer (dont have solutions)

they arnt isomorphic cuz in G_2 4 and 3 have 4 nodes are of degree 4 and none of the nodes in G_1 are of degree 4

thus not isomorphic

confirm/deny anyone :)

[near prawn]

they arnt isomorphic cuz in G_2 4 and 3 have 4 nodes are of degree 4 and none of the nodes in G_1 are of degree 4
what?

[karmic nymph]

am i totally wrong?

[near prawn]

more like that sentence isnt legible

[karmic nymph]

(sorry for bad english)

im really bad at english

but

what

i mean

you see nodes 3 and 4 in G_2

they are of degree 4

[near prawn]

no theyre not

[karmic nymph]

omg

they arnt

[near prawn]

check again

yep theyre degree 3

[karmic nymph]

rip

lemme try again

they are isomorphic then

correct?

@near prawn

[near prawn]

idk did u come up with an isomorphism?

[karmic nymph]

wdym

like set up a function?

[quaint star]

Yes, if you say they are isomorphic, you should be able to create an isomorphism between them

[karmic nymph]

i can create an isomorphisn with a function tho?

[pale epoch]

a graph isomorphism is a bijection between the nodes

[karmic nymph]

so function i get should be a bijection ? @pale epoch

[pale epoch]

at the very least, yes

there are more requirements for a graph isomorphism

[karmic nymph]

what does the 2nd and 3rd point mean

[pale epoch]

that its also a bijection between edges kinda

if {x, y} is an edge in one graph, then {f(x), f(y)} is an edge in the other and vice versa

[karmic nymph]

i see

are those the only 3 requirements then

[pale epoch]

yes

for this example i would first try to draw the left graph differently

switch b and d to get a 'square'

and then move f and c inside

should be easier to see then

[karmic nymph]

so you try and make it visually the same

[pale epoch]

ye

[karmic nymph]

hm ok

ill keep that in mind

[pale epoch]

remember, the drawin is arbitrary

[karmic nymph]

ye

[pale epoch]

and the given drawing of G_1 is kinda ugly imo

too many crossings, makes it hard to check for isomorphism invariants

[karmic nymph]

ye

[signal rampart]

When the question asks to find the simplest g(x) function of the same order as f(x) such that f(x) O(g(x)). I'm having a really hard time reducing this whole function. Like I don't see anything to factorize that would be useful or any properties that I can directly apply.

[spice cloud]

any idea on this?

im thinking pigeonhole

[weary tiger]

can't guarantee I'm gonna be much help, but what does make a line mean here? there will be some 3 in a row, diagonally, horizontally, or vertically, such that all 3 are either all black or all white?

[vast narwhal]

There's only so many slopes of lines allowed, maybe that helps somewhere?

Oh snap I think that does it

[tawdry pasture]

can't guarantee I'm gonna be much help, but what does make a line mean here? there will be some 3 in a row, diagonally, horizontally, or vertically, such that all 3 are either all black or all white?
@weary tiger i think what it means is that even though there isn't a straight line of black dots, there will exist 3 separate pairs where two black dots will have an empty white dot between them that connects the black dots to make a line

[weary tiger]

I don't think I understand

[weary tiger]

can i get help with this question

[minor dagger]

alright for part i do you have any ideas what the elements of each set will be?

what values of x satisfy 1<x^2<42

[urban olive]

I need to convert this to non canonic CNF

How can I start?

[minor dagger]

try to focus on the inside before distributing the negation

[urban olive]

So focus on q => r ?

@minor dagger

[minor dagger]

do you know a statement logically equivalent to q implies r

[urban olive]

I could use one of this I guess

[minor dagger]

yes you can

[urban olive]

Lemme try then

[minor dagger]

not p and q

and then you can break the biconditional down into conditionals

and use the logical equivalence on them

[urban olive]

Alright

Let me see

[rugged pebble]

how do i find reflexive closure

[compact orbit]

Can any one help me do this?

[urban olive]

@minor dagger is this right?

Looks like I got the CNF

[compact orbit]

Can any one help me do this?
@compact orbit I want to covert this to non canonic CNF

Can any one help me do this?
<@&286206848099549185>

[rugged pebble]

what is the transitive closure of this {(a,a), (a,c), (b,a), (c,a), (a,1), (1,2)}

i got (a,2) (c,1) (b,c) (c,2) (b,1) and (b,2) but not 100% sure

please @ me

[mystic moss]

@rugged pebble (c, c) would also work right

[rugged pebble]

for which two?

[mystic moss]

(c, a) and (a, c)

[rugged pebble]

oh, you can do that? even if it goes back to itself?

i thought pairs that are the same count

[mystic moss]

i mean, doesn't transitivity mean that if a*b and b*c, then a*c

[rugged pebble]

ya

[mystic moss]

replace a and c with (c) and b with (a)

it should work, i think

[rugged pebble]

hmm

ok then that would mean

(a,c) also

[mystic moss]

hm?

[drifting pewter]

Does anyone know what B is

[last timber]

,rotate

[last timber]

well thinkof it

[stray reef]

no

presumably there is a universe of discourse here

do you have the problem exactly as stated

the "only" is whats tripping me up

yeah but P & G says nothing of everyone else

yea

i mean idk you could have sth like

E: someone else has been caught by the police

and then it'd be P & G & !E

[drifting pewter]

Did anybody understand my question?

[glacial flame]

@drifting pewter This Venn diagram?

[drifting pewter]

Yes @glacial flame

[glacial flame]

What is your attempt

To find the smalles central area you have P^Q^R ^=intersection

Making a complement of that will give you everything but that small shaded area, and intersecting that with P again, will give you everything in P without that small shaded area.

So (P^Q^R)c ^ P gives you everything in P but that small central shaded area. That is this formula gives you the unshaded area on the picture.

You are asked to get the shaded area, so you need to complement all that once more and that is your final solution.

[drifting pewter]

My attempt had P complement in it but I realized it couldn’t be P complement if part of P is shaded

[glacial flame]

So my solution is clear to you?

[drifting pewter]

You said it’s (P intersect Q intersect R) complement intersect P

So put all that in parentheses and complement it

[weary tiger]

hi so does anyone know how to do a turing machine that returns x if x >= y, and y if y > x? i found a few similar examples online but couldn't tell if they returned x when x and y were equal (e.g. https://www.geeksforgeeks.org/turing-machine-to-accept-maximum-of-two-numbers/)

[mystic moss]

@weary tiger as far as i can tell, they return y when x and y are equal in that example. you can just change the order in which you search, though, and you'll get the opposite result.

[weary tiger]

@weary tiger as far as i can tell, they return y when x and y are equal in that example. you can just change the order in which you search, though, and you'll get the opposite result.
@mystic moss oh thanks, how do i change the order though?

[mystic moss]

search for a 0 on the right side first

(@weary tiger)

[weary tiger]

search for a 0 on the right side first
@mystic moss oh okay and how do i do that? sorry

im kinda lost

[mystic moss]

i think you can just start in q1 @weary tiger, maybe.

[weary tiger]

hmm maybe let me see

[lethal sequoia]

Hi can someone help me understand the answer to this question?

6d

I don’t get it from this sentence: “but in any such coloring, at most k-2 colors appear on the neighbors of v”

Do they mean that since we assumed that there is a vertex of degree k-2 or less that, by definition of k crit, we have neighbors with at most k-2 colors?

[lethal sequoia]

<@&286206848099549185>

[meager verge]

Can someone verify if this answer is correct?

[coral raven]

pain

[glacial flame]

@meager verge Can you explain what is the question and this table?

[inner veldt]

any hints?

[vast narwhal]

@meager verge I think that looks right

Unless the booleanification of your Heyting algebra is nontrivial...

nah jk

[near prawn]

the sum of all the elements is 465 @inner veldt

[coral raven]

no it's not

465?

[inner veldt]

lol yeah

[near prawn]

my bad

typo

[coral raven]

i don't intuitively see how to go from there tho

[inner veldt]

465, but then what? I thought about looking for a bijection but haven't found much

cuz like 465 - 232 = 233

but huh

[near prawn]

well if u take any subset

either the set or its complement will have a sum larger than 232

very useful fact right there

[inner veldt]

I also saw that this subsets should have at least 9 elements and at most 21

oh Ic

okay

will go on from there

thanks

[mortal wing]

Can someone help me understand this? Is it saying that each digit in '00000' is a set with two possibilities, hence 2^5?

[stray reef]

when constructing a bitstring of length 5, you have two options for each bit (0 or 1)

(kind of by definition. thats what a bit is)

[mortal wing]

Gotcha. Thank you! I'm new to all this. Just started a CS degree

[wind idol]

Hello all, just joined, I have a very basic "Big O" question, f(x)= x^2 and g(x)= 2^x, i know g(x) is the upper bounded equation, but how would u say that correctly in big oh format?

would it be g(x) is big O f(x)?

[stray reef]

no

it's the other way around

f(x) is O(g(x))

[wind idol]

thank you (:

[stray reef]

g(x) is the upper bound, not the upper-bounded

[mortal wing]

Could someone help me understand this? Does 'u' under the recursive definition represent any possible 'string'? As in, it could represent 'a', or 'b', or even 'ab'?

And lambda I believe just represents 'nothing'?

[stray reef]

lambda represents the empty string

u represents a string in S

[mortal wing]

by 'string' does it have to be just a or b, or can it be any combination of a's and b's together?

[stray reef]

strings do not have to consist of only a single character

would be kinda boring if they did, no?

[vast narwhal]

there's a bunch of strings listed above. The alphabet is the stuff with single letters only...

[stray reef]

the alphabet has the letters

which sounds obvious and tautological

and it kind of is

[vast narwhal]

well, it's a primitive object

start going anywhere but up with them, you just go in circles, logically, lol

Or at least I do, when I don't realize I'm trying to get something to imply an axiom or definition, lol

[stray reef]

sometimes people overthink things

[mortal wing]

Thanks friends. Feels like i'm asking the obvious but it's nice to have affirmation ❤️

[brave lava]

https://i.imgur.com/RA1kFJ2.png

can anyone check this

Im confused if it should be i < n

or i <= n

[stray reef]

<=

you want the loop to run another iteration to add n

[brave lava]

Thank you.