discrete-math

[unreal stump]

Ok my instinct is constructing a MST

With a change of the total order

So a<b iff a > b in conventional order

So this should get a tree where edges are as high as possible

nvm ig that is 6a)

https://en.m.wikipedia.org/wiki/Expected_linear_time_MST_algorithm
I guess this could be what you want?

[weary tiger]

median of the weights

We can't do MST. That's for a). You can't find MST in O(m) time

[unreal stump]

Well this algorithm is MST in O(m)

[weary tiger]

The median selection algorithm can find the kth largest element in linear time

[weary tiger]

Interesting

[unreal stump]

Ok I guess they were not expecting this

[weary tiger]

median selection is deterministic though with no randomness

my TA said the problem involves finding the median edge and recursing on subgraphs

Not sure what the subgraphs are

In general, you can find the kth largest element without sorting using "median of medians algorithm"

[unreal stump]

Ok why does this seem similar

[weary tiger]

I'm guessing using median of medians eliminates the need for randomess

We also need DFS according to my TA

So instead of randomly picking an edge we might pick the median edge, and split the graph into subproblems like they did here

[unreal stump]

Possibly

I think the algorithm I linked is like "randomised quick sort*

While you want like quick select

[weary tiger]

yeah exactly

i think quick select and median of medians are the same thing

[unreal stump]

Ah

[weary tiger]

the point of the median is to split an array into equal sized left and right arrays

[unreal stump]

Actually it's the algorithm that finds the pivot

[weary tiger]

If I understand how they're reducing the problem into a subproblem I might be able to solve this

[jolly ledge]

How many possible inequalities can I form using "=", "<", ">" given n-number of arbitrary real. no.s ? For example, if n = 2, then its just a=b, a<b, or a>b. (No need to consider b>a or b<a, since they're equivalent to a<b and a>b respectively).

For n=3,
(a<b<c), (a=b<c), (a=b=c), (a>b=c) and so on...

[unreal stump]

3^n?

[jolly ledge]

I thought so too but it doesn't work for n=2?

[unreal stump]

3^{n-1} then

I was looking in terms of no of comparisons needed

[vestal bronze]

i don't know what's 3^(n-1) but it feels too small
oh it's what you can do with a,b,c... in that order

because there's a=c>b

which is not equiavalent to anything you'd count with 3^(n-1)

it implies a>b<c but it's not implied by it

it's bell number but each partition is times factorial

[unreal stump]

Ok if you want the total count of total orders

[vestal bronze]

like

[jolly ledge]

Total orders?

[vestal bronze]

@jolly ledge https://oeis.org/A000670 this?

[jolly ledge]

Wholly crap.... that's a LOT, zamn. Never knew that website existed, gimme a moment to look through

[vestal bronze]

wikiepdia has it too https://en.wikipedia.org/wiki/Ordered_Bell_number

not that we confirmed you meant this

[vital locust]

Prove that every tree with a vertex of degree 4 has at least 4 leaves

i'm struggling with this proof

i'm not sure where to start

should i try induction on the number of vertices?

[jolly ledge]

This should be it, tysm

Damn tho never expected it to be this complex

[lavish peak]

need help with this question (number d):

heres the answer i came up with: $\binom{9}{5}\bullet\binom{4}{3}+\binom{9}{3}\bullet\binom{6}{5}-\left[\binom{8}{5}\bullet\binom{3}{3}+\binom{8}{3}\bullet\binom{5}{5}\right]\ =\ 130+90-56-56=108$

[vital dew]

silveh

[lavish peak]

the thought process is that i find the number of ways Cal and Dot do sit in the same row, and i subtract that from the total number of ways 9 people can be standing in the 2 rows

basically just finding the complement

is this correct?

[lavish peak]

this is assuming that when either Cal or Dot are not in the picture at all is an instance where theyre not standing in the same row

[slender hawk]

Greetings, I am taking discrete math honors as a Mechanical Engineering student and I am trying to come up with a project that would incorporate both disciplines. Does anyone here have any good ideas on how to get started, or where I could look? TIA !

[unreal stump]

What does your discrete math class cover

Because like in theory discrete math can mean anything

https://www.sciencedirect.com/science/article/abs/pii/0094114X95000303
Could be relevant

[sacred fern]

Could someone help with the justification of this?

[obtuse lance]

what I do is I imagine I have the series written out like $a_0+a_1x+a_2x^2+...$ and try to imagine what terms contribute to any single term in this, like $x^n$ how can I get that from $\prod_{k=1}^\infty (1+x^k)$?

[vital dew]

Merosity

[obtuse lance]

if you expand out the product a bit it might help to get a feel for it until you're comfortable with what happens

I think of it like each term 1+x^k is like x^0 + x^k and you are picking exactly one coefficient from every term, and only finitely many end up being nonzero

I think this is hard to see unless you just expand the product yourself or I hand hold you through it

to be a little more clearer, like I said work backwards, so like for instance $x^6$ terms can come from $x^6 + x^1 * x^5 + x^2 * x^4 + x^1 * x^2 *x^3$

[vital dew]

Merosity

[sacred fern]

Wow that’s ingenious

How do people come up with this 🥴

[hearty geode]

\

[obtuse lance]

just sitting and trying random crap alone in a room for many hours, honestly lol

[coral parcel]

It doesn't help that "the number of partitions of n into distinct parts" can be a somewhat impenetrable description of what the formula is trying to do in the first place. I can deduce what it must mean here by working backwards from the generating function, but it wouldn't be immediately clear to me, for example, that "into distinct parts" implies that the order of the distinct parts doesn't matter.

[jolly ledge]

I've understood up to the part up till where they came up with Q_1 from, but I'm unable to understand how Q_2, 3 and onwards are formed...

[pulsar glade]

take that vertex to be the root. Of course it cannot be a leaf, so you will have 4 branches.

Each branch must have at least 1 leaf. QED.

[vital locust]

are we allowed to assume the vertex with degree 4 is a root?

do we have to consider the case where it's an internal node?

[pulsar glade]

What? it's an unrooted tree. You can take any vertex to be a root.

Unless we're using different terminologies.

[vital locust]

ahhh okay okay that make sesne

[lavish peak]

need help with b

[vital locust]

I think you can use a generating function and find the nth coefficient

[lofty patrol]

Hi! Does anyone mind just explaining how baye's rule is different from conditional probability? I understand that baye's is kind of related to a new understanding you get after getting new info, but it seems a bit abstract to me/not too clear

And what's the point of using baye's I guess? I'm just having trouble seeing it in the bigger context of probability

[inner otter]

Bayes' Theorem is a statement about conditional probability (i.e., it's not different)

[lofty patrol]

Got it hm, but I guess they're not the same thing though?

Oh wait, I just saw my notes that Bayes' Theorem is just rearranging terms in conditional probability. I'm not entirely sure about this, if anyone would mind explaining?

[inner otter]

It is still a conditional probability. Read this post if you need some clarification: https://stats.stackexchange.com/a/250737/42597

[weary tiger]

more precisely it tells us how to go from P(B|A) to P(A|B), sort of like a way to invert things

[lofty patrol]

Thank you!

[fringe siren]

i have trouble building minimal total DFA from this regular expression:
L = Σ∗ \ ({1, 2}Σ∗ ∩ Σ∗{3}) ∪ {123}∗

even more funny, after the DFA is built, it has to be proven that it is minimal and total

why do one need mental health when one have discrete math

[delicate maple]

Does someone mind helping me w a problem rq?

[royal holly]

how do u tell if its valid or invalid

from the truth table because im confused a bit

[silk basalt]

there are rules

[silk basalt]

and there isnt 1 truth table

[royal holly]

y is ur false a upside down t

[silk basalt]

the upside down T is false

[silk basalt]

there are few rules and you combine them

pure logic

[weary tiger]

can anyone explain this in more detail for me? i dont understand the whole thing

[elder berry]

No, there are also n possibilities for games, 0 included

[weary tiger]

a player has to face someone else right
@below I see. Got to think on it. Sorry for the mistake.

[elder berry]

(any time moment is the key word, meaning at some moment one player might not have played any game)

the idea is the following,
There are n players, and at each stage, one singular player can play any of the following number of games: {0, 1, 2, ..., n-1}.
One player plays n-1 number of games if they play against everyone else.
If no two players have finished the same number of games, then each player (ball) has to go play a distinct number of games (box).

One example would be:
{Player 1 finished 0 games} - {Player 2 finished 1 game} - ... - {Player n finished n-1 games}
This example however is not possible and never will be.
The reason for it is if Player n has finished n-1 games, he has played with every other participant, so it is impossible for Player 1 to have finished 0 games.
So either Player n in reality finished n-2 games (which puts him in the same box as Player n-1), or Player 1 finished 1 game (which puts him in the same box as Player 2).
Regardless how you look at it, you'll always have two people in the same box

[weary tiger]

that's so nicee

thanksss

just to clarify, since there can't be a player who played 0 games and also a player who played n-1 games, therefore the number of possiblities is n - 1, combine that with the fact that there are n players, so there must be 2 players who have played the same number of games

is that correct?

also, the number of possibilities could even be smaller than n-1, so there might be the case where 3 or 4 people played the same number of games (and it isn't necessary that all 3 or 4 of them played the exact same number of games) right?

[elder berry]

yes and yes to both questions

[weary tiger]

thankkss

[verbal pebble]

L = {w in Σ∗ | the max amount of a's following a b is equal to the maximum amount of b's following an a}

where Σ = {a, b}

if we wanna do pumping lemma we take w = a(b)^p (a)^p, is this a right choice?

because if we take x = empty, y = ab^x and z = b^(p-x) a^p, then for i =1, this word is still in the language right?

or am i total wrong

[unreal stump]

Yeah the language satisfies pumping lemma

[verbal pebble]

wdym

[unreal stump]

I have a feeling you can prove you can split any arbitrary string in L like that

So pumping lemma holds for L

[timber barn]

Having a problem with understanding the fibonacci tree

How do I draw the first 5 fibonacci root trees

[marble kindle]

i have no idea on how to find rules for these kind of sequences,can anyone help me?

[royal holly]

i am having trouble with this

How do we prove this without using laws

we suppose x is in the set(B-A)

so we must show x is in the set B/\A^c

so X is in the set B and X is not in the set A
then what cases can we conclude from this

[unreal stump]

You can just model a polynomial for it

[weary tiger]

well a venn diagram can help visualize, maybe you can conclude something from there further

[tight hound]

Assuming that the pattern continues as 6,6,7,7,... , the following rule generates it:
a_(2n-1)=a_2n=n ∀ n ∈ ℕ

[tight hound]

Do you mean a polynomial p(x) such that a_n = p(n) for all n? Wouldn't that mean that the derivative of the polynomial is zero at infinitely many points, which is impossible?

Or does 'model a polynomial for it' mean something else.

(I'm new to this terminology, so apologies)

[unreal stump]

Well you know p(1),p(2)...p(9)

You can find a polynomial with degree <=10 such that p(i) = a_i

And you can claim this generates the rest of the sequence

[tight hound]

Fair, but I guess the question was intended in the spirit that the sequence continues as 6,6,7,7,... and so on

[unreal stump]

Well how do you know it's not 6,7,7...

[tight hound]

That is why I said I guess the question was intended that way

Obviously this is not a well-posed question

But pointing that out probably doesn't serve the purpose of the person who posted it lol

[tight hound]

At least at this point in time, but it would certainly do them good to realise that this is the case.

[unreal stump]

Ok I would just like do $a_i = 3 * \floor{\frac{i}{5}} + \floor{\frac{i\mod 5}{2}}$

[vital dew]

DraK

[unreal stump]

If I were to do what the person framing the question intended

[royal holly]

anyone know why 11 is not onto

cant u do the same step as b

[stray reef]

(resolved in help channels)

[sharp herald]

Need hint in (ii). I am a begineer in Graph theory. Intuitively it seems to be connected always but I don't how does one argue it. May be through contradiction approach?

[elder berry]

Assuming G is connected and proving it with contradiction does seem like the way to go. Assume that there are two connected components H1 and H2, then ||pick any vertex in H1, it must be connected to 11 other vertices so |H1|>=12, you argue the same thing for H2 and get that G must have at least 24 vertices||, contradiction

[sharp herald]

Thanks

[floral forge]

does anyone get the difference between 1 and 2

like why does "only if" make a difference

im confused because in the first one technically r can be true even if (p or q)is false

but in the second u can only get the sandwich if u meet the two conditions

so does it mean that theres other ways to get a free sandwich (in #1)

[coral parcel]

"Only if" is a piece of mathematical jargon that needs to be learned as a unit: it's used to express an implication that goes the opposite way from "if".

It won't make you much more enlightened to ask why -- that's just how that combination of words happen to be used in mathspeak.

[prime dagger]

Hello, I am having a little difficulty incorporating these conditions in

The answer that I arrive to is the following: $(10 \times 9){13 \choose 3}(5 \times 4 \times 3){9 \choose 3}30^9$

[vital dew]

FamilyFriendly

[haughty garden]

You'll have to break this up into multiple cases.
Case 1: t does not appear as either the first or last symbol. You need to fix four out of 13 positions to place the t. You also need to choose three elements out of V to appear in the string but they can appear anywhere else in the string.

Case 2: t appears as the first symbol. You need to fix three out of 13 positions to place the remaining t's.

Case 3: t appears as the last symbol. You need to fix three out of 13 positions to place the remaining t's.

[prime dagger]

t's cannot appear in the first or last place tho?

so is it like some inclusion-exclusion argument?

[haughty garden]

They can, they just can’t appear in both the first and last position simultaneously

Ah wait

They say the first and last positions are filled by digits

In that case, this simplifies it a bit

We can figure out the three constraints individually: the first is to figure out where you place the t's. Choose four positions to place the t's. Once you fix the t's, choose three of the characters in V and then pick places to fix these. Then you need to arrange the remaining spaces

[silk basalt]

How to find how many isomorphic graphs are for k5?

Is there a formula or I have to do it manual

[coral parcel]

It looks like you get one of those by choosing 5 of the 8 vertices to be in your K5.

[silk basalt]

I have the answer but I cant understand it now

[coral parcel]

Each 5-element subset of the vertices of your K8 gives you an induced K5.

Do you know how to count subsets of a given size?

[silk basalt]

not really

anyway this is the answer

total 56

[coral parcel]

Yeah. You may need to go back in your book or course material and reread what it says about binomial coefficients.

[silk basalt]

Ok I got it

[quiet tendon]

hey I was wondering, is it necessary to do it like this, I was thinking can't u just do so for the first number there are 4 options and then the leftover 6 numbers u can just choose whatever and then divide by the double numbers so u get
4 * 6! / (2! 2!)

https://cdn.discordapp.com/attachments/326138783181438976/1100099884616532090/image.png

but now I see his solution where u had to take different cases I thought my way is wrong but it is getting the same answer so idk if it's bad

[quiet tendon]

hey u seem realy knowledgeable do u know my question?

nvm I understand it

I think it's just coincidence my way right?

[pale herald]

I will be taking discrete math again

[feral lance]

how do you guys solve something like this

if anyone knwos the puppies thing mk

[vestal bronze]

ok i get it there's 2 colors

there's n magenta puppies and 5 transparent puppies

count ways to choose 2 of them

[snow cedar]

why are they constructing it starting from n + 2? i thought these are easier to think about when you write it in terms of f(n) = ...

[elder berry]

that's just the authors preference, you can freely say
[ t_n = 3t_{n-1} - t_{n-2}, \quad n \geqslant 3. ]

[vital dew]

peaceGiant

[snow cedar]

yeah i wrote it that way

thanks

also does anyone have tips for where to look for these type of problem?

like its saying the difference is divisible by 7, so its congruent to 0 modulo 7

pigeon hole princip[le?

[broken sonnet]

yeah thats definitely PHP

[jolly ledge]

is [\bigwedge_{n=1}^{9}\bigvee_{j=1}^{9}p(i,j,n)\wedge\bigwedge_{n=1}^{9}\bigvee_{i=1}^{9}p(i,j,n)\equiv \bigwedge_{i=1}^{9}\bigwedge_{n=1}^{9}\bigvee_{j=1}^{9}p(i,j,n)] ? Or is this question perhaps too vague and more context is needed?

[vital dew]

Kiameimon | Welt Rene

[jolly ledge]

Was asking cuz I was reading up on using satisfiability to solve sudoku problems (btw for context, $p(i, j, n)$ is the proposition which is true iff the $i$-th row and the $j$-th column contains the $n$-th number). Naturally, one of the conditions the solution must satisfy is that every row and column must have numbers 1-9. To assert that every row has all $n$ numbers, we form the conjunction of the disjunction- $$\bigwedge_{n=1}^{9} \bigvee_{j=1}^{9}p(i,j,n)$$. I was thinking that I could apply the same logic for every $j$-th column, so it'll be $$\bigwedge_{n=1}^{9} \bigvee_{i=1}^{9}p(i,j,n)$$ would also assert that, following which I would combine both propositions with a conjunction. I was thinking, "naturally the answer would be $$\bigwedge_{n=1}^{9} \bigvee_{i=1}^{9} \bigvee_{j=1}^{9} p(i,j,n)$$ right? (quite similar to the normal distributive laws). But the book I was reading did something different; to apply it to every column, they simply took the conjunction of $$\bigwedge_{n=1}^{9}\bigvee_{j=1}^{9}p(i,j,n)$$ over all 9 rows, which results in $$ \bigwedge_{i=1}^{9} \bigwedge_{n=1}^{9}\bigvee_{j=1}^{9}p(i,j,n)$$. Where did I go wrong?

[vital dew]

Kiameimon | Welt Rene

[elder berry]

On the left side of the first image you provided, you can't really and these two expressions

[jolly ledge]

oof

[elder berry]

the first part of the expression is free in terms of the variable i, while the second part is free from the variable j

[jolly ledge]

yeah.... true...

I just noticed it as I expanded the expression out

[elder berry]

what the author meant through the book, is that those separate parts hold for each i in {1, 2, ..., 9}, and similarly for each j in {1, 2, ..., 9}

so because, for example, the expression in this image v, must hold for all i in {1, 2, ..., 9}, you need to and all of them for i in {1, 2, ..., 9}

I'm trying to not use latex cuz lazy, so I hope I got the point across

[jolly ledge]

gotcha, ty

[jolly ledge]

Still however, is this expression wrong? I get that we can't "combine"/simplify this expression, but I feel that it's still logically equivalent to asserting that for all columns and for all rows, there must be numbers from 1 to n.... or is it?

[elder berry]

Yes, the expression is wrong. The right-hand-side (RHS) as discussed states that for each number and each row, there is a column where said number appears, which satisfies the conditions for Sudoku.

The LHS for non specified i and j (which is a bad thing to do in general), means that the following is true:
-there is some row i for which the sudoku constraint holds;
and
-there is some row j for which the sudoku constraint holds.
Which is not enough to show that every row and every column of the sudoku table satisfies the constraint

(edited my answer, the RHS expression only talks about satisfying the rows)

[jolly ledge]

ah, ic... Gotcha, ty

[grand totem]

Find two injections, one from (2,6) to [0,2] and one from [0,2] to (2,6)

[chrome osprey]

@grand totem sorry how do you do that?

f(a) = f(b) + 3?

[grand totem]

sending an a in A to a + 3 is certainly a nice injection from A to B. Now figure out an injection going the other way and conclude with Schröder-Bernstein.

[quiet tendon]

can someone help me how to proof it

[inner otter]

use the formula for P(A u B)

[sonic swan]

how are they saying this??

im looking here

on the top shouldnt it be x^{p - n} instead of just x^n?

[jolly ledge]

Huh

What top

[sonic swan]

the first pic

well i guess order matters here

i substituted it as (x + 1)^p

[jolly ledge]

They're equivalent

U can try expanding

[sonic swan]

yeah i got it thanks

i was trying to expand out theese steps but im not sure how they're getting these lines here

is it just algebraic manipulation because im not able to think of this as quick

[jolly ledge]

what P(p,k) is it referring to?

[sonic swan]

permutation i guess

[weary tiger]

you are using the induction hypothesis there in the second line. Remember you have assumed the validity for k = m.

[sharp crag]

can someone help me with question 2?
thanks

[snow cedar]

is there an intuitive way to undertand this

[jolly ledge]

When does the dual of a compound proposition equate to the original proposition?
Question in Rosen's discrete maths. I'm baffled- I don't think such a thing exists

[indigo rapids]

how would i solve this question?

[peak vine]

I'm dealing with automata. A finite state machine is defined in our class as the pair A = (Σ, Q, q0, F, δ). I'd like to express the cardinality of Q from that automata, which is a set, how do i do that?

[unreal stump]

Like notation for that?

[peak vine]

Q ∈ A, |Q| = 4

[peak vine]

yes

[peak vine]

would that be sufficient to state "cardinality of Q is 4" assuming Q has 4 elements?

since Q is a "well known" property of A

[unreal stump]

afaik there is no special notation for that

[peak vine]

do i just write "Q in A has 4 elements, therefore the automata has 4 states?"

[cobalt ledge]

Hello

Could you please help me with this?

[digital raven]

Is there name for a binary tree where every node has exactly two vertices up to N branches? So the tree's vertex count grows 2^N. What if every left branch has the value T, and every right branch the value F? Would this be called a strict binary tree?

[amber wolf]

Raaaaaaahhhhh I hate formal prooooooofs

[limpid gulch]

halp

plaeze

i stuc on meth

wat is 5 + 5?

is it 268?

i think itss

fish

HEHEHEHE

[brave vine]

???

[indigo rapids]

sorry for pinging you but if you get the answer, could you let me know too please

[rose widget]

How do u do this

[sly kernel]

When I have 71 different characters ( lowercase letters, uppercase letters, 9 symbols, and digits (0-9)) would (62^5) * 9 * 8 * 7 suffice as an answer? Or am i missing something?

[plain valve]

hey guys im stuck on this problem "Let A be a set. Prove that A − ∅ = A"

[sharp locust]

kruskal's algorithm

or prim's

[chilly hemlock]

for any a != 0, is gcd(a,0) =a ?

[pure veldt]

it's 10

[jolly ledge]

ignore these trollers

[quaint notch]

Might be a bit basic but sometimes I struggle with the basics more than the complicated stuff -

$Let n,m \in \mathbb N$:
prove -
if $n\in m \to n+1 \in m $ or $n+1=m$
$n\in m$ or $m \in n$ or $n=m$
Prove that for each non-empty subset A of $\mathbb N$ there exists $b \in A$ such that for each $a \in A$ the following apply - $b \in a$ or $b=a$

I know I got to use induction. Hopefully I proved correctly that $0 \in m$ or $0=m$ so I wanted to somehow apply it on the first section here but I got a bit lost.
I mean, the first two are pretty obvious but not 100% sure how to prove, and the 3rd I think b is the minimum of the new set?

[vital dew]

meitar5674

[obtuse lance]

you can use stars and bars if you're clever with how you pick your stars and bars.

[zinc kettle]

hello guys. suppose you have a graph with vertices. these vertices can be represented by anything like apples or like ducks or something right

in this case graph G looks like this?

why is everybody gone

[brave rock]

Yes

[zinc kettle]

im getting confused so much when mathematicians just randomly decide to connect things that aren't of the same class

[plain valve]

Let A and B be sets. Prove that A ∩ B ⊆ A

[jolly ledge]

well, since A is a subset of itself and all elements of A intersect B will be an element of A, then it'll also be a subset of A

[stray reef]

do you still need help with this?

[plain valve]

im now stuck on this Let A and B be sets. Prove that A ∩ (B − A) = ∅.

[stray reef]

ok

do you know in general how to show two sets are equal?

[plain valve]

tbh not really

[stray reef]

to prove S = T you prove that S ⊆ T and that T ⊆ S.

i.e. to prove two sets are equal you prove they are subsets of each other

this must have been mentioned in class at least once, and maybe even more than once

[plain valve]

is there a definition for a subset in symbols?

[stray reef]

of course there is

[plain valve]

A and x∈A?

[stray reef]

S ⊆ T means (∀x)(x ∈ S => x ∈ T)

this should also have been mentioned in your class

if you were able to prove A ∩ B ⊆ A earlier, then you should know what the definition of a subset is.

[plain valve]

i dont think i have seen the =>

[stray reef]

-> maybe?

[plain valve]

nope

[stray reef]

we say that S is a subset of T if every member of S also belongs to T, or to put it another way, for every x, if x belongs to S, then x [also] belongs to T.

[plain valve]

okay i get that

I probably did my previous proof wrong tbh lol

[stray reef]

out of curiosity... how did you show A ∩ B ⊆ A

if you didn't know or didn't remember the defn of subset until now

might be worth looking at

[plain valve]

i appreciate the help because this stuff is a little too "abstract" for me

[stray reef]

If A ∩ B ⊆ A, then ...

yeah, everything that follows after this is basically bullshit.

you cannot assume your goal.

also "the a subset of A"... questionable grammar

[plain valve]

typo

[stray reef]

still like

do you understand why starting your proof with "If <goal>, then ..." is bad

[plain valve]

so how should i start it

[stray reef]

that doesn't answer my question

[plain valve]

When i previously learned proofs thats how we started them thats why..

[stray reef]

???

who the fuck taught you to do that

whoever that was they should be fired for incompetence imo

[plain valve]

wait thats just a statement

its the start of a statement

im basically just saying the statement

[stray reef]

the point is
if you start your proof of X by saying "If X, then <whatever>"

you're skipping ALL the steps from your assumptions to your goal.

[jolly ledge]

Wait how's that different from assuming your conjuncture is true and then proving/disproving it via contradiction, contrapositive etc?

[stray reef]

what's a conjuncture?

[jolly ledge]

conjecture

mb

[plain valve]

okay i shall start with "let x ....

[stray reef]

i think there is a better way to start

it's a bit more wordy but it is something that should like... make sense

We wish to show that $A \cap B \subseteq A$. To do this, in accordance with the definition of the subset relation, we show that \underline{if} $x \in A \cap B$, \underline{then} $x \in A$.

By the definition of set intersection, $x \in A \cap B$ means ($x \in A$ and $x \in B$). From this, it follows that $x \in A$, QED.

[vital dew]

Ann

[stray reef]

(could probably do some even more formal logic shit here with like... disjunction elimination or something, i.e. that from a bunch of statements linked by "ands" you can pluck one out and assert it)

[jolly ledge]

yeah, just show the definition of subset and the definition of intersection ans show how it all connects

[plain valve]

okay

seems like the write solution. Im looking at my books solutioin

[stray reef]

write ≠ right?

if you're looking at your book's solution, share it with us too.

[plain valve]

you match the "i, ii, iii" to the bottom of the picture

[stray reef]

okay so like

hm

putting "We must show that ___" or "We wish to show that ___" at the beginning of your proof is kosher.

it's the "Suppose <goal>" or "If <goal>" that is very much not, and which made me curse.

might've been a misunderstanding on your part? i don't know.

[plain valve]

idk what the point of the "if an and statemetn is true.." is

[stray reef]

spelling out the logic behind the proof.

[plain valve]

the in particular x is in A

[stray reef]

this is what i did

i took the statement "x ∈ A and x ∈ B", which is two statements joined by an and, and plucked one out

[plain valve]

but what lets you do that

cuz both is true

(x ∈ A ^ T ) = x ∈ A

[stray reef]

both are true, meaning that you can focus on just one of them if you so desire.

[plain valve]

that thing

so how would i start this one A ∩ (B − A) = ∅

I have to prove that they are subset of one another

an empty set is a subset of everyset???

[stray reef]

the empty set is a subset of anything, yes.

[plain valve]

thats what im trying to prove

[stray reef]

no

you wish to show A ∩ (B − A) = ∅, and for this you need to show two things:
(1) A ∩ (B - A) ⊆ ∅
(2) ∅ ⊆ A ∩ (B - A)

because you have (presumably) already proved that the empty set is a subset of any set, you get (2) for free.

[plain valve]

by definition right?

thats what you woudl say

[stray reef]

??

i don't think i would say that.

[plain valve]

i did proof by contradition

[weary tiger]

why is "r balls" the contradiction of "r+1 balls"?

[haughty garden]

The key is that you’re distributing n balls into m identical boxes. Supposing that none of the boxes contain r + 1 balls, the maximum amount of balls you can hold in each box is r so you’re distributing at most rm balls. But, by the assumption of the statement, n > rm so you’re (a) distributing n balls and (b) distributing at most rm balls, which is a contradiction

[weary tiger]

Supposing that none of the boxes contain r + 1 balls
i needed this part, thanks

[glad shuttle]

Does anyone have any tips for better understanding how to apply logic laws to simplify propositions in propositional logic?

I kinda struggle with it

[chilly hemlock]

hint?

[quaint notch]

Hey all, another one 🙂
I'm trying to figure out whether or not there's a set A such that there's a set X:= {All the sets that are not in A}
Any ideas?

using ZFC

[elder berry]

$2^{3n} = 8^n = (3+5)^n$

[vital dew]

peaceGiant

[elder berry]

does that help?

[chilly hemlock]

Yea thanks

[torpid seal]

um

[lyric quartz]

Prove that forall x in S x T -> x in E x E, that's the subset definition

[vivid gust]

these were wrong

and ik hamilitonian circuits is when you can visit each vertec once and return back

[graceful owl]

god graph theory looks so interesting and i havent touched it

[dapper stone]

Can anyone hel me with this?

[sharp locust]

ye its very interesting

[unreal stump]

Look up Extended Euclidean

[unreal stump]

I am pretty sure you induct on the number of vertices here. I am not sure how to proceed with that induction

[pale epoch]

a few observations:

• the image is a tree as well
• inductions seems the way to go: do you want to induct on the size of the codomain or the image?
• probably start by picking a leaf and "removing" it

[unreal stump]

I guess on the size of the codomain?

[pale epoch]

oh lol, i actually meant domain

but i think its easier to work with the image

domain = codomain here though so wtv

if everything gets mapped to a single point you are done, if not pick a leaf in the image and assume the preimage is neither that same vertex nor its contracted from that edge, then ...

[vivid gust]

its so fun but annoying bc you can easily get confused

[spice warren]

Can someone explain while this is not true? Intuitively, it seems like it is asking if a set is less than itself + another non empty set which seems to be always true.

(e is set of evens and o is set of odds)

additionally, it is equivalent to |E| < |Z| which i can confidently say is true, because f: E -> Z is a injective function. Am I going wrong anywhere here?

[vestal bronze]

you can make a bijective E → Z

[spice warren]

oh you can true.

[vestal bronze]

so it's all equal

it's not a fun concept lol

[spice warren]

wait how is E -> Z bijective?

because all the odd values have no pairing?

[vestal bronze]

you make it so they all have a pairing

[spice warren]

oh

[vestal bronze]

every integer to every even and vice versa

[spice warren]

tysm

this topic is hard

[spice warren]

| P u E | = | Z |
can you explain why this is true? how do you claim f : P u E -> Z is bijective?

[vestal bronze]

is P primes?

[spice warren]

yes

[vestal bronze]

i don't know what's the mapping, sorry

[spice warren]

allg

[coral parcel]

You don't make the claim without defining what f is.
Simply writing "f: P union E -> Z" tells us something about the function f, but there still are many different functions that match the description. Some of them are bijective, others are not.

The claim is really that some of all those functions are bijective. And to prove it we just need to show one such example.

For example, we could define $$f(n) = \begin{cases}
n/2 & \text{if $n$ is a negative even number} \
n & \text{if $n$ is a positive even number or zero} \
2k-1 & \text{if $n$ is the $k$th odd prime} \end{cases}$$

[vital dew]

Troposphere

[spice warren]

ah i see, I didn't realize you could create functions like this, i thought it had to be like a conventional function

a ca said some things about a set being countably infinite and proving bipartite was unneccesary -> is "countably infinite" enough justification to claim two sets cardinality is equal?

[coral parcel]

Typically you'd only be asked to reason about cardinalities after a painstaking sequence of "a function is any set of ordered pairs such that ..." which makes it explicit that whatever way to describe your set of pairs is fair game for creating a function.

[coral parcel]

All countably infinite sets are in bijection with N and therefore with each other. So they have the same cardinality.

[spice warren]

this makes a lot of sense, thank you!

[little stag]

help

is it 1/2

[ivory badge]

divide by 2

[coral parcel]

Yes, if those are mixed fractions. No, if they are multiplications. But such questions belong in #prealg-and-algebra or a help channel.

[thorn bay]

my textbook defines a multigraph (allowing loops) as a vertex set 𝑉, an edge set 𝐸, and a correspondence: 𝜓: 𝐸 → (𝑉,2) ∪ 𝑉, where (𝑉,2) are the pairs of the vertices in 𝑉. Is this the usual definition? (𝑉,2) ∪ 𝑉 is a set of mixed objects and that throws me off a little bit. I'm thinking of an alternative definition, where normal edges are defined by 𝐸 and 𝜓: 𝐸 → (𝑉,2), and loops are defined by 𝜆: 𝑉 → ℕ

[grand totem]

If I had to guess, then the text might first define an (undirected) multigraph to specifically not allow loops. Then with (V,2) = { {u,v} | u,v ∈ V and u ≠ v } such a multigraph becomes a tuple (V,E,ψ) with ψ : E -> (V,2).
An undirected multigraph that allows loops might then be define as a tuple (V,E,ψ) with ψ : E -> { {u,v} | u,v ∈ V }. But I guess they opt to reuse the notion of (V,2) from the previous definition and use the fact that { {u,v} | u,v ∈ V } ≅ (V,2) ∪ V

[coral parcel]

"(V,2) cup V" is evidently considered to be a disjoint union here. It would perhaps be better to write it as (V,2) cup (V,1), or alternatively as {A subseteq V: 1 <= |A| <= 2}.

Handling loops and other edges differently in the way you propose feels like it would be awkward, but we could do it
either by having E with a function E -> (V,2) cup (V,1)
or by not having any explicit E but just a function (V,2) cup(V,1) -> N

[thorn bay]

ahh, { {u,v} | u,v ∈ V } ≅ (V,2) ∪ V is neat, thanks for the perspective

[weary tiger]

can someone explain why the bionominal theorem works? not its proof but an intuitive explanation.

[stray reef]

when we expand (a+b)^n with the distributive law, we get a lot of terms each of which is the product of some a's and some b's

since we are multiplying together n copies of (a+b), each term will contain n letters in total, and thus be one of:
a^n
a^(n-1) b
a^(n-2) b^2
and so on down to b^n

the coefficient nCk counts how many of each type of term there is, and appears once we collect like terms

@weary tiger

[weary tiger]

thanks but can you elaborate more on the coefficient part, why is it nCk?

[ember obsidian]

if you want more specific details, either read the proof or work out some examples for small n

eg expand (a+b)^n for n=2,3,4 and see that they agree with the binomial theorem

[obtuse lance]

I like to think of it as making the distinct strings that it's counting with a and b. But then those simplify down since multiplication commutes and we have exponents

For instance, abb+bab+bba are the strings of length 3 with two b and one a. If you do the initial multiplication as if the variables don't commute, that's a term you'd get from (a+b)^3

[weary tiger]

sorry but i think my question was a bit off, what i didnt understand is how the formula for the binomial coefficient represent an entry in the pascal triangle

[river garden]

Say that a language A is star-closed if A = A∗ . Give a polynomial time
algorithm to test whether a DFA recognizes a star-closed language?

[woeful pulsar]

what would be R/{0}? would it just be R without the element 0? R here is just the set of real numbers without any topology on it or any vector space structure

[tight hound]

ℝ∖{0} is just ℝ without the element 0. I am assuming here that you meant the set difference ∖ and not /.

[celest gazelle]

maybe you can try just converting DFA to regex R, and proving when L(R) = L(R)^*

[river garden]

How to compare equivalence of two regex

[celest gazelle]

although you might need to clarify what it means polynomial wrt what

[river garden]

Input size

[celest gazelle]

like encoding of dfa?

[river garden]

Yes

[celest gazelle]

i think sipser gives polytime algorithm for equivalence of regex

or at least definitely decidability algo

[river garden]

I dont think regex equivalence is poly time possible

If I convert regex to nfa then to dfa and compare dfa equivalence that is exponential

[celest gazelle]

wait it might be just checking that every accept state loops back to the starting state

lmao

lemme give it some more thought and get back

[river garden]

Ohh yeah that seems crct

Ty

[celest gazelle]

wait actually?

[river garden]

No

Start goes to same state as every acc state on every Input symbol

[celest gazelle]

i think you can do this

take your initial DFA D

[river garden]

Delta(astart,symbol) = delta(acc,symbol)

[celest gazelle]

create GNFA D' by adding the epsilon transition thing

and convert D and D' both to regexes

[royal gull]

how do i approach this number theory problem

i have been circling around mods

[woeful pulsar]

ohh set difference got it

[obtuse lance]

I would try factoring 3367 and factor f(a,b), then focus on showing f(a,b) is divisible by each of those factors individually if possible

since it's 6 times, you can write it as ab*10101010101 then start factoring that to

essentialy the trick to factoring these geometric sums is that: $$\frac{x^{ab}-1}{x-1} = \frac{x^{ab}-1}{x^a-1}\frac{x^a-1}{x-1}$$

[vital dew]

Merosity

[obtuse lance]

right now you have $$\frac{100^6-1}{100-1}$$ so you can start to factor in multiple ways based on the exponent. (or you might not need to do this if you can employ flt directly or something like that too)

[vital dew]

Merosity

[royal gull]

Thank you I will look into it, and by flt you mean Fermat's little theorem?

I was at classes so i couldnt see your reply until now

[obtuse lance]

yep

[royal gull]

been circling around on this

[hollow ferry]

i don’t know if this will be helpful but the only function I can think of that satisfies the equation is f(n)=n+1/2

and that obviously doesn’t map natural numbers to natural numbers

[obtuse lance]

the hint is pretty nice imo, I suggest writing down what the image set of f(f(n)) and f(n) is. In particular, think about the inner and outer f of f(f(n)) if that makes sense

I will just say 0 is in N for this since it literally doesn't matter.

||fof: N -> N\{0}
we can split it into two parts now:
f: N -> A
f: A -> N\{0}
hopefully it's obvious now||

[zinc rivet]

hello people

i need some help

what 5 - -3 x -18 / -99

help plz

[stray reef]

@zinc rivet #prealg-and-algebra

[royal gull]

@obtuse lance what does fof: N -> N/{0} mean

Is it [1, infinity)?

N maps 1 to infinity*

[obtuse lance]

Sort of. N{0} is the natural numbers with 0 removed

The set you put includes non integers like 1/2

[weary tiger]

I have $2^n \equiv 1$ (mod 3), $n \in N$

N is closed under multiplication, hence n can be written as a product of two natural numbers.

Let $n = ab; a,b \in N$

$\implies 2^{ab} \equiv 1$ (mod 3)\
$\implies (2^a)^b \equiv 1$ (mod 3)

We know $2^a$ has no factor of 3. Hence $gcd(2^a,3) = 1$.
Hence $b = \phi(3) = 2$ (from Euler's Theorem), where $\phi(x)$ is the Euler Totient Function.

Therefore, $n = a\phi(3) = 2a$ is the solution.

Is this right?

[obtuse lance]

N usually means natural numbers, I'm not sure why you are talking about it being closed under multiplication here

n will have to be even though

[weary tiger]

I meant that if we take two natural numbers, their multiplication also yields a natural number

[weary tiger]

Yes

Oops a typo

I have $2^n \equiv 1$ (mod 3), $n \in N$

N is closed under multiplication, hence n can be written as a product of two natural numbers.

Let $n = ab; a,b \in N$

$\implies 2^{ab} \equiv 1$ (mod 3)\
$\implies (2^a)^b \equiv 1$ (mod 3)

We know $2^a$ has no factor of 3. Hence $gcd(2^a,3) = 1$.
Hence $b = \phi(3) = 2$ (from Euler's Theorem), where $\phi(x)$ is the Euler Totient Function.

Therefore, $n = a\phi(3) = 2a$ is the solution.

Is this right?

[vital dew]

Miles Edgeworth

[obtuse lance]

I'm on mobile, so hard to respond, but I'd change some things

[weary tiger]

Oh alright

[halcyon lynx]

Which of these are true?

1. ∅ ⊂ ∅
2. ∅ ⊂ { ∅ }
3. ∅ ∈ { ∅ }

[agile magnet]

What do you think

Seeing when you’re right and wrong will be more valuable rather than just giving answers

[halcyon lynx]

my guess is that 2 and 3 are true

[agile magnet]

Why

[halcyon lynx]

but its kinda tricky

[agile magnet]

Why is 2 true, you’re right but I want an explanation

Same with 3

[halcyon lynx]

i don't how to call ∅ on english so I'm calling it with symbol
the ∅ can be a subset of any set, so it is contained also on itself, ∅
same with belonging to another set
1 is false cause it don't have the {}

i think that is

(sry for my english)

[agile magnet]

You’re fine

Don’t be sorry

So it’s called the empty set

Ok why is the empty set a subset of any set

Use the definition of subset

[halcyon lynx]

it is a fraction of a set, so the emptiness is also a fraction of it

[agile magnet]

Can you write out the definition of subset?

[vital dew]

Spamakin🎷

[halcyon lynx]

all of the elements of A are included on B

[agile magnet]

Yea

Ok so let’s try with 2

Is every element of ∅ included in {∅}?

[halcyon lynx]

yes

[agile magnet]

Cool so 2 is true

What about 1?

Is every element of ∅ included in ∅?

[halcyon lynx]

when it don't have the {}, is it a set?

[agile magnet]

Yes

Empty set is still a set

It’s just the set with no elements

[halcyon lynx]

so it won't have any elements

[agile magnet]

Yup

[halcyon lynx]

even the empty set

[agile magnet]

So is this true?

[halcyon lynx]

no

[agile magnet]

Why?

What element of ∅ isn’t included in ∅?

[halcyon lynx]

{∅} ?

[agile magnet]

That’s not an element of ∅

Empty set has no elements

So you can’t find an element of ∅ not included in ∅

So ∅ is in fact a subset of ∅

[halcyon lynx]

ok

but why is it false?

[agile magnet]

It’s not

1 and 2 and 3 are all true

[halcyon lynx]

oh

ok then, tought it was false

[agile magnet]

Does it make sense why all 3 are true?

[halcyon lynx]

yes, now i get it

[agile magnet]

Nice!

[halcyon lynx]

been having trauma with that theme

thanks man!

[grave nexus]

Isn't the symbol ⊆ more appropriate here ,i.e ∅ ⊆ ∅ which means ∅ is a subset of ∅ and it may be improper subset, rather than ∅ ⊂ ∅ which means ∅ is a subset of ∅ (and it's not a improper subset) ?

[tough gull]

1. A massa de substancia radioactiva em certa amostra é dada pela
   fórmula:
   ( )

Com em anos e ( ) em miligramas.
1.1. Quantos miligramas havia no inicio da contagem do tempo?
1.2. Quantos miligramas restavam decorridos 10 anos, desde o início da
contagem do tempo? Apresenta o resultado com uma casa decimal.

[halcyon lynx]

amigo, ta faltando umas coisas ae

[vital dew]

Spamakin🎷

Spamakin🎷

[agile magnet]

Which is awful

Tbh should have clarified

[grave nexus]

Indeed, that is awful.

[chilly hemlock]

Does anyone know what that symbol "*" means? p **y

[inner otter]

looks almost like poor typesetting for "p does not divide y", I think

[chilly hemlock]

@inner otter Thanks

[mental pecan]

Hey guys, I was wondering why this is false

If we let A = divisible by 6, and B = divisible by 8, we certainly get P(A \cup B) = P(A) + P(B) - P(A \cap B)

And every 6th number is divisible by 6 so it seems like it should be floor(1000/6) for the number of numbers divisible by 6

Oh... it has to do with being divisible by both 6 and 8 means you are actually divisible by lcm(6, 8) not necessarily 6*8

[wraith kelp]

So I am practicing some induction proofs for a final tomorrow and I'm having a bit trouble on understanding why this proof works:
Specifically the last section. (The solution was written up by the professor)

[clever sage]

With induction you want to show that if a statement for n is true, it is true for n+1. He sorta skipped a step in adding 2, but the idea is you have some expression for the (n+1) case and you try to reduce that to the n (base) case.

they are just using the fact that for n>=3 that 2^n>2 as well. They seem to doing the reverse in this question, building up the n+1 case from the base case, which is also possible, as long as you have a string of true statements that follow from each other, you will have something that is valid

[inner otter]

you could see this and linked posts for more on induction: https://math.stackexchange.com/a/1255268/993372

[livid root]

Does anyone know where I could find some first year discrete math exercises?

[tight hound]

What are you looking for, exactly? Combinatorics, set theory, number theory, logic?

[indigo rapids]

how do i go about solving this recurrence relation?

[unreal stump]

Well consider b_n = a_{n+1}-a_{0}

You get a homogeneous recurrence for b_n from that

@indigo rapids

[vivid stump]

based pfp btw

anyone able to hop in a call and help me on this discrete math assignment?

dealing with asymptotics

[vivid stump]

[celest gazelle]

MIT's 6.042 is pretty decent and comprehensive

at least i self-studied that and never formally took a discrete course

[indigo rapids]

can someone explain to me where im wrong

[unreal stump]

Just to be clear, does this mean f(1)=2 , f(2)=5,etc

[indigo rapids]

yh

this also 😭 the first section is right but the others arent

[unreal stump]

Isn't f (1,2,5,6,3,7)

f^3 should be be (1,6)(2,3)(5,7)

[unreal stump]

f is (7,5,3,2,4)
So f^-1 should be (4,2,3,5,7) if I am not mistaken

[indigo rapids]

ohhhh f^x is the f written in 3 transpositions?

oh no wait

3 rotations?

f but three rotations in?

[unreal stump]

f^3 is f o f o f

[indigo rapids]

ahhh yeahhh i see

thatnk youu

[halcyon lynx]

Ty

[weary tiger]

Apparently we use bellman ford first then run dijkstra k times

I get with dijkstra you have ElogV runtime so you'd have to use it k times to get that E.k.logV runtime

But why did they start off with bellman ford?

[honest holly]

i havent seen graphs in 2 years, but djikstra assumes no negative edge weights

[weary tiger]

Yeah I know

[wicked escarp]

Help

[honest holly]

yeah so that should answer ur question

no?

[weary tiger]

They want you to use dijkstra k times

But they combined it with something else before they run that

[honest holly]

yes the point is that the graph has negative weigts

[weary tiger]

Bro Ik that

[honest holly]

so how do u plan to run djikstra

[weary tiger]

Doesn't mean part of your code can't use it

[weary tiger]

That and bellman ford have been taught. The problem assumes no other algorithms

Also the TA with the solutions said so lol

[honest holly]

i have no idea what u r saying

im sorry lol

[weary tiger]

The teaching assistant for our class with the solution for the problem literally said run bellman first, then dijkstra k times.

[honest holly]

i dont know what your question is

[weary tiger]

the question is there lol

Are you high rn?

[honest holly]

this is your question

I already told you

You need to do something to handle the negative weight

[weary tiger]

That's why they used bellman ford first

[honest holly]

you don't need to attack me

[weary tiger]

Bro i'm not attacking you

[honest holly]

if you are asking for help, 1) be respectful to others 2) ask clear questions

[weary tiger]

Did both

Then you said you don't know my question

It's like right there lol

[plain mesa]

how can i find particular soltn

[inner marsh]

What does this mean?

[little prism]

the cartesian product of R with itself three times

[inner marsh]

oh ok

so like

[little prism]

the set of tuples (x,y,z) with x,y,z being real numbers

[inner marsh]

yea

thank you

[quaint notch]

Hey all I'm trying to prove using the ZFC axioms that given sets A,B there exists another set C such that C := {The bijections from A to B}. I was thinking about using the axiom of choice in order to create a function from A to B but not sure how to really show that it is a bijection.

[cerulean slate]

how are these 3 not isomorphic?

they all have the same amount edges, vertices, and cycles

[honest holly]

That’s not the definition of isomorphic

Isomorphic means that it’s literally the same graph up to superficial differences

In other words your bijection needs to preserve edges

Having the same amount of edges is not the same as having the same edges

[obtuse lance]

one simple way to see, the first one has only one vertex of degree 1 (one edge coming out of it) while the other two have two vertices of degree 1

try to see if you can use the degree of the vertices to distinguish the last two apart from each other

[heavy rain]

I have a general question about graph theory,

walks can repeat edges, and trails cannot, does that mean that walks that happen to not repeat edges are trails?

like is there anything that differentiates walks that happen to not repeat edges and trails? or are they just the same thing

[weary tiger]

yeah it just has to do with edge repetition

it's weird when you learn graph theory in a CS Algorithms class vs one in a maths class cause they define words differently.

[weary tiger]

the degrees (number of edges emanating from a vertex) of corresponding vertices aren't the same

Heck even the shortest paths from one vertex to another isn't necessarily the same

[plush canyon]

not really sure about this question

Pls ping if reply

[glacial flame]

If you are given a password of length, say 12, and want to find the number of valid passwords that have at least one letter, at least one digit, and at least one special character, I am aware that you can solve this using inclusion-exclusion. However, if another constraint were to be added, such as at least one <different category of characters> (just assume that it is specified how many characters in this category exist, say 4), the inclusion-exclusion solution involves a considerable more amount of individual computations of intersections. As the number of distinct "category" requirements increases, it wouldn't be realistic to use this approach. Is there an alternative solution to this using combinations/choosing, such as with stars and bars? I can't really think of how to do it with the normal choosing/"fixing" while properly handling overcounting, and the stars and bars method can only be used to assign each slot a category; it wouldn't factor in the possible types of items in said category.

I guess what I'm trying to ask is how would you solve the problem of counting the number of passwords with at least 1 letter, at least 1 digit, at least 1 special character, at least 1 ..., without using inclusion-exclusion?

[weary tiger]

Draw 10 nodes with values 1,2, .. 10.
Connect two nodes if the condition is met. So either y divides x or x divides y is true
1 gets connected to everything since everything's divisible by 1
2 gets connected to even numbers like 4,6,8,10
3 gets connected to 6,9
4 gets connected to 8
5 gets connected to 10

Since this graph is simple, no multi edges or self loops

[weary tiger]

I apologise to ping you again.
What would the changes be?

[indigo rapids]

i'm not getting it?

[unreal stump]

What did you try

[indigo rapids]

i didn;t cuz idk what you mean by it

so right now, in that question, we have a non-homogenous relation because of the 9n right?

[unreal stump]

Consider

a_n= -4 a_{n-1} +12 a_{n-2} +49 n
a_{n+1} = -4 a_{n} +12 a_{n-1} + 49(n+1)

mb, I meant b_n =a_{n+1}-a_{n}

Now subtract these 2 expressions to get

b_n=-4 b_{n-1} +12 b_{n-2} +49

[indigo rapids]

I'm gettin $$-4a_n -16a_{n-1}+12a_{n-2} +49$$

[vital dew]

MildCurry

[indigo rapids]

When I do your one

[unreal stump]

Don't simplify it

Write $-4 a_{n} + 4_a{n-1} + 12 a_{n-1} - 12 a_{n-2} + 49$ as $-4(a_n-a_{n-1}) +12(a_{n-1}-a_{n-2})+49$

[vital dew]

DraK

[unreal stump]

$=-4 b_{n-1} +12 b_{n-2} +49$

[vital dew]

DraK

[inner marsh]

how do I prove that there are infinite rational numbers in (11^-10, 10^-10)?

[stray reef]

can you prove that any interval contains infinitely many rational numbers?

[cloud dirge]

I apologize for my caligraphy, but does the logic hold?

[sharp rune]

I want to study set theory,on my own,I know little bit of logic ,
Which book is good?

[cloud dirge]

For what purpose? The First chapter of hammack's book of proof covers the basics of set theory needed for proofs

[sharp rune]

For real analysis

[cloud dirge]

Do you know the basics? I have not studied analysis, but i dont think you need in depth knowlegde of set theory for that

[sharp rune]

I know little bit of logic and set operations and I completed calculus 1 computational course(proof not inclued)

[cloud dirge]

You should finish the calc sequence and learn proofs before attempting analysis

It is a difficult subject

[sharp rune]

Yeah I know calc sequence is in my calc 2 syllabus,but it does not include proof it's more of applying.i search for proof writing.i download so many e- book.then i found so many set theorem stuff in book.i don't know sets more than level so that's i looking for set theory begineer book.

[stone wing]

enderton is nice for set theory

[sharp rune]

Is it begineer friendly?

[stone wing]

yeah

[sharp rune]

@stone wing can you reacommend some YouTube class or some course .for work with this book

[stone wing]

the only one i know is this https://youtube.com/playlist?list=PLjJhPCaCziSQyON7NLc8Ac8ibdm6_iDQf but i never followed it

[sharp rune]

Why

[cloud dirge]

I meant the calculus sequence, calc 1,2 and 3

If you havent seen proofs yet It is strongly recommended that you study proofs before starting a higher math course

Im using the book of proof and i have no complaints

[sour scarab]

I feel like I'm missing something here; how is this an identity?

[little prism]

well its two things that are equal (identical)

[sour scarab]

oh I'm dumb

[glacial flame]

Does anyone happen to have any insight on this which I posted a day ago?

[heavy rain]

why is it that V1 is 18

it e = v - 1 and E is 17, shouldnt V1 be 16 not 18?

[haughty garden]

e = v - 1 so v = e + 1 and e = 17

[inner marsh]

does 2^aleph-one = aleph-two?

[chilly hemlock]

hints?

[glacial flame]

I am unsure what theorems you have and haven’t learned, but if it helps, what you are aiming to prove is Wilson's theorem.

[chilly hemlock]

fermats little theory

eulers theory

addition and multiplication with modular

euclides algorithm

[glacial flame]

It seems like one of the proofs involve FLT, though it doesn’t really use it in the way I was taught.

[chilly hemlock]

what i've done so far

maybe this is the wrong approach

what are FLT:s?

[glacial flame]

Where did your p! come from

[chilly hemlock]

ur right, i meant p!, but that means i have to scratch everything

haha

[glacial flame]

Oh by FLT I meant fermat’s little theorem

I’ll be honest, I’m really rusty on this stuff; all I can “see” but not really put into formal words is that p-1 is === -1 (mod p) and (p-2)! === 1 (mod p) yielding -1; I have no clue how to prove the second part.

[chilly hemlock]

interesting

maybe i can use this

[glacial flame]

Oh I guess it involves multiplying both sides of the second equation by the inverse of (p-1)?

[chilly hemlock]

this works

however I have to find a way to show that (p-2)! === 1 (mod p) now

[chilly hemlock]

that is what i can come up with

[tulip vale]

Okay! Let's work from where we left off in the hint i shouldn't have deleted

We know that the order of our multiplicative group is (p-1), which is even (since p is an odd prime)

The elements 1 and -1 are definitely both their own inverses.

[chilly hemlock]

"-1" as an inverse?

[tulip vale]

yes -1 = p-1

[chilly hemlock]

oh yea -1 * -1 = 1

[tulip vale]

and (p - 1)(p-1) = p ^ 2 - 2p + 1 = 1

(mod p)

now, since Z/pZ^* is a group, each element has a unique inverse

this means that each remaining term in the product 23...*p-2 has its own inverse, which has to be an element of the product above

So we can split the rest of the product into a product of products of pairs of inverses

(p-1)! = (1)(p-1)(2 * 2^{-1})...

but the products of all the inverse pairs are 1

[chilly hemlock]

hence (p-1)! = -1

?

[tulip vale]

yep 🙂

[chilly hemlock]

okay i have to analyze this a little bit because I don't know group theory hahah

but thank you 😄

[tulip vale]

that the rest of the terms in the product are all inverse pairs is precisely why (p-2)! = 1

you don't (really) need any group theory here

you just need to check that each element of 1, ..., p-1 has exactly one multiplicative inverse mod p, and figure out why the only elements that are their own inverses are 1 and -1.

[chilly hemlock]

alright i think i got it

thank you for your time

and your clear explanation

i really appreciate it!

have a nice weekend 😄

[sharp rune]

find sum formula for
F(x)=1/(2x+1)(2x+3) x>=0

[chilly hemlock]

Do you mean 1/((2x+1)(2x+3))?

[sharp rune]

Yes

In question they are asking fo find a formula for calculation sum

[lime linden]

hi guys,I have a hard time with questions of proofs related to functions (injective , Surjective and such), is there some way / approach to these proofs ? thankyou very much

[meager mural]

i already proved the first part (onto and one-to-one). how can i go about proving that g = f^-1

[mossy shore]

hi

how can i enumarate this?? hehehe any help

[sharp rune]

Anyone know about dave4math
https://youtube.com/@directknowledge

[weary tiger]

Xij = 1/m
Does this summation look correct?

I expanded the sum and there are nC2 terms not n(n+1)/2 terms

[honest holly]

yes its correct

[weary tiger]

Why do you think so?

[honest holly]

because the inner sum equals (n-j)/m

(that might be off, check it)

but it doesnt matter if you just care about asymptotics

[weary tiger]

yeah but I'm trying to be precise

The first term is sum X1j from j=2 to n

which has n-1 terms

the next would have n-2 terms, and so on

which adds up to n(n-1)/2 terms

[weary tiger]

It might be n-j+1/m

[weary tiger]

That sum actually doesn't make sense because the last sum goes from n+1 to n

The correct version is in CLRS

[honest holly]

i love thomas cormen

all i know about him though is quora answers haha

[weary tiger]

This guy

[honest holly]

i took algorithms freshman year...def could not parse clrs

but our stuff covered more or less the same, though we didnt really use the text

[unreal stump]

Honestly CLRS is kind of overrated

I can parse CLRS only because I already know the algorithms

[weary tiger]

it's for our course but no one reads it lol

[unreal stump]

True

[weary tiger]

have my algo finals next week. I'll try reading it since I have a better grasp of the topics

[honest holly]

one of the professors in the ds department uses it as

their monitor stand

haha

honestly... i probably will too

biggest book i own that i will never open again

[weary tiger]

that book is thicc af

I downloaded the pdf

[unreal stump]

I think CLRS is good as a refresher

Not good for learning first time

[weary tiger]

watching abdul bari is best for beginners

But he's not mathematical enough

[unreal stump]

I found this book via quora and it seems pretty decent

Like it reads somewhat like Polya's problem solving strategies

[weary tiger]

loved that book

This sounds like an algorithms book that emphasizes intuition over rigor

[unreal stump]

Well it also has more rigor than any other book lmao

Well apart from TAOCP

[weary tiger]

I'd read it if it didn't use an ancient programming language

[unreal stump]

Example

[honest holly]

im interested in algorithms for statistics

i have no idea where to start, but one day ill get there hopefully

[unreal stump]

I guess you want like numerical analysis?

[weary tiger]

Like machine learning algorithms?

[honest holly]

idk

i guess like the stuff here: http://proceedings.mlr.press/v30/Berthet13.pdf

people always talk about complexity too

i just nod along haha

[weary tiger]

People here avoid theory of computation

It's one of the only electives that don't get filled up

[unreal stump]

Well understanding

It is tough

And it's like not obvious why it is useful or interesting

[weary tiger]

Does it directly make you write more elegant code?

[unreal stump]

No

An algorithms class might make you do that

[weary tiger]

isn't theory of computation about algorithms

[unreal stump]

It's about automata

Turing machines ,pushdown automata and such

[weary tiger]

Sounds very cool

[unreal stump]

Look into sisper ToC ig

[weary tiger]

The last lecture prof gave us mentioned these topics

It was for fun. We won't have NP stuff in our exam

He just couldn't fit it in

[unreal stump]

So you don't even have like Knapsack?

[weary tiger]

Uh we had greedy algorithms

We had the easier version

the fractional knapsack problem

[unreal stump]

That's strange

0-1 knapsack is pretty important for interviews and such

[weary tiger]

Not the discrete version

[weary tiger]

rip

I feel like we missed a lot of things

he said he was covering two semesters stuff in one

[unreal stump]

Like dynamic programming is the most common kind of questions in interviews and tests

And 0-1 knapsack is the simplest example

[weary tiger]

At least we studied DP

He gave 3 lectures on it

[unreal stump]

And he didn't cover discrete knapsack in that?

[weary tiger]

Nah

unless I fell asleep in class

[soft charm]

could someone help me with providing intuition for why this identity holds?
based on the hint, I can see where the n+1 choose 2 case comes from, as that will correspond to all 3 integers chosen being the same
the n+1 choose 3 and n+1 choose 4 terms correspond to 2 and 3 distinct integers respectively

however, I can't see where the 6 coefficients come from?
why do we multiply those first two terms by 6?

[obtuse lance]

Strange, I've derived this identity before but never thought to put some kind of combinatorial interpretation on it. I'll think about it later

[weary tiger]

there was a bonus question in my proofs class

where they asked us to prove that using a combinatorial argument

Could never figure it out

[unreal stump]

I guess some kind of permutation?

Like you choose 3 elements and each permutation will get you a new thing

[zealous elbow]

for a is it just by checking all cyclic orderings of the vertex set?

and b, if it has a polynomial time algorithm the problem is in P so it can be solved in polynomial time

[soft charm]

yeah i think that's it
in the n+1 choose 3 term, we have 3 numbers, a_1,a_2,a_3 less than the largest one, k
if two of them are equal, then there are 6 possible ways to do that
a_1 = a_2, a_1 = a_3, a_2 = a_3 - and for each one, two ways to decide whether they will be the smaller of the two numbers other than k

in the n+1 choose 3 term, all 3 a_1,a_2,a_3 are distinct, and there are 3! = 6 ways to assign 3 numbers to 3 different objects

i worded that badly

i'll rewrite that in a cleaner way when i wake up tomorrow if nobody understood that 🤣

[haughty garden]

For (a), imagine you had a Hamiltonian Path in your graph. This means that G has a way of starting at a vertex and travelling to every vertex exactly once. You would now like to construct a graph which has a Hamiltonian cycle; the issue is that you don’t know what the starting vertex is unless you solve the problem

To resolve this, you should construct a new vertex that is connected to every other existing vertex

So G’ is the graph G with an extra vertex that is connected to every other vertex

You can now argue that G has a Hamiltonian path iff G’ has a Hamiltonian cycle

Checking all cyclic orderings is exponential because it’s the same as permuting all of the vertices which is not very efficient

[empty ridge]

Suppose I have a graph w/ a positive number of vertices, and 0 edges, could this type of graph exist, and if so, what are they called?

[brave rock]

Yes, such a graph exists, as you have described them. There is no name that I'm aware of for this type of graph.

[empty ridge]

Thank you

[weary tiger]

https://walkccc.me/CLRS/Chap23/Problems/23-3/

Anyone know how the solution works

[pastel canopy]

Guys for g) i

Do I have to move it two steps to the right

So it will be 11100000001.11 divided by 101

[coral parcel]

If that is what you'd do when dividing in base 10, sure.

(There are various ways of teaching elementary-school long division -- some start by normalizing the divisor like that, others don't. It works out to essentially the same computations in the end, just the punctuation along the way will look different).

[glacial flame]

Isn't this also true even with u and v aren't both odd?

since all possible cases of this are of the form gcd(a + b, b) or gcd(a + b, a) which is equivalent to gcd(a, b)

(and technically gcd(a, b) = gcd(-a, b))

[obtuse lance]

eh what is this

the euclidean algorithm seems superior

[glacial flame]

This is part of a more efficient version (binary gcd/euclidean alg)

but that's not really relevant to my question either way

[obtuse lance]

yeah, to answer your question, the 'both are odd' means you do line 4 when it's none of the preceding 3 cases

[glacial flame]

ah I see, I was reading it as "identities," since I had first read the code snippet (which calls them identities)

thanks

[obtuse lance]

yeah, you're welcome

[jolly ledge]

euclid asserting dominance

[grim tapir]

why is i set to be m+t+1 as default?

[heavy rain]

quick question about power sets

if C = {a, b ,c}, then the power set P(C) = {phi, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}

so does that mean the order of the contents doesnt matter, as in like {b, c} is the same as {c, b} so i dont need to repeat it?

[haughty garden]

Yes, order doesn’t matter in a set

[heavy rain]

okay thanks, as long as there is some combination of the two its fine

[chilly hemlock]

Any idéa how to approach this problem?

I can do it the "brute force" way

but I don't want to do it

[neon gyro]

How would one explain why a graph wouldn't have any other minimum spanning trees?

this graph does have more than one but in a scenario where a graph didn't

[snow junco]

Using prim’s algorithm(???) Or the one where you pick individual edges by minimum anywhere, rather than min adjacent, if you finish the tree by using every edge of each cost up till your max, ie all the 1s present, all the 2s present, then you can argue that by the algorithm there are no other potential edges to be selected as they are all of greater cost to your single spanning tree’s maximum edge and thus not minimjms

Whereas if at any cost you have surplus, ie you used only 3 of 4 2 cost edges, then that tier can be shifted to connected the same vertices at the same cost with an identical edge that isolated elsewhere (the 4th replaces one of the first three, which forms a new valid minimums spanning tree)

[chilly hemlock]

Any idéa anyone?

How to start?

[vestal bronze]

there's two parts, like you deal with the 9 and the 22

start with either one

[haughty garden]

Consider running Kruskal’s algorithm on a graph where all of the weights are unique. Kruskal will deterministically choose one edge every time, the only reason why you obtain multiple MSTs is because Kruskal or Prim’s will break ties arbitrarily

[restive void]

i think since you are proving divisibilty by 7, the 7x2^k is divisible by 7-> so that part can be combined into thr D(7)

and the 9 in front of the D(7) does not matter since that term literally has yhe D(7) itself.

its like saying:

9(7m) + 7(2^k) where k,m are in N
factor out the 7->
7(9m+2^k)
so this term is divisible by 7

[plain valve]

im really stuck on how to start these

all the examples i see online are A_n and not A_n+1

so for part A)
a1 = a2 = 5?

[earnest prairie]

a1 = -a0
so a1 = -5

[crimson osprey]

Any idea on how to start case one?

[brave rock]

Hint: if floor(x) = x, then in particular, x is an integer.

[weary tiger]

Im new to combinatorics, but can someone define what is "a way", does "how many ways" just mean "how many elements"?

[quiet tendon]

I can't find a video where it explains about x 1:n I think the x_1:n means it's the first sample of the n samples u got and they are ordered so it's the smallest sample?
and min xi means it's the minimum value so the smallest value of all the samples?

https://cdn.discordapp.com/attachments/1078340536634720398/1106728019227316244/image.png

[vestal bronze]

If there's 3 cans of coke and 2 children, there's 10 ways to decide how you deal with it
don't give them anything (1 way)
give one can to someone (2 ways)
give two cans to someone (1+1+1 = 3)
give all 3 (4 ways to do that)

[coral parcel]

It's often horribly underspecified, and you need to make some guesses about what makes the question possible to answer in the first place ...

[vestal bronze]

it's easier to give examples, way means way

[quiet tendon]

do u by any chance know my question too?

[coral parcel]

But yes, in general "how many ways" means how many elements in some set of descriptions of solutions. What can be ambiguous is how much detail there are in the descriptions we're counting.

[quiet tendon]

isn't this more often used in counting problems

[coral parcel]

As far as I can see, we're talking about counting problems here.

[quiet tendon]

ah mb

[quiet tendon]

but do u know my question by any chance

[coral parcel]

I can't make heads or tails of either your image or your question, sorry.

[quiet tendon]

no my question is this

[quiet tendon]

a

it's about cdf I think

[coral parcel]

I still can't make sense of what you're writing. Stop pinging me about it.

[quiet tendon]

do I need to change my question?

[delicate sentinel]

hello i was wondering if all the unions of intervals ]-n,n[
Is equal to IR or not because i asked an AI and it answered that the union of all the intervals should exclude n and -n out of IR ?

[unreal stump]

It is R

If you take an arbitrary element x in R, then x can found in the interval ]-n,n[ where n= floor(x)+1

And well the other inclusion is trivial

[coral parcel]

(With some absolute-value signs inside the floor).

[unreal stump]

mb

[haughty garden]

Well, suppose that mRn. Then, by definition, m + 7n is even; it is now your goal to prove that n + 7m is also even. It might help to look at (m + 7n) - (n + 7m) and deduce that n + 7m must be even; specifically, what do you notice about the difference here?

this argument also works; although I'd probably phrase it a bit better

firstly, m + 7n <=> n + 7m doesn't really make sense here. You're proving that, if m + 7n is even, then n + 7m is also even (and in turn, this means that mRn implies nRm)

the overarching argument seems fine; you'd want to explain why 7s - 24n is an integer which isn't too hard since s and n are integers

you don't really need the bottom argument since it's a one way implication

well, okay that kinda depends on the definition you're using; some texts use one way implications, others use iff

(1) you know that m + 7n is even;
(2) the difference is even (try expanding this out);
(3) what does this tell you about n + 7m?

👍