discrete-math

[unique elm]

ayo

is it always false that A belongs to A

for any set A

[brave rock]

This is false due to the axiom of regularity.

In fact there are models of set theory in which some sets may contain themselves; it is not inherently paradoxical.

But the axiom of regularity does exclude these in ZF

[gilded ember]

I am not quite follow how to make a totally ordered subset of $\mathbb{N}$ with the relation of divides. I learnt that totally ordered set is a partially ordered set in which every pair of elements is comparable. I understand how we can compare two numbers with the relation $\le$, but I just don’t understand how to compare two numbers with the relation $\mid$, can anyone help? Thanks.

[vital dew]

Trenton

[gilded ember]

I also understand that $\mid$ fulfills the condition of partial order. But I still don’t know how to compare.

[vital dew]

Trenton

[gilded ember]

[gritty crescent]

The "a divides b" relation cannot be a total order for the simple reason that 2 and 5, for instance, are not comparable

If you want to extend this relation to a total order, then it will no longer correspond to "a divides b"

[gilded ember]

Oh I got it now, so ${2,4,8,3,9,27}$ is partially ordered set because $2|4$ and $4|8$ and $3|9$ and $9|27$. But how about the subset $Q={2,3,5,7,11}$? Why is it a partially ordered set?

[vital dew]

Trenton

[gritty crescent]

Check the axioms: (1) verify that the relation is reflexive, i.e., each element is related to (in this case, divides) itself.
(2) Verify that the relation is antisymmetric: for all pairs of distinct elements (a,b) in Q, verify that if a|b, then b does not divide a.
(3) Verify that whenever a|b and b|c, then it must be the case that a|c.

You can see that (1) makes sense, right?

And are potentially confused about (2) and (3), since seemingly no two distinct elements are related here

But for a partial order, you do not require that distinct elements be comparable: if they are comparable, then they should obey antisymmetry and transitivity. If not, then they vacuously satisfy the conditions for being a partial order.

Also, keep in mind that while what you said about divisibility in {2,4,8,3,9,27} is true, mere comparability of elements is in general not a guarantee that your relation is actually a partial order. You must always check that they satisfy the 3 listed axioms.

[gilded ember]

So the key is to stick with the axioms. Thank you so much! I got it now. 👍🏻

[gritty crescent]

[plain pawn]

Hi all, is MaxCut problem on Complete graphs already solved analytically?

[pale epoch]

solved analytically?

[tacit thistle]

How can the matrix representing a relation R on a set A be used to determine whether the relation is asymmetric?

[hard citrus]

Start from the definition of what it means for a relation to be asymmetric

[tacit thistle]

Let R be the relation {(a, b) | a is not equal to b} on the set of integers. What is the reflexive closure of R?

[tacit thistle]

is this right? {(a,b) | a not equal to b or a = b}

[onyx pewter]

it would not be reflexive and it would be reflexive. When studying reflexivity you would modify the statement to show {(a, a) | a is not equal to a} which is never true for all x in the domain. Therefore making the statement irreflexive

irreflexive means that there does not exist a reflexive relationship in the set.

@tacit thistle I can go through some problems with you if you would like

[tacit thistle]

what's the answer?

what's the reflexive closure of R

[onyx pewter]

i dont think there is reflexive closure

[tacit thistle]

oh

[onyx pewter]

because the relationship is irreflexive there does not exist a relfexive relationship

i think... I haven't seen a problem like this

[tacit thistle]

let's say the set A consists of all integers, right? a not equal to be would be like (2,3), (4,5), (6,7)

we need to add (a,b) such that a = b right?

[onyx pewter]

these images are reflexive because 1=1 2=2 3=3 4=4 5=5

thats what reflexive means

[tacit thistle]

I know

reflexive means that u have (a,a) for every element in A

right?

[onyx pewter]

if the condition is if they are not equal to, then there will never be any 1=1 for example

yes

[tacit thistle]

yeah im confused by that question lol

[onyx pewter]

that question is bad

i dont like that question

[tacit thistle]

what if the condition was a = -b?

[onyx pewter]

what is the domain

[tacit thistle]

all integers

[onyx pewter]

of a

0 = 0

is the only reflexive relationship in the set

I vaguly remeber reflexive closure so im trying to refigure it out, but I think it would be 0

[tacit thistle]

is this reflexive

A = set of all integers

the answer is yes btw

[onyx pewter]

i belive so

yes

good

[tacit thistle]

but if we follow ur reasoning it can't be both a = b and a = -b

right?

unless a = 0, and b = 0

[onyx pewter]

it is or

a will always equal a

therefore the conclusion is always statisfied

[tacit thistle]

then why is this wrong?

{(a,b) | a not equal to b or a = b}

it's also an or

[onyx pewter]

oh..

im sorry, i didnt see the second or condition

i thought it was only not equal to

yes it is a reflexive function

[tacit thistle]

that's the reflexive closure i got

[onyx pewter]

im sorry, I missread

I agree with you

[tacit thistle]

for {(a,b) | a is not equal to b}

[tacit thistle]

Find the smallest relation containing the relation below that is both reflexive and symmetric.

is it also {(a,b) | a # b or a = b}

[hard citrus]

What is a#b?

[tacit thistle]

a not equal to b

[hard citrus]

Yes

It ends up being {(a, b): a, b in N^+}

[tacit thistle]

so all integers?

[hard citrus]

Mhh, that's what this is saying

For reflexive you make the relation a>=b, and for symmetric the other way should also hold: a>=b or a<=b

[tacit thistle]

for symmetric u get a>b or a<b (a not equal to b) right?

is the answer all integers?

for parts b, d, f, h, is the answer yes to all of them?

[hard citrus]

Yes, there is a path

[ebon atlas]

hi everyone, can i ask about simplification of Context-free grammar here?

[empty escarp]

how can i prove that the set (0,1,2,...p-1) is a field iff p is prime without using any concepts from aa?
i know that unless p is prime each element is not going to have a multiplicative inverse but im not quite sure how to formalize this
i want to show that for each x there is a unique solution ax=1 mod p
apart from this, all of the other field axioms will carry out from R right?

[brave rock]

This follows from Bézout's lemma.

[empty escarp]

I am trying to show that if x>0 then x \in R+

this is my method but idk if its rigirous enough:
Assume for the sake of contraidction that x>0 and x is negative. This implies that -x \in R+. We can also write this as \sum_{j=1}^x -1 \in R+. Since 1 \in R+, we must have that -x+1 is also in R+ so we add 1 x times to get \sum_{j=1}^x (-1+1) = 0 which by axiom 1.6.2 is 0 which means it cannot be positive. Hence -x cannot be positive

oh fuck me i think i could have just said x>0 \implies x-0=x \in R+

[stray reef]

yes

[fresh hollow]

Do you still need help?

I'm a little familiar with induction

[tacit thistle]

why is R6 transitive?

[weary tiger]

Because it's just one element?

[tacit thistle]

why would that mean it's transitive

transitive is basically if u have (a,b) and (b,c) then u must have (a,c)

right?

[olive wren]

Yes

But for every (a,b) there doesn’t exist a (b,c)

So the transitive property is true vacuously

[tacit thistle]

why did they go up to M[3]

[steep creek]

I'm getting told {0}⊂{0} is false, why is that?

Nvm

[ember obsidian]

does ⊂ mean strict or nonstrict subset

[steep creek]

proper subset meaning the same definition applies but they cannot be equal

[ember obsidian]

{0} equals itself ofc so its not a strict subset of itself

[steep creek]

Yeah but my teacher didn't cover the differences

Which was weird considering it was a HW problem

[ember obsidian]

maybe they expect u to already know the definitions

[tropic mural]

i need help memorizing boolean algebra laws

especially and distributive law

[stray reef]

you need help specifically memorizing them?

[tropic mural]

and using them

i understand boolean algebra

i just need help memorizing the different laws that will help with simplifying expressions

[unique abyss]

do you understand why all of them are true?

if so, you can try practicing deriving them yourself

if you only care about memorization (I don't recommend as it limits your understanding of the subject)

You can try making flashcards, there's not too many of these laws after all

[tropic mural]

i can understand why inputs into a boolean eqaution result in its given output, but i dont understand the reason behind every boolean algebra simplification law

[unique abyss]

My recommendation would be to start there

Before memorizing said laws

try to understand why they are true

[tropic mural]

thats kind of impossible with how little information there is on specific stuff like that

atleast online

they kind of just skim over stuff like that

[unique abyss]

Where are you looking?

There should be enough content online to learn these laws

if all else fails, you can always make a truth table yourself and show that said relations are logically equivalent

[unique abyss]

In terms of using them, you have to go over a lot of practice problems yourself

No easy way to do get better at using them then using them lol

[tropic mural]

every learning source online i could find skims over each law very briefly

[oak violet]

Hello everyone. I have a graph theory question. In a directed graph, a vertex v is said to be reachable from u iff there is a directed path from u to v. Vertices u, v are said to be mutually unreachable iff u is not reachable from v and v is not reachable from u. The question is: what would you call a set of vertices X such that for all u ≠ v ∈ X, u and v are mutually unreachable?

Someone I spoke with suggested "independent set". X is indeed an independent set, or anticlique, but this is a strictly stronger notion. I've searched a lot online (finding mentions of reachability mostly on wikipedia and stackexchange) to no avail. I have limited experience in this field and don't know where else I could look for an answer.

[austere cedar]

I would probably call the set of vertices "totally disconnected", but i don't have a reference to someone using this phrase and its likely that i just invented it.

[naive arrow]

Im reading this paper on Sparsifiers and I dont understand the nomenclature here, what is x? Im assuming is an eigenvector, but the paper does not specify . Can a Vertex be represented by a vector? How?

It does not clarify if this is a row from the laplacian or nothing, all it says is:

[unreal stump]

@naive arrow well a vertex can be represented as a bunch of co ordinates in a co ordinate system which is a vector

[steep creek]

in a set difference if A - B = B - A does that conclude A = B?

[ember obsidian]

did u try proving it?

[steep creek]

Well I only concluded that this works in the case of them being only empty sets

Because we haven’t really gotten into proofs yet

[tacit thistle]

can someone please answer my question

[hard citrus]

What does theorem 3 say?

[hard citrus]

So they go up to the third power because the set on which the given relation is defined has 3 elements

[sharp turtle]

First draw a Venn diagram to get intuition and then formalize using mathematics

[tacit thistle]

how do u know that it has 3 elements though

[hard citrus]

Because of the matrix representation of the relation. If you define a relation R on the set A with cardinality n then R will be a subset of AxA; for matrix representation you'll have an nxn matrix with n rows and n columns each for one element (here you have 3 rows and 3 columns).

[tacit thistle]

so if u have 3 rows and 3 columns that means u have 3 elements?

what if u have 4 rows and 4 columns

[hard citrus]

Then you have 4 elements

This is only true for relations defined on AxA and not always true for those defined on AxB

[coral parcel]

What did you get in part a?

= 1, one supposes?

Try writing your identity -16 · 59 + 7·135 = 1 modulo 135.

What do you get wen you write -16 · 59 + 7·135 = 1 modulo 135?

Don't evaluate the left-hand side.

Just $-16\cdot 59 + 7\cdot 135 \equiv 1 \pmod{135}$.

And then recall that 135 is 0.

[vital dew]

Troposphere

[coral parcel]

Whoops yes.

Modulo 135.

Calculating modulo 135 means we ignore differences that are divisible by 135.

And the difference between 0 and 135 is certainly divisible by 135, so we're ignoring the distinction between 0 and 135.

So 7·135 = 7·0 = 0 when you work modulo 135.

Yes -- though with proper notation: -16 · 59 == 1 (mod 135)

This says you have found something that makes 1 when multiplied by 59.

So add or subtract an appropriate multiple of 135 to get into that range.

"Multiple of 135" is "135 multiplied by some integer".

Because that gives you something whose distance from -16 is divisible by 135.

And therefore it is the same congruence class as -16.

It's more of a definition than a lemma (in most books).

As in, that's what it means for two numbers to be "the same" modulo 135.

Now you have found the inverse-modulo-135 of 59.

I'm confused. Do you not see that you're done here?

How is "the inverse of 59 modulo 135" defined for you?

Yes.

I don't understand what you're asking here.

You've just worked through an example of exactly that.

It is not 119·59 == 1mod135, but 119·59==1 (mod 135). The "mod 135" morally applies to the entire congruence, not just to the right-hand-side of it.

Good.

[rich hedge]

so it says to write this into a math question not to solve it

but how would you write two math equations into one equation

when I read this, that's what comes to mind

[coral parcel]

No, your equations say that the quotients of dividing by 5 and 6 are such-and-such. The question, however say that the remainders must be such-and-such.

[rich hedge]

I thought remainder was what's left after doing the division

[coral parcel]

But your notation there simply means the result of the division.

Since the problem is not asking you to find such an x, but merely predict whether there is a solution, I imagine you're expected to apply the Chines Remainder Theorem, which immediately gives you the yes/no answer you need.

[coral parcel]

Integer division -- for example 23 divided by 5 -- gives two results at once. In this example the quotient is 4 and the remainder is 3, because 22 = 4·5 + 3.

[rich hedge]

I've never even heard of the chinese remainder theorem

this is the first question of the homework for my first discrete math class so I don't have like the tools yet to actually go in-depth

so i feel like that's not what it's looking for

[coral parcel]

Unfortunately there's no commonly accepted symbolic way to write this operation in mathematics. We can specify the quotient in this case as $\Bigl\lfloor\dfrac{23}{5}\Bigr\rfloor=4$ fairly compactly, but there's no compact and common operation for the remainder. Some borrow the % symbol from programming languages and write $23\mathbin{%}5=3$, but the more mathematically common way switches around the inputs and outputs and would instead write $23\equiv 3 \pmod{5}$ as the closest statement of the remainder result.

[vital dew]

Troposphere

[rich hedge]

maybe this changes things, I'm doing number two and then that blue text is explaining what I'm supposed to do

[coral parcel]

If you haven't heard of the CRT, you might be expected to try brute force trial and error to find the appropriate x.

[weary tiger]

you can also just list them out

like

integers that have a remainder of 2 when divided by 5 are

[coral parcel]

There ought to be a solution somewhere between 0 and 30.

[weary tiger]

2, 7, 12, 17, 22, 27, 32, 37

integers that have a remainder of 3 when divided by 6 are

(you try this)

and you will find an integer

in common of both

[rich hedge]

ok I think I have like a sever lack of understanding of math terms, so remainder being 2 from being divided by 5, the only answer is 10 in my head

[weary tiger]

Ok here

[rich hedge]

so like if I divide 27 by 5 I don't get two

[weary tiger]

lets put it this way

[rich hedge]

so is there something I am completely missing

[vital dew]

jswatj

jswatj

[weary tiger]

for example $2=5\cdot 0+2$ and $7=5\cdot 1 + 2$...

[vital dew]

jswatj

[weary tiger]

you will get a quotient and a remainder

[tacit thistle]

wouldn't that make the relation not a partial ordering, since it would be symmetric?

[rich hedge]

omg

thank you

remainder just clicked

[weary tiger]

you're welcome

[rich hedge]

that is what is fucking me up so hard is I didn't understand what remainder meant

[coral parcel]

Correct, the "is comparable to" relation itself is not a partial ordering.

[tacit thistle]

then why is the set called a poset

[coral parcel]

The partial ordering, notated "$a \preccurlyeq b$" in your first quote, is a \emph{different} relation from the "a is comparable to b" relation.

[vital dew]

Troposphere

[tacit thistle]

let's say we're dealing with the divides relation, a|b, the relation is antisymmetric since a|b does not mean b|a, but if we're trying to see if two elements are comparable either a|b or b|a (or both), but if both are true that would make the divides relation symmetric

[coral parcel]

No, it wouldn't make the "divides" relation symmetric. It makes the "is comparable by 'divides'" relation symmetric

They are not the same relation.

[tacit thistle]

explain i'm confused

can u give me like an example

[coral parcel]

There are two different relations involved.

The "divides" relation relates, for example 5 to 45, but doesn't relate 45 to 5.

The "is comparable by the divides relation" relates 5 to 45 and also relates 45 to 5.

The first relation is a partial order. The second one is not.

[tacit thistle]

why does it relate 45 to 5?

[coral parcel]

Because 5 | 45.

[tacit thistle]

yes but 45|5 is not a whole number

[coral parcel]

By definition "45 is comparable to 5" holds if 5 | 45 or 45 | 5. One of these is true, so 45 is comparable to 5.

[tacit thistle]

oh I see

ok

thanks

[coral parcel]

On the other hand, for example, 25 and 45 are not comparable.

[tacit thistle]

How is Example 6 totally ordered?

U can have a = 3 , b = 2

for example

[coral parcel]

Yes?

[tacit thistle]

not every two elements are comparable

a<=b is the relation right?

[coral parcel]

a=3 and b=2 are comparable because in that case b<=a is true.

[tacit thistle]

but is the relation is a<=b

not b<=a

im confused

[coral parcel]

Again, the definition of "a comparable to b" is that a <= b OR b <= a. One of these is enough.

[tacit thistle]

I see

[coral parcel]

You need to distinguish between "is comparable to (by the relation R)" and "is related to (by the relation R)". The "comparable to" is a weaker condition.

[rich hedge]

it would be an element of the set right or no?

and if it isn't could you please say why

[weary tiger]

It is an element

you are right

[rich hedge]

thank u bruh

ur a huge help

[tacit thistle]

this is an equivalence relation right?

[weary tiger]

looks reflexive

looks symmetric

and prob transitive too

looks good to me

[gilded ember]

Let $S={a_1,a_2,a_3,\cdots,a_n}$.

The number of functions from $S$ to ${0,1}$ is just $2^n$, since each input of the $a_i$ can have 2 choice of output.

Recall that the number of subsets of a finite set with cardinal number $n$ is just $2^n$. Hence the power set $\mathcal{P}(S)$ of a set $S$ is of cardinality equals to the set of all functions from $S$ to ${0,1}$.

Therefore, there is a one-to-one correspondence between the power set $\mathcal{P}(S)$ of a set $S$ and the set of all functions from $S$ to ${0,1}$.

Yet I can’t understand why this result implies the theorem 0.14. Can anyone help?

[vital dew]

Trenton

[stray reef]

you do not really need the assumption of S being finite to establish this bijection

[gilded ember]

Due to the Cantor’s theorem?

[normal hatch]

What is

The no of subsets in AxB = ?

[coral parcel]

What are A and B?

[stray reef]

no

[coral parcel]

(2) is from Cantor's theorem, though.

[normal hatch]

I need formula

[normal hatch]

Any sets

[coral parcel]

Do you know how to find the number of subsets of a single set C?

[normal hatch]

@coral parcel yea

[coral parcel]

Which is?

[normal hatch]

2^n

@coral parcel but my teacher made me note down

No of subsets of AxB = nA * nB
Which is for no of elements for Cartesian product so i m so confused

Or am i wrong?

[coral parcel]

That is the number of elements in A×B.

[normal hatch]

Yea i have good teacher...i looked at the text he was right the formula it said the same, so i was confused

[coral parcel]

which is never the same as the number of subsets.

[normal hatch]

So 2^n right an

Ans?

[coral parcel]

Well, 2^(#A·#B) but yeah.

[normal hatch]

Thanks for the help

[autumn hull]

,help

[vital dew]

A brief description and guide on how to use me was sent to your DMs!
Please use ,list to see a list of all my commands, and ,help cmd to get detailed help on a command!

[weary tiger]

Hi, does anyone have an idea how to solve this problem in a 'nicer' way? There is an urn with 5 distinct coloured balls, we draw 20 times every time putting ball back in the urn. What is the expected number of colours drawn this way? So the problem is to find P(X=k) for k in {1,2,3,4,5}. What I tried to do, was just for each k count the 20 element sequences satisfying a_i \in [k] and for all n \in [k] exists i such that a_i = n, then divide by 5^20 (all possible draws). Although somehow Im miscounting. Maybe there is a better approach, if not really, how would you calculate in this way say P(X=3)?

[elder berry]

What have you tried? Looks like a principle of inclusion/exclusion sort of thing

[weary tiger]

Yeah when calculating I saw some i/e-esque terms appearing, wasn't sure how to model it so i/e is useful.

[elder berry]

So did you try something like this
[(5 choose 3) 3^20 - (5 choose 2) 2^20 + (5 choose 1)]/5^20

[weary tiger]

Something very similar although not quite this. Shouldnt it be rather maybe 3 choose 2 and 3 choose 1 in the 2nd and 3rd term?

Maybe not quite again, but Im not sure about the thing you wrote

[elder berry]

Oh right, since we are working with just the 3 colors

It comes out to the same thing, the above would work as well

I think you meant
(5 choose 3) [3^20 - (3 choose 2) 2^20 + (3 choose 1)]/5^20

But it would simplify to the same thing No it will not lol

[tacit thistle]

confused on part b

do we distribute the ybar and then use demorgan's or do we use demorgan's directly

[tacit thistle]

Is this correct?

[unique elm]

for a relation to be reflexive

besides having (a,a) in R for all a that belong to a certain set

does the relation also have to be on one set

like a relation from set A to set B would not be reflexive?

[weary tiger]

the definition i am aware of has to be on one set

so A x A

like, you would say "R is reflexive on A" so it can only be reflexive on one set at a time i believe

[weary tiger]

does anyone understand the statement For p , it is sufficient q

[final cliff]

"P is sufficient for Q" just means "P implies Q".

If you know P is sufficient for Q, then anytime P is true you can conclude Q is true also.

[fair hull]

Hi, can anybody help me with this question? I am stuck..

this is what i did...

im sure somewhere im wrong.. or totally wrong on how i do it.. T.T

i cant use induction for this question..

[gilded ember]

sorry for late reply, thanks anyway

[coral parcel]

But "For P, it is sufficient that Q" not the same statement as "P is sufficient for Q". The word "for" applies to P in one of them and Q in the other one.

[coral parcel]

I would understand it as "if you know Q, then P will necessarily also hold". In other words, Q is a sufficient condition for P, or Q -> P.

[coral parcel]

That's a good start, but since you have two unknowns C, and D, you need two equations. Continue by computing v4 using both formulas to get a second equation.

[fair hull]

hihi thx, i got the answer already 🙂

[final cliff]

Ah shoot, you are right. I was misreading the original statement. Thanks for the correction.

[lusty compass]

I am here because your boy is scared shitless

any reccomendations to look or watch to get good at discrete maths

Long story short, I am in this Discrete math course in college, I know I am bad at math, I have taken C++ as an intro course and it was okay, But I struggled in Algebra and Pre Cal brought me to my limit, I am studying to be in IT and not some software engineer but I know these concepts are important but nevertheless I just want to start good any video series or resource would be helpful. Only one class has started it is the intro and all that, no material but I want to start having an idea and understand concepts so that I am not lost when I get to HWs and Lectures

[weary tiger]

what even is the question 😭

[weary tiger]

what concepts does the class have

because

discrete math books cover different areas

[lusty compass]

let me find the syallbus lol

[weary tiger]

depending on the book

[lusty compass]

they gave us a book online and it is okay

@weary tiger

[weary tiger]

ahh

looks like

you might have to go for

Rosens Discrete Math

or Susanna Epps Discrete Math

because they have the trees/algorithms section to them

[lusty compass]

Would you say the rosen book is easy to follow along for someone thats dog poopies at math

[weary tiger]

I've only done bits of the book but I think its good enough for first timers

proof of what exactly

if A, n are coprime then gcd(A, n)=1

from there it follows immediately from bezouts identity

why would it not be necessary

actually i don't believe it is necessary

it should be

if gcd(a, n)=d and Ax=B (mod n) then d | B

you said if gcd(A, n) divides B then Ax=B (mod n) exists

converse of what I said

not sure if its true though

either way though, its probably a good condition that A, n are coprime for Ax=B (mod n) to have a solution since A^{-1} might not exist in mod n

[chilly kayak]

check this please

[weary tiger]

would my answer be DNE if the question is asking find the truth value of p if "(p AND q) -> (q OR r) is false"

its a tautology so i assume its Does Not Exist

[chilly kayak]

https://highered.mheducation.com/sites/125967651x/student_view0/extra_examples.html

Extra Examples Chapter 01 (1882.0K)

page 35

[rich hedge]

not even sure where to start with this

would it be yx and then yyyxyx ?

[cerulean wind]

yes

[rich hedge]

thank you

beginning of discrete is fucking me up cuz im trying to understand everything but i dont think thats the goal just yet

[weary tiger]

Does anyone have any good resources to explain predicates, universal/existential, and nested quantifiers?

[weary tiger]

most discrete math books

Discrete Mathematics by Rosen, Discrete Mathematics by Susanna Epp, How to prove it by Daniel J Velleman

theres 3

Well I figured as much. I just was not sure if there was a standard suggestion such as Stewart for Calculus

the first two seem pretty standard

or at least i've seen the name come up a lot

[still slate]

Would anyone be able to help me out on this next part? I seem to be lost on how to test this part into the original question to prove it. Thank you.

[brave rock]

You conclude that either k1 = k2 = 1 or k1 = k2 = -1 here.

As for why, since they are both naturals and their product is 1, we have |k1| <= 1 and |k2| <= 1, which reduces the problem to a finite search.

The rest follows immediately.

[still slate]

I appreciate it. I read something similar online, but you throwing in absolute values in there made it make sense to me. Thank you!

[brave rock]

No worries

[weary tiger]

Are topics including difference equations part of discrete math?

Like discrete time dynamical systems

[unique abyss]

Recurrence relations are often taught in discrete math so yeah

One way to think of it is like the discrete version of differential equations

[weary tiger]

Yeah I was just wondering if it officially classifies as discrete math

I never had a course about discrete math but I work much with discrete time dynamical systems

[verbal crystal]

Not sure if this is the right channel to ask this or if I should go into a help channel,

but I wanted to ask about interrogatives and imperatives being true or false

[brave rock]

This is not really a math question, perhaps a linguist could help

[verbal crystal]

hm well it is in my discrete structures class

[hexed crater]

I was hoping if someone could check if I did this correctly? any help would be appreciated thank you!

[chilly kayak]

if you can't assign a true or false value, then is not an statement

questions are not statements

same with imperatives

"get out" . you can't assign a true or false value

[verbal crystal]

gotcha, I figured that was the case. just wasn't 100% sure

[chilly kayak]

"do you want to go to vacation?" same

[verbal crystal]

appreciate it

[tepid crystal]

Does the following connected simple graph G exist?
δ(G) ≥ 2, V(G) = 20, no 2 vertices with same degree are neighbors

[halcyon dock]

What is a unit set?

[stray reef]

what's delta(G)? minimum degree over all vertices?

[chilly kayak]

this is an author error, right?

A) is correct answer. no?

[tepid crystal]

Yes

[coral parcel]

Yeah, A looks correct, and the offered refutation of it is nonsense.

[half bane]

Is a square with it's diagonals a planar graph?

[coral parcel]

Yes -- you can draw one of the diagonals outside the square instead.

Then there are no crossings.

[half bane]

Oh, so is it true because this graph is an isomorphic graph?

[coral parcel]

Yeah, "planar graph" just says that the graph has a crossing-free drawing, not that the particular drawing you're looking at is one.

[half bane]

Thanks, I get it now!

[surreal crescent]

Hello! Suppose I have two partially ordered sets A and B. There are many possible relations between them. Let me denote the set of such relations A — B. Is there a natural way to define a partial ordering of A — B?

[coral parcel]

"Natural way" is fairly vague. Since your set is the power set P(A×B), you could at least order it partially by set inclusion, but that's probably not very satisfying because it's not using the orders on A and B at all.

[surreal crescent]

Yep. For example, one ordering for functions A → B says f₁ ≥ f₂ ≔ ∀ (a: A), f₁ a ≥ f₂ a. But this definition only looks at the ordering of B.

So, I am looking for something similar but for relations.

I can make «natural way» precise by asking «is the category of partially ordered sets and relations closed». But this is a tall order — I should be happy to see a «weakly universal», non-unique construction.

I suppose I shall have to require that relations be monotone then…

What are monotone relations though? Looks like I have to do some more work here.

[halcyon dock]

How do you prove two sets?

For example A = {1,2,3} and B = {1,2,3,3}.

How about infinite sets?

[hard citrus]

What do you mean by prove two sets?

[halcyon dock]

Prove them equal.

[honest holly]

Why do you need to prove theyre equal

Just look at it lol

[chilly kayak]

define "equal"

[halcyon dock]

Bruh

[halcyon dock]

What are the ways we can define it?

[cerulean wind]

formally, two sets A and B are equal if for all x, x in A iff x in B

[halcyon dock]

Can you show this using the example I provided?

[cerulean wind]

there is really nothing to show since sets are a mathematical object with don’t support repetition of its elements

so by definition, B = {1,2,3,3} = {1,2,3} = A

but for your question, given any two sets A and B (infinite or finite), to show that A and B are equal, you show that A is a subset of B and B is a subset of A

to show that A is a subset of B, you fix an arbitrary element a of A and show that a is in B

since A subset B is defined to mean for all x(x in A implies x in B)

[halcyon dock]

cool. so like how do I go about proving that say the even numbers equals the odd numbers?

Or show that they don't.

[cerulean wind]

the even numbers do not equal the odd numbers

they don’t even share any elements in common

to show that two sets are not equal, you need to find an element in one set that is not in the other

[halcyon dock]

I meant the same amount lmao

[cerulean wind]

you need to construct a bijection between the two sets

[halcyon dock]

Oh

What would that look like mathematically?

[cerulean wind]

that’s not really a precise question

are you asking for an example of a bijection from the even integers to the odd integers?

[halcyon dock]

You can't do it with a function right because there is not any equation that describes the odd numbers.

at least I know of lol

[cerulean wind]

i think you are confusing sets and functions from one set to another

a bijection is an invertible function between two sets

in order two show that two sets X and Y “have the same size” or are equinumerious, you need to find a function f : X —> Y that is both injective and surjective (then f will be a bijection between X and Y)

[halcyon dock]

okay thanks a mil

Why is your name c squared btw?

[cerulean wind]

my initials are CC

[halcyon dock]

Isn't c a already large number. Why do they have to square it.

😆

[halcyon dock]

Nice sounds cool

[cerulean wind]

lol i always thought of it as a variable

[rose wing]

how to represent "M to N Cardinality" in math? Is there any terms to describe it? Thank you

[weary tiger]

Can you restate your question? No clue what you mean.

[rose wing]

M companies can have N customers.

[weary tiger]

What about them...

[rose wing]

?

[weary tiger]

?

[rose wing]

https://www.youtube.com/watch?v=ri2ARKNB_gI

[weary tiger]

I have no clue what you are asking, sorry. Maybe someone else can help.

[weary tiger]

hey guys, could we consider the relationship between combinations and combinations with replacement the same as permutations and factorials?

[broken plank]

@weary tiger I'd like to say no to that, although I'm not sure what sort of relationship you're describing between permutations and factorials

typically speaking, when you don't have replacement, you answer can be written as some sort of factorial expression, while when there is replacement, it can be written as a power of something

For example, suppose you had to choose 5 marbles of 5 different colours, and you arranged them from left to right, if there was no replacement, you have 5 marbles for the leftmost position, then 4, since no replacement, for the next position, then 3 and so on, giving you 5! combinations, while if the selected marble was replaced, then you have 5 for every position, so 5^5 combinations.

[primal jolt]

im having trouble setting this up. it says to prove it by induction. im still kinda struggling with the whole strong induction thing.

the basis is 0 right? cause i can see how if there were 0 offspring, then we would have 1 node, which is odd.

[sharp field]

it can be whatever, as long as the case is easy to verify

[primal jolt]

ok, so the basis is true. so now my induction hypothesis...isn't it that we assume that it's true for a "0 (< / 🙂 k (< / 🙂 n"?

the smileys are the = sign. idk why it changed it.

[brave rock]

Discord turns =) into 🙂 by default. You can turn this off in settings

You could also just write <= instead of (< / =)

[primal jolt]

ok ty

[cerulean wind]

@primal jolt here is your setup:
define the set M = {n : if T is a binary tree with n leaves then T has 2n - 1 nodes}

1. show that 1 is in M
2. show that if 1,2,...,n in M, then n+1 in M
3. conclude via strong induction that M is equal to the set of natural numbers and complete the proof

[weary tiger]

thanks for taking the time to answer ZeBeast. I just felt that since combinations with replacements has replacement, maybe its like factorials. This is pretty confusing, not gonna lie.

[sturdy helm]

each edge e ∈ E, an MST of graph G − e is also an MST of graph G.”```
How do I check this efficiently?

[cerulean wind]

constructing an MST for a graph can be done efficiently via prims algorithm or kruskals algorithm, for example
@sturdy helm

[sturdy helm]

yeah right, but question is different

i have to check this in O(VE)

[cerulean wind]

use this to check it efficiently

given a graph G, for each edge e, construct an mst for G - e in V^2 time

then check if it is an mst for G

[sturdy helm]

okay so mst calculation takes ElogV time so, if i do that for every edge

it would be

E^2 log(V)

but i have to do all this in O(VE) time

[cerulean wind]

maybe i misinterpreted this

so for each edge e, if we are given an mst of G - e, it takes V steps to check if it is an mst of G

if we do this for each edge then it is EV time

[sturdy helm]

we are not given MST of G\e

[cerulean wind]

that’s what the condition says

[sturdy helm]

the way you are saying it would lead me to calculate all the MSTs after removing one edge

which is not efficient right?

[cerulean wind]

no, it’s just saying that if we have an mst of G - e, then it must also be an mst of G

it’s not saying to construct and check every mst of G - e

[sturdy helm]

each edge e ∈ E, an MST of graph G − e is also an MST of graph G.” Design an O(mn)
time algorithm to check if a given connected graph G is edge-fault-resilient```

mb

this is complete question

[cerulean wind]

yes ik

[sturdy helm]

the fact that MST of G\e is given doesn't make sense to me

for this problem

the only input I have is graph G

nothing else

[cerulean wind]

i’m having a hard time getting my pint across

let me think a moment and see if i can reformulate

[sturdy helm]

sure

[jagged osprey]

im new to discrete math and its so confusing

for example

B = {2,{2},{3}}. {2}⊆ B ?
dont get why {2} is the subset of B

[vale cairn]

A is a subset of B precisely if every element of A is an element of B.

What are the elements of {2}? Are they elements of B?

[jagged osprey]

but where is A?

[vale cairn]

That was just a more general statement about sets aha sorry

Just reminding you what a subset is

[jagged osprey]

so if A was {2}, would it mean B ⊆ {2} ?

[vale cairn]

Uh okay maybe I've unwittingly caused some confusion - no

I'm saying A is a subset of B iff every element of A is an element of B

Take A = {2} in this example

What are the elements of {2}, and are they all elements of B?

[jagged osprey]

the element of {2} is A

{2} Ɛ A

and they're not all elements of B because B has other elements not just {2}

thats how im getting it

[brave rock]

No, A = {2}, A is certainly not an element of itself. 2 is the only element of {2}.

[jagged osprey]

so A = {2}

how can you use that then to prove that A is a subset of B

[brave rock]

So you look at the elements of A, and for each of them, you show that it is an element of B.

The only element of A = {2} is 2. So all we need to do is show that 2 is an element of B.

This is what potato was saying a moment ago

[jagged osprey]

wait

but i thought now that {2} or 2 is not an element of A

since A isnt an element of itself

is there any math i should go back and relearn since I really dont get how these concepts work

" {2} is an element of 2 "

" 2 is an element of A "

2 Ɛ A

[brave rock]

This is wrong

[brave rock]

This is right

[brave rock]

You are confusing {2}, which is a set containing just the element 2, with the number 2.

2 is an element of {2}

{2} is not an element of 2 — in fact 2 is not a set*
||*Yes, I know in the usual construction of the naturals 2 is a set, I don't care for this at the moment||

We are defining A = {2}

So we are just giving this set, namely {2}, the name A.

So 2 is an element of A

3 is not an element of A

Does this make sense?

You're not answering so I'll continue for a bit longer.

Now remember that {2} is a different thing from 2.

So while it is true that 2 is an element of {2}

It is NOT true that {2} is an element of {2}.

Similarly, it is true that {2} is an element of { {2} }

{ {2} } is a set containing exactly one element, namely the set {2}.

Note conversely, that 2 is not an element of { {2} }. It is an element of an element of { {2} }, but it is not an element.

[surreal crescent]

This person is talking about data bases, or so it appears. In relational data bases, it is a frequently seen construction that you would have two tables employee and project that each have a primary key (and any other columns you could need), and then a third table works with only two columns for the keys of employee and project. There is no special name for this in Mathematics since this does not say anything non-trivial yet. You could make an argument that having this third table lets you represent your data more efficiently, but this argument is not made in the video.

[lusty fern]

what is meant by "rigorous' proofs?

like each step in the proof has to prove the previous step?

[brave rock]

A rigorous proof is essentially one that uses correct inferences to make conclusions, without appealing to facts that have not been proved.

[lusty fern]

ok so not making assumptions

[humble pollen]

oh nvm lol

oh, wait i should probably post in a help channel instead. Mb

[jagged osprey]

got it thanks

[honest holly]

As opposed to non-rigorous hand wavy proofs

for example, fundamental theorem of calculus

[still slate]

Anyone have any resources or proof on how the second logical equivalence is proven? We went over it in lecture the exact steps, but I was lost the entire time

[haughty garden]

p -> q = (not p V q)
= (not p) V not (not q) (by double negation)
= not (not q) V (not p)
= (not q) -> (not p)

You can let r be (not q) and s be (not p) and it’s easy to see that the second last line is just (not r) V s which is equivalent to r -> s which is equivalent to the last line

[still slate]

I guess where I got lost is why are we using double negation? I see he did that in my lecture notes as well

[haughty garden]

Double negation is used so that we can pull out a “not q” eventually

Note that what you wanted to prove was (not q) -> (not p) which is equivalent to not (not q) V (not p)

[still slate]

That is starting to make sense. I really appreciate it a lot

[still slate]

For the second step, when applying the logical equivalency, when did we only change p to not p and the operator?

Why was not (q and r ) left alone.?

[lusty fern]

I’m confused with this wording

“ Find 2 integers x and y that do not have the same parity such that xy - min(x,y) is odd.

Is it asking for a proof?

[wraith aspen]

hey guys

[lusty fern]

Is this the same as :

“ If 2 integers x and y do not have the same parity then xy - min(x,y) is odd.”

[stray reef]

no it isn't

the first asks you to prove by example the statement "exist x, y: x and y have different parity and xy - min(x,y) is odd"

the second is "forall x, y: if x and y have different parity then xy - min(x,y) is odd"

[wraith aspen]

Can somebody help me with the conversion of statements involving "if ..., then ..."

I did the 'a' part

[lusty fern]

So I’m just plugging in numbers?

[stray reef]

idk what you are doing right now

but as i said

the statement you presented first is an existence statement

which is meant to be proved by presenting one example

[lusty fern]

Just odd/even proofs

[wraith aspen]

my answer for "a" came out to be "The grass isn't purple, only if the sky isn't green"

I don't need complete answers as that would be plagiarism, help with underlying concepts would be sufficient

:/

[lusty fern]

For some reason I’m getting a even answer every time, not odd

[wraith aspen]

3 and 4?

12 - 3 = 9

[lusty fern]

LOL

I’m so dumb

[wraith aspen]

I mean

[lusty fern]

Thanks

[wraith aspen]

no problem

[lusty fern]

So you know how odd is 2k + 1

[wraith aspen]

the trick was to keep the odd number smaller

[lusty fern]

What about 2k - 1

[brave rock]

2k - 1 = 2(k-1) + 2 -1 :)

[lusty fern]

I see

[wraith aspen]

same could be said about this one too ig

2k+1 = 2(k+1) - 1

always odd

[lusty fern]

yeah

2k always even then +1 or -1 just makes it odd

[wraith aspen]

yeah

[shadow silo]

New to discrete and i’m having trouble with 2d and 2f, anyone mind giving me the details or steps to get to the answer ?

[stray reef]

there are twelve questions you are supposed to answer, five of which are YES/NO questions and seven of which require you to write down a set.

are we to understand that you are having trouble with answering some of these questions in subproblems (d) and (f)?

or would you rather say that the entire problem is leaving you completely stupefied and unable to even begin? @shadow silo

[shadow silo]

yeah im having trouble with the entire problem honestly, ive been re-watching some lectures and i cant seem to grasp it at all

[stray reef]

ok well alright

there are twelve questions you are supposed to answer, five of which are YES/NO questions and seven of which require you to write down a set.
do you at least understand this?

like, do you understand that in each subproblem there are 12 things asked of you?

[shadow silo]

for A you have to write a set down if i am correct and the B are the YEs and No questions?

or am i mistaken

[stray reef]

...you are mistaken

as was i

[shadow silo]

figured

[stray reef]

five yes/nos, two numbers, five sets

it sounds like a lot but in all honesty each one of these is like

bite-sized

would you like to go through each one of these one by one

[shadow silo]

that would help honestly

[stray reef]

ok

let's do this for letter (d), i.e.
A = {a, b, d, 1, 4, 5} and B = {c, e, 2, 3}

these are going to be the sets we work with

and our universal set, which will matter at one point, is {a, b, c, d, e, 1, 2, 3, 4, 5}

are we clear on this and are you ready

[shadow silo]

yeah

[stray reef]

ok

question 1: Is d ∈ A?

[shadow silo]

Yes

[stray reef]

great

question 2: Is A a subset of B?

[shadow silo]

No

[stray reef]

good

question 3: Is B a subset of A?

[shadow silo]

Yes

[stray reef]

...since this is a yes/no question i don't really have any option but to tell you that you're wrong and no, B is not a subset of A

let's examine that in more detail

do you know what it means for one set to be a subset of another set?

[shadow silo]

Wait, If B is a subset for A if they are the same right?

[stray reef]

can you say that again but without it being word salad?

i do not understand this:

Wait, If B is a subset for A if they are the same right?

[shadow silo]

Is B a subset for A only when they are equaled to each other?

hopefully thats worded better

[stray reef]

the wording still could use some work

but now at least i can answer your question

no

we say $A \subseteq B$ (read ``$A$ is a subset of $B$'') if every member of $A$ is also a member of $B$.

for example, the set ${1, 2, 3}$ is a subset of ${-2, 1, 2, 3, 5, 11}$.

[vital dew]

Ann

[shadow silo]

so basically as long as the set has the numbers of the subset then it is considered the "subset"

[stray reef]

...

bad

on multiple accounts

i know i gave a numerical example but you must understand sets can have elements that are not numbers

the set of all children is a subset of the set of all humans on earth, for example.

let's go back to question 2 (Is {a, b, d, 1, 4, 5} a subset of {c, e, 2, 3}?) to which you correctly answered "no"

tell me: was that no just a random guess, or did you take some time to think it through before answering?

[shadow silo]

i saw that in the set {a, b, d, 1, 4, 5} there was no same points in {c, e, 2, 3} that were alike so i said my answer as NO

[stray reef]

ok, but when the sets switched roles and i asked you whether {c, e, 2, 3} was a subset of {a, b, d, 1, 4, 5}, you answered "yes". why was that?

[shadow silo]

i figured that if set A was not a subset of set B then if swapped it could turn into a subset, i honestly don't know my logic to it but it was more of a process of elimination thought process

[stray reef]

ok so it was no better than a random guess

maybe it is better if i repeat the definition of subset in relation to these two particular sets

A = {a, b, d, 1, 4, 5} is not a subset of B = {c, e, 2, 3}, because there exist members of A that aren't members of B; for example, 1 ∈ A but 1 ∉ B.

do you understand this? read the entire statement carefully and ensure you understand every part of it and the statement as a whole.

[shadow silo]

I read and understand it now

[stray reef]

ok

now you try it. explain in the same fashion why B is not a subset of A.

[shadow silo]

So B is not a subset of A because in B {c, e, 2, 3} there are members that A {a, b, d, 1, 4, 5} does not have

[stray reef]

and can you give an example of such a member?

[shadow silo]

e ∈ B but e ∉ A

[stray reef]

ok, good.

ok, let's continue down our little table

question 4: Is A = B?

[shadow silo]

No

[stray reef]

and why is that?

[shadow silo]

in order for A = B , A needs to be a Subset to B and vice versa

[stray reef]

ok yeah good

and in our case, neither set is a subset of the other

so in fact we have more than is needed to ascertain that the sets are not equal

ok

moving on

question 5: Are A and B disjoint?

this is the last yes/no question

[shadow silo]

Yes

[stray reef]

ok, good

just to make sure

do you know what it means for two sets to be disjoint?

[shadow silo]

When a pair of sets have nothing in common

[stray reef]

...ok yeah that works

would have been slightly better if you said "have no elements in common"

alright

now we come to two questions whose answer is going to be a number

question 6: How many elements does A have?

[shadow silo]

6

[stray reef]

ok, good

question 7: How many elements does B have?

[shadow silo]

4

[stray reef]

ok

good

ok

the answers to the next five questions are themselves sets

question 8: What is the complement of A?

[stray reef]

this is the point at which the universal set actually matters.

[shadow silo]

so it would be { c , e , 2 , 3}

[stray reef]

yes

ok

question 9: What is the union of A and B?

[shadow silo]

A = {a, b, d, 1, 4, 5} U B = {c, e, 2, 3} = {a, b, c, d, e, 1, 2, 3, 4, 5}

[stray reef]

notation could be somewhat better

but yes that is correct

question 10: What is the intersection of A and B?

[shadow silo]

wouldnt that be None?

[stray reef]

there's a word for that

what do we call a set that has nothing in it

[shadow silo]

empty set

[stray reef]

right

ok

question 11: What is A - B?

[shadow silo]

{a, b, d, 1, 4, 5}

[stray reef]

and now question 12: What is B - A?

[shadow silo]

{c, e, 2, 3}

[stray reef]

great

ok now aside from the hiccups you had with subsets

it appears that you're able to do all this on your own

[shadow silo]

correct, thank you for helping me with this!

helped me understand it way better

[stray reef]

i mean the thing is

for literally all the other questions you were able to answer them when asked

just fine

so was it just that you found it daunting to have to decipher and answer 12 questions, or what

[fluid dune]

can someone help me with some questions please?

[rich hedge]

thats the correct way to b. and c. and e. right?

[stray reef]

b and c yes, e no

what you have for e says john is wealthy and neither healthy nor wise

[lime plinth]

I was recently solving 2-SAT related problems, one of them was the following:

You are given an undirected graph that consists of n vertices and m edges. Initially, each edge is colored either red or blue. Each turn a player picks a single vertex and switches the color of all edges incident to it. That is, all red edges with an endpoint in this vertex change the color to blue, while all blue edges with an endpoint in this vertex change the color to red.
Find the minimum possible number of moves required to make the colors of all edges equal.
This is clearly just a 2-SAT problem since we only care about choosing a vertex once or not choosing it at all (actually two of them: for making all the edges red or blue, and then choosing the minimum).

I'm wondering if we can solve a similar problem where instead of coloring edges we would color vertices: each turn a player picks a single vertex and switches its color and the color of all adjacent vertices. I've been trying to start with some simplifications:

1. initially all the vertices are colored red
2. the goal is to color all vertices blue
3. we don't care about the number of moves
   But even this turned out to be a hard problem, at least I can't figure out how to solve it efficiently. The only solution that came to mind so far is to use linear algebra:
   Let A be the adjacency matrix, then by calculating (A^-1) * (1, 1, ..., 1)^T we get a solution. Finding the inverse matrix and matrix multiplication are too inefficient though, especially if m is much less than n^2.
   Are there any better methods to solve it? And what can we do to generalize it (remove all/some of the simplifications)?

[coral parcel]

What makes the edge-color problem tractable is that there are only two possible moves that influence the final color of each edge.

We don't have that luxury in your variant.

(Hmm, it's not actually obvious to me how you'd use 2SAT to minimize the number of moves in the first problem, rather than just find out if a solution is possible).

[lime plinth]

If for each X <-> Y we also have !X <-> !Y (and for X <-> !Y we have !X <-> Y etc) then it's possible to find a solution of 2-SAT with the number of variables set to 1 minimized
For each pair of components we just need to choose the one that has more negated variables
And in our case we have exactly that. E.g. if we want to color all the edges blue:

1. uv is already blue: add edges u <-> v and !u <-> !v (either both of them are chosen or none)
2. uv is red: add edges u <-> !v and !u <-> v (exactly one of them is chosen)

[coral parcel]

Ah, duh! Thanks.

[coral parcel]

They are "check that you've understood what the words mean" exercises. Not "follow a general method for computing this" exercises.

Yeah.

Well, it should be clear that an independent set cannot contain more than two vertices of an independent. Similar for the inner star.

So if you can find an independent set that has two vertices in each, that must be maximal.

[agile magnet]

Not sure if this is the appropriate channel

suppose you have N pencils, each one of c different colors

how many ways are there to pick a subset of k pencils

I tried doing stuff with multinomials but the issue is that assumes no bound on the number of pencils of each color

I have a solution that uses polynomials and fast polynomial multiplication algorithms but is there a purely combinational way to do this??

We are told that k << N

so really this is something like "how many ways are there to put k balls into c bins" but some bins have a fixed capacity

[coral parcel]

What do the pencils have to do with picking a subset of k colors?

[agile magnet]

should say "k pencils" my bad

[coral parcel]

Okay, and treating pencils of the same color as identical?

[agile magnet]

yes

[coral parcel]

I think you might need to know how many pencils there are of each of the colors.

[agile magnet]

you do know that

[coral parcel]

So you know N_1, N_2, ..., N_c, where N_i is how many pencils have color i, and N_1+N_2+...+N_c=N?

[agile magnet]

ya

If we had unlimited numbers of each color it would be nice and fun and easy because that's just a multinomial coefficient

[true venture]

Hello, I have a question about finding periodic functions.
I want to find a function that repeats {1 ,3,1,0} for inputs {1,2,3,4,5....}
If found ones before messing around with n mod 4, but is there a more systematic way to think of this?

[zinc bloom]

hello

Please solve this question

Please help me guys

I want to know the answer

anyone??

[unique abyss]

I got 457

[zinc bloom]

😭 i writed 323 in exam

-10 marks

[unique abyss]

not completely sure if this is right but

I tried using inclusion exclusion to find the number that should be subtracted from 1000

[zinc bloom]

I divided 1000 by 3,5,7 separately

you are right

and incremented 1 if answer comes in point

then I added all

then minus from 1000

[unique abyss]

yeah so this alone won't work because you will overcount some numbers

for example take 15

[zinc bloom]

yeah

my bad

[unique abyss]

it's a multiple of 3 and 5

[zinc bloom]

hey are you free I want to discuss my todays paper with you

[unique abyss]

sure

You can just ask here, someone will come along and help

[coral parcel]

Inclusion-exclusion is almost certainly the intended solution method here. "Use the pigeonhole principle" must be a typo; there's no reasonable way to employ that.

I get 457 too, by another method: The pattern of coprime numbers repeat with a period of 3·5·7=105, and due to the Chinese remainder theorem there are 2·4·6=48 coprime in each period. That gives 9·48 of them up to 9·105=945. But the pattern is also symmetric under negation, so we get a further 24 solutions from a last half-period which takes us all the way up to 997. Then we just need to count 998 too, for a total of 9·48+24+1=457.

[unique abyss]

Yeah I think so too

The closest thing to pigeonhole principle I can see, is when you are calculating how much to include/exclude you have to use the floor function so

$\left \lfloor \frac{1000}{3} \right \rfloor + \left \lfloor \frac{1000}{5} \right \rfloor \ldots$

[vital dew]

ALPH2H

[unique abyss]

Someone what reminiscent of generalized pigeonhole but barely

[unique abyss]

Yeah this is neat way to do it

[azure willow]

could somebody explain one thing for me really quickly?

what is a fault-line, in regards to chessboards? i'm super confused on what it specifically means

[jagged osprey]

in most cases is the empty set almost always a subset of a set, the only time its not is if theres a set of the empty set?

[grand totem]

It's a subset of any set, no exceptions

[stray reef]

@azure willow did the word "fault-line" come up in a problem you were solving? it sounds like something ad-hoc for that problem specifically

[weary tiger]

Any tips for discrete math exam on combinatorics, resursive equations and graph theory?

[azure willow]

how would i start this?

[weary tiger]

definitely pigeonhole principle

[lusty light]

∀x(A(x)→B(x))
can someone help me negate this ? im very new and trying to self teach with online questions / courses !

[weary tiger]

well what would you do first?

[weary tiger]

Question: Find all positive two digit integers whose product of their digits divide their respective integers (example, 11 is divisible by 1×1 = 1).

I used modular arithmetic to try solving this problem. I'm getting the set of answers {11,12,15}. But, that's the incomplete answer. Actual set of answers is {11,12,15,24,36}. Where am I going wrong?

[coral parcel]

Hopefully you agree that e.g. 36 is indeed a solution.

Try to plug a=3, b=6 into each of your intermediate conclusions to find where you somehow start concluding something that is false in that case.

That must be the location of an error.

(I can see at least one error, but it's more instructive for you to discover it yourself by checking step for step).

[floral field]

Saw this problem on social media, and I was kind of stumped

There has to exist some partitioning, where it’s possible, right?

[floral field]

If we cut it in n pieces, where all n pieces are symmetric about some line, can we still complete the task ?

[tepid crystal]

On a chess board n x n there is a figure on bottom left corner. Figure can move only one square right or one square up per turn. In how many ways can the figure reach top right corner?

Any tips how to approach this problem?

[brave rock]

Hint: the figure must go up n times and to the right n times, out of 2n total steps. So we must count the number of ways to choose which steps will be going right and which will be going up.

[tepid crystal]

What ive noticed is that, all squares except top right corner square, all far top squares and all far right squares, have a choice of 2

So i thought maybe its 2^(n*n - 2n - 1)

[brave rock]

Unfortunately that's not right.

Try for some small numbers, maybe.

[tepid crystal]

but for each step

I can only choose 2 other squares

unless im on top or right

[brave rock]

Exactly, so your approach doesn't work.

[brave rock]

Let me rephrase this hint.

[tepid crystal]

o wait

[brave rock]

You have 2n steps to choose. Exactly n of them must be right, and the n remaining must be up.

[tepid crystal]

i was looking at it like

2 choose 1

it might be

nxn choose 2

but that would make it even bigger number than my solution

[brave rock]

If you can't justify your answer, it's not good enough.

[tepid crystal]

wait how so

[brave rock]

This is just a hint, it's up to you to see why.

[tepid crystal]

are you telling me

any option i choose

I wont make more than 2n steps?

or less

[brave rock]

Let's think this through a bit.

You start in square (1,1)

and you want to get to square (n,n)

Moving up increases the second coordinate by one. Moving rightwards increases the first by 1.

You must increase (1,1) to (n,n).

[tepid crystal]

holy

[brave rock]

So you must take n-1 steps rightwards, and n-1 upwards.

Is this clear?

[tepid crystal]

yea

[brave rock]

Great.

[tepid crystal]

so i then calculate

on how many ways i can go right and the rest is up?

n times right*

[brave rock]

That's correct

[tepid crystal]

2n-1

[weary tiger]

Thanks 👍

[pulsar obsidian]

I think we can use combination also

n*C(2,1)

[brave rock]

This is not correct

[pulsar obsidian]

yup

ans is something else

ig

I can write a c++ solution which take polynomial time complexity for it

but what will be for formula, it's not 2n-1 for n=3 it's 4 but ans is 6

[brave rock]

There is a very simple formula for it which my hint will lead you to.

[pulsar obsidian]

okay I have already solved similar coding question(just figure is replace by a robot) i remember it now

it give time complexity O(2^n) which can be optimized to O(n^2), by mathematics we can make it O(n) if get the formula

[tepid crystal]

(2n - 2)! / ((n - 1)! x (n - 1)!)

[pulsar obsidian]

can you explain it?

[tepid crystal]

n - 1 moves going right to reach (1,n) square

same amount of moves up to reach (n,1) square

which is 2n - 2

so now it should be from that total amount, we choose n - 1

[pulsar obsidian]

what if we change question to m x n rectangle instead of square?

[tepid crystal]

so from (1,1) to (m,n)?

[pulsar obsidian]

I mean if the figure in bottom left of m x n matrix and it has to reach top right

[brave rock]

This is correct. Another way of writing this is 2(n-1) choose (n-1).

I'm afraid not

[tepid crystal]

yea so we start at (1,1) and have to reach (m,n)

it would probably be

since you need m-1 amount of "up" moves

[pulsar obsidian]

asking to me about programming?

[tepid crystal]

to reach most upper square

and n-1 moves right

to reach most right square

m+n-2

[pulsar obsidian]

yes..

[tepid crystal]

total amount of moves to reach (m,n) square

and you can choose either n-1 or (m+n-2) - n-1

[brave rock]

Correct, by the way

N.b that (m+n-2) - (n-1) = m-1.

[pulsar obsidian]

I am not getting it

like combination is used for choosing

[brave rock]

This is not a programming problem

[pulsar obsidian]

so why don't we choose 2(up or down) after each step

[brave rock]

Because we don't always have two choices

If I start off by going all the way up, all subsequent steps have only once choice

However if I go alternately up and right, all steps have two choices until the end

Since the number of choices is not uniform, we cannot use that method.

[brave rock]

I give away most of the answer here.

[pulsar obsidian]

oh ! i got your point

[brave rock]

Admittedly, I should have written n-1 instead of n, but oh well.

[pulsar obsidian]

but i didn't get logic of adding all the step and then choosing up or right

[pulsar obsidian]

awakening moment

got your reason feeling nice

[brave rock]

That's the right answer

The rest is unnecessary

By choosing the n-1 rightwards moves, you have implicitly chosen the rest

[rapid pelican]

∀x∃yP(x, y) v ∀x∃y𝑄(x, y)

im suppose to express the negations of this statement, so that all negation symbols
immediately precede predicates. how should i go around this?

[unique abyss]

First notice that you are negating a disjunction

so apply De'Morgan's law to turn it into a conjunction

after that, apply the negation to the for all and existential quantifiers

remember, that the for all turns into an existential and existential turns into a for all

that all negation symbols
immediately precede predicates.
This means to have the negation symbol preceding the P(x, y) and Q(x, y)

[rapid pelican]

thank you so much 🙂

[tacit thistle]

what does this mean?

[unique abyss]

a set with 0 as an element

since 0 times anything is 0

[tacit thistle]

what do the exponents mean

im confused

[unique abyss]

it's short-hand for repeated multiplication

In this set-builder notation, it's letting the exponents be any natural number

[tacit thistle]

what happens when n = 0

the full question

[unique abyss]

they're probably saying 0^0 = 1

so the set would be {0, 1}

[tacit thistle]

and when n = 1?

{00, 11}?

wait why is there a comma

I think it should be {01} when n = 0?

it's a string isn't it

[unique abyss]

when I said that, I hadn't read the full question that you sent lol

it does make more sense for it to be a string since you're dealing with grammars

[tacit thistle]

what happens when n = 0, n = 1, etc

[obtuse breach]

That should be the set of strings that look like n 0s followed by n 1s

[tacit thistle]

ok

[obtuse breach]

(not the answer to the question, but what the set looks like)

So it would be "", "01", "0011", "000111",...

[tacit thistle]

i see

[obtuse breach]

And 0^n here means 0...0 (n 0s)

[normal raptor]

Would this channel be where I can get help with Boolean Algebra ?

[coral parcel]

Here is fine for boolean algebras.

[normal raptor]

Awesome, thanks

I need to simplify as much as possible..I ended up with C(B'+A'B) But that doesn't feel right

[coral parcel]

The parenthesis is simply not(AB), isn't it?

[normal raptor]

I'm not sure. My list of theorems does not look similar to that.

[hybrid ravine]

Hi. Do I get help with Knuth Concrete math or art of programming? I'm at the very beginning, but I don't understand anything anymore. And sorry for my poor English.

[hybrid ravine]

Why are there two letters of "p" in the fourth picture?

[rich hedge]

validity or invalidity

i get p and q then r

but i dont know if im doing that correctly

[elder berry]

What are your propositions p, q, r?

Also you can do this with only two statements p, q

[rich hedge]

i figured that one out

[rich hedge]

would you be cool with answering a new question

create a boolean circuit

Would that be correct ?

[coral parcel]

The the last equation corresponds to the step

E3. [Reduce] Set m <- n, n <- r, and go back to step 1.
After this step has been executed, both of the variables n and r have the same value, namely the one previously had by r.
I'm not sure why Knuth chose to use the letter p for that value instead of r, but the name doesn't matter anyway.

I believe there's nothing particularly deep happening here. Remember that Knuth was originally writing at a time where programming was not widely known and understood, and writing for an audience who felt more familiar and comfortable with mathematical notation than with code. He's simply trying to convince that audience that the prose pseudocode in the first image corresponds (in a systematic way) to a rigorous mathematical definition.

[tepid crystal]

In how many ways can you organize letters "F","E","S","T","I","V","A","L" in array if letters "I" and "A" are always next to eachother, and letters "E" and "I" are never next to eachother?

My first attempt was to group "A" and "I" together and make permutations with other letters which would be 7! and time that with 2! since "A" and "I" can permute between themselves. Then I group letters "A" "I" "E" together, permute them with other letters which is going to be 6! and time that with 2! since letters "E" and "A" can permute between themselves, and final solution would be: (7! x 2!) - (6! x 2!)
If someone could confirm wether this answer is correct or I'm missing something

[elder berry]

When you group "AIE" together, I think you'll miss out on some words.

For example AIE<else> and EIA<else> will be present. but what about I being at the front?