discrete-math

[dire stag]

Separate the 2b+11 into:

2b+10 +1

then factor

2(b+5)+1

[fossil mural]

yep that works
well that proves that 3n is odd but it is true that if 3n is odd then n is odd

[dire stag]

Alright, thanks a lot! I think hat I've got it from here. :)))

[lone verge]

T(x): x is a tiger
C(x): x eats chocolate

What is the difference between saying

1. There exists x, such that T(x) implies C(x)
2. There exists x, T(x) and C(x)

[rugged dock]

There exists an x such that if x is a tiger than x eats chocolate. There exists an x such that x is a tiger and x eats chocolate.

Indeed, for the first one we can have x not be a tiger but x still eats chocolate.

[sand pelican]

Does there exist a simple closed formula for Stirling number of 1 kind?
$\left[ \begin{array}{c} n \ k \end{array} \right]$

[vital dew]

Mike Tuan

[fossil mural]

if you imagine replacing C(x) with false

"T(x) implies false" is just "not T(x)", so the first expression is "exists x such that ¬T(x)"

"T(x) and false" is "false", so the second expression is "exists x such that false" which is obviously false

[hidden totem]

dont think so

[north swan]

how is the set of complex numbers defined

[brave rock]

Typically just as R x R with a new addition and multiplication.

[near kiln]

Is the word "form" a permutation or combination?

[brave rock]

"Formed" means neither. Note a word has order.

(I.e., the word you need to interpret here is, hilariously, "word.")

[weary tiger]

Who the fuck define R like that

[brave rock]

That's not how the reals are defined.

[north swan]

wait I'm dumb

shit mb

[brave rock]

How is one supposed to construct the set of real irrational numbers without first constructing the entire set of reals?

[agile magnet]

Equivalence classes of integers

[near kiln]

so it's a permutation? (since in permutation order matters)?

[brave rock]

Indeed the order matters.

[near kiln]

So? permutation? (I am kinda doubting myself since my friend thinks it a combination)

[agile magnet]

I wouldn't get too caught up on permutation vs combination

Let's just try to logic through and count

What choices do you have to make to form a word from the given characters (7 consonants, 4 vowels)?

[near kiln]

I used 7P4 and 4P2 since order matters

giving me like 2 set of the permutation of 4 consonant and 2 vowels, then I can just multiply it to each other

[agile magnet]

Ah but there are some things you aren't considering

First, you can repeat vowels and consonants

[near kiln]

what is it?

[agile magnet]

Second, you have to pick where in the word each letter goes

So let's figure out the latter question

Do you believe me that if you just choose where the 2 vowels have to go in the 6 letter word, then we know where the consonants have to go?

[near kiln]

I don't get it

[agile magnet]

Well we can only have consonants or vowels right?

If I pick the two spots for the vowels

Then I must have that the other 4 letters are consonants

That's what I mean

[near kiln]

2 vowels and 4 consonant?

[agile magnet]

Yea that's what the question says

[stray reef]

can you?

[agile magnet]

Where does it say you can't

[near kiln]

My question is, about the question asking for permutation or combination?

[stray reef]

i had read the problem as giving you a set of scrabble tiles like BCDFGHJAEIO

[agile magnet]

aabbbb is a valid word is it not?

[stray reef]

the question isn't clear about that imo

[agile magnet]

I think you can repeat letters, that's what I'm going with

It doesn't specify so I guess I'm making that assumption but you have to make an assumption either way

[agile magnet]

What I'm saying is that you shouldn't get caught up in those terms, you should try to logic out the answer

[agile magnet]

So does what I said here make sense?

[near kiln]

yes, I know, but first I really need to know if I am wrong here or not?

[agile magnet]

We're going to get an answer at the end of this

And then you can compare that to the number you and your friend got

And see who was right

Ok so first choice we have to make is where the vowel goes, how many ways can we choose where the 2 vowels go out of the 6 letters in the word?

[near kiln]

3?

[agile magnet]

How did you get that?

[near kiln]

Just a guess since you're talking about where to put the 2 vowels in 6 letter word

[agile magnet]

Well let's not guess since there are infinitely many numbers we could guess from, let's try to count it out

You want to choose 2 spots out of a total of 6 spots

Order doesn't matter right? We're just choosing which ones are the vowels and which ones are the consonants

So what formula do you think we should use?

[near kiln]

Ohh It can go like 1,6. 2,5, 3,4, etc

[agile magnet]

yea yea exactly

[near kiln]

So it is a combination?

[agile magnet]

Yea, so what would the answer be for just this part?

6 total spots, wanna choose 2 of them for vowels

[near kiln]

6C2?

[agile magnet]

Yea!

Ok so now we've chosen where the vowels go

So for each of the vowel spots, how many letters can we pick from?

[near kiln]

letter you mean consonant?

[agile magnet]

Well we have 2 spots for vowels and 4 spots for consonants

So in each spot for a vowel, we have to pick a vowel to go into that spot, right?

So how many choices of vowels do we have for each vowel spot?

[near kiln]

yes, there's 5 vowels

[agile magnet]

You mean 4?

[near kiln]

oh 4 wovels

[agile magnet]

In the context of this problem there are 4 vowels not 5 like in the English language

[near kiln]

my bad

[agile magnet]

Yea

So we have to make that choice twice, and so it's 4^2

4 for the first vowel spot

4 for the second vowel spot

(I'm assuming we can repeat letters)

Make sense?

[near kiln]

elaborate

[agile magnet]

2 vowel spots right?

Each one, we can pick one of 4 vowels

[near kiln]

yes

[agile magnet]

So there's 4 choices of vowels for the first spot

And 4 choices of vowels for the second spot

So a total of 4^2 ways to choose the vowels for the 2 spots

[near kiln]

let's say we have a row of combinations and each rows needs 2 vowel and the choices are 4

[agile magnet]

idk what a row of combinations means

We're just choosing which vowels go in our 2 spots

And so there are 4^2 ways to do that

[near kiln]

just my way of visualization

[near kiln]

why is that?

[agile magnet]

Please read what I wrote here

And then apply the same logic to find how many ways there are to pick the consonants

[near kiln]

I cannot visualize it

[agile magnet]

And then multiply the number of ways to make all the choices we've made (where to place vowels * what vowels to use * what consonants to use) and you'll get your answer

I have to leave now, sorry

[near kiln]

It's okay

[analog tinsel]

hi everyone!
This is a proof turans theorem for the number of edges in an extremal K_k+1 free graph on n vertices.
It is in german but I think my question can be understood with the math part only.
I am not really familiar with the cauchy schwarz inequality that is used here. I read some stuff on it on the internet but couldn resolve my question.
Why is <a,b> = n , the number of vertices , here ?

what even is <a,b> in the context of graphs `?

oh no nvm I just didnt use my brain

sorry

[twilit sundial]

im not confident on my answers for most of these

currently i have

true, false, true, true, true, true, false?

a true by demorgan
b false since the right to left implication does not hold
c true by demorgan
d true by being able to exchange like quantifiers
e true for the same reaseon
f true
g false

[near kiln]

Why is he multiply it by 5!? I thought the 210 is number of all combination of 3 consonant and 2 vowel?

[stray reef]

imagine that the letters are Scrabble tiles

$\binom{7}{3} \cdot \binom{4}{2}$ is the number of ways to pick which tiles you use for your word, and $5!$ is the number of ways to arrange them into a word.

[vital dew]

|Ann⟩

[stray reef]

@near kiln

[near kiln]

210 is the tiles to pick (no need to know what wovel or consonant it is certain that there's always 3 consonant and 2 vowels) then there's 5! ways to arrange them

[stray reef]

you just said the same thing as me except in a clumsier way

[near kiln]

yeah, it's just from my understanding

[analog tinsel]

Can someone help me with this ?
In a proof for kuratowskis theorem (K5 and K33 subdivision free implies planar) the author first assumes the theorem is false, therefore there has to be a counterexample with minimum amount of vertices. So a graph that is K5 and K33 subdivision free and not planar , with the smalles amount of vertices possible.
Then it is claimed that this graph has to have connectivity at least 3.
The case for at least 1 is clear. But in the case for at least 2 they write :
H is only 1-connected, i.e. it has a separating node v. Let H1 be a component of H \ v and H2 = H \ H1. There are planar drawings of H1 + v and H2. We can make a face incidend to v, from H1+v, be the outer face and then combine the drawings as shown in Fig. 32.2
My question : how can we be sure that there is a drawing of H1+v where v lies on the outter face ?

[stray reef]

imagine that the graphs are drawn on a sphere instead of the plane

and then you rotate the sphere so that the face incident to v also contains the north pole, and project stereographically onto the plane

alternatively: start with any planar drawing of H1, then project it stereographically onto the sphere, then do the rotation as i described @analog tinsel

[analog tinsel]

thank you very much. I am quite bad at imagining this but I have heard of this process before. But it definitely helps. Thank you !

[analog tinsel]

This is from a proof for kuratowskis theorem again. The question is : Does anyone know what the partial derivative symbol here for ∂F_e is supposed to mean ? It was never introduced anywhere and suddenly appeared out of nowhere. Is there some canonical meaning of it that I dont know ?
Now let e be a 3-contractible edge, this exists according to Lemma 32.2. Now H /e is 3-connected and because of Lemma 32.3 also free of K3,3 and K5 subdivisions. Due to the minimality of H, H /e cannot be a counterexample. Therefore H /e is planar. We now consider a planar drawing of H /e. With F_e we denote the plane in the induced drawing of ¨ H /e - v_e in which v_e lies. We know that ∂F_e is a simple cycle C, because otherwise we had a separating node.

H / e is the graph resulting from the graph H with the contracted edge e , if that has any relevance to it

[muted moth]

I've been working on Dirac's theorem on Hamiltonian graphs, that every simple graph on n (>= 3) vertices where every vertex has a degree >= n/2 is Hamiltonian.

I found its proof really difficult to grasp

it assumes a maximal counter example, graph G, that follows all the conditions of the theorem, but is still not Hamiltonian

the proof says that there exists a Hamiltonian Path between two vertices u and v of G, where u and v are assumed to be any two non-adjacent vertices

but haven't provided a reasoning behind the existence of such a path

why should there exist a Hamiltonian Path between u and v?

[muted moth]

yeah, i figured it out!

understood the proof now

[weary tiger]

is this the arithmetics channel?

[gilded sun]

Could someone help me with this problem?

[hidden totem]

do you know what the degree of a vertex means?

[gritty garnet]

||degree of a vertex is the number of edges connected to it||

[stray reef]

@gilded sun do you still need help with this?

[near kiln]

This hurts my brain

[empty aurora]

The wording is so bad lmao

why "homochromatic" just say the same color 💀

[upbeat ruin]

Answer :
000
010
110
100

How do I get to this answer?

[near kiln]

I literally have to google that word. Do you have any solution?

[agile magnet]

Do you know what a gray code is?

If so can you tell me the definition?

[upbeat ruin]

Idk about the definition, I mostly just know the process of changing 0,1 but I dont know how it relates to this question

0,1 to 01,10,10,01 for example and so on

[agile magnet]

So the idea behind a grey code is that we want to number these binary strings such that as we move from one binary string to the next

We change exactly one bit at a time

So the problem wants you to fill in the remaining unused binary strings on 3 bits such that as we go from one to the next, only one bit at a time changes

So what could the next string after 001 be?

[upbeat ruin]

Couldnt it be either 000 or 010?

[agile magnet]

Can't be 010

There you've changed 2 bits! The last and the middle one

[upbeat ruin]

I see

But what about 100?

Ohhh

Nvm

[agile magnet]

100 changes 2 bits also

[upbeat ruin]

I gotchu

Hmm

[agile magnet]

So you know the next string s5 is 000

[upbeat ruin]

Then why couldnt 000 just switch back to 001

Or 100

[agile magnet]

Well we want to enumerate all 8 possible strings

So we don't want to repeat anything

[upbeat ruin]

I see

[agile magnet]

But you could do 100 after 000 that's fine (there are multiple ways you can complete this sequence)

You just can't do 001 after 000 since you already used 001

[upbeat ruin]

Ok I see

Ill try one more gray code and get back to you

[agile magnet]

Sounds good

[upbeat ruin]

I think i got it thank you

Did 1 more and got it correct

[agile magnet]

🔥

Gray codes are cool

[upbeat ruin]

Ya once i figured it out its pretty interesting

But when i didnt know how it worked i was just utterly confused

Thank you for your help

[dawn folio]

A={a, b, c} B={{a}, b, c}
the intersection of them would be {b, c} right?

[stray reef]

indeed

[dawn folio]

thx

[gilded sun]

Could someone help me with this problem?

specifically 2 part b

[stray reef]

2 part ii you mean? @gilded sun

[agile magnet]

use part i to solve ii

I feel like saying anything more would amount to just giving away the whole problem. If you actually say what you try after looking at my hint, that would be helpful

[stray reef]

i remember op asking for help finding the degree of a single vertex in a graph, and then when i asked if he still needed help with it, i got ghosted

[agile magnet]

meh if I get ghosted so be it

[abstract mantle]

How many six letter words can be formed using the letters of the word ALGEBRA, where the seven letters in the word are only allowed to be used once. I tried calculating the total number of six letter words formed using the letters of the word ALGEBRA, and thereafter subtracting the number of words where the A occurred two times, but got the wrong answer. Could anyone explain how to do this?

[agile magnet]

Can you elaborate how you did this because this should be correct

Errrr almost correct

Technically in every word the letter A appears twice

So just explain your working more

[abstract mantle]

Well, I think that the total number of six letter words formed using the letters of ALGEBRA is 6!/2! because you have to account for when A appears twice, and that the number of words where the A occured two times to be ((5)(4)(3)(2))/2, since if you include the A two times there are only 5 options left for the third letter, 4 options for the fourth letter and so on. So my answer would be 6!/2!-((5)(4)(3)(2))/2

[agile magnet]

Ahhhh ok so you're doing too much

Let's dig into 6! / 2!

Where did you come up with that?

[abstract mantle]

I would say because for the first of the six letters there are six options, since two of the A's are essentially the same - and then dividing by 2 in case 2 A appear in the same letter. But I'm guessing now that this is wrong

[analog tinsel]

I am so confused about why my T2 is not acyclic. In theory I understand that since T1 is acyclic, the graph induced on E(G) \ E(T1) has to have no cut of G, since T1 is a spanning tree. Therefore T2 has to be acyclic by duality. But why then is my drawing like this. Does someone understand what I am doing wrong?

[analog tinsel]

Ok sorry I just realized my drawing of G\T1 is nonsense

Ok ok nevermind

In the proof I read they, for whatever reason, decided to use the name T1 and T2 for sets of edges

That explains everything

[agile magnet]

ah but there aren't 6 letters, there are 7 letters!

If all 7 letters were distinct, the number of words would be 7!

but as you've correctly identified, in our case of ALGEBRA that overcounts the two A's being the same letter and so any permutation of those 2 A's actually counts the same word

so the answer is 7! / 2!

not 6! / 2!

[snow sleet]

@agile magnet @abstract mantle The answer is actually way simpler. Because the question asked to form 6 letters (each letter no more than once) from the word ALGEBRA, there must be exactly 6! ways of doing this since that word only has 6 distinct letters.

[agile magnet]

wut

oh bruh

I can't read

[abstract silo]

hi

i dont able to understand why discrete mathematics needed help me please by showing where used this stuff

[little prism]

well not sure what you think discrete math is

for example its a foundation of a shitload of computer science

[near kiln]

Show that given any 32 distinct integers, there exist two whose sum, or whose difference, is divisible by 60.

How do I answer this one?

[uneven violet]

I would consider two cases. First consider the case, where at least two of the integers have the same remainder when divided by 60. What can you say about the difference of these two integers?

[near kiln]

So I just pick any number and check if it is divisible by 60? (I am so dumb)

[near kiln]

Ok I think I get it now, what I did is basically just divide 60 by 2 giving me 30 : 30 and just move some numbers to the next side let's say 31 : 29 = so if I add it, then it is divisible by 60

[hidden totem]

just dont forget the edge cases

thats why its 32 not 31 or 30

[analog tinsel]

https://youtu.be/OZWZpQmGp0g?feature=shared

I hope posting yt links is not against the server guidlines. I just wanted to ask, does anyone think that this proof is incomplete? I saw a similar proof in university but it was a little bit more involved at the end. Here it is presented as pretty simple. I havent found any specific point to criticise but I feel like this is too simple. Does anyone have any thought on it?

[tardy finch]

i havent typed it out yet

but does this make sense

basically since any number 0 <= m <= n has a multiple in A
the product of all elements of A will be divisible by 0 <= m <= n

then n! factorial divides it

[cursive dew]

If i wanted to discover math from scratch, would discrete math be a good path?
I want to see the why of it 😄
Not just blindly follow predefined rules such as -a * -b = +ab

[twilit sundial]

it is generally a waste of time to go “from first principles” unless you already have a solid foundation in more advanced topics imo

[stray reef]

I hope posting yt links is not against the server guidelines.

never was

[weary tiger]

Why 2x or 2y?

Another solution for the general case in our textbook says 2 min(a, b)? Why the 2 and minimum function?

[stray reef]

x - y = (x+y) - 2y

y - x = (y+x) - 2x

[weary tiger]

Ok got it now.

anything about the 2 * minimum?

[stray reef]

when you replace x + y with |x - y|, you are subtracting 2 times whichever of x and y is smaller

[rare scaffold]

counterexample when n=4 and k=3

[tardy finch]

3, 4, 5, 6

one factor of 4

namely, 4

hmm

i think i may have used the wrong definition

should I have used permutations?

no its my mistake for using n choose k instead of k-permutations

the product of n-consecutive integers is divisible by n!

thats what I was going for kind of

I used that method for a different proof

the product of 5 consecutive integers is divisible by 120

yeah

[rare scaffold]

$(n-k)(n-k+1) \cdots (n-1)(n)$

[vital dew]

polya*

[weary tiger]

is there a way to visualize this. I am having trouble thimkimg about this with an example

[tardy finch]

why not just $(n-k)....(n)$

[vital dew]

aÿb

[tardy finch]

oh i see whats going on

[stray reef]

replace 5+3 with |5-3|, how much did the sum go down by

[weary tiger]

change, is the keyword. Thank you, got it.

[vital dew]

polya*

polya*

[vital dew]

polya*

[rare scaffold]

Note that n choose k counts all subsets of size k of a larger set of size n. Think about this discretely, rather than a divisibility criteria.

[vital dew]

polya*

[vital dew]

polya*

[near kiln]

What is edge cases?

[stray reef]

are you asking what the word "edge case" means generally, or are you asking what they are for your problem specifically?

[near kiln]

both

[stray reef]

basically an edge case is when something about your setup is either as small as possible or as large as possible

or sometimes when two things that usually aren't equal, are.

[thin galleon]

Can someone tell me why my answer is different from the given?

[stray reef]

$x_2 = 4k_2 + \mathbf{14}$, no?

[vital dew]

|Ann⟩

[stray reef]

and likewise $x_3 = 4k_3 + 11$ and $x_4 = 4k_4 + 12$

[vital dew]

|Ann⟩

[thin galleon]

I don't get it. I think x_2 can be 2. All x_i have to positive integers.

[stray reef]

oh my bad

i misread x_1 ≥ 11 as x_i ≥ 11

[tardy finch]

guys does this make sense
using bezouts lemma

if a | bc and gcd(a,b) = 1 then a | c

what I did was show that since a | bc, gcd(a,bc) = a
and not by bezouts lemma actually but another proposition, the gcd(a,bc) will divide any number
in the form ax+(bc)y

but the fishy part is this

if gcd(a,b) = 1 then a doenst divide b and b doesnt divide a
so b = qa+r for 0 < r < a

so ax+by = ax+(qa+r)cy

c = a(0)+((0)a+1)c(1)

so c is in the form ax+(bc)y
so gcd(a,bc) = a divides c

this feels a little mickey mouse

[lost stone]

how would one approach a formal proof for this?

[agile magnet]

What does your intuition say?

[lost stone]

some kind of argument along the lines of "pick an element, either it is least or you can pick a lesser element, repeat"
but I'm not quite sure how to prove you wouldn't cycle back
it's intuitively obvious based on antisymmetry and transitivity just not sure how to formalize that part

[agile magnet]

Ahhh but what if it does cycle back

What can you say about all the elements in that cycle in the order?

[lost stone]

if it cycles back it wasn't a partial order in the first place

[agile magnet]

Well no then all the elements are equal

[lost stone]

hm?
if there is a direct cycle A <= B and B <= A that violates antisymmetry, and if there is an indirect cycle then by transitivity you eventually end up at the same issue

[agile magnet]

So if you can form an arbitrarily long chain of distinct smaller and smaller elements

What contradiction do you get

[lost stone]

that it's not well-founded?

[agile magnet]

What do you know about A

[lost stone]

it's finite, but that doesn't mean it doesn't have a <= cycle

that part comes from the rules for a partial order rather than it being finite

I think

and I'm not sure how to formalize the idea that a partial order cannot have a cycle

[fossil mural]

it's impossible that $a_1 \leq a_2 \leq a_3 \leq \cdots \leq a_n \leq a_1$ (unless they're all equal)

[vital dew]

bee [it/its]

[agile magnet]

^^

Hence we can reduce to now forming a chain of decreasing elements where all the elements are distinct

[lost stone]

is that something I can just state then?

[agile magnet]

And you should be able to get a contradiction from here

Well you'd have to prove it but it's pretty obvious form it being a total order

[fossil mural]

well you can prove it by induction

[lost stone]

I guess yeah

[fossil mural]

for n = 1 it's trivial

then as the successor step just remove one of the intermediate elements by transitivity

basically you just apply that <= is transitive n times

[lost stone]

yeah I suppose so

so basically just "pick an element, either it is least or you can pick a lesser element, repeat", and then justify why you will reach a stopping point

[fossil mural]

yep

...although there is also a somewhat quicker argument

do induction on the size of A (which is valid because it's finite)

if there's 1 element then obviously that's the minimum

so now think about taking a total order that has a minimum, and adding an element to it

[agile magnet]

Yes but I think it's more instructive to see where the intuition took them

[lost stone]

not entirely sure if we'd be allowed induction

[agile magnet]

Why not?

[fossil mural]

yeah it is a good idea to work out how to formalise the intuitive idea, i just thought i'd also mention this quicker route i found

[fossil mural]

...i have no idea how you're supposed to prove anything about finite sets without induction

[lost stone]

probably would tbf we've just not had to use it before
we covered it briefly and it was never relevant to the questions
all our formal proofs were very first principles
"We have A, and we have B, therefore we have A and B", etc
but this is a "show" rather than a formal proof so it'd probably be fine

[fossil mural]

there isn't really anything you can do with the qualifier "finite" other than

1. induction
2. some statement you've already shown about the natural numbers or finite sets

[lost stone]

yeah fair enough

ok thank you this was very useful

I'm also now wondering if every partial order on a finite set is well-founded?

ah I guess they are

[wise ingot]

does anyone know some good material to study recurrence relation stuff?

like specific video tutorials or something

[gilded sun]

Could someone help me solve this?

[agile magnet]

what do you need help with?

do you know what a closed Eulerian trail is?

[gilded sun]

Yes, this is my logic: it is false, because there's 2 vertices that are not even. So it can't be a closed eulerian trail

[agile magnet]

ok so what do you need help with?

sounds like you have an answer, is it right?

[gilded sun]

Not sure, that’s why I wanted to check in

[agile magnet]

well you're using the condition that a graph has an Eulerian cycle if and only if it has a single connected component and every vertex is of even degree

and you identified there are some vertices with odd degree

so why would you not be correct lol

[cursive dew]

When do i know im ready for discrete math? I want a journey through the proof of math.
Also where do i start when im ready? Logic? Sets?

Logic and sets are my two words ik of this stuff, thats it XD

[ivory badge]

You can do it whenever

Consider the pinned pdf of Loch in #proofs-and-logic

[cursive dew]

looking through it, it seems to get complex pretty quickyly, im better off with things in slow steps, especially witha new field/concept, should i start with basic logic ideas? Or set info?

[cursive dew]

A tautologies is a truth table where all results are true?

[gilded sun]

Could someone go over this with me?

[rare scaffold]

Take $[ 0;\overline{3,3} ]$. Then solve, $\alpha = [0;y]$

[vital dew]

polya*

[stray reef]

do you still need help with this?

[rare scaffold]

im trying to figure it out

[stray reef]

im asking op if he still wants help with it

last 2 times i did that, he ended up ghosting

so don't say anything until he shows up :p

already did

with the reply

[cursive dew]

May i ask a question in the mean time if you guys are waiting for sonny's response? Or should i wait till later

[stray reef]

go ahead

[gilded sun]

Yes, I do. Can we discuss about this?

[stray reef]

ok right

do you know how continued fractions work? Y/N

[gilded sun]

yes

[stray reef]

ok

then can you write down the continued fraction [1, 4, 1, y] in ordinary notation?

in latex if you're able, on paper otherwise.

[gilded sun]

yes. I was working on the problem in he meantime. I have this thus far:

[stray reef]

you... could have shown this work

why didn't you

[gilded sun]

i was working on it

i did not have it complete when we were discussing/at the time I asked question. sorry

[stray reef]

hang on i think your equation is incorrect

$y = 1+\frac{1}{4+\frac{1}{1+\frac{1}{y}}}$, no?

[vital dew]

|Ann⟩

[gilded sun]

am having hard time seeing equation

oh

[stray reef]

and then i would have asked how you simplified that anyway

so unfortunately you're gonna have to redo it all now

[gilded sun]

😦 ok

[lime trench]

this is crazy, I'll solve it

[gilded sun]

Modified work based off of new equation. Better?

[stray reef]

hmm hold on

id like to see more detail on that simplification

let me retrace it myself...

i am not getting your cubic, and in fact not getting a cubic at all.

show your work for how you got that.

[gilded sun]

After the equation, isn't it the case that we multiply through by y(4y+5), to eliminate the denominators?

[stray reef]

what, straight away??

also you are framing it as a mandatory action, which it isn't lmao

[gilded sun]

to get y^(2)(4y+5) = y(4y+5)+y

[stray reef]

so you are able to instantly simplify that big nested fraction??

is this a single step for you?

[gilded sun]

what do you suppose i do

[stray reef]

simplify the fraction one step at a time before diving headfirst into multiplying both sides by whatever.

also you could have and should have said "yes i view that as a single step" or sth. i don't like it when my questions go unanswered

[gilded sun]

Sorry, don't take offense. My notifications are silenced and sometimes im working on the problems. Is this better?

[stray reef]

now this matches mine

[weary tiger]

Lads how to Determine whether the relation (like x+y=0) is on the set of numbers (like integers real numbers so on) is an equivalence relation

[cerulean radish]

Look at the definition

[weary tiger]

Wdym

[cerulean radish]

The definition of an equivalence relation, can you state it?

[weary tiger]

So basically its relation that satisfies three properties which are Reflexivity Transitivity and Symmetry

[cerulean radish]

Right, so you verify those properties to find out whether a relation is an equivalence relation

[weary tiger]

Well i get that but i dont get how to find equalvence relation if the relation is x+y=0 for example when i try to solve it my brain freezes yk

How to kick start it

[cerulean radish]

Start by checking whether it is reflexive

Does x + x = 0 always hold in the given set?

[weary tiger]

Nope

[cerulean radish]

Right, so it's not reflexive and therefore not an equivalence relation

[weary tiger]

Quick question

Can you explain how reflective property work is used like the part that confuses me is the variables say that you get more than 1 variable it can became more challenging

[cerulean radish]

A relation R on a set S is reflexive iff xRx holds for all x in S

[weary tiger]

And how about the y in that x+y=0 shouldnt we do the same for y? Or we just ignore it

[cerulean radish]

If xRy is defined as x + y = 0, then xRx means x + x = 0

[weary tiger]

What made you take xRx? Like how did you come up with it

[cerulean radish]

The definition of reflexivity:

[weary tiger]

Oh yeahh

Alright then

How about symmetry

Ik its not relation

But say we take that property first

[cerulean radish]

A relation R is symmetric iff xRy implies yRx

[weary tiger]

So in case of x+y= 0

It means

X+y=0 implies y+x=0

[cerulean radish]

Yes

[weary tiger]

Which means it holds

[cerulean radish]

Yes, the relation is symmetric

[weary tiger]

I see

And as for Transitivity

I remember that its xRy and yRx in case of x+y=0

Then that means

[cerulean radish]

A relation R is transitive iff xRy and yRz implies xRz

[weary tiger]

Ohhh

z being 0 right?

[cerulean radish]

No, z being arbitrary

[weary tiger]

Arbitrary of the set?

[cerulean radish]

An arbitrary element of the set

[weary tiger]

I see

Then what to do to know it it hold or not

this part confuses me the most

[cerulean radish]

In this case, transitivity says x + y = 0 and y + z = 0 implies x + z = 0

Do you think this is true?

[weary tiger]

Yes because if x and y can hold it wouldnt make sense for z to not hold

Like if x and y is true then z has to be true

[cerulean radish]

Try proving it

[weary tiger]

I see

Its false

@cerulean radish much appreciated

[rare scaffold]

x + y = y + z = 0

we derive it from that algebraic prescription

[cerulean radish]

||There is no proof of transitivity for that relation||

[rare scaffold]

this is the sort of problems in real analysis

where is the contradiction?

[cerulean radish]

The proofs in real analysis are nothing compared to this

[cerulean radish]

Consider x = z = 1 and y = -1

[rare scaffold]

fixing x sets a unique y

[cerulean radish]

Right

[rare scaffold]

so x must be z. x and z are supposed to be distinct?

[stray reef]

for what purpose

what are you trying to (dis)prove the transitivity of?

[cerulean radish]

x and z must be equal, yes

[rare scaffold]

if x y and z are all distinct then the relationship is not transitive

because x must be equivalent to z

[cerulean radish]

Of the relation R defined by xRy iff x + y = 0 (probably defined on the real numbers, or, at least, on a nonzero ring)

[rare scaffold]

there's probably a more careful statement behind it. but that's my sketch

[cerulean radish]

I don't see why being distinct is of any relevance

[rare scaffold]

so if fixing x sets y then there exists some z for which x + 2y + z = 0

[cerulean radish]

The existence of z is in the premise though

[stray reef]

you have a big misunderstanding

the definition of transitivity has all three letters under a forall quantifier

∀x∀y∀z : (xRy & yRz) -> xRz

so "if x, y and z are distinct" in our case implies "the premise xRy & yRz is unsatisfied"

therefore this is not grounds to decry R as not transitive

[cursive dew]

what is an axiom compared to logic(propositional logic)?

Learning about propositional logic but idk how i can use it, or what i could use it for

[brave rock]

An axiom is just a proposition that we call an axiom

There is no material difference; only the communication that we are assuming it.

It is comparable to the difference between a theorem and a lemma :)

[cursive dew]

is there no such difference between if and only if and only if?

cant find any symbols for the difference if so

[stray reef]

A only if B technically means A => B, while A if B means A <= B (because it is a syntactically inverted version of if B then A)

seeing an "only if" on its own is very rare

[cursive dew]

seeing more examples i see how this can be quite odd.
The "If raining, then ground is wet"
Can it be rewritten as "The ground is wet if its raining"
and "its raining only if the ground is wet"?

feels like theres 3 ways going on here... if A then B, A if B and A only if B(not keeping order here)

[gilded sun]

can anyone help me with this problem, specifically if my answer to part 2 makes sense?

I get this

[patent marlin]

i need help with this i’ve been stuck on it for a bit

[pallid swift]

From what I can see, a digraph is a graph with edges that have direction, a tournament is a complete graph with all edges being directed, and a score set is a way of labelling the vertices so that no matter which vertex you start on and which direction you choose, the numbers will always be increasing until you reach a dead end. Is this also what you've gathered?

[near kiln]

Suppose that n numbers are deleted in the set S={1,2,…,2005} such that among the
remaining numbers, no number equals to the product of other two. Find the smallest
positive integers n with the above properties.

how do I solve this?

[analog tinsel]

when people define stuff they usually write something like this :
Let G be a graph. G is called k-colorable if there exists a proper coloring of V(G) with at most k colors.

It always confused me why it was formulated as an if and not an if and only if . I mean this would leave the possibility to call a graph for which no proper k coloring exists a k-colorable graph, wouldnt it ?
I was reminded of this because recently I saw some definitions formulated with an iff .

Can anyone explain why it is ok to use the if then formulation instead of the iff formulation ?

[stray reef]

when we define a new word, we give it meaning

it is implied that this is an if and only if

that definition is what gives the word "k-colorable" its meaning

[analog tinsel]

yes I understand that

so people write it because implicitly it is clear that it has to be an iff ?

yeah thats what you said ig

thank you for the answer. Then I'll keep on accepting it, it is still a bit weird to me

[cursive dew]

still curious about this

[tawny sigil]

Hey, could anyone please help me with the below problem; I know we should think of the problem as the counting marbles problem. Like if you have red marbles and blue marbles in the bag. When you pick one red marble, try to see if you can a blue marble and vice versa. If you pick red but there’s no blue marble left to pick then red more than blue, same for blue. If you pick a red and a blue and the bag is now empty, it means red = blue. But I actually have no clue how to implement it. If anyone could help with the state transition table it would be much appreciated

[pallid swift]

I think "iff" should only be used when it must be clarified that it is the only condition that can satisfy whatever is being stated, for example in proof. Using "iff" all the time instead of "if" would take away from its meaning and make it much harder for people to understand the distinction of "this must be satisfied" and "this must be satisfied or else there is contradiction" but yes iff is valid here but not necessary

[final cliff]

One way to do this is to try and pair 1s with 0s while erasing symbols.

If there is only a 0 or a 1 on the tape and nothing else you would know whether the string had more 1s than 0s.

Otherwise read and erase the first symbol, if it was 1 scan down the tape and erase the next occurrence of 0. Likewise if it was 0 scan down the tape and erase the next occurrence of a 1.

Iterate on this process. Eventually you are left with a tape containing only 1s, only 0s or an empty tape.

If there are only 1s left your starting string contained more 1s than 0s. If there are only 0s left your starting string contained more 0s than 1s. If the tape is empty your starting string had the same amount of 0s as 1s.

Implementing this kind of thing is in general very tedious and depends on your specific formalization of turing machines.

There are a handful of formalization details for Turing machines that can vary from course to course so providing the particular state transition table is probably not something people here will be able to do for you.

[final cliff]

Also, fwiw it might be easier to do a state transition diagram first before the table and then using that diagram to construct the table after the fact.

The diagram approach lends itself much more to algorithmic reasoning imo than just doing the table immediately.

[cursive dew]

given that A and ~A are contradictory, are they also contrary to eachother?
I hear "a contrary can not both be true", so could a true/false be a contrary?

[final cliff]

There are also probably nitty gritty details you'd wanna look out for like ensuring you don't walk off the edge of the input indefinitely or that you don't accidentally chop the string into two pieces separated by a blank and forget to deal with the second half of the string etc.

You can do things like delimit the start and end of the string with your extra symbols. Shift the whole string left or right to fill the gap after erasing, instead of erasing with blanks you can "erase" via an extra symbol for example.

There's probably a bunch of other ways to deal with these kinds of problems so take my idea above more as a sketch of the algorithm.

[final cliff]

What do you mean by contrary to each other?

[cursive dew]

idk, just following this series: https://youtu.be/vdJjsqUPNAA?si=O7MI0XAW8hKCMMe4

[final cliff]

I'm understanding the meaning of contrary statements in the video as being two statements that can't both be true at the same time

You're thinking of it that way too right?

If that's what they mean then I agree with you.

[cursive dew]

i believe so

[final cliff]

Yeah, I agree. In math and classical logics we reject contradictory propositions.

[cursive dew]

so with that logic, can some statements be both contradictory and a contrary, such as A and !A?

[final cliff]

I think A and not A would be examples of this yes.

[cursive dew]

ty 😄

at one point im gonna find out how to include math into all this logic stuff then my fun is REALLY going to start 😄

[final cliff]

In math you would claim by contradiction A and not A can't both be true.

[cursive dew]

how would a contradiction work in math?
5 and 'not 5'?

[final cliff]

Well 5 by itself isn't really a proposition.

Like it doesn't really have a truth value in most classical logics I mean.

But 5=2 or ax=by+c do.

So, say you have A is the proposition 1+1=2

Then A and not A would be a simple arithmetic kind of example of contradictory claims.

[cursive dew]

would !A claim 1+1=2 is false?

[final cliff]

You're asking if "1+1 =/= 2" is false?

I'd agree in usual arithmetic with like reals and stuff

Oh if you are asking if !A is the claim "1+1=2 is false", then that is correct.

[cursive dew]

oh phew xD, got worried there

[final cliff]

I think the video is kind of conflating contradictory with being the negation.

Like, if I have a real number c and I refuse to tell you what it is, then c=2 and c=4 are propositions that are not the negation of each other.

For example if c is not 2, that doesn't mean c is 4.

But they can't both be true, and if c=3 both are false, so they must be contraries according to your video.

Most people in math would probably still call them contradictory though in normal arithmetic with reals fwiw.

They would just say c=2 is not the negation of c=4 (and vice versa).

[cursive dew]

so would that mean people may see the meaning of a negation differently in math?
c is 10, but propositions claim its 3 or 4, these are both false, therefore the contradiction of c=10(if they're ONLY seen as true/false)
versus, a more mathematical approach which i would assume would be c is -10

Logic seems easy but when our language is brought in it gets quite...fugly

[final ravine]

Can someone help

[cursive dew]

what does the 2 in the middle of the left triangle mean

[cursive dew]

Im confused, they dont claim anything about the consequent here:

but in their example they clearly negate that too right?

[final cliff]

I think their example is wrong.

[final cliff]

Here are some more examples/explanation that should be correct. Excuse the poor photo quality on my end.

The second (blurrier) photo cropped weird on mobile for me but if you click on it it should be readable.

They probably just mixed up that the consequent stays unnegated in your image.

[analog tinsel]

thank you !

[analog tinsel]

For the chromatic number if a graph there are two easy lower bounds. The maximum clique size and the number of vertices divided by the maximum independent set size.
Is there any reason one would be better than the other? I couldnt really find anything on this and couldnt really think of anything myself. I mean both can be arbitrarily bad, so Id say theyre equally as good. Does someone know why one could be better than the other?

[fringe gull]

Cant seem to figure this out

[prime flicker]

Hello, I really need some help with my discrete math homework. We are covering mathematical induction and I am stuck on two hw problems

Prove that for 𝑛 ≥ 2, 3^n > 2^n + 𝑛^2 − 1. I understand the base case, I understand what I need to solve for but I get stuck in the algebraic part of the inductions step

[agile magnet]

ok it sounds like you're in a good spot

can you send your algebraic work?

so that I can see where exactly you're getting stuck?

[prime flicker]

yes thank you, so heres the actual question

[prime flicker]

Here’s my work

[night fog]

How did you get this?

@prime flicker

[prime flicker]

through my inductive hypothesis

that i stated before the actual induction process

instead of an = it should be a > next to that line

[night fog]

ah

[prime flicker]

are you able to help with the problem?

[night fog]

maybe?

I'm not great at discrete math, mid way through an intro course.
I'm looking through it though

[prime flicker]

This is what I have now idk if it’s right tho

Idk how to deal with the -3

[stray reef]

two big typos that i see immediately

what did you do on this step btw

[night fog]

that is not adding up

[stray reef]

very much not adding up, yes

i do see a way to prove this, but it won't be via a chain of inequalities exactly.

i will share it if and only if you ask me for it @prime flicker

[prime flicker]

For this i split up the 3 to 2 and 1 and same for the 3k^2

[stray reef]

how did 1*2k^2 happen tho

would the "split" not result in 2 * 2^k + 1 * 2^k?

or does the Theorem of Bullshit guarantee 2^k = 2k^2 now

[prime flicker]

Yes please share🙏

[stray reef]

ok right

[prime flicker]

And honestly I have no idea but I have a problem in the book I’m using for the class and it’s VERY similar I just don’t know how to do any of the steps

this is it, basically the same expect for that -1 at the end

but i dont know how to solve for inequalities

[stray reef]

and then they just summon the -1 out of thin air to make the expression's value lower

anyway i do not think this is best described as "solving" inequalities (much less "solving for" inequalities -- you "solve for" a variable in one)

[prime flicker]

to make the statement even truer?

[stray reef]

no

no such thing as "even truer"

but if a > b thene surely you would agree a > b-1, yes?

[prime flicker]

yeah

[stray reef]

in any case, my idea is that you prove two smaller, "auxiliary" inequalities:

1. 2^(k+1) < 3 * 2^k
2. (k+1)^2 - 1 < 3(k^2 - 1)
   with these combined, you will have:
   2^(k+1) + (k+1)^2 - 1
   < 3 * 2^k + 3 * (k^2 -1) [with those]
   = 3(2^k + k^2 - 1)
   < 3 * 3^k [by IH]

[prime flicker]

This is what I did but I lowk just copied the problem

[prime flicker]

i will try it

rip i just sent the same photo lol

[stray reef]

do not just copy mine blindly.

[prime flicker]

i wont, tbh i dont understand it 😭

I understand the hw answer, but would it be wrong if I just add the -3 in the end? wouldnt n>=2 hold true still since it is still less than 3^k+1?

[stray reef]

but would it be wrong if I just add the -3 in the end?
i mean, you would end up not proving what was asked for...

[stray reef]

as i see it, you (a) don't understand it, AND (b) have decided not to ask me about the part(s) you don't understand.

[near kiln]

What do you call this topic where it is like exclusion inclusion principle but instead of set, you'll be given a number? question is something like this

"How many integers between 1 and 6300 inclusive are divisible by none 5,3,7? " I only see the one with sets and not this

[stray reef]

the topic is the same

if you actually wanted to ask "how do you do this": you'll have to make the sets yourself

[vapid cove]

Hi, can someone help me with modular arithmetic? Specially numbers with high numbers that you can’t do with a calculator, for example, 13678^666 in z_19

[stray reef]

well you can reduce 13678 modulo 19, for a start.

that one's calculator-friendly -- hand-friendly, even

@vapid cove do you still need help w that one?

[vapid cove]

I’ve just solved it, thank you though! I’ll let you know if I get stuck on another

[cerulean ore]

I am trying to solve this question: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/description
My initial bruteforce approach is completely naive and recursive.

The other way I am trying to solve this question is to think about this example: bbbbcccaaabbbb vs bbbbcccaaabbbbcc"
Best strings are "bca" and "abc" respectively.

So, if I greedily pick the elements in the first example: I would pick bca then, when I am at the last b I would think about cab which would be worse so, I will keep it as "bca" only.

Now, for the second example I would choose bca then if I choose b again it would lead to a worse answer therefore, I would not choose it. Now, if I choose c it would be bac, but the best answer is abc.

So, the thing is that I don't have much information when I stand at the latter sequence of Bs. So, I have to devise such a way that if I choose this b then it would help me when I will be working with c.

---

Other way I can think of is that I will store the indices with respect to each character.
Then, I will start from the a to z and try to build up the string. So, first example: I would choose a then the b after it, but then c would be the first one so it would give me cab and the best is "bca".

I don't want to looka the solution. Can someone please give me some hint? Thanks.

[cerulean ore]

Looks like it required stack and I had solved the same problem 3 years ago.:|

[near kiln]

It is, I just need to know if it actually have a different name for it (I was about to do some practice)

[vapid cove]

how would you do fraction powers in zn? e.g. 6^1/8 in z_19

[stray reef]

uh

@vapid cove yeah ok sorry i was busy

that amounts to solving the polynomial equation x^8 = 6

which. im not sure theres a clean way to do that that generalizes to all exponents.

[little prism]

factoring x^n-a over finite fields is pretty hard. even a=1

[stray reef]

this is not a math question, this is a vocabulary question. reread your textbook or lecture notes.

[static briar]

could someone explain how the congruence was rly reduced in the second last time, rly hate how theres no explanation

[errant bear]

what specific step

[static briar]

second last line

[vapid cove]

thats okay

how do they calculate 1 or -1 here?

[errant bear]

the second sentence of the solution you have 17x = 14 mod 55. the goal is to solve for x. to do this, you need to first find the inverse of 17 (mod 55). the inverse is found to be 13. now that you have the inverse of 17 mod 55, you multiply the whole equation by it. thus the coefficient in front of x gets canceled. now you just reduce 182 mod 55

you understand that a number times its inverse is the identity, right?

[static briar]

wdym by identity

just x on the left?

[errant bear]

what is 2 * 1/2

[static briar]

1

[errant bear]

1 is the multiplicative identity

[static briar]

ahh

[errant bear]

any number times the multiplicative identity is itself

this doesn't necessarily have to be 1 always depending on the scenario, but under normal circumstances it is

so 13 * 17 = 1 mod 55

hence they "cancel"

[static briar]

how would u go about reducing 182 mod 55

[errant bear]

just normal arithmetic

find the remainder when diiding 182 by 55

[static briar]

bet

[odd prism]

So I’m trying to solve this matrix game and I don’t see any dominations or saddle points

How do I go about finding a mixed strategy?

[cerulean radish]

What's matrix game?

[stray reef]

two players, P1 chooses a row, P2 chooses a column, the corresponding entry is the game value. P1 wants it to be high while P2 wants it to be low.

[dense briar]

How would i go about making an 8-bit ALU unit in labview?

[agile magnet]

I don't think this server could help with that

@dense briar try the Electrical Engineering server linked in #old-network perhaps

[dense briar]

Okay, ty

[cursive dew]

I was mentioned to learn propositional logic before getting further with deeper math understanding, when do i know i can move on next?
Also where do i go next? Set theory?

[errant bear]

set theory/intro proofs

[shrewd ether]

Prove that 1² + 2² + . . . +n² = n(n + 1)(2n + 1)/6 for all n ∈ N.

Help me

How I prove it 💀

[stray reef]

do you know induction?

[shrewd ether]

Yea I read on #help something like that and tried it

On #help-34 I send what I tried

But I got a problem

[shrewd ether]

@stray reef one question

If I cant reduce more the expression

Can I give values?

🤣🤣

I can prove it is right too

Lmao so I couldnt reduce more the expression but if I put a value for k

Then I get it

I simply thought if P(k) is true then the add is all P(k) +(k+1)² so it must be equal to the expression of (k+1)

[empty vale]

what's the right tool to solve this problem "there are 3 routes from B to R, 4 distinct routes from R to S, 2 from S to C. How many distinct routes are there to go from B to C while passing 2 distinct elements?"

is this a combinatorics problem?

@shrewd ether is that exercise 4 a-) from the 2nd guide of algebra?

if so, you and i may be studying on the same course, lol

[empty vale]

anyways, my solution for this was 3 (B to R) times 4 (R to S) times 2 (S to C) = 342 = 24

but i'm not really sure if this is the right answer

3x4x2 = 24

[agile magnet]

Seems good to me

Each path choice is independent

So you multiply the possibilities together

[empty vale]

right, thanks

[shrewd ether]

No idea, lt was just my professor's exercises no idea where that come from

[empty vale]

right, i just thought you came from the same course that i'm doing right now since you wrote your proof in spanish and were doing the same exercise i was doing 1-2 weeks ago

that one can be solved by induction by the way

[true condor]

would the ans for this one be option 1

[uneven violet]

Yes.

[weary tiger]

yo

[weary tiger]

sup

lads I got discrete math final tomro

any tips

mee tooo

actually?

nice

what topics are you preparing

hey can someone help me find the b fig question

graphs, trees, matrix, and boolean functions

wby

good luck bro

[weary tiger]

I am preparing the following:
topic 1 Logic & Proofs
Topic 2 Boolean Algebra & Combination Circuits
Topic 3 Basic Structures
Topic 4 Induction
Topic 5 Counting & Discrete Probability
Topic 6 Relations, Graphs & Trees

[weary tiger]

havent reached to that topic yet

[weary tiger]

apperciated you too

[weary tiger]

oh shey alr

[weary tiger]

i finished logic nd relations in prev sem,

[weary tiger]

yooo

cool

how about induction

havent studied tht

have you learned pre order ?

[weary tiger]

pre order?

yes in trees

I did a lab about it

oh alr

but that about it

funny thing is we didnt do lecture about Relations, Graphs & Trees

and we're getting tested on it

because yk eid holidays and what not

by the time I reach that topic I will try to solve ur question

yes thankyouuu

np more practice for me yk

which course?

yess yes

discrete structure

cool

u are doing ug in discrete struc?

this course is painful in a lot of ways lmao so many new concepts to learn in few weeks

its fun a course but in same time squashed

yeh ik ik for me its a sub , and its like this

[weary tiger]

yep

I better get back to studying

cyah

see you

[lyric quartz]

I have a question about notation of specifying elements in symmetric groups. For now my book uses a matrix of two rows that specify how numbers are mapped.

In some other sources I see notation like (1)(2 3)(4 5 6), can someone translate this for me?

[little prism]

its called cycle notation

it tells you that 1->1, 2->3, 3->2, 4->5, 5->6, 6->4

you always look up where a number is and then it gets sent to the one next to it

[lyric quartz]

oh that is straight forward, thank you 🙂

[little prism]

unless its at the end of cycle, in which case it gets sent to the first one

[pearl ermine]

hello i have a problem in understanding the principle of inclusion eclusion, can someone help me with it?

[stray reef]

are you looking at a particular problem or trying to understand it in general?

also, how many sets? 2, 3, n?

[pearl ermine]

tbh i am confused on how the formula works out beyond 3 sets, i have manually tried and investigating why the formula works up untill sets of 3, but when it goes beyond like 4 sets (extending upto n sets), i dont understand why specific additions are put in place like the subtraction of ∣A ∩ B ∩ C ∩ D∣ and again adding or subtracting ,etc. I even checked for higher sets like 5 ,6 and they seem to work flawlessly, but i have no clue how, or why those alternating addition and subtraction of sets are there.

[stray reef]

well you can kinda think of the additions and subtractions as repeatedly correcting for over- and undercounting elements which belong to exactly k of your sets

formally you can tie it, ultimately, to $\sum_{k=0}^m (-1)^k \binom{m}{k} = 0$

[vital dew]

|Ann⟩

[stray reef]

(which itself follows from the binomial thm)

[pearl ermine]

"well you can kinda think of the additions and subtractions as repeatedly correcting for over- and undercounting elements which belong to exactly k of your sets" -> this is the abstraction that i've been trying to unravel for the past 2 days, why is this the case, i mean i have heard it and it just works, without any intuitive proof (like the proofs for total count in 2 sets or 3 sets) of any sort.

[zenith moth]

We denote E = 1 + delta (i.e. the triangle symbol).
I understand delta signifies the change in a function but can anyone tell what does E signify?

E as in E.f(n) = f(n+h)

[pearl ermine]

i thank you sincerely for this valuable insight, but u did not clear away the abstraction, you just concluded with "by binomial magic once you get to the end you've counted it precisely 1 time", leaving the problem as it is, unscathed.

[stray reef]

shift?

[zenith moth]

Oh, its just shift? Ok then ty😅

[pearl ermine]

Heres the thing:

to count all of the elements in 2 sets: |A ∪ B|

it follows that |A U B| = |A| +|B| -|A ∩ B|,
since both sets can have same element counted twice, so the subtraction of the intersection makes up for that overcount, logical.

to count all of the elements in 3 sets: |A ∪ B ∪ C|

it follows that |A U B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|,
since any other set can have the same element as the other, they may be counted counted twice, so the subtraction of the intersection makes up for that overcount, but when we subtract -|A ∩ B| - |A ∩ C|, and if an element is present in all 3 sets, we are reducing it to 1, 3-2 =1, but keeping in mind that same element is also removed for |B ∩ C| (to correct for duplicates across B and C), it removes the remaining 1, 1-1 = 0, so to correct for that we add |A ∩ B ∩ C|, as it is evident that if an element is not present in all 3 of them, it wont see the fate I just mentioned.

this type of intuition, every step being broken down into easy to comprehend and analysable bits

I apologize if they seem clumsy, but thats the best way i could word it out.

[copper steeple]

Hey can i get some help over here

A circle with the center lying on the hypotenuse of a rectangular triangle ABC touches the legs AC and BC at the points D and E, respectively, so that AD=3 cm and BE = 1cm Find the magnitude of the angle BAC.

Answer is 30 degrees

But how do we get to it?

[stray reef]

#geometry-and-trigonometry

[copper steeple]

Ok thanks

Wrote there

[mental mirage]

cant u just induct

to write a formal proof of that

[vivid osprey]

I have a basic doubt. Let $A_i$ and $B_j$ be arbitrary sets indexed by $\mathbb N$. Consider the identity $$\bigcup_{i\in \mathbb N}A_i \times \bigcup_{j\in \mathbb N}B_j = \bigcup_{i\in \mathbb N}\bigcup_{j\in \mathbb N}(A_i \times B_j).$$ The two unions on the right confuse me and I wonder if one can treat them as two "sums", i.e. can I write this like $$\bigcup_{(i,j)\in\mathbb N\times\mathbb N} A_i\times B_j,$$ and say it's a countable union since the index set is $\mathbb N\times\mathbb N$?

[vital dew]

Philip

[vivid osprey]

great 👍

[frosty wedge]

This is a worksheet for a class called Problems and Solutions. I am struggling to find a tutorial on YouTube which explains how to do this worksheet.
The closest I have found is from Abdul Bari. Explanations on YouTube I have found so far don't satisfy the nature of the questions.

I met up with my lecturer and he explained that only the exponents need to be paid attention to because they will affect the speed not entirely sure

this worksheet is for a maths computer science class

More from my lecturer

He said this slide would help me the most but IM still trying to make sense of it

[zenith moth]

Cryptography: Can someone check if I am doing this right? And also how to we take the mod of really big numbers like (1858)^1949 (mod 2537) as mentioned here?

[empty vale]

Can someone link material that has proofs regarding counting sets and the like?

We just finished with induction in my algebra course and were starting to do stuff with cardinality but i'm having a hard time coming out with proofs that requires counting sets

[weary tiger]

A graph with 4 vertices of degrees 1,1,3 and 3

Can anyone draw and send all the possible graphs of this

[stray reef]

!noans

[lofty cloud]

The purpose of this server is to help you learn, not to hand out answers. Do not ask someone to give you the answer directly.

[frosty wedge]

are there any youtube channels that you suggest to help in learning discrete math?

[cerulean ore]

What if there are multiple edges that are present in the MST produced by Kruskal T and some other MST T1? If {e1, e2, e3} are the edges that are there in T and {e4, e5, e6} in T1.
Then, let's remove {e4, e5, e6} and add {e1, e2, e3} in T1 and it becomes T2. Now, I have to somehow prove that T2 is connected graph.

[weary tiger]

Graph with five vertices of degrees 1,2,3,3&5

Is this a correct graph??

Just realised it's wrong 🥲🥲

[cerulean ore]

I would definitely write which vertex has what number of degree to improve readability.

[weary tiger]

Agreed
Will keep it in mind

[cerulean ore]

How it is wrong btw?

[weary tiger]

Oh wait it's correct 🤩🤩

[cerulean ore]

Write down vertex vs degrees to clear any confusion.:)

[weary tiger]

Better now?

[cerulean ore]

Let T2 be a tree after adding e1 to T1 and removing e4 - assuming that e1 forms a circuit with e4 edge. Then, the weight(T2) = weight(T1) + weight(e1) - weight(e4).
Now, weight(e1) <= weight(e2)
As e4 wasn't chosen by Kruskal algorithm because:
i) e4 was already existing in the T produced by Kruskal, but that's not true as it is in not in T.
ii) Adding e4 made circuit, which is not true because e1 wasn't existing already in the T.

=> weight(T2) <= weight(T1)
So, T2 is also an MST and T1 is as well. But T2 has more edges common with T than T1 which contradicts the assumption that T1 has most common edge between them.

What do you guys think about this proof? I am not really sure why still still assumption makes T an MST.

[pearl ermine]

@forest bear I don't understand how expanding (1-1)^n related , in short expanding through binomial theorem relates to the alternating adding and subtracting, ok here is a simple question, on what basis do you believe this formula holds true for sets greater than 3 or on what logic? (like the formula consisting of alternatingly adding and subtracting sets, that is supposed to give the total count)? Please do forgive me for my pestering behavior I am just trying to understand the whole mechanism of why the formula works the way it works.

[weary tiger]

Graph with 4 vertices of degrees 1,2,3 and 4

Is this a correct diagram?

[pearl ermine]

ok then on what basis or logic do you believe this formula to hold true for sets greater than 3, like with full certainty 100% confidence that the conclusion dictates every element will be counted once, can you demonstrate and elaborate kindly?

[pearl ermine]

exactly exactly, u pointed it out correctly i dont understand it why u all of a sudden pulled up binomial in this case, also what's up with the (1-1)? i didn't understand the part where u equated "This is equal to 0^k which is 0, but it's also equal to 1 - [the number of times I counted the element]".Please do bear with me for a while.

[short ridge]

does this answer seem right? for S composition R i thought it meant there exists some c s.t. (a, c) exists in S and (c, b) exists in R, however this is not consistent with the answer provided

like im thinking the answers should be flipped

[pearl ermine]

so 1− [the total count] equals 1, each element is counted exactly once in the original sets, despite the apparent cancellation in the expansion, so thats why the binomial formula holds true? How did u generalize -> taking an element in k of the sets, the number of times you count it is k - (k choose 2) + (k choose 3) ... ± 1 ? thats just an assumption right? then u are equating this with the binomial expansion of (1-1)^k, to prove the binomial method of adding and subtracting holds true for correcting the count of an element?

yes but how did u equate the binomial formula for (1-1)^n with 1 - [number of counts], first u have to prove that the binomial formula indeed follows the trend set by the counting and uncounting of elements that are common across multiple sets right?

[lyric quartz]

I got an exercise at the end of the chapter about dihedral and cyclic groups that asks to "construct" a group for every n > 0 with two elements g, h of order 2 such that the order of gh is n.
Now for triangles and up I found the two elements in the dihedral group that have this properties: f (flip) and fr (flip and rotate).

But does this also work for D_1 and D_2? I don't see how this visually works. D_1 and D_2 do not have any faces, right? So what does a flip even mean there.

No frf = ffr^{-1} = r^{-1} which has order n, also for uneven n

Or are you responding to me?

But the dihedral groups are not cyclic right...?

The order of the group, yes

Hm, but in my book the dihedrals are defined as automorphisms of rigid motions of regular polygons on R^2. Then flip or reflection doesn't make any sense

Wouldn't f and r be isomorphic in the groupoid D_2?

Ok, I get what you mean but don't understand it completely

[mental hull]

I’m having trouble proving this identity, I’ve tried algebra and looking at its relation to Pascal’s triangle but nothing has really shown promise to me

[pearl ermine]

@forest bear ah man I dont seem to get it then other than abstractions, can you link me some articles or videos that helped you / would help me understand this much better? i already lost hope in getting the intuitive proof of it so thats there.

[mental hull]

Can’t find any counterexamples either

[lyric quartz]

Yes, but for D1 and D2 that feels like the identity morphism which has order 1

Ok so then in D1 r = e and f /= e

[pearl ermine]

meaning other than accepting the formulas for what they are basically, and not looking under the hood, btw can you link me some articles or videos that helped you understand this thoroughly?

[lyric quartz]

So the book talks about morphisms from subsets A to B, but for D1 and D2 I have to take the whole space R^2 for A and B. Ok got it

Although aren't there infinite rotations in R^2... Now it makes less sense 😛

[mental hull]

I’d like some help on this identity if someone can spare the time

[lyric quartz]

I guess to make it easier, I can just pick figures with the same symmetries of D1 and D2, So something like a nonsquare rectangle centred for D2 and noncentred for D1. Can I do something like that?

Well if I don't allow translations, so not exactly 😛

how about a teardrop?

🥲

Or a smiley 😂 that's ismorphic to D1 right?

Thank you Eliza, I will have to let this rest now. Maybe the more abstract constructions will click later

They define a category with objects subsets of R^2 and morphisms "rigid motions", then the dihedral groups are automorphisms of the regular polygons centred at the origin

So yes, i get it's about leaving the n-gon where it was, but for D1 that is only a single point, right? Any linear transformation leaves the point at the origin, does it not?

ok

The "rigid motions" are not defined 😛

Well it says "such as translations, rotations and reflections"

Right. So does there even exist a "regular" 1 and 2-gon?

Right, because it uses functions on subsets of R^2 and then a point and line do not represent D1 and D2. But something like a teardrop and an ellipse do.

[mental hull]

Yeah it was that

I tried but missed it in my search for counterexamples

[lyric quartz]

So my book has only talked about the dihedral groups, but what if you look at the platonic solids. Are the only elements rotations along all the axis or is there also something like a flip/reflection in R^4?

Well I guess for the cube there is a reflection, that is not a rotation

Well I meant like in R^2 a reflection is like a rotation in R^3. And I guess reflections is R^3 are rotations in R^4?

Ok

Linear algebra was a long time ago... Not sure what that would imply

[cerulean ore]

What book did you guys follow during graph theory class? I am trying to self learn Maths and Reinhard Diestel's Graphy theory seems very difficult.

I studied about isomorphism around 4-5 years ago so this will take more than the time that I can give right now.

[urban girder]

Does anyone know how to solve such a recurrence?

It solves to O(sqrt(n)) but I am unsure how to solve this formally.

[analog tinsel]

I just finished a graph theory course so let me give you my experiences :D . Diestel is a very clean and good book but imo sometimes hard to read because a lot of the proofs are super compact and expect a lot of the reader , meaning, you wanna see a proof for this theorem ? Cool, go look up these 4 lemmas, then the proof follows directly.
Thats often not what one is looking for as these lemmas can sometimes then require understanding of other topics and so on.

Douglas B. West's book "Introduction to Graph Theory" was imo very good in explaining seemingly complex proofs and concepts in an easy to understand manner. I liked it a lot.
But still it is not perfect and for me didnt contain everything so in the end I had to look up a lot of random papers and paper like documents on the internet as well as fairly low quality youtube videos.

Then there would also be "Pearls in graph theory - A comprehensive introduction" by ringel and hartsfield. I didnt really study it , but it seems good as well

[analog tinsel]

however if youre a complete beginner to graph theory then maybe a book that is specifically designed for beginners would be more suitable for your purpose. Since also wests book requires at least some basic knowledge.

[analog tinsel]

also maybe you would wanna start with an introductory book to discrete mathmatics that discusses sets and relations as well as combinatorics and some basic order theory, and logic , if you havent been in contact with math for a while. Because basic things from these topics can come in quite handy for a lot of things in graphtheory.

[agile magnet]

There are a few methods to do this

You could try substituting the recurrence into itself that's probably the most basic straight forward way

So you'd get Q(n) = 4Q(n/16) + 2 + 4

And then subbing in again

You get Q(n) = 8Q(n/64) + 2 + 4 + 8

And this pattern continues

Can you generalize this pattern to after you substituted in the recurrence say k times

So you get Q(n) = {something} * Q(n/4^k) + {something else}

Where the things in { }'s are in terms of k

[zenith moth]

So what I'd do is replace n by 4^k. So now your new recurrence relation will be something like Q(4^k) = 2 + 2Q(4^(k-1)).
And you can also right this as A(k) = 2 + 2*A(k-1) which is pretty easy to solve

[pearl ermine]

hey are combinatorics possible with fractions like (3/2)C1 or similar? I mean are they valid and used anywhere in mathematics?

[stray reef]

don't use the word "combinatorics" to mean "binomial coefficient"

the top argument can be allowed to be any real number

$\binom{α}{k} = \frac{α(α-1)\dots(α-k+1)}{k!}$

[vital dew]

|Ann⟩

[stray reef]

you see this in the binomial expansion of (1+x)^α

the bottom argument is still an integer tho

[pearl ermine]

sorry, i meant the one in the format -> (3/2)C1, Are they valid and used anywhere in mathematics?

[stray reef]

i mean i thought that i did answer your question and then some

but i can repeat myself

[pearl ermine]

i didnt quite understand your answer

[vital dew]

Eliza.

[stray reef]

the answer is yes, the top argument of the choose function can be allowed to take non-integer values (which is not limited to only rationals either)

and that does find use

[pearl ermine]

ah thanks, because it felt confusing how one can choose 1 out of 3/2 elements.

[stray reef]

the "choose elements from a set" interpretation does not generalize to this.

the function itself generalizes, but this interpretation doesn't.

[pearl ermine]

ok then what does 3/2C1 mean if the "choose elements from a set" interpretation does not generalize to it?

[stray reef]

it doesn't mean anything

[mental hull]

Having trouble with this problem, I’m trying to find something within Pascal’s triangle that might give me insight but I’ve been unsuccessful

[viral crown]

here's a few ways i can think of:
||n^2 = (n,2) + (n+1,2)|| <-- probably the intended way
||show that the sum grows asymptotically like n^3/3 (integrals or difference operator) and use known values to find the coefficients for an arbitrary degree 3 polynomial|| <-- easy with calculus
||guess and check to find the formula and use induction (the guess and check part seems hard. i don't recommend this)|| <-- guess and check
||consider sum_{k=1}^n k^3 - (k-1)^3|| <-- little more analytic

[mental hull]

I’d rather not just have the solution

[viral crown]

none of them are solutions

they're big hints though

hm

[mental hull]

I know the geometric derivation but I want to do it in this combinatorical way the book seems to be pointing to

[viral crown]

do u want it to be "derivable" from pascal's triangle

[mental hull]

It seems to want the hockey stick identity used so yeah I think?

[viral crown]

okay

so

we can write pascal's triangle like this

1 0 0
1 1 0
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
so on and so forth
but this is (in terms of combinations)
(0,0)
(1,0) (1,1)
(2,0) (2,1) (2,2)
(3,0) (3,1) (3,2) (3,3)
(4,0) (4,1) (4,2) (4,3) (4,4)...

[mental hull]

Mhm

[viral crown]

from here it's easier to spot a pattern

look at the (k,2) column

do you see anything?

[mental hull]

No

[viral crown]

maybe its better written like this

[mental hull]

Not seeing anything

[viral crown]

0 + 0 = 0^2
0 + 1 = 1^2
1 + 3 = ?

[mental hull]

2^2

But what does that have to do with Pascal’s triangle

Oh wait I see it

Woah

[viral crown]

!!

so n^2 = ?

[mental hull]

(n choose 2) + (n+1 choose 2)?

[viral crown]

yep!

and iirc that will very well fit the terms of the hockey stick identity

[mental hull]

I’ll see what I can do with this

[viral crown]

good luck!

[mental hull]

Hmm it’s like a double hockey stick identity

Since all the terms are added twice except 1 choose 2 and n+1 choose 2

[viral crown]

sounds about right if i'm remembering the identity correctly

[mental hull]

Is 1 choose 2 0 or 1

0 I think but I don’t remember

[viral crown]

0

[mental hull]

Cool

Wow it just popped out perfectly

Very nice

[viral crown]

yep it's a cute proof

[mental hull]

Just proved that identity in Pascal’s triangle always holds for completeness so that should be it

[viral crown]

nice!

[mental hull]

Missed a small thing actually but I caught it!

[lyric quartz]

So yesterday I used the actions f and r for reflections (flip) and rotations in the dihedral groups. But in literature I see that s is used for reflection, is there any reason for that other than that it comes after r in the alphabet?

[viral crown]

notationally f is reserved for functions almost always

r and s are also commonly paired together

[lyric quartz]

ok, thank you

[lyric quartz]

Also another question about notation. Seeing elements f, g in G as automorphisms in a groupoid how is the composition g ∘︎ f written as a group operation? My book says fg is the main notation but on wikipedia it looks like it is written the same as composition of morphisms, gf.

[viral crown]

you should probably follow what your book says

for now, at least

[lyric quartz]

But it's kind of confusing when looking at other literature

And it says it the most common way, is that correct or was that something from the past?

[viral crown]

yeah, reading and understanding different notation is a skill everyone has to pick up at some point. hopefully this is the time for u!

[viral crown]

hard to say, i want to say i've seen both

[lyric quartz]

ok

[mental hull]

Yeah that’s what it was

I know it I was just having trouble deriving it

Also !noans

!noans

[lofty cloud]

The purpose of this server is to help you learn, not to hand out answers. Do not ask someone to give you the answer directly.

[merry storm]

oh sorry

but if other people have already helped u i just wrote the more common looking answer actually

[viral crown]

not sure what u mean; the answer is the same

plus my hints give a few methods of deriving it

[merry storm]

thats why posting it is not forbidden right

[viral crown]

what if someone else wanted to try the problem?

it's not forbidden

it's just in bad taste

[merry storm]

i mean if u already posted a solution

[viral crown]

i didnt

[merry storm]

oh

[viral crown]

neither did aradia

[merry storm]

yeah i see

[viral crown]

at most there are steps to work it out

but the final solution was never posted

its nbd js keep it in mind ig

[orchid widget]

How can Hypothetical syllogism rule can be used to establish the validity of the Resolution rule

[pale epoch]

how did you define "->"?

[orchid widget]

not(p) or q

[pale epoch]

use this fact then

[orchid widget]

This is what I have right now

but i'm not sure where I made a mistake

where did the (not)p or r go

[pale epoch]

im not sure what your goal here is even?

[orchid widget]

I was wondering if I needed to use Hypotheticacl syllogism rule to derive resolution rule?

[pale epoch]

thats what you want, yes

but you want to start with the assumptions of the resolution rule

i.e. p \lor q and \not p \lor r

[orchid widget]

oh so should I work from resolution to Hypo?

[pale epoch]

and then find a way to use hypothetical syllogism on this to prove q \lor r

you just rewrote what hypothetical syllogism means

[orchid widget]

ok let me give it a try

[pale epoch]

not quite, you have to prove resolution using hypo

not work from one to the other

[orchid widget]

if I assume that resolution is right, where would I implement it?

[pale epoch]

you dont assume its correct

you start with the assumptions (p \lor q and \not p \lor r) and then you prove q \lor r using only hypo

so you have to reword the assumptions in a way that you can use hypo

[orchid widget]

oh wait

so I do this?

[pale epoch]

yeah

[orchid widget]

ohhh I see, thank you so much

[pale epoch]

you should probably add \equiv symbols to line 2 and 3 tho