discrete-math

[pale epoch]

@summer gull

[honest zodiac]

hi Guys

am I in right place for Graph theories?

[kind tapir]

I think so.

[honest zodiac]

well, I don't know the format for question posting in this group

is there any?

or I should just start describing the question

[kind tapir]

Just start describing the question. Make sure you read #rules before participating in the server though.

[honest zodiac]

Okay. I am currently on graph edge improper coloring. Currently investigating case of complete graphs. I am trying to improve lower bound of t^(G) (the maximum number of colors, that graph can be colored).

I present the graph in matrice way, where in each cell I write the color of the edge connecting corresponding vertices

so the matrix symmetric

and if I want it to be improper each row and column of matrix has to be an interal

that's where i stuck, I mean, I think this problem should be famous and want to know if anyone has any info related to that.

[honest zodiac]

<@&286206848099549185>

[west zenith]

What is improper coloring?

And what is an "interal"?

[reef thistle]

interval?

improper probably means you are given k colours, but you don't have to use all of them

https://en.wikipedia.org/wiki/Edge_coloring

@honest zodiac

[honest zodiac]

improper interval coloring is where each vertex's spector make interval where numbers can be repeated. Like {1, 2, 3}, {4, 5, 6} {4, 5, 5} but not like {1, 3, 4}

[reef thistle]

so, you want to colour the edges with as many different colours as possible while the colours adjacent to each vertex are contiguous integers

well, the diameter of the graph probably is a nice lower bound, just bfs from one end, and colour edges connecting vertices of distance a and a+1 colour a+1, edge connecting vertices of distance a and a, colour a.
Assuming connected, every vertex distance a>0 would have an edge with colour a, possibly an edge with colour a+1

@honest zodiac

[honest zodiac]

yes, but t^(G) is the parameter of the maximum number of colours in an
improper interval colouring of G. Ans as I am researching on total graphs your idea will result in max 1 or 2.

am I right, or I didn't get your idea

[reef thistle]

yeah if you are doing complete graphs, it wouldn't be too useful there

[honest zodiac]

ah yeah, sry, complete graph 😄 total is very different from complete 😄

[ocean viper]

i dont get this 😦

[honest zodiac]

https://hal.archives-ouvertes.fr/hal-01416358/document

on page 9-11 there is a lower bound

and some kind of algorithms

but that needs still to be improved

[kind tapir]

9/11 haha

[ocean viper]

😦 can someone possibly help me wif this

i dont get it

[sour arrow]

You want to check a space if it is in A or (B and C)

[ocean viper]

like this?

[sour arrow]

I see a few in A that aren't checked

I also see one in (B and C) that isn't checked

[ocean viper]

im confused

[sour arrow]

So A is that entire top left circle

Not just that half of the circle

[ocean viper]

oh so the the intersection has to be included too?

[sour arrow]

That red circle is everything in A

[ocean viper]

so i check everything in that circle?

[sour arrow]

If something is in A or (B and C)
Then it's in A
Or it's in (B and C)

So yes, everything in A is in A or (B and C)

[ocean viper]

so if i check a i dont check b and c?

o-o

[sour arrow]

Nope, you want to check them all

[ocean viper]

when it says b and c

its talking abt the intersections?

i only check that?

[sour arrow]

The red is A
The green is B intersection C

Then, the union of both of those spaces, is anything that's in either space

[ocean viper]

oh ok

lemme try to do another one

is this correct?

[sour arrow]

A U B
Is anything that's in A or B

A U C
Is anything that's in A or C

Then, the intersection of those two spaces is anything that's in both spaces

The bottom check is in A U C
But it is not in A U B
So it is not in (A U B)∩(A U C)

[ocean viper]

so like this?

[sour arrow]

Missing one check

[ocean viper]

yikes

[sour arrow]

The red is A U B
The green is A U C
You're interested in their intersection. That is, what's in both?

[ocean viper]

that check in between b and c?

i ma try color coding my next one

is this correct?

[sour arrow]

You're interested in whatever's in both the red and green

I know what the answer needed to be without doing any mental shenanigans, there's a way to cheat here lol. Both questions have the same answer

[ocean viper]

o-o

[sour arrow]

This is the distributive property.
A U (B ∩ C) = (A U B) ∩ (A U C)

[ocean viper]

oh

ohhh i remember seeing that from the textbook

okok

[sour arrow]

If I write ∩ as +
And U as ×

A(B + C) = AB + AC

It has a familiar look

[ocean viper]

ok

did i get this right though?

[sour arrow]

No

A is the red
(B ∩ C) is the green
You want their union. That is, whatever's in both

[ocean viper]

oh so i check b c and the intersection of b and c?

[sour arrow]

I don't see our regions being similar

[rose crystal]

i really need help with the top question

[sour arrow]

Please, an empty channel

[ocean viper]

oh the one i showed is a different question

[sour arrow]

Oh mb

The red isn't A, but yes that's correct

[ocean viper]

hmm ok i think i get it a bit now although i may be circling wrong i guess

[sour arrow]

The green is B U C

[ocean viper]

ok and i circle the entire a circle for a

these two didnt match did i do something wrong?

[sour arrow]

In order to find
(A ∩ B)'

You want to find
A ∩ B

But select everything that's NOT in that @ocean viper

Oh, no you got that right

The other one. You want to identity A' and B', then check everything in both

[ocean viper]

i dont really get A^c U B^c

[sour arrow]

What's NOT in A? Check those.
What's NOT in B? Check those too.

[sour arrow]

It's hard to do these with circles because we're looking for what's NOT in the circles lol

[ocean viper]

yeah its confusing

everything that is not in these circles is the answer

but it doesnt match the first one

so idk if i got it right

[summer gull]

Can someone help me with this problem ?

[sour arrow]

@summer gull
Weird hint. I would instead begin by finding specific and simple sets to sub in. We want to show that C is not a subset of B, what better way than letting B be the empty set?

[summer gull]

Okay... and to clarify, the empty set exists in all sets right?

What is the overarchign set? I'm still kind of confused. Which side of the subset symbol is the bigger set?

[ocean viper]

can someone possibly explain to me what i do here?

[pale epoch]

summing from k=1 to k+1 makes no sense

[ocean viper]

oh i was guessing

i tried m+1

idek

lol

[pale epoch]

that's not a good approach

[cerulean ore]

[1/(1+2) + 2/(2+2) + 3/(3+2) + 4/(4+2) + ....+ m/(m+2) ] + (m+1)/((m+1)+2)

Now it is self explanatory ^

@pale epoch I have a question

It is related to the problem : https://codeforces.com/contest/1244/problem/C which was asked in a contest 3 days ago

||The crucial observation is that d wins give us the same amount of points as w draws. Let's use them to solve a problem where we want to minimize the total amount of wins and draws giving p points (if it is not greater than n, we can just lose all other matches).||

that's the crucial information they've made

I am unable to understand why

[ocean viper]

i dont get this 😦

[last sigil]

Notice that it is alternating minus and plus @ocean viper

[ocean viper]

does this work?

[last sigil]

You need the k=1 to be positive

Watch your signs

[ocean viper]

this is difficult :c

[last sigil]

You are close, just need to change the exponent to something else

[ocean viper]

k-1?

[stray reef]

parentheses around the (-1)

[last sigil]

Yep that should work

[ocean viper]

aight

[stray reef]

and uh

[ocean viper]

it worked

[last sigil]

Nice catch on the () I forgot

[ocean viper]

hb this one?

[cerulean ore]

-.-

[last sigil]

So what it is asking is for the same summation just with using a different variable

[cerulean ore]

@last sigil is that homework?

[last sigil]

? Not mine

Even if it is, I won't give answers

[ocean viper]

yes on the textbook they didnt have variables on the upper limbit

limit*

im not sure how to approach this

[last sigil]

Just Google it so you can learn the method

[ocean viper]

whats the name of the method?

[last sigil]

iirc change of variables in summations

[ocean viper]

aight thanks

[last sigil]

Also seems to be called change of index @ocean viper

[pale epoch]

@cerulean ore d wins give d * w points and w draws give w * d points

[cerulean ore]

argh

What I thought it is : wx+dy = p can be written as dx+wy = p

even though I read it 5 times

@pale epoch Did you get the rest of the part as well?

||

[cerulean ore]

how can we limit y to w-1?

[stray reef]

can you give the original problem again

[pale epoch]

i mean i could check it later, i have some other stuff to do now. but i'm sure ann can help as well

@stray reef https://codeforces.com/contest/1244/problem/C i think

[stray reef]

oh it's code

pass

[zealous parrot]

Hey guys can anyone tell me good books about discrete maths?

[zealous parrot]

<@&286206848099549185>

[violet tide]

hey guys i have a question, how would i go about calculating the number of solutions to an equation with 5 variables such as (x1 + x2 + x3 + x4 + x5 = k) if each of the variables has an extra set condition (lets say x1 > 10, x2 <=5 etc)

i know the formula to calculate it without the conditions is n + k -1 over n - 1 (or however u call it in english), with n being the number of variables and k is the right side/solution of the equation

[cerulean ore]

@stray reef Actually, it is more of maths than code

[violet tide]

can someone help me with that problem?

[violet tide]

Nvm I already figured it out

[open glacier]

anyone got a clue how to write it out?

my homework task expects me to write it out without using set theory stuff

One example in my book:

'

Im really stuck with it, cant understand how its supposed to be written out 😶

[faint narwhal]

You might be confused about the indexing

When people index like that they mean that you do it over all things

So the first one means you union over all natural numbers

[open glacier]

@faint narwhal So thats essentially just.. ℕ?

[faint narwhal]

No

Sorry maybe not the best explanation

You know how sigma notation works right

[open glacier]

not too well, but go on

[faint narwhal]

Things like $\sum_{n = 1}^8 n^2 $

[vital dew]

Zopherus:

[faint narwhal]

Is just 1^2 + 2^2 + ... + 8^2

Well you can write this as $\sum_{n \in {1,2,\dots, 8}} n^2$

[vital dew]

Zopherus:

[faint narwhal]

As in you sum over all possible n

[open glacier]

okay so my task is union of natural numbers AND negative versions of them?

[faint narwhal]

Yeah

You should think about the example they give though

[open glacier]

i mean sure it makes sense now, it just is confusing since im quite new to all this stuff :p

however

i do not understand the how real numbers R comes from rational numbers Q

[faint narwhal]

Think about what (a,b) means

[open glacier]

a to b, both not included, idk the english word for _____ between them

[faint narwhal]

Between them is fine

Anyways, this contains a lot of real numbers

Like sqrt(2) is in (1,2)

[open glacier]

Correct but sqrt(2) is not a rational number

[faint narwhal]

Yeah

And that's how you can get real numbers from this union

[open glacier]

okay so what it means is, all numbers between a,b but they don't have to be the same kind as a and b are?

[faint narwhal]

Yeah

[open glacier]

Thank you, kind Sir.

[faint narwhal]

The notation almost always means

All real numbers between a and b

[open glacier]

got 1 more question

does it mean i can present my initial task as {-N,N}

mm sounds wrong

[faint narwhal]

Yeah thats not right

[open glacier]

Could u push me a little more :)? i suck too hard at this :S

[open glacier]

@faint narwhal

[gentle nebula]

{-n,n} is just a set of 2 elements

(a,b) is a infinite set of all real numbers between a and b

[shrewd spindle]

Could someone help me create functions from N to N (natural numbers) that are also one-to-one and onto

this idea of them being natural numbers is kind of confusing me

[stray reef]

the identity function

[shrewd spindle]

so the question I have to answer says but not the identity function

[stray reef]

can you

post the question

[stray reef]

,rotate -90

[stray reef]

and you're asking about (a)?

[shrewd spindle]

yes.

[stray reef]

yeah there are plenty of functions like that actually

you could have something like
f(n) = 2 if n=1, 1 if n=2, n otherwise

[shrewd spindle]

and then so a function that is neither onto or 1-1, would sin(x) be a valid answer or no, since it's mapping only natural numbers?

or part (d)

[stray reef]

uh

you have a function from N to N

there is basically no sensible way to wrangle sine into that

not only are your inputs natural numbers, your outputs have to be natural numbers too

[shrewd spindle]

that's what i assumed. so what would be an example of part (d) that would fit?

[stray reef]

a constant function

[open glacier]

https://cdn.discordapp.com/attachments/496785905474994186/633739245613481994/IMG_20191015_215250.jpg

how to write it out

my homework task says: Present this witout using set theory elements

and to prove the equivalence

[stray reef]

does your book say $0 \in \bN$ or $0 \notin \bN$

[vital dew]

Ann:

[open glacier]

says 0 does belong to N

[stray reef]

then that union of yours is Z

[open glacier]

makes sense 😄

got any clue how to prove it?

[stray reef]

just as you would prove any other two sets are equal

show they're subsets of each other

[open glacier]

@stray reef I never done any of that

[stray reef]

wat

you've never proved two sets equal to one another?!

[open glacier]

not really

would be super helpful if u gave some guidelines

my homework is due 30min

[stray reef]

ok let's step back

have you ever proved one set is a subset of another set

bc if you don't even know that then there is nothing i can do in 30 mins

not in the state i'm in rn

[weary tiger]

Uhm i'm trying to write an recursive function of n+1 choose k+1.
(n+1 choose k+1) = (n choose k) + (n choose k+1)

( (n choose k) = (n-1 choose k) + (n-1 choose k-1) ) + here i'm lost, dont know if i'm even trying the right approach

[weary tiger]

My classmates tell me this is a recursive function, should I just accept that?

[reef thistle]

it's a recursive definition of binomial coefficients

but you can make a nonrecursive definition (if you accept factorial as nonrecursive)

there's another one too, considering the factorial based definition

[ocean viper]

uhmm how do i write show the relationship of when
x_0 = 0
x_1 = rad(2)

x_2= rad(2+x_1)

so x_2 = rad(2+rad(2))

this is the question

[weary tiger]

@reef thistle Yes I buy that, I just can't see how i'm going to replace the (n choose k) with the whole thing

[last sigil]

@weary tiger wdym

I find looking at pascal's triangle as a good way to understand that identity

[weary tiger]

It's okay I get it now 🙂

[warped topaz]

Can anyone help me with cardinality

[pale epoch]

[warped topaz]

ok

A = {x^y|x, y ∈ Z, xy = 4}

what is the cardinality of Set A

I just know the very basics of cardinality

which is why I am confused

[reef thistle]

@warped topaz how do you find elements in set A?

@weary tiger so you have n!/(k!(n-k)!) and you probably want to relate to n!/((k-1)!(n-k+1)!)

[humble bridge]

$F(x, y) = 1$

[vital dew]

Doukutem:

[humble bridge]

this is relatively simple but I don't know how to find the sum-of-products expansion of this

could i break the right side into x + complement(x)? what happens to the y then?

[reef thistle]

ah, but you see, 1 is a product of zero variables

@humble bridge

and 1 is a sum of one product

[humble bridge]

so then what?

is the answer just 1?

or is it just all the combinations?

[warped topaz]

Yes @reef thistle how many carinality of set A

[clever nacelle]

Would anyone be kind enough to review my midterm practice sheet. 10 questions, and they are all finished and easy to read.. I would greatly appreciate it. I would just like to know if I missed any.

Particularly this problem

[sour arrow]

@warped topaz
The cardinality is just how many elements in the set A.

So, the question is about finding what's in set A. It's pretty clear what should be in the set, if you understand the rule that we use to build set A.

@clever nacelle
Both of those work, I like it.

[clever nacelle]

Thank you! And I have a really simple questions.
Negate (b) The variable S is undefined or the data are out of order.
->The variable S is defined, and The data are not in order.
That is what I got, I was marked wrong. I feel like it was a mistake.

[sour arrow]

I agree with you

[sour arrow]

3^3 = 3 (mod 8)

So I don't know lel

You meant 3² = 1 (mod 8)

[clever nacelle]

maybe they want "The variable S is defined, and The data are of order. "
and The data are not in order is two negitives

[sour arrow]

You're lucky you got 2 points lol

Maybe they were happy you knew the mod laws

Argument was good other than that number

Np. Feel free to ask if you need anything else!

[clever nacelle]

Last two questions for you! Thank you for your help
(b) Simple graph with four vertices of degrees 1, 1, 1, and 4.
We must have an integer when we sum all of the degrees and divide them by 2. We do
not, therefore this is impossible. (1+1+1+4)/2 =7/2, 7/2 is not an integer. Therefore a
simple graph does not exist.

Is this correct?

[faint narwhal]

Correct

[clever nacelle]

And this is my last one. Did I prove Onto correctly?

[sour arrow]

@weary tiger
Wait, I do have a problem. It looks like you're implying that 3^3 × 3^3 = 3^9

Your final result didn't depend on this assumption so nbd, but that's not correct.

Your final answer didn't depend on this, so nbd

Dividing and finding the remainder was the right move

[clever nacelle]

All triangles are equilateral, for Onto. Do you have to do more than prove it is in the set of R? I feel like I have more steps

[sour arrow]

@clever nacelle
f is onto (or surjective) if every element of R is an output for f

@weary tiger
You can add and multiply the same as you can in base 10. Do the carry as you'd expect

Just, 10 isn't your limit anymore, 8 is

[tranquil cargo]

(a,b) is notation for gcd(a,b)?

yea in

i think

horsintiawntrin

book in algebra laso uses that

but i thougth thats like the only zombie

horinstein*

or whatever his name is

[faint narwhal]

Unrelated

But the reason they use that notation is because in rings, usually (a,b) will denote the ideal generated by a and b

And if a and b are coprime, then (a,b) will be the whole ring

Ring theory stuff

[tranquil cargo]

cool

ideal is a subset of a ring taht is group ig?

idk

[wanton sable]

hey, can i get some validation/invalidation on my answers here? thanks kindly

[kind tapir]

you're wrong in number 2

inconsistent propositions are ones that the conjunction of is a logical impossibility

but their disjunction may still be true

For example, 1+1=2 and 1+1=3 are inconsistent propositions, but their disjunction 1+1=2 V 1+1=3 is true.

[faint narwhal]

Yes

Where the vertices are points in the euclidean plane

And two vertices are connected if and only if they're exactly distance 1 apart

I mean sure if a graph only has one vertex then you could use less than 5 colors

But there are finite graphs where you need a lot of colors

Uh

It just means infinite because there are infinitely many vertices

It has nothing to do with how many colors you need

There are infinite graphs you can color with 1 color

There are finite graphs that you need a billion colors to color

Because

This is a special infinite graph

They're not saying that you need 5,6, or 7 colors for any infinite graph

They're saying that this particular graph needs 5,6 or 7 colors

[weary tiger]

I'm so lost in discrete math

[faint narwhal]

What are you confused about?

[weary tiger]

Where do I begin

Well let's start with trying to understand it

[warped topaz]

Same with me I am lost in discrete math as well

[weary tiger]

Should I just Google problems ?

And Google their answered

Answers*

And see how they got to it?

[warped topaz]

And it's very hard to find good videos to learn

[weary tiger]

Yea

[sour arrow]

Sadly there's no "it" in discrete. There's a lot of subjects that discrete covers. Which one you mean?

[weary tiger]

I'll have to whip out my book later and dive into them

I'll come back on specific topics if I have a question

[warped topaz]

For me I am doing Logic, Proof & Sets

[weary tiger]

Just struggling to think problems through

[sour arrow]

Graphs? Combinatorics? Logic? Proof methods?

And probably primes if you're lucky

[warped topaz]

I am confused with the laws

that we apply to prove identities

like the De Morgan law

I have super confused with A)

[sour arrow]

The cardinality of A is just how many elements are in A

So one way to do this is to simply find everything in A

[warped topaz]

Yeah

I could do simple cardinality like {1,2,3,4}

so the Z is set of intergers right?

[stray reef]

integers yes

[warped topaz]

I am just confused about how it says x^y

then it says x and y are element of Z (intergers) and xy = 4

[stray reef]

it's the set of all numbers of the form x^y such that x and y are integers (x, y ∈ Z) and xy = 4

also, the word "integer" only has one R

here's what i would do

[warped topaz]

ok

[stray reef]

list out all the pairs of integers (x,y) satisfying xy = 4

then for each of those pairs

compute x^y

then write those out in a set

and that'll be A

[warped topaz]

but isn't Z infinte

[sour arrow]

Yes, but the integers that multiply to 4 are a very small list

[warped topaz]

how do I know which elements satisfy 4

Can you clarify bit more

[stray reef]

it's not "satisfy 4"

it's "satisfy xy = 4"

x*y = 4

you want all the integer solutions of that equation

[warped topaz]

I am so confused

[stray reef]

that's because you're overthinking it

[warped topaz]

ok Imma think from beginning

so x**y such that x and y are element of (z) integer, xy = 4

[stray reef]

english isn't your first language, is it?

[warped topaz]

no

[stray reef]

if you don't mind sharing, what is your first language

[warped topaz]

I need to learn this math lol

Slovak

[stray reef]

ok nvm

[sour arrow]

For example,
1*4 = 4
Therefore 1^4 ∈ A

[warped topaz]

oh ok

2*2 =4

but it says x and y

In the basics it only had one element

[sour arrow]

2*2 = 4
So x = 2, y = 2

And x^y ∈ A

[warped topaz]

so the question is trying to say

what power makes xy =4

[sour arrow]

Choose an x and y so that xy = 4

[warped topaz]

oh ok

[sour arrow]

Then x^y ∈ A

[warped topaz]

I need all possible soluions for xy =4

solutions*

[sour arrow]

Where x, y are integers

This means negative numbers count as well

[warped topaz]

oh ok

but I can't have fractions right

since it's integers

[sour arrow]

Yes

[warped topaz]

what about 1/2 **-2

that gives me 4

[sour arrow]

You want all possible solutions to xy = 4

Not x^y = 4

And, remember, this is all integers

[warped topaz]

oh

wait

2^2 isn't a solution?

oh it's x times y

A = {-4,-2,-2,-1,1,2,2,4,1}

/A/ = 6

[stray reef]

no

the set of all (x,y) such that xy = 4 is {(-4, -1), (-2, -2), (-1, -4), (1,4), (2,2), (4,1)}
(-4)^(-1) = -1/4
(-2)^(-2) = -1/4
(-1)^(-4) = 1
1^4 = 1
2^2 = 4
4^1 = 4

A = {-1/4, 1, 4}

|A| = 3

[warped topaz]

oh ok

so you put x,y within a open bracket ()

and then you do the power of those possible solutions

then the one's you get 4 will be the cardinality

oh ok I got it now

[stray reef]

...

"open bracket"?

........................

[warped topaz]

[] or ()

I forgot what it was called

tuple and list

Thank you!

[scarlet anvil]

Just wondering...when people were learning Discrete in university, did your teacher like...give examples of problems?

[warped topaz]

nope

The teacher is very hard to understand. I learn more by just reading the power point then by paying attention in clas

[scarlet anvil]

Okay so I'm not the only one. Just making sure. I understand the approach but sadly I need more examples to learn.

Though it seems Discrete is more about the theory, but it isn't really connecting for me (or apparently 85% of the class as we all failed the first test)

[pale epoch]

what are you doing in your discrete class?

[scarlet anvil]

We started with proofs and now are on number theory

we are using Mathematics for Computer Science by Albert Meyer from MIT

[faint narwhal]

I think the point is that examples are generally things you can read from the textbook on your own, but explaining new topics is the hard part which is done in class

[scarlet anvil]

and it's super dense, very little examples

[pale epoch]

at some point a student has to come up with examples himself

it's part of the learning process

not sure if this should be that point, though

[scarlet anvil]

Yeah but when 90% of class fail LUL

I think something needs to be reevaluated yeah?

I'll ask a question in one of the question channels if someone has some free time to help me understand...(#help-9 )

[warped topaz]

So for sets what does " how many subsets does example Set A have?"

mean

[pale epoch]

which word are you confused about?

[warped topaz]

so

my question is asking how many subsets does B have?

B = {2^3x+y |x, y ∈ Z, −4 ≤ 2x ≤ 2, xy = 12}

it says write elements of B and then compute |P(B)|)

.

.

So first I found elements that are inside or equal to −4 ≤ 2x ≤ 2

Then I multiplied those elements to see if I got 12

Then I placed them inside 2^3x+y

is this how is goes?

[pale epoch]

that is one approach to get B, yes

[warped topaz]

what is the another approach

[pale epoch]

well, you can first find solutions to xy=12 and then check if x satisfies the other condition

[warped topaz]

Also is this right or wrong −4 ≤ 2x ≤ 2 = {-4,-3,-2,1,0,1,2,3,4}

Then I do xy= 12 right?

[pale epoch]

it is neither right nor wrong

it makes no sense

[warped topaz]

oh

my bad remove 3, 4 from the element

so would it be {-4,-3,-2,1,0,1,2}

[pale epoch]

what would that be?

the possible solutions for x?

[warped topaz]

no

Then I think you do xy =12

so only {-4,-3,3,4} multiply to 12

[sly dagger]

there is no constraint on y

well only that its an integer

[warped topaz]

what do you mean

[sly dagger]

so you don't need elements from {-4,-3,3,4} to multiply together to give 12

that subset should be a set of elements that multiply with any integer to give 12

[pale epoch]

where is {-4,-3,3,4} even coming from

[warped topaz]

because xy= 12

x*y =12

3*4 =12

[pale epoch]

1*12 = 12 as well

[sly dagger]

i think you've interpreted it as −4 ≤ 2x, 2y ≤ 2

but its just −4 ≤ 2x ≤ 2

[warped topaz]

yeah but 12 is not inside the condition −4 ≤ 2x ≤ 2

[sly dagger]

y=12

[pale epoch]

this is only a condition on x

[warped topaz]

oh ok

so y can equal anything

[sly dagger]

any integer

[warped topaz]

oh ok

[sly dagger]

so long as it can be multiplied by an x to give 12

but while considering xy = 12 yeah the only constraint is that its an integer

[warped topaz]

ok

but also

since it's −4 ≤ 2x ≤ 2

what does 2 interpret

2x?

Does it mean I need to find a value inside -4 and 2 but when the value 'x' is multiplied by 2 it should still be inside the range

[pale epoch]

yes

it means x multiplied by 2 is within that range

[warped topaz]

oh ok

so for example -3 is within the range but when it's multiplied by 2 it will be -6 which means it's not in the range anymore

[pale epoch]

yes

[warped topaz]

Alright

[pale epoch]

so x=-3 does not satisfy that condition

[warped topaz]

oh

How do I write power sets of 4

I know how to do power set of 3

nvm

[tranquil cargo]

wdym 4

[warped topaz]

I got 4 element in my set

Set B

[tranquil cargo]

ok

[warped topaz]

so the power set of 4 will be 16

[tranquil cargo]

wdym the power set

of

4

[warped topaz]

yea

P(s)

[warped topaz]

If A ∩ B = A and C ⊆ A, then which of the following is equivalent to (A − B) ∪ (C ∪ B)?
Explain your solution.
a) B b) C c) {} d) A ∪ C

What is this question trying to say?

[tranquil cargo]

try

picking an element

in (A-B) U (C U B)

see where that leads you

[warped topaz]

oh ok

[tranquil cargo]

and know that C is a subset of A

and A n B = A

[warped topaz]

Yeah

but none of the laws apply to (A-B)

the laws are only for union and intersect

which is where I am having problems

@tranquil cargo so I just solve the (A-B) U (C U B) how?

[tranquil cargo]

let x be in (A-B) U ( C U B )

keep like

unfolding definitions

x in (A-B) or x in ( C U B )

if x in (A-B)

then x is A not B

[warped topaz]

ok

[tranquil cargo]

now do this and use your givens

A ∩ B = A and C ⊆ A

[warped topaz]

so I can use my givens and the others law (De morgan's law)

[tranquil cargo]

yea sure

A = A intersects B

[warped topaz]

Alright

[tranquil cargo]

try to thinnk of this

and think of what u got

then x is A not B

[warped topaz]

what about A-B

[tranquil cargo]

keep thinking

[warped topaz]

ok

[tranquil cargo]

A = A intersects B

so for example

let x be in A

then x is in A and B

so its just like i said

if x is in A then its in B

now

from this like

piece of information

try to solve ur problem

you got it?

[warped topaz]

so Like (A-B) would be ((AnB)-B))

[tranquil cargo]

ok

[warped topaz]

I am confused about '-'

[tranquil cargo]

here is a definition

[warped topaz]

it doesn't apply in any law

[tranquil cargo]

X and Y are sets

X-Y = { a| a is in X and a is not in Y }

[warped topaz]

Yeah

[tranquil cargo]

ok use that defintion

pick an element

and try going around

see what u get

maybe u get a contradiction

or anything

just try

[warped topaz]

ok

[trim oak]

Me again... very confused with this answer on recurrance relations and how they got the characteristic equation here:

Isn't the characteristic equation supposed to be x^2 - 4x + 3 = 0

Because the CE = r^2 - c_1*r_1 - c_2. I thought c_2 in this case would be -3

[sour arrow]

A(n) - 4A(n-1) + 3A(n-2) = 0

@trim oak

x² - 4x + 3 is the equation I'd expect

[trim oak]

Thanks, that means they've marked the exam wrong :/

This is the rest of the question

The formula that they get at the end seems to work, which is even more confusing to me

If they derived the wrong characteristic eq, why does it work 😩

Nvm

[slender skiff]

Isn't it always true that if:

if m | z then m | z*2 iff m is a positive integer

[faint narwhal]

What do you think?

[slender skiff]

Yes

makes a lot of sence

[faint narwhal]

What exactly is this statement saying though?

Specifically

The iff part

[dusky silo]

im assuming i can message now
info: theres 1000 computers, 20 are broken.
question: 5 are randomly selected, P(exactly one of them being defective)
my solution: if exactly one is defective, that would be 20/1000 odds and then the other 4 would have probabilities (980/999, 979/998, 978/997, 977/996) and then i could just multiply all of these numbers together, giving me 0.01851917584 but the answer is 0.092 somehow

not sure what im doing wrong, btw logic for 980/999... bit is just that there are sequentially one fewer to choose from but we start at 980 since there are 980 good ones after the one bad one is picked

[reef thistle]

hmm

ah, but there's exactly one

how many ways to select 5 computers, one defective?

how many ways to select 5 computers?

[dusky silo]

to select 5 computers its 1000C5 ?

[reef thistle]

yeah

then to select 5 computers, exactly one defective would be

[dusky silo]

uh im blanking haha like

i keep coming back to original solution

[reef thistle]

okay let's see carefully

actually, you are off by a factor of 5

yeah

but let's analyse it slowly

to select 5 computers, exactly one defective, how many ways?

[dusky silo]

20C1 * 980C4 ?

okay my brain is fried sorry idek

[reef thistle]

yeah

okay now take one and divide by the other

what do you get?

[dusky silo]

oh i get the right answer thank you but like why is my other process wrong ?

[reef thistle]

ah

because

you were selecting with order

but you didn't consider the position you selected the defective one

you were "selecting the defective one first", where it could have been second to fifth

[dusky silo]

ahh and based off of that then for each position, there will be 999/980 * 998/979 ... combinations okayy

thank you!

[slender skiff]

How do you determine if a undirected tree is a binary tree?

If you choose one vertex as a root it’s binary another vertex would result in the tree not being binary

[azure lichen]

assuming we have the same definition of binary tree (every vertex has either 0 or 2 children) then I think you just have to
•check it’s a tree
•check that there’s exactly one root (vertex of degree 2)
•check that all other vertices are either leaves (degree 1) or have degree 3

which you can all do while executing a BFS

if you allow vertices to have any number of children ≤ 2 then it’s more complicated and I’d have to think about it

though actually I think in that case it simply boils down to checking it’s a tree where every vertex has degree ≤ 2

[slender skiff]

But its undirected that means there can be multiple roots(multiple vertexses with degree of 2)

So if there is ONE vertex

that makes it be a binary tree

then its a binary tree?

[azure lichen]

yea I think it wouldn’t matter where you start? because at every step you either find a vertex with degree 1 (leaf), degree 2 (only one child) or degree 3 (two children)

as long as you start at a vertex with degree 2

but again it depends on the definition

i.e. whether having just one child is allowed

[slender skiff]

okay just to make sure, in my case there is multiple vertexses that i could choose to make it a binary tree, but there is one vertex with a degree of three.

This would make it a binary tree

since there is the other vertexses (if chosen as root) it is a binary tree?

[azure lichen]

(it’s vertices btw, not vertexes)

[slender skiff]

oh

XD

[azure lichen]

also I’m not quite sure I understand your situation

if you have the following situation:
•T is a tree
•every vertex in T has degree 1, 2 or 3
then you can build a binary tree out of it by starting at a vertex of degree 1 or 2 and simply declaring its neighbors to be its children, and so on

and because of condition 2, at every step you’ll at most get two children

so it’s a binary tree

actually I guess the root doesn’t even have to be of degree 2 sorry

it could also have degree 1

[slender skiff]

This is the problem if with rn, it is a tree since its connected and not a circuit. By the things i have read, is for it to be binary, it needs to be rooted, and a rooted tree is a tree where a vertex can be distinguished from others, but thats not possible in this case?

[azure lichen]

well a binary tree has a distinguished root and often even distinguishes children into “left” and “right”
so this tree could be made into a binary tree but I suppose you could say it isn’t one per se

in particular except for b and d, any node could be chosen to be the root

[slender skiff]

would result in a binary tree yes

So by definition of Math (lol) are you allowed to just select one vertex as a root (on a undirected graph)

and from that say its a binary tree

[azure lichen]

So by definition of Math
this is very meaningless

[slender skiff]

idk how to explain

is it "valid"

[azure lichen]

the image above is not a well-defined binary tree because it lacks a root

if you choose a vertex to be a root, then it would define a binary tree

but choosing a different vertex gives a different binary tree

(note if you think I’m contradicting earlier statements of mine, I didn’t have enough context before to properly answer so I made a guess at what you’re asking :P)

[slender skiff]

Welp, would the best thing to do, is to argument for both possibilities ?

[azure lichen]

I’m honestly still not quite sure what the thing is you have to show

nor what “both possibilities” are

it would be best if you gave the whole problem, plus your definition of a binary tree

[slender skiff]

Well i was given that picture from above,
And this question: "The graph represents a binary tree" Explain why this is true or false.

We already confirmed its a tree.

A binary tree is a rooted tree in which every parent has at most two children. Each child in a binary tree is designated either a left child or a right child( but not both)m and every parent has at most one left child and one right child.

A rooted tree is a tree in which there is one vertex that is distinguished from the others and is called the root.

Since no vertex can be distinguished, this answer is true and false based on the vertex you choose.

[slender skiff]

Wait for it to be binary it must be a rooted tree

and definition of rooted tree is

where one vertex has been designated the root

AKA you can choose whatever vertex you wan

to make it a binary tree

[azure lichen]

I would argue that the answer is “no, because it does not have a distinguished root”

maybe with an added “however, if we chose a root, it would”

note that your definition says

A rooted tree is a tree in which there is one vertex that is distinguished from the others and is called the root.

and not

A rooted tree is a tree in which there is one vertex that can be distinguished from the others and is called the root.

so while, sure, you could choose a root, this didn’t happen, so it’s not a rooted tree, and thus in particular not a binary tree

[warped topaz]

If A ∩ B = A and C ⊆ A, then which of the following is equivalent to (A − B) ∪ (C ∪ B)?

How do I solve this

I said ( x is an element of A and x is not an element of B or x is an element of C or x is not an element of B)

is this correct

[sour arrow]

A ∩ B = A implies that A ⊆ B

So with that, A - B gets real simple

@warped topaz

[warped topaz]

oh

How tho

[sour arrow]

Which one?

[warped topaz]

I am confused with the subset

so the subset for example c subset of A defines

that they are equal?

How do I apply subset

[sour arrow]

C ⊆ A
Means that every element in C is also in A

[warped topaz]

Yeah

[sour arrow]

Essentially, A has all of C's elements, and perhaps more

[warped topaz]

oh ok

but How do I apply it to the identity

[sour arrow]

Let's start with the other one, as that one is more important

[warped topaz]

ok

[sour arrow]

A ∩ B = A

That is, the elements common to both A and B
Are exactly the same as
The elements in A

[warped topaz]

yes

so A is a subset of B

B and subset of A

[sour arrow]

Indeed, A ⊆ B

If you can logic that together

[warped topaz]

using the laws?

If A ∩ B = A and C ⊆ A, then which of the following is equivalent to (A − B) ∪ (C ∪ B)?
Explain your solution.
a) B b) C c) {} d) A ∪ C

[sour arrow]

Anyway, you know that
A ⊆ B and C ⊆ A

[warped topaz]

Yeah

[sour arrow]

It follows that
C ⊆ B

Because ⊆ is transitive

[warped topaz]

what is transitive

[sour arrow]

Like, let's say
A ~ B and B ~ C
If ~ is a "transitive" relation, then
A ~ C

If you can go from city A to city B, and if you can go from city B to city C, then ultimately you can go from city A to city C

[warped topaz]

oh ok

I get it

but how does subset help with (A-B_

(A-B)

[sour arrow]

Well, we know that A ⊆ B
What is A - B then

A - B is the set that contains the elements in A, unless they are also in B

[warped topaz]

isn't it AnB that contains A

not A -B

[sour arrow]

What is A - B?

[warped topaz]

x is element of A and x is not an element of B

sorry if I am asking too many question

[reef thistle]

we know A ⊆ B so, what sort of x satisfy that?

[warped topaz]

I am confused

[mild flicker]

I'm having trouble with calculating the run time for this code

Node *head = new Node;
Node *curr = head;
head->data = 0;
head->next = nullptr;
for (int i = 1; i < n; i++)
{
   curr->next = new Node;
   curr = curr->next;
   curr->data = i;
   curr->next = nullptr;
}
for (int i = 1; i <= n; i++) {
   curr = head;
   while (curr != nullptr) {
      if (curr->data % i == 0) {
         for (int j = 0; j < n; j++) {
             A[j] ++;
         }
      }
      curr = curr->next;
   }
}

I get that the first for loop is theta(n)
but for the second for loop, the most inner for loop has run time of n
for the while loop, is it also theta(n)?

[reef thistle]

well, how long does it run for (depending on the linked list)?

@mild flicker

[mild flicker]

@reef thistle yeah that's what I was thinking

but then the curr->data % i threw me off a bit

What I'm thinking is that it'll jsut traverse through the whole LL, so it's theta(n^2) run time?

n^3

[reef thistle]

ah, for that you should count how many times it is true. You should get 1/1+1/2+1/3+1/4+...+1/n

@mild flicker

[kind tapir]

The non-coders mustbe so confused if they'll assume this is soe kind of obscure maths notation.

[weary tiger]

Can anyone explain b to me

Ugh where's the cropped version

I don't understand how (i,j) is setup

Like [i,j,i,...]?

Or is it like x = i and y = j

[obtuse lance]

it's like a 5x5 identity matrix

[weary tiger]

Yea

I get that part

[obtuse lance]

except the 1s and 0s aren't where you would normally put them

[weary tiger]

But how do I even know how to start

[obtuse lance]

what's in the (1,1) entry

[weary tiger]

i?

[obtuse lance]

...

you said you got it

[weary tiger]

Sorry I'll just Google

[obtuse lance]

but you didn't

[opal crescent]

the entries are either 1 or 0 lad

[obtuse lance]

apology accepted

[opal crescent]

[weary tiger]

@opal crescent so the answer is 1,1,1,1,1
00,1,00,
1,1,0,1,0

00010

10110?

I'm so lost

[opal crescent]

well in the second line i=2

what are the multiples of 2 between 1 and 5?

[weary tiger]

And third line I=3?

5

Oh 2

[opal crescent]

well 4 also

[weary tiger]

2*2 = 4

And 4 is in 5

Right ?

[opal crescent]

yeah

so what should your second line be?

[weary tiger]

4

2,4

2 and 4 is a multiple of 2 between that range

[opal crescent]

yeah so that's the j indexes on the second line where the entry should be 1

what does that give in the matrix

[weary tiger]

Let me draw this out so I understa d

Like this

Or inside

[opal crescent]

the entries are only 0 or 1 remember

you can't have 2 and 4s in there

[weary tiger]

What about the 2 and 4

What did that mean

[opal crescent]

it just tells you where the 1s are on the second line

[weary tiger]

OH!!!!!

So there would be a 1 in the second spot

And the 4th spot

How did you know that

[opal crescent]

it's what they tell you to do idk

[weary tiger]

They never said mind multiples of 2 between 1 and 5 though

[opal crescent]

"5by5 matrix whose (i,j)th entry is 1 when j is a multiple of i__, otherwise 0"

[weary tiger]

Find*

Yea

Where'd you get the 2 from

[opal crescent]

but that's freaking implied by the q

for the 2nd line

[weary tiger]

😪

[opal crescent]

but you have to do this for all lines

i from 1 to 5

[weary tiger]

Ok so for line 1

Row 1

Where do I start

[opal crescent]

same

what are multiples of 1 between 1 and 5?

hard question isn't it

[weary tiger]

Yes hang in

On

Let me get my calculator

Ha ha!

1,2,3,4,5

So all row 1 will be 1!

[opal crescent]

yeah all 1s as you wrote before

[weary tiger]

And row 2 is 01010

[opal crescent]

yup

[weary tiger]

Row 3 is 00100

[opal crescent]

i think you got this now

^^

[weary tiger]

Yay I got it!!!

All because you're an amazing teacher

How could I ever repay you

[opal crescent]

$$\begin{bmatrix}1&1&1&1&1 \ 0&1&0&1&0 \ 0&0&1&0&0 \ 0&0&0&1&0 \ 0&0&0&0&1\end{bmatrix}$$

[vital dew]

emeric75:

[opal crescent]

[weary tiger]

Yes!! I for that !!!

Got

Thank you teacher

[opal crescent]

[weary tiger]

What does the upside down y mean in part c?

[opal crescent]

it just means empty string i suppose

(and it's not an upside down y, it's a greek letter : lambda)

[weary tiger]

Only way I could describe it

Thanks

[scarlet anvil]

Does any one have some insight into this:

[warped topaz]

is this (AnB) U (BUC) n (C-A)

[lilac pivot]

you can just do (AnB) U (C-A)

middle term is redundant

[warped topaz]

oh ok

What about this question

really cofused

[reef thistle]

well there's only 16 possibilities

consider where an element can be

there's only 4 possibilities to consider

[warped topaz]

oh

Is it empty set

[reef thistle]

idk I didn't calculate

[warped topaz]

oh

@reef thistle can you help me with this please?

[reef thistle]

hmm

What does A intersect B=A say about A-B?

[warped topaz]

Do I have to do all a,b ,c and d

or is this multiple type question

[reef thistle]

just simplify that

[warped topaz]

oh

Can you guide me

I have to hand this today

and I have been doing it for 2 days

[reef thistle]

A intersect B = A, so what's A-B?

[warped topaz]

AnB'

[reef thistle]

and when you use the condition A intersect B = A, can you simplify it?

[warped topaz]

not sure

let me show you where I got up to

@reef thistle ??

[reef thistle]

well if A intersect B = A, what's A intersect B'?

[warped topaz]

what do you mean

[reef thistle]

(A intersect B) union (A intersect B') is?

[warped topaz]

I am confused

sorry

can you explain it

[reef thistle]

okay what do you know?

[warped topaz]

I know that A N B = A

so A is a subset of B
also

so

[reef thistle]

ah A is a subset of B, so...?

A intersect B' is?

[warped topaz]

empty set

?

[reef thistle]

yeah

so you are now left with?

[warped topaz]

empty set U (CUB)

so it would be (CUB)

[reef thistle]

okay

can you simplify that further?

[warped topaz]

oj

How can I simplify (CUB)

@reef thistle are you ok?

[reef thistle]

busy

look at your subset relations

[warped topaz]

Plz

help me with this question

only

[reef thistle]

what subset relations do you have?

[warped topaz]

That's where I am confsued

how do I apply these subset relations means to the set

[reef thistle]

how can you relate C and B?

you have subset relations

[warped topaz]

oh

[reef thistle]

you have C and A, and something between A and B

[warped topaz]

oh

so C and B is also subset

[reef thistle]

can you show it?

[warped topaz]

I am so lost

[reef thistle]

where were you last?

[warped topaz]

wdym

[reef thistle]

what did you get?

[warped topaz]

I got (CUB)

which is not right

[reef thistle]

you can simplify it further

[candid flicker]

Did you look at the sample solutions @scarlet anvil? You could also start by writing out what “a EQUIV 1 (mod p-1)” means by definition.

[scarlet anvil]

I have glanced at them @candid flicker. But I did want to see if I could get a little nudge in the right direction first. I didn't look at the sample solutions for this one in particular yet. I'm at work but I'll ping you later and see if you're around, perhaps you can join me in one of the #question channels.

[river yarrow]

Find the minimum number of elements that one needs to take from the set S = {1, 2, 3, . . . , 9} to be sure that two of the numbers add up to 10.

I dont understand how to approach this

problem

[stray reef]

pigeonhole principle

[river yarrow]

1 and 9, 2 and 8, 3 and 7, 4 and 6, and 5 and 5 are pairs that add up to 10

I have no idea what to do with this info

[azure lichen]

well you need to guarantee that at least one of those pairs are in there (5&5 isn’t one btw because that’s the same number twice)

[river yarrow]

i dont get why there's even a minimum

I mean, you can pretty much pick 1 pair. doess that count as a minimum?

I dont think i understand the wording of the question

[scarlet anvil]

Well if I just grab 2 I could grab {5, 6} which is not 10.

[river yarrow]

oh shit, your right.

[scarlet anvil]

So how many more do I NEED to grab to make sure I have one of the pairs you mentioned

[river yarrow]

well i came up with 5 pairs

[azure lichen]

one of which is wrong

[river yarrow]

huh

[azure lichen]

you can only have one 5

so 5+5 is out

[river yarrow]

I dont even know what is the pigeonhole and what is the pigeon (since someone pointed out this uses the pigeonhole principle)

@azure lichen Are you suggesting that we are thinking each pair as a set?

[azure lichen]

the pigeonhole principle is phrased as “if you put n+1 pigeons into n boxes, then one box will contain contain two pigeons”

but I don’t wanna go there tbh, I’ll explain the problem but then I’ll have to go back to my own homework

[river yarrow]

So the number of pigions will always be more than the number of containers?

[azure lichen]

no?

the statement is “if you have too many pigeons for the containers, then they’ll have to share”

[river yarrow]

right

I'm trying to think this problem in terms of the principle but I just cant

[azure lichen]

so the point is this:

you pick some subset of {1,…9}. let’s say for example, you pick some subset with 8 elements. are there now two numbers in there which add to 10?
well, yes. you picked all but one of the numbers, so one of the pairs is in here for sure

does this also work with 7? 6?