discrete-math

[dire stag]

I don't understand the stupid question with the balls, I don't understand why b. is not C(3,1), but d. is 3

integer?

[haughty garden]

no

should be 10

pick one element in each of the 8 pairs, pick 8. Then picking one extra element guarantees that at least one of the 8 pairs has both of its elements chosen

if one of the 8 pairs has both of its elements chosen, then the two elements in the pair add to 16, which correspond to elements in the original set that sum to exactly 2010

[dire stag]

ok

What does cardinality mean in this context?

Is it the column of pascals triangle?

[gilded dragon]

does a proposition have to verifiable? in the sense like "There is life in the andromeda galaxy"

[rain moth]

dont think so
not sure but assuming as a given whether its true/false is the closest you can get to "verifying" it

[dire stag]

:/ Pls help

[agile magnet]

Let $X$ be the set of 11-bit strings that have weight 5 and start with 011. Let $Y$ be the set of 11-bit strings that have weight 5 and end with 01. The question is asking you to compute $\abs{X \cup Y}$.

@dire stag

[vital dew]

Spamakin🎷

[agile magnet]

so compute that using inclusion-exclusion

so rewrite |X U Y| as something perhaps easier to compute

and go from there

[stray reef]

@dire stag do you still need help w/ this

[ionic ice]

Assume that we have five operations, union, intersection, difference, symmetric difference and cartesian product and three sets $A, B, C$. How many different sets can we create using these 5 operations? I think the answer is $5 \cdot 4 = 20$. My reasoning is the following: We can create 4 sets using union as the primary operation (meaning it comes first, reading from left to right) and the other operation(s) come afterwards. We can use only union as the operation but that can be discarded with because of associativity. Therefore there are 4 different sets from these 5 operations. However, because this can be written in 2 different orders, one beginning with the operation union and the other ending with it, there are 8 different ways this can be achieved. But the latter 4 sets, those that end with union, are respectively these sets where the other four operations come first. Therefore there are 4 different sets that start with a different operation than union. We can continue to do this and eventually get 4 sets for each operation. Therefore there are 20 different sets. Is this reasoning correct or incorrect?

[vital dew]

Forsaken

[twilit sundial]

the solution given here seems somewhat poorly explained: what about the classes that come after class i? do we just repeatedly apply that transformation at all points where the schedules deviate?

[haughty garden]

yeah, it's the standard exchange argument. You actually do not need an explicit contradiction. The idea is that any time a solution deviates from your greedy algorithm, you can swap it with the element that your greedy algorithm chose and argue that by exchanging this element, the new solution is either strictly better or not any worse

Repeat this argument for each index where your greedy algorithm and some optimal solution disagree

Here's the way that I normally prove the result. We prove the following claim.

Claim. There exist an optimal scheduling that includes the class with the earliest ending time.
Proof. Let x be the class with the earliest ending time, and suppose that S is an optimal solution that does not contain x -- we let y be the class in S with the earliest ending time. Firstly, since x ends earlier than y, then e_x < e_y (where e_i denotes the ending time of class i; similarly, we will also let s_i denote the starting time of class i). Since S is a valid solution, it follows that e_y <= s_i for each class i in S (otherwise, some class will clash with class y). Therefore, e_x < e_y <= s_i, which implies that S' := (S \ {y}) U {x} is also a valid solution with |S'| = |S|. In other words, swapping y for x does not yield a worse solution.

Convince yourself that this actually implies the correctness of the algorithm

[twilit sundial]

hmm aight

thanks

do we then use a similar argument for each successive class?

[haughty garden]

yes

you just repeat the same argument to slowly transform any optimal solution into your greedy algorithm using the exchange

[somber spindle]

hi, im a bit confused on well order relations since my lecturer only glossed over it a bit, can someone please walk me through how to solve this question/explain how to go about this question?

[pale epoch]

whats your definition of well-order

also this question is formulated quite open, so it might be useful to play around a bit with examples

[somber spindle]

see thats what im not sure of, all my lecturer said is if every subset has a least/smallest element

in that case are we instead looking at the sets (in this case set A and B) rather than the relation to determine if its well order?

[pale epoch]

this is a definition

a well-order is defined on a set, you need both pieces of information

do you have examples of well-ordered sets?

[pale epoch]

at least if you know what an order relation is

[somber spindle]

my lecture slides don't have any

it only gives the definition

[somber spindle]

so as long as we know that it's a total order relation, that means to determine if its well order we just have to look at the set?

[fossil mural]

well as an example: the natural numbers, with their usual order

every set of natural numbers has a minimum element (in fact this is equivalent to induction), so this is a well-order

if you take the normal order on the real numbers, that's not a well-order, because the set of all positive real numbers has no minimum element

[somber spindle]

ahh i see

[somber spindle]

so in a question like this, will a set of ordered pairs have a minimum element?

not entirely sure how ordered pairs work and if you can determine a minimum element from a set of them

[fossil mural]

well that depends on the order

they're asking you to define an ordering on A \times B

that is also a well-order

[somber spindle]

wait so that means you can have a well-order relation on a set of ordered pairs?

[fossil mural]

yes

for instance a well-order on {(a, a), (a, b), (b, a), (b, b)} is (a, a) < (a, b) < (b, a) < (b, b)

(any total ordering on a finite set is a well-order)

[somber spindle]

ahh you order them like that

i see

[somber spindle]

ill have to keep this in mind, thank you 👍

[dire stag]

idk what to do

How do I find the results?

if I already have numbers like 011 or 01, then how does that affect the weight?

How do I find the overlap if I'm doing this in binomial coefficient notation?

[stray reef]

do you know what the weight of a bitstring is?

[dire stag]

number of 1s

[stray reef]

right

so when you're finding |X ∩ Y|, i.e. the overlap as you say

you are calculating the number of strings that begin with 011 AND end with 01

and have length eleven

so you are counting strings of the format 011xxxxxx01

do you understand y/n

[dire stag]

y

[stray reef]

right

so you've got those start and end fixed

how many 1's are thus fixed?

[dire stag]

3

[stray reef]

and so how many 1's need to appear in the middle?

[dire stag]

2

[stray reef]

well there you have it

[dire stag]

15?

(6 2) = 15

[stray reef]

yes

C(6,2) is my go-to plaintext equivalent if the binomial brackets can't be typed

[dire stag]

[agile magnet]

Instead of giving a number with an emote can you explain how you arrived to 15?

[dire stag]

The overlap, has 6 spots

and 2 1s

hence, C(6,2)

[agile magnet]

Do you know that |X ∪ Y| = |X| + |Y| - |X ∩ Y|?

You have to use this

[dire stag]

yes

[stray reef]

well do it lmao

[dire stag]

Monkey brain did something

2^8 I believe is C(8,3), because 011 already reserves 2 of the 5 weight. 5 - 2 = 3.

Same for 2^9

2^6 is the overlap

[agile magnet]

Can monkey brain compute |X| as a start

[agile magnet]

Is this correct?

What do you think?

[dire stag]

idk, I'm not sure if I'm supposed to

subtract
5 - 2 = 3 from |X|, because 011 already reserves 2 1's

and

5-1 = 4 in |Y| because, 01 already reserves 1 1.

or

if I just ignore it and apply the weight 5 to the X's without looking at 011 or 01.

It's interesting just how similar the answers are to one another.

[weary tiger]

how do I find y?

[agile star]

Hello guys, weird question, how do I get better at combinatorics?

I've found it verg hard even at beginner level and I think I lack many of the basics

And time is very tight lately, my final exams are 120 days away and it's pretty life changing especially due to my shittys country's economy

So any recommendations??

[pale monolith]

Do problems

[brave rock]

How do you get good at literally any skill? You practice.

[agile star]

How about learning the basics?

And getting a better understanding on how it works and all

[agile magnet]

Do you have a textbook you're looking through?

Like for whatever course you're taking

[agile star]

Yes but it barely has any practice problems and it has very shitty outlaying

[agile magnet]

Ok so maybe a better text would be worth getting

[agile star]

Like I've read it all twice

[agile magnet]

There's a good text, A Walk Through Combinatorics

[agile star]

It's actually not possible

We are forced to study our gov curriculum

From official books from the ministry

[agile magnet]

Ok but you can still learn the material through different stuff

Do problems from different stuff

[agile star]

So I'm kinda stuck with it

[agile star]

Yeah that's what I'm trying to do

[agile magnet]

Sooooo if that's what you're trying to do

Find a PDF of the textbook I mentioned

[agile star]

But honestly I'm ignorant to all different sources

[agile magnet]

And do problems from that

[agile star]

That one?

[agile magnet]

Ya

[agile star]

Cool

Imma check it out

Thanks man

Oh crap internet is out

Now you understand my resentment towards my country

It's the upgraded version of Detroit

Anyways thanks man

.close

[dire stag]

Where did I go wrong?

for a, I did C(20,18), and for b, I did P(20,18)

[haughty garden]

C(20, 18) means that the ordering of the books doesn't matter

I think the phrase "Notice that here we will allow the books to end up in any order" can be a bit misleading

P(20, 18) doesn't work for part (b) because you allow permutations where the books aren't necessarily in alphabetical order

e.g. if you had books A and B, then P(20, 18) will consider arrangements where A comes before B different to arrangements where B comes before A (which we do not allow)

(in fact, you have it the wrong way around but I'll let you think about why)

[dire stag]

oh

b will be 190

[haughty garden]

yes but it might help to think about why

[dire stag]

Permutations are all the possible rearrangements of objects / elements.

[haughty garden]

another way to think about permutations is to that it is an ordered collection of objects

in other words, once you choose your collection of objects, you want to find the number of ways to permute these objects

hence, you also have that P(n, k) = k! * C(n, k)

for part (b), in any group of 18 books, how many ways can you arrange these books if you require these books to be in alphabetical order?

for example, let's say I have the letters {B, C, A, D}, how many ways can you arrange them so that these letters are in alphabetical order?

[dire stag]

1

[haughty garden]

yup

[haughty garden]

now what about this?

[dire stag]

😑

[dire stag]

1?

[haughty garden]

exactly

in other words, if I choose any 18 out of the 20 books, there's exactly 1 way to arrange these books

but how many ways can I choose 18 books from a total of 20?

[dire stag]

P(20,18)?

[haughty garden]

P(20, 18) assigns an order

we don't care about the order

because remember that there's only 1 ordering

[dire stag]

oh I see

C(20,18)

C selects, P arranges

[haughty garden]

yep

so we can first select 18 out of the 20 books and then realise that once we choose these books, there's only 1 way to arrange them

which gives you C(20, 18) for part b

[dire stag]

Ahh I see now!

Awesome! Thanks!

[haughty garden]

[onyx axle]

Can someone tell me what multi-sets are?
Specifically why is the formula this, why do we subtract 1 and add k?

[vestal bronze]

multisets have a certain amount of each element

like, {a,a,a,b} or {3a, 1b}

the formula is like this because we can count ways to e.g. add up to 10 with 4 integers
by taking 3 dividers and 10 stars**********|||
and permuting it
****||******| 4+0+6+0
**|***|**|*** 2+3+2+3
meaning there's 286 multisets with 10 elements if there's 4 types of an element

so we choose 3 spots out of 13 to be dividers
or 10 spots, it's the same thing
the formula is at the same time (n−1+k)C(n−1)

[agile magnet]

,rotate

[wheat hound]

guys please lock in

[agile magnet]

yay now its readable

ok how many rows are there in a truth table with 2 statements?

[wheat hound]

4

[agile magnet]

how did you get that?

You're right, but explaining why will hopefully help you figure out how to get the 4 statement version

[wheat hound]

well like its p q not p not q

[agile magnet]

?

what?

[wheat hound]

idk twin thatx ehy im asking

[agile magnet]

can you write out the truth table for P and Q?

this has 2 statements: P, Q

and it will have 4 rows

[wheat hound]

twin im sorry i knos how to do it but i have tobgo go to bed in 5 mins

its

ttff

tftf

[agile magnet]

idk what that means

[wheat hound]

like for the possibilities beloe it

[agile magnet]

possibilities of what below what?

[wheat hound]

for a scensrio

please tell me how to solve this

i needbthe 4 extra credit points

spamakin

is it 16

[agile magnet]

how did you get that?

[odd prism]

I know it’s 9!/2^3 - something

[haughty garden]

my first thought is inclusion/exclusion

the complement is "either the m's are together or the t's are together or the e's are together" and apply inclusion/exclusion on that

[odd prism]

Gotcha

E + M + T - ET - EM - MT -TE + MTE

[haughty garden]

yes

and those cases are easy to compute

[odd prism]

I’m completely brain farting can you give an example for case E

[haughty garden]

Treat the E's as 'one letter' and arrange the rest

There are 8 letters once we group the e's together; so you have 8!/(2! * 2!) total permutations

[odd prism]

Ohhhhhh

Now I’m starting to get the generalization for the multi nominal

[odd prism]

So for case et we would have (9-1-1)!/((2-1)!(2-1)!2!)

[haughty garden]

try it out by hand

[sonic shadow]

How should one approach this problem?

I have been aching this one for quite some time, and I actually have no clue as to how to set up the pigeons and the pigeonholes

I know that it's a pigeonhole problem, I can just simply taste the yummy pigeons

But I actually have no idea

Here is my take to this problem, so that I am not just spoonfed the answer, because I want to know how to squeeze a pigeonhole from a rock

We let X be the set of numbers from 1 to 49, and we define a function a_i =1,2,..5 for all i in X.

In other words, a_i is the number of hours the student plays video games at the ith day

We see that using our formulation, we have \sum_i ^{i+7} a_i \le 11 for all i,i+7 in X

That is, for every "interval" in X that is 7 days long, the corresponding sum is always less than or equal to 11

I found out that the suitable intervals for which the student plays 20 days is atleast 218

So, that's a lot of pigeonholes

How do we catch our pigeons?

Thank you in advance

The total number of intervals possible was 1225

Thanks in advance

:)

[last flume]

Can anyone help with this problem? Should the 1st premise be
c(Linda) ^ r(Linda)

[gilded sun]

Am I understanding this properly? I used the property that (n/k) = (n!)/k!(n-k)!

[agile magnet]

how did you get that answer

[vital dew]

Spamakin🎷

[gilded sun]

So basically what I did was the following: if we follow the property i put above we get (17/5) = (17!)/(5!17-5), which gets us (17/5) = 17x16x15x14x13x12x11x10x9x8x7x6/5x4x3x2x1x12x11x10x9x8x7x6

12x11x10x9x8x7x6 can be canceled from numerator and denominator

so I get (17x16x15x14x13)/(5x4x3x2x1)

then i simplify

[vital dew]

Spamakin🎷

[agile magnet]

so that first step is wrong

but then you correctly simplified (17!)/(5! 12!) to (17x16x15x14x13)/(5x4x3x2x1)

[agile magnet]

so you realize you made a mistake typing this out here right?

[vital dew]

Spamakin🎷

[agile magnet]

you follow everything I said so far?

[gilded sun]

yes

[agile magnet]

ok so you see how what you wrote here is different to your selected answer?

so what is the correct answer?

[gilded sun]

1747*13

17x4x7x13?

[agile magnet]

why?

[gilded sun]

wait no, my original answer is the correct one..

[agile magnet]

huh?

why?

[olive wraith]

I have a question 1/10 = 0.1
so how 1%10 == 1 I did not understand this can any one eleborate this

[stray reef]

do you know what the percentage sign stands for here?

@olive wraith

[olive wraith]

modulas

reminder

[stray reef]

remainder.

that's right, a % b is the remainder of the integer division of a by b.

when you integer-divide 1 by 10, your quotient is 0 and your remainder is 1:

1 = 10*0 + 1

do you understand this? Y/N

[olive wraith]

Y

[stray reef]

does this answer your original question of "How is 1 % 10 == 1?"

Y/N

@olive wraith

[olive wraith]

Y

[somber spindle]

ive encountered a problem while solving this question, i got that the answer is
b = -19,
c = 90
d = 112,

but when my friend tried doing it using almost the same exact method but differing ever so slightly, he couldnt get the answer, even though logically we did the same thing

(image is missing curly brackets for the set {3,4,...,10}, sorry)

in my work, i decided to multiply the 2's from the nC2 terms into the 56 and reached the correct answer

but here my friend decided to fully evaluate the nC2 instead of multiplying the 2's from them it into the 56, and found that the value for b changed every time he tried to use different numbers of i for his elimination

is there any reason why this happens?

[ashen sandal]

Let M(n,m) denote the complexity of the best algorithm for assimilation of series a1<...<an and b1<...<bm. Prove that M(3,6) <= 7

You have 15 white,32 black and 17 red balls. There is exactly 1,
radioactive ball among each group. There is a device, which says
if there is at least one radioactive ball among some group of balls
(quantity and color doesn't matter). You have to give an algorithm
that sorts out the 3 radioactive balls with minimum measurements.
[10:24 PM]
Please Help me to solve this

[errant bear]

are you familiar with binary search?

[wraith pelican]

Just started working with floor and ceiling functions, and I'm confused with what should probably be a very simple proof. This is what I'ge got so far. Not sure about the logic after this, though.

This is what my book has for the solution. Can I really just assume that floor(-x)=-n-1 and do the substitution? It feels like there are steps missing. But, again, I am seeing floor functions for the first time

[errant bear]

its not an assumption

[summer falcon]

Yeah you can prove it from the inequality

[wraith pelican]

Like so?

[summer falcon]

I mean yeah you can just say its by definition (I mean its fairly trivial) but you could also assume that there is an integer a between x and -n-1 and then show that a has to be -n-1 by contradiction for example

[static briar]

Can someone explain the answer

[haughty garden]

inclusion/exclusion principle

[static briar]

Total arrangements - those with two consecutive letters for the Es and then again for the Ts

But I don’t understand how the 6! Comes from

[haughty garden]

T's are consecutive and E's are consecutive

you treat the two T's as 'one letter' and the two E's as 'one letter'

so you now have 6 'letters'

[static briar]

Is that where the two 7!/2! Comes from

[haughty garden]

the 7!/2! comes from treating the T's as 'one letter'

and then arranging the rest

there are 7 'letters' after grouping the T's together, so now you can think of it as arranging BAGUE(TT)E

which is 7!/2!

and similarly for the E's

[static briar]

Ok but why do we have to add 6! Then

[haughty garden]

because you have to consider the case where the T's are together and the E's are together

e.g. EEBAGUTT is counted once when you consider the T's together and once when you consider the E's together

[static briar]

Ahh so we over counted got it

[haughty garden]

i.e. one way to count it is (EE)BAGUTT and another way is EEBAGU(TT)

[warm egret]

Can someone recommend an ebook on number theory am a beginner

[brave rock]

#book-recommendations

There is a pinned list here iirc ^

[jade tangle]

why is discrete math so anoying and ass

fr calc 1 is so much more fun

[calm chasm]

Where am I using conditional interpretation here?

[meager prawn]

The point of this server isn't to ask people to DM you
It's to ask your question and then someone should help you

[rose acorn]

Hey. Let G be a graph and phi be an automorphism of that graph. Then, it does not necessarily hold that phi(G) = G?

An example of why I think this does not hold: Consider G = ({1,2,3}, {{1,3}, {1,2}} and the mapping phi that maps:
1 -> 2
2 -> 3
3 -> 1

Then phi(G) = ({1,2,3}, {{2,1}, {2,3}}) which is not equal to G (but isomorphic to it).

So this example here:

I am misunderstanding automorphisms, aren't I?

[cerulean radish]

Pretty sure what you provided isn't an automorphism in the first place, it doesn't preserve the degree of the vertices 1 and 2

[stuck blaze]

If I'm understanding you correctly, this is true

not all graph automorphisms are the identity function

[cerulean radish]

They are asking about the image though

As far as I am aware, yes, phi(G) must be equal to G

That's almost the entire point of an automorphism

[rose acorn]

Thanks for the replies. I am interested in the general statement: every graph automorphis is an identity function. The image is supposed to be a counterexample to that

[cerulean radish]

Then yeah not every graph automorphism is the identity function

Here the mapping 1 -> 1, 2 -> 3 and 3 -> 2 provides an automorphism different from the identity

[rose acorn]

Okay that is good! Thanks. Just realized that the image is not exactly what I wrote down. Are the drawn things still automorphisms?

[cerulean radish]

No, the degrees of 1 and 2 are not preserved in the mapping

Graph isomorphisms in general must be degree-preserving

[cerulean radish]

This in fact should be the only nontrivial automorphism

[rose acorn]

What exactly do you mean by degree-preserving?

[cerulean radish]

A vertex v has degree n in the original graph <-> The vertex f(v) has degree n in the codomain

A function f satisfying this is called degree-preserving

In your example, the vertex 1 is the only vertex with degree 2, so it must be fixed by any automorphism of G

[rose acorn]

Oh yes, I see why that should be the case

So G and G' are isomorphic but not automorphic?

[cerulean radish]

You can say that, yeah

[rose acorn]

But in this example:

Here the mapping 1 -> 1, 2 -> 3 and 3 -> 2 provides an automorphism different from the identity
We get an identical edge set?

[cerulean radish]

Yeah

[rose acorn]

So the graphs are actually identical and the automorphism is an identity?

[cerulean radish]

No, that's like saying a bijection of a set is always an identity mapping because the image is the same set as the domain

[rose acorn]

okay thanks, gotta think about this for a bit

[rose acorn]

Okay, I am still confused 😄
Would you say that the following definition of graph automorphism is correct (marked in blue)?

[cerulean radish]

Yeah

[rose acorn]

So if i have some edge {i,j} in my edge set E(G), then I will also have that edge {i,j} in the edge set E(sigma(G)) where sigma is an automorphism?

[cerulean radish]

Yes

In general adjacent vertices should stay adjacent after a graph isomorphism

And viceversa

[rose acorn]

Yea, but do the indices of the vertices change?

Because I fail to reconcile this (image, from wikipedia) with the fact that an automorphism is supposed to give me the same graph back (so not even an isomorphism)

[cerulean radish]

I don't see where the confusion is coming from

In case you are asking if the names of the vertices change, yes, they may change under an automorphism

So {i, j} being an edge in G and also in sigma(G) does not mean that i and j get mapped to themselves

[brave rock]

You will get the same graph in the same way that a symmetry of a square – for instance flipping it horizontally – will get you the same square at the end. The vertices of the square have been permuted by this reflection despite it being the same object.

In fact here is a similar 'flipping' example. I define a graph automorphism of this graph here by exchanging the vertices as indicated by the red arrow. If you like, the labels of the vertices have been changed (and the edges connected to them have been exchanged to follow them) and the graph looks no different.

Automorphisms encode symmetries of graphs in this way.

[rose acorn]

Yea, I think I somewhat do get that but I cannot relate that to the proof I want to understand. I guess my problem is somewhat connected with the idea of indices (or names of vertices). I'll just post the proof, here v and w being similar means that there is an automorphism between them. My problem is that I do not understand the last line where they just get rid of the \sigma

[icy swift]

https://gyazo.com/7275bfb8a5f8d4085ebab82d5af4fc96

https://gyazo.com/15189d646bf69c1200b65c2e6b8c20dd

I'm confused by the solution

As to how the choices for x,y,z, and w were chosen

actually i think i understand how they were chosen but

what is the logical reason that solving for the integral solutions of x+y+z+w = 15 gives us the same number of 3 integer sets that satisfy the problem

[narrow robin]

Anyone knows why this is true?

[haughty garden]

Say that modules on processor 1 belong to the set $S$. Convince yourself that the total cost is given by [\sum_{i \in S} \alpha_i + \sum_{i \not\in S} \beta_i + \sum_{i \in S} \sum_{j \not\in S} c_{ij}.]
Construct the flow network as follows: let $V = {1, \dots, n} \cup {s, t}$ and define the edges in three parts.
\begin{itemize}
\item For each module $i$, construct an edge $s \to i$ with capacity $\beta_i$.
\item For each module $i$, construct an edge $i \to t$ with capacity $\alpha_i$.
\item For each pair of modules $i, j$, construct an edge in both directions with capacity $c_{ij}$.
\end{itemize}

Now, consider any cut $(S, T)$ in this flow network. The only edges that contribute to the value of the cut are exactly those edges of the form $S \to T$. Convince yourself that this corresponds to the value of the total cost and therefore, the value of the minimum cut corresponds exactly to the minimum value of the total cost.

@narrow robin

[narrow robin]

I'm still confused, what exactly is the meaning of the flow in this case?

[haughty garden]

As in you’re not sure what the flow network is doing?

If you compute any flow, you can find its corresponding cut

The value of the cut will correspond to the value of the total cost

So to minimise the total cost, you want to find the value of the minimum cut

but this corresponds to the value of the maximum flow (by the maximum flow-minimum cut theorem)

[cursive hamlet]

I've been working on a personal (programming) project for a long while related to mazes, but I haven't made much progress more most of that time because I don't have a good mathematical understanding of mazes because I've learned very little discrete math. Would studying just graph theory eventually give me a good understanding of mazes, or is there another category of math I should also study? I'm also open to any textbook/online course recommendations.

[static briar]

how do I come up with combinatorial arguments quickly

[brave rock]

You practise

[static briar]

unfortunate

there has to be a trick tho right

[narrow robin]

oh i see thanks

i get it now

[brave rock]

There is not a trick to finding proofs; a proof can be as hard as anything

[summer falcon]

You could learn different techniques to have an repertoire to use on a given problem but otherwise as Boytjie says

[tidal kindle]

Need help with this question

[static briar]

Can anyone explain how they got this

[haughty garden]

Inclusion/exclusion with stars and bars

[static briar]

lemme eplain my thought process

we have 50 that we want to distribute into r,s and t so that 50+3 -1 choose 3 which is 52 choose 3 for the solutions including overcounting

how did they get 52 choose 50

[haughty garden]

Using stars and bars should give you C(50 + 3 - 1, 3 - 1) = C(52, 2)

[static briar]

the formula says its just k in teh bottom not k -1

[haughty garden]

This formula swaps the n and the k in my formula

You want to distribute k objects into n bins

[static briar]

ye so 50 objects into 3 bins in our case

[haughty garden]

Yep

[haughty garden]

following this formula should give you k = 50 and n = 3

[static briar]

ah ok got it

where does the - 26choose24 twice come from

[haughty garden]

when you counted C(52, 50), you counted the possibility that either r or s were > 25. So you need to remove the number of solutions where r or s > 25. We can do it one at a time. Suppose that r > 25 or r >= 26 (since r is an integer). Then this is equivalent to saying r - 26 >= 0 and so we can set r* := r - 26. The equation r + s + t = 50 then becomes (r* + 26) + s + t = 50, where r*, s, t >= 0, or equivalently, r* + s + t = 24. Then apply stars and bars on this equation to get C(24 + 3 - 1, 3 - 1) = C(26, 2) = C(26, 24)

then do the same but with s >= 26 (you should get exactly the same as when r >= 26 because of symmetry)

then count the number of non-negative solutions when both r, s >= 26 (you'll realise this has no solutions!)

[static briar]

goat

also i just found out the question was changed to have both r and s <=25 but u seemed to have caught on to it

acc a legend

[wraith pelican]

Having trouble on a proof involving floor functions. I've made it work when n is even, but I honestly have no idea what to do with it when n is odd. The hint in my book says to split the odd case into 3 separate cases, which I have tried, but I can't see how that yields anything useful. I'm sorry I can't be more specific with my question. I'm just very confused on this. Here's my work so far.

[dire stag]

How am I supposed to do this?

Pricniple inclusion/exclusion, binomials? What do I do?

[agile magnet]

at least 6 means it could be exactly 6, 7, or 8 heads

these cases are all disjoint right?

so compute each of these cases and combine

[dire stag]

Like this?

[agile magnet]

what do those products represent?

Like ok 1/2 = probability of a head or tail

why multiply? What does that count?

[twilit sundial]

those computations completely fail to account for the fact that the heads/tails could occur in different orders

[azure hamlet]

Does anyone know a good Soviet Math book that explains the Expansion series? (Dévelopment Limits)

[carmine pond]

Can any1 explain how natural deduction works

I have this but don't know wut to do

[unique girder]

Is the minimum order of a graph containing exactly one vertex of degrees 0, 1, 2, 3, and 4 n=11?

[stray reef]

by "order" do you mean vertex count?

[unique girder]

Yes

The best I have produced is connected the K_5 graph to the vertex of degree 4, and leaving the vertices of degree 0, 1, 2, and 3 alone. But I'm not sure if there is a way to decrease the order even further by connected the vertices that will have degree 1, 2, and 3 to vertices other than the one of degree 4, if that makes sense.

[stray reef]

yeah it looks like you're right

i don't have an ironclad proof but i did manage to convince myself at least 11 vertices will be needed

[unique girder]

Very well, thank you!

[fervent wyvern]

When is the boolean lattice graph ($BL_n$) non planar?
I'm looking for a specific n for which this happens

[vital dew]

piss_master49

[stray reef]

do you mean graphs like these?

(the one depicted would be BL_3 i guess)

[unique girder]

Is the following a fair slightly informal proof?

Proposition: If $G_1$ and $G_2$ are isomorphic graphs, then the degrees of the vertices in $G_1$ are exactly the degrees of the vertices in $G_2$.
\vspace{12pt}

My informal proof: Let $G_1 \cong G_2$. Then there exists some bijection $f: V(G_1) \rightarrow V(G_2)$, with ${f(e_1), f(e_2)} \in E(G_2)$ for all ${e_1, e_2} \in E(G_1)$.
\vspace{12pt}

Now, let $e_1, e_2 \in V(G_1)$ such that ${e_1, e_2} \in E(G_1)$. That is, suppose $e_1, e_2$ are adjacent in $G_1$. Then ${f(e_1), f(e_2)} \in E(G_2) \Rightarrow f(e_1), f(e_2) \in V(G_2)$. Since it is the case that for any edge $e={u, v} \in E(G_1), f(e)={f(u), f(v)} \in E(G_2)$, all adjacent vertices and therefore edges must remain invariant under isomorphism. That is, $\text{deg}{G_1}(v)=\text{deg}{G_2}(f(v))$ for all $v \in G_1$.

I'm mostly just ensuring that my logic, especially towards the end, is consistent here

[vital dew]

j.ross.

[near stream]

Hello, could anyone help me with this question? I have no clue if I am on the right track at all ;-;

[summer falcon]

your solution for a) looks good

[near stream]

yay, thanks a bunch!

[near stream]

could someone pls guide me through this? i dont know where to start..

[twilit sundial]

while it's not a formal solution

at least one of p,q,r is true, so at least one of 2,3,4 is true

then by modus ponens $a\vee s$ holds, at which point you finish with disjunctive syllogism

[vital dew]

elrichardo1337

[lofty geode]

Does anyone know whats the minimum order of a graph? or the maximum order of a graph. Graphs in terms of graphs in graph theory.

[stray reef]

"order" probably means vertex count

and without conditions placed on the graph, the answers to those would be... 0 and +∞, i guess?

[brave rock]

Do you mean given a graph, what is its minimum order?

Because that's just the smallest order, and that could mean various things

[lofty geode]

Yes, thats why i am confused. G_BD is independant from the definiton i believe, but they never defined what minimum/maximum order meant. They mention distance alot however

now that i think about i feel like its just setting a bound for the min/max number of vertices for the given graph

[stray reef]

well yes

but we would need to see the defn of G_beta,D to actually tell you anything

[lofty geode]

its just a special subgraph so thats what makes me believe is the definition, thank you it helped to ask

[hard pasture]

Don't know where to put this, but can anyone prove if this formula eventually reaches a power of 2 if recursively put into itself?

$\frac{5}{2}x^{2}-\left(5x+2\right)\operatorname{floor}\left(\frac{x}{2}\right)+\frac{3}{2}x$

[vital dew]

Vanouper

[coral raven]

this is some collatz type shit

[coral raven]

oh wait

this is literally collatz

okay cool

[frozen blaze]

ok so

for this is it just Z or

[stray reef]

what makes you think it is Z?

[hard pasture]

lol

[weary tiger]

Whats the answer to
x²y +3yz - 2x² + y - 6z - z

[stray reef]

there is no answer because there is nothing to solve

!original

[lofty cloud]

Please show the original problem, exactly as it was stated to you, with the entire original context. A picture or screenshot is best. If the original problem is not in English, then post it anyway! The additional context might still be helpful. Do your best to provide a translation.

[stray reef]

and also:

!noans

[lofty cloud]

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

[weary tiger]

👍

[stray reef]

ok but like are you gonna show the problem

or did you decide to abandon it

[weary tiger]

Give me one sec

No.19

[stray reef]

well this is a mess.

but what were you asked to do with this?

[weary tiger]

Separate factors of degree polynomials

Yeah

[weary tiger]

Check No.18
I think thats how it work

[stray reef]

this sounds like a bad translation

[weary tiger]

yeah

I'm bad at english

[stray reef]

and if you're asked to factorize

i think that's going to be difficult

x²y +3yz - 2x² + y - 6z - z

i don't really see how to proceed here

[weary tiger]

Wait ill give u another one

How about this one

[stray reef]

this one looks more doable, but do you have any progress for it?

[weary tiger]

no.

Lemme try

[stray reef]

how did you do number 18?

oh, ok, you're going to try.

ok.

[weary tiger]

idk

But i would say its right

[weary tiger]

But I'm stuck at no.19

I think its not right

[wet flame]

do we even need the alphabet? surely it doesn't help with the question?

so we just get {ε,a,b,ab, ba,bc,aa,bb,abc,bbc,bca,bcb, aaa,bbb,baa,bab,aab,bba,aba} ?

[agile magnet]

in this case no you don't need the alphabet I guess but technically, languages are defined over an alphabet so it's I guess for completeness

[wet flame]

ah

also

[agile magnet]

at a glance this seems fine

[wet flame]

i feel like im doing this wrong, say i have two elements in some set e.g x= {a,b,ba}*
is this correct?: u ∈ x ∧ v ∈ x ⇒ uv ∈ x

[agile magnet]

do you think it's correct?

if so, why?

or if you think its incorrect, tell me why

[wet flame]

I thought it would be incorrect given this definition, e.g for x again, we get {e} U {a,b,ba} U {aa, ab, bb,aba} ,... for the first three terms right? if we go by the implication definition, i feel like that also gives additional elements not given by this union definition, e.g ba

[agile magnet]

ba is in L^2

[wet flame]

nvm

i got confused

ye

so it is true ig

[agile magnet]

ya

proof shouldn't be too hard

[tidal bridge]

can someone do this

[agile magnet]

oh thank god it's a recurrence lol

[agile magnet]

ok so what is the key to a recurrence?

step 0 should be identifying a decision you make

and your recursive cases depend on that choice

your decision here is what tile you place

So if your first tile is green, how does that influence your next choice?

etc etc

[crimson canopy]

I am learning graph theory. Trying some questions...not very satisfied with my presentation kf answers so far. But i will work on thay

But..i am stunned by a question.

A simple connected graph has 2024 vertices such that there are exactly 2 vertices with the same degree.
What is the degree and why?

I have no idea where to begin or what to think

The maximum number of edges is v(v-1)/2 right?

But it doesn't need to be maximum edges

[twilit sundial]

the degrees being involved makes me think you might need to use handshake lemma

it’s been a bit since I did graph theory in combo class, my memory is a bit rusty

[crimson canopy]

Hmmm... i will read up on that.
Thank you.

Hmmm...anything i should like keep in mind while reading up?

[twilit sundial]

ah wait

I did a problem very similar to this one

ok so since the graph is connected

what are the possible degrees of each vertex

||1,2,…,2023||

and how many vertices do we have

I have a feeling that there being 2024 vertices is not that important, and the answer is probably similar for smaller numbers of vertices too

try it for some smaller cases: 3 vertices, 4 vertices, 5, etc.

[crimson canopy]

Sorry, i am pretty lost.

I don't have the number of edges.
Isn't that a crucial info.

Hs lemma state that sum of vertex degrees = twice of number of edges, but i don't have either of these numbers.
Only number of edges.

It can be 2000 vertices connect 2023, and the remaining 23...connect skme number

[twilit sundial]

we have 2024 vertices, and 2023 possible degrees, since the graph is connected (1,2,…,2023)

by pigeonhole two vertices must have the same degree: what that degree is im still trying to figure out

I think the best strategy for now is to try some small cases and see what you get

[crimson canopy]

I don't understand what do you mean by 2023 possible degrees.

I think that is the possible number per vertex?

So the total number of possible configurarions, while remaining a simple graph is 2023^2024?

[stray reef]

I don't understand what do you mean by 2023 possible degrees.
if you list out all the vertices' degrees, without duplicates, the list will contain 2023 numbers.

So the total number of possible configurarions, while remaining a simple graph is 2023^2024?
probably not, but it's also probably not very helpful to think about that number of configurations anyway

[fossil mural]

there are at most that many configurations but a lot of them don't work

like anything where the sum of degrees is odd, or twenty vertices with degree 2023 and then all the rest have degree 1

[twilit sundial]

I reread the problem statement and I think the “exactly two vertices with the same degree” part might be important

[crimson canopy]

Ah. So its the sequence number thingy.

Sorry if my terminology suck. I am still weak at that

[crimson canopy]

Oh ya. True. Thank you

If i "assume" which my profs say i should never.

Suppose 2024 vertices lie along a line.

The 1st and last points are...idk how to say...like, they are bounded? So they are only connected 1 way

So...that means 2 points with degree 1?

But if correct, i have no idea how to proof if this unique or not.

I just guess and hit ssr

[twilit sundial]

so give the first 2023 vertices a unique degree each, then see what the degree of the 2024th vertex must be

might help to try this on a smaller number of vertices

3, 4, 5

[stray reef]

can the duplicate degree be 0?

[twilit sundial]

no, since the graph is simple and connected

[crimson canopy]

Wouldn't this raise the question of why can't some of the vertices have same number of degrees?
As long as its not a pair

[pale monolith]

There are exactly two vertices that have the same degree

I.e. all other vertices have different degrees

[dire stag]

?

$(4/18) --> (2/9)$

[vital dew]

Girimuszek

[dire stag]

$18-4 = 14 (14/18) --> (7/9)$

[vital dew]

Girimuszek

[dire stag]

I'm confused by what I did wrong

[twilit sundial]

read the question more carefully

“odds in favor” != “probability”

[crimson canopy]

Oooh.

I am starting to understand.

Suppose there is a pair of vertices with the same degree n.

Suppose there is a triplet or more vertices with same degree k, for k=/= n.

That means there are exactly 2 vertices with a specific degree n, not same degree?

Rip my english

Hmmm..i see.. i have to give the 1st 2023 vertices each a unique degree.

[formal falcon]

est-ce clair?

[dire stag]

Thanks!

What do I do here?

[crimson canopy]

@twilit sundial
I think....i got it, but its not math, i didn't guess and check, but its inspiration rather than hard work which i am ashamed to admit.

So exactly 2 vertices have same degree.
As you said, suppose the other 2023 vertices have unique number of edges.

I had this thought. We know some propertiss of degree sequences of simple connected graphs.

So suppose i write the degree sequence append n, where n is some integer [1. 2023] is the degree of the last vertex that has the same degree number as one of the other 2023.

By the havell hakimi algorithm?
We remove 1st term, and subtract 1 from k number of terms, where k is the value of subtracted term.

Largest term is 2023, so whether n is 2023 or not, 2023 will be the 1st removed term, and 1 will be subtracted from all other term.

Issue: if n = 2023, that means it connects to every term, then since there is already another node that connects to all other nodes, then there cannot be only node with degree 1, since 2 2023 meaning min degree is 2 then.

Idk if and (andd if correct) induction should be applied here to extend through the numbers.

Then we can find the value of n

Thanks so far for being patient with me

And.....ngl...this argument is more english than mathy?

[twilit sundial]

imma read through this more closely later

but yea graph theory proofs tend to be like that

which is why it’s potentially a good way to introduce proof writing (much better than Euclidean geometry or analysis for that matter)

[formal falcon]

use the concept of probability of getting a sum of 11 with a pair of fair dice in general

and then use the binomial distribution

and take the summation over something, this part is rather obvious

[icy swift]

this is from a chapter on Pigeonhole principle and I'm confused on ithttps://gyazo.com/39bfadc9fc49d7016e4f7c4d92cb3cea

What if he were to play 1 game everyday, then a_22 = a_1 + 21 and a_23 = a_2 + 21 and so on, then you can say that a_1, ..., a_77, a_1 + 21,...., a_77 + 21 is an integer between 1 and 89?

I don't think you'd be able to apply the pigeonhole principle then?

Does having multiple numbers from the sequence a_1 to a_77 equaling a_1 + 21 to a_77 + 21 affect whether or not you can apply the pigeonhole principle?

[gusty swallow]

where do you see php being applied?

And, no. Your first sentence is the same as the conclusion of the application. "If he were to play 1 game everyday, then a_22 = a_1+21"
So you have that he played 21 games on consecutive days from day 2 to day 22

[icy swift]

somewhere in the last part of the proof where he says there are 154 integers between 1 and 153 so there must be atleast 2 integers that are equal like a_i = a_j + 21

[gusty swallow]

ah, i see now.
Then you can still use pidgeon hole, you still have 154 numbers listed, that have values between 1 and 89 (88?), so some of them have to be the same.

[icy swift]

I see

Since 154 is still bigger than 88 which is the number of boxes in this case

[gusty swallow]

correct

[icy swift]

i have one more confusion which is the php "strong form" https://gyazo.com/d35fd462077ae8e9ea1ab5e0654397b8

I don't really understand the "- n + 1" part

is there an intuitive explanation for this theorem like there is with the "simple" form of php where if there are n+1 objects and n boxes there must be atleast 1 box with 2 objects

[gusty swallow]

That sum is just the number of objects being distributed.

But I think it comes from -(n-1), so theyre removing a ball for almost every box. If they just subtracted n, then I suspect this wouldn’t be true.

[dire stag]

Followed my notes for this exact same type of problem, and I honestly have no clue where I went wrong

C(7,7) = 1

[vestal bronze]

that's the answer

0.000046

[dire stag]

Thanks!

[agile magnet]

why did you say you have no idea where you went wrong?

[dire stag]

because my answwer was 4.6

on the calculator

[agile magnet]

do you know what the E-5 means?

it's scientific notation

[dire stag]

I forgot how to read scientific notation

[agile magnet]

Look it up then

[dire stag]

my bad, but thanks!

[plain totem]

This is a little puzzle which one of my classmates came up with
Consider the parallelepiped spanned by vectors (1,0,0), (0,1,0), and (a,b,c) where a,b,c are integers (c>0)
Try to prove that it can be partitioned into a total of 6c tetrahedra, all of them having vertices with integer coordinates

[quiet eagle]

I found this article, while studying Edmonds' branching algorithm. I believe there is a mistake, it should say |C-B| = 1. Is that right?

https://onlinelibrary.wiley.com/doi/10.1002/net.3230010305

[old peak]

yes i believe so

[quiet eagle]

ok ty

[distant otter]

Any tips on how to approach this problem?

Initial thoughts: Find at most 3 linear orderings whose intersection results in the original poset P. When constructing each linear ordering, keep track of the antichains (incomparable pairs within linear ordering) and make sure that the other linear orderings contain the same pair in reverse order so that their intersection contains neither pair.

[coral raven]

giving =< 3 orders explicitly would suffice

[distant otter]

Can any linear ordering be a part of the realizer or do I need to be careful about how I construct them so that I can derive the original poset from 3 of them?

[mighty ingot]

anyone knows how to do this

[quiet eagle]

Can you think of any not-surjective function?

[elfin furnace]

does this graph have any self-loops?

[elfin furnace]

How do I use the adjacency matrix here

[agile magnet]

what is the definition of a self-loop?

[agile magnet]

Do you know what the definition of the adjacency matrix is?

[elfin furnace]

a vertex with the same edge

[elfin furnace]

not really

[agile magnet]

wdym same edge

[elfin furnace]

i mean a vertex with the same edge that goes in and out of the vertex

[agile magnet]

You mean an edge with the same endpoints

[agile magnet]

Ok, so does this graph have any such edges?

[elfin furnace]

yeah if the head and the tail are the same

[elfin furnace]

no

was getting skeptical about my own knowledge of self loop cos i thought the graph was incomplete

[agile magnet]

wdym incomplete?

[elfin furnace]

if you look closely on vertex e it looks like the far right of vertex e is not fully printed

[agile magnet]

Oh

Nah it seems fine lol

I mean from what you can see in the pic there are no self loops

[agile magnet]

Look in your notes / textbook

If you're still confused come back and ping me why you're confused

But I want you to try first

[elfin furnace]

yeah i'm done studying linear algebra for now, when i get back to it after my next class i'll let you know

thanks

[brave rock]

Well it'll please you to know that despite there being a matrix here, nothing here asks you to understand them more than simply being a list of numbers. No linear algebra is being done.

[elfin furnace]

i mean the course

i'm taking linear algebra

wait

no nvm

this is discrete math

my bad

i'm taking both, and they both have matrices so i get them mixed up

[elfin furnace]

discrete math*

[agile magnet]

Both notions of matrices are the same

Just the adjacency matrix is defined in terms of the edges of a graph

[static briar]

Can someone explain why 5 is also right

Ion see how the function is surjective if a = 5

[brave rock]

Well, here's a hint: what happens when you do f twice when a = 5? Or more directly, what's 5 x 5 mod 6 (and why is that relevant)?

[static briar]

Who said ur allowed to use the function twice

[brave rock]

Me. I said you're allowed.

Do you need written permission?

[static briar]

Nah I’m asking like shouldn’t a function be bijective in only one go

Using it twice is foreign to me

To prove its bijextive

[brave rock]

Well think about it and see.

[static briar]

In that case u r right

I didn’t know in general u could show bijectivity by applying a function twice ngl

Seems like cheating

[twilit sundial]

in this case, you want something relatively prime to the modulus

since that's the condition for a modular multiplicative inverse to exist

[brave rock]

It's not.

[static briar]

I took an intro to proofs course and it was never mentioned once

[brave rock]

You can do anything you like to prove something as long as you don't make a logical error.

It is impossible to cover all the ways to prove things.

You seem to still think of math as an exercise in following a fixed recipe to solve a problem, when in fact you can be creative – and will eventually have to be – to solve problems.

[agile magnet]

ehhh I see what you're saying @static briar

Do you see know what 5 x 5 (mod 6) is?

Do you see how this correlates to computing f(f(x)) for a = 5?

And thus do you see why a = 5 means that f is a bijection?

[static briar]

0?

[agile magnet]

how did you get 0?

[static briar]

5/6 has no remainder

so 0

[agile magnet]

1: 5 (mod 6) = 5

it has remainder, 5

2: I asked about 5 x 5

[static briar]

mb im dumb

[agile magnet]

not 5

[static briar]

ohhh

so 25mod6?

[agile magnet]

yes

[static briar]

1

[agile magnet]

but there's a reason I wrote it as 5 x 5 and it connects to my second question here

[static briar]

kinda cause its the same as 1mod6 and 1 is for sure right

[agile magnet]

why is 1 right?

[static briar]

the fucntions just f(x) =x

[agile magnet]

which is clearly a bijection right?

[static briar]

ye

[agile magnet]

because it has an inverse, namely itself

[static briar]

ye

[agile magnet]

ok so 25 (mod 6) = 1

[static briar]

yes

[agile magnet]

this is the a = 5 case we are talking about

what is f(f(x))?

[static briar]

ye

[agile magnet]

for arbitrary x in Z_6

[static briar]

f(x) would be 5x

[agile magnet]

f(x) = 5x yes

[static briar]

then f(f(x)) would be 25x

[agile magnet]

but 25 = ? (mod 6)

[static briar]

1

[agile magnet]

so f(f(x)) = x right?

[static briar]

ok ye

[agile magnet]

so now explain to me why f is a bijection

[agile magnet]

what is the inverse of f?

[static briar]

f is injective and surjective

and uhh

the inverse is y = 1/5x

[agile magnet]

1/5 isn't an integer...

[static briar]

bro idk i just didnt knwo you could use the function twice ngl

[agile magnet]

but we've shown that the inverse of f is itself

so f has an inverse!

so f is a bijection!

[static briar]

ahh yee

[agile magnet]

that's what they were getting at here

[static briar]

goat

[agile magnet]

makes sense?

[static briar]

yeah

[odd prism]

I’m thinking pigeonhole

3 holes but I can’t think of how to partition

[compact owl]

How exactly does it go from the first highlighted part to the next?

[stray reef]

expand (1 + (-x))^-3 with the binomial thm.

[compact owl]

Ah I see

Thanks! @stray reef

[twilit sundial]

does the form of that expression remind you of a certain trigonometric expression you might know?

[odd prism]

Uh yes… I was shown it

[odd prism]

$\tan(a - b) = \frac{\tan(a) - \tan(b)}{1 + \tan(a)\tan(b)}$

[vital dew]

Alex

[odd prism]

Did not see it at first though

Would not have even thought about trig

Until my classmate showed me

[twilit sundial]

yea it can be kinda hard to see unless you already know the trick that it uses

[odd prism]

Some bs, I was spending hours thinking about remainders and multipels

Getting no where

[twilit sundial]

||in this case i think your "boxes" can just be the four quadrants||

[odd prism]

I believe it is the range of inverse tan

Cut at pi/4 and -pi/4

[twilit sundial]

oh right

yea

mb

[odd prism]

So first and fourth quad cut into 4 pieces

[twilit sundial]

yea sounds right

[odd prism]

Some bs

[odd prism]

How did you immediately notice it

Have you done the problem

Or are you just good with trig identities

[twilit sundial]

i've done a very similar problem

there's no way i would've seen it otherwise LOL

😭

[odd prism]

I’m lowkey pissed

It was such a hard problem goddamn

I wasn’t even thinking in the right realm

[crimson canopy]

I am having trouble understanding radius of a graph

Distance of graph is the shortest distance between 2 vertices.
Eccentricity is the greatest distance a vertex has.
Diameter is the largest eccentricity in the graph.

Then comes radius which is the minimum eccentricity.

Wait...hmmm...

I think i got it

Maybe

[jade tangle]

Man discrete math is ass

[fossil mural]

if you imagine you were dealing with a circle
the distance from the centre point to any other point is at most the radius of the circle, so the eccentricity of the centre point is the radius of the circle
for any other point, the point at the "opposite" side of the circle (draw a line through the point and the centre point until it hits the edge) will be more than the radius, so it will have an eccentricity of more than the radius

intuitively eccentricity is sort of the extent to which a point is out at the edges of the graph instead of being closer to the middle, so the points of minimum eccentricity are basically the centre, and then radius is "maximum distance from the centre point"

[wet flame]

any hints on what language this DFA describes in plain english? kinda just seems like a random assortment of a's and b's, not sure if its something more specific

[wet flame]

s0 is the initial state and {s1,s2} are end states (red doesnt mean anything)

[wind kraken]

difference between a's and b's is odd

[wet flame]

i think its also that it accepts odd length strings?

[wind kraken]

oh ya that's true

so a and b are really the same

[wet flame]

wdym by that

[wind kraken]

like you might as well glue s2 to s1, and s3 to s0

then a and b do the same thing at each state

[wet flame]

ahh

[wind kraken]

given a finite set X, and an alphabet Σ = {0, 1}, define the norm |-|: Σ* -> N_0 as taking the number of symbols a string is constructed with. a transition function (monoid homomorphism) δ: Σ* -> End(X) is transitive if for any pair x, y in X, there is some σ in Σ* such that δ(σ)(x) = y.

what transitive transition function m: Σ* -> End(X) minimizes

[vital dew]

quasi_semi_group

[wind kraken]

i probably used the wrong jargon for this. in other words, i have some finite amount of states, and i want a transitive transition function such that the average amount of time needed to get from a state to another is minimized

what i know so far: up to constant factor we can get |X|^2 log |X|, which is also optimal

[agile magnet]

don't just give away answers

[agile magnet]

in the future a good strategy would be first to compute some example strings that are and aren't in the language

[wind kraken]

i'm not convinced this is a good strategy though

[agile magnet]

it's a good starting point

yes of course examining structural properties is better

but 1: that comes with time seeing more and more DFAs and NFAs and 2: doesn't mean other strategies aren't valid

[wet flame]

i did do this, didnt realise they were all odd lengths 😭

[wet flame]

also what sort of structural properties?

[crimson canopy]

Thank you.

Yeah, my mistake was i forgot eccentricity of a point is the (shortest)distance between 1 point and another point furthest from it.

I was thinking distance between any 2 arbitrary points. Which is pretty much just 1.
That was my mistake.

I should like you said, think of it like a circle. Thank you.
Radius would be
Find distance between center and an "end" point.

[mild root]

can someone help in channel 28

[agile magnet]

I mean you see things like the arrows labeled a going back and forth, same with the b's, maybe look for cycles, etc

shortest paths from start to accept states

etc etc

It's sort of like integration: the more integral you see the more patterns you see

[quiet eagle]

Why is it not possible to find and delete negative weighted circuits in a graph in polynomial time?

[errant bear]

C is correct

your answer should be in the form
"f(A), f(B), f(C), f(D), f(E), f(F)"
so since you have already identified that f(F) = Y, f(C) = V, you have to fill in the rest:
"_, _, V, _, _, Y"

where f is your isomorphic function

does this answer your q, or were you asking for the process of identifying the mapping itself?

for this problemc that is a good way to go about it. i would personally just note that A doesn't have an isolated point, and B doesn't have an point with only 1 edge, therefore it must be C. but i would do a handwavy squint my eyes and rotate/move drag points around as a sanity check to verify that C can me shifted into lambda

if however, the graphs are complicated messes with no easy visual cues, you have to have an algorithmic approach

which I'm sure there are millions

I would use a traversal method

in this case, if we pretend there is no isolated point, in any of the graphs (lambda included), i would start with point C

why C? because it only has 1 edge

now we just travel along the graph and count edges at successive nodes

ehh, this isn't text friendly

okay. I would first try to "untangle" the original graph, if possible

then, for the candidate graphs, you can "trace" it out over the initial graph

you will probably have a few starting nodes to go check depending on the initial graph structure

yes this is what i was trying to describe (and failed)

yes, you can "drag" it out so it doesn't cross over the other edges

yes

nope

you can probably just google graph editor

err

that will give you plotting things

maybe graph edge node editor

also btw, you are/were, at least in the image

[errant bear]

looks good

[stray reef]

of course

[fossil mural]

B isn't a tree

think about what the difference is between a tree and a forest

[errant bear]

just adding as an aside, you should try not to become too reliant on a visualization software like this that you won't necessarily have for tests

you should get comfortable doing/vizualizing these untangling transformations in your head, or on paper

[calm chasm]

I am not following this. Why is having at least one y working for multiple x is stronger than having multiple x works for at least one y?

[brave rock]

If every kid in class has a pet, this does not mean that there is a single pet that every kid in class shares.

Forall kid, Exists pet, has(kid, pet) is the former statement.
Exists pet, Forall kid, has(kid, pet) is the latter statement.

[calm chasm]

I'm not getting why one is harder to defend? Or stronger

[sick grail]

in the former, each kid has a pet. in the latter, there is a single pet, which is the pet of every kid.

[calm chasm]

I did not see that at first.

Okay following

[sick grail]

so the latter is stronger, because going one way that single animal works to show each kid has a pet (not necessarily the same one)

but the other way doesn't work

this is what is meant by the "there is universal y ... might all be the universal y)" bit

[calm chasm]

I just can't see why that makes sense.

Why that would imply one is stronger

[sick grail]

because each kid having a pet doesn't mean they all have the same pet

[calm chasm]

I'm missing an important piece here

Like I know that already

Idk why that means it's stronger

Maybe I'm not asking the right question

[sick grail]

it's stronger because it implies the other, but not vice versa (I think it's being defined for you in this section)

so if it's true so is the 'weaker' statement

(which is true more often so says less, I think is the logic behind the naming)

[calm chasm]

OHHHH

I think I finally get that

Is it kinda like a set and the other is a subset?

[sick grail]

I don't see why that analogy would break down

so yeah

except the subset is the stronger statement

[calm chasm]

oh god

[sick grail]

you're being more precise

[calm chasm]

nvm then

I don't understand

[sick grail]

I do think it takes a while to get the language here

[calm chasm]

I thought the stronger proposition would be the set

[sick grail]

when you have a stronger statement, you know more than you would with the weaker statement

because the stronger statement implies the weaker statement, so you know at least as much

but the weaker statement does not (by definition) imply the stronger statement, so you know more

so e.g. being strictly increasing is a stronger statement than being increasing (for functions)

(or inceasing compared to nondecreasing, idk what terms you're used to)

there's 'more'* increasing functions than there are strictly increasing functions, because each strictly increasing function is also increasing but not vice versa

(*maybe technically not really but that's more with issues in defining quantity when you start getting infinite collections than what I feel the motivation for the language is)

because you know more, you also tend to get more / nicer results when you have stronger conditions e.g. continuing this example strictly increasing functions are injective/one-to-one, whereas increasing functions don't have to be

as a non mathematical example, "I will go to IKEA tomorrow" is a stronger statement than "I will go to a store this week"

[calm chasm]

This made it super clear

[weary tiger]

Can someone explain this to me

[stray reef]

do you know big sigma notation for summations

[weary tiger]

Yessss

[stray reef]

yeah, these are similar in spirit

only instead of adding you take unions or intersections, accordingly

[weary tiger]

Understood

[weary tiger]

Can I dm ya something?

[stray reef]

why do you want to dm it to me instead of asking on the server

[weary tiger]

Yeah that works too

[storm prism]

is there a way to concisely write 2 variables as a member of the same set?

ie {(x,y) | x, y E R } (ignore me using E and R I mean to say x and y are members of the set of all real numbers)

or do I have to state separately x E R and y E R or is there another concise way to do it?

rly wishing I could use latex right about now

[stray reef]

$x, y \in \bR$ is fine.

[vital dew]

Ann

[storm prism]

ah okay thanks

[crimson canopy]

Are there any patterns to degree sequences of simple graphs beyond sum of everything = 2| E |, where | E | is the number of edges?

Because i can have a bogus degree sequence and add them up, multiply by 2, but if we don't know the exact form of the graph, we can't tell

Only way is the havel hakimi method?

But that's assuming we know the entire degree sequence

I mean, i do know most of them, i just don't know the value of 1 term, except that it must be even

So e.g, i have 1, 2, 3, 4,...2023, n where n is some even number between 1 and 2023

Burrowing a different example:

Degree sequence: 6, 5, 4, 3, 3, 2, 1 is that of a simple connected graph.

Or at least that's what i submitted in my homework kekw.

From some...idk what you call them, theorem? Lemma? , the number of odd degrees must be even.
Make sense because sum of all degrees must be twice number of edges.
So sum od odd number of odd numbers = odd number = contradiction.

So there must be even number of odd vertices degrees

However, looking at the sequence, we have 1, 3, 5 and let's say 7.

7 does not work of course, because that would imply a loop, thus not simple graph.

If we were to replace 1 of the 3 with 1 or 5...the resultant sequence would not be simple too.

So, we know that there is some kind of sweet spot.
But i can't find any theorem about what that sweet spot is

Edit: let me test if i replace a few odd degree instead of 1 odd degree.

[crimson canopy]

Okay, messing around for a bit,

Suppose, we keep even numbers the same, counting multiplicity,
6, 5, 4, 3, 3, 2, 1 work
6, 4, 3, 3, 3, 2, 1 work
6, 5, 5, 4, 3, 3, 2 work
6, 5, 5, 4, 3, 2, 1 don't work
6, 5, 4, 3, 2, 1, 1 don't work
6, 4, 3, 2, 1, 1, 1 don't work
6, 4, 2, 1, 1, 1, 1 don't work
6, 5, 5, 4, 2, 1, 1 don't work
6, 5, 5, 5, 4, 2, 1 don't work.
6, 5, 5, 5, 5, 4, 2 work

So....it seems like the more 1s i have the more...likely its not going to work

6, 5, 5, 5, 4, 3, 2 work

So...it seems like the number of 1s has some impact on necessary number of 3s

6, 4, 3, 3, 3, 3, 2 work

6, 5, 4, 3, 3, 3, 2 work

Its just the 1s being shit

Maybe this is trying to tell me something. I don't understand what does the min refer to though

[agile magnet]

the minimum of d_i and k

[crimson canopy]

what is k?

why is it different from n?

i suppose it is saying

suppose we arrange the degrees in descending order

taking the sum of the 1st k terms, if the sum is less than k(k-1) + sum min(d_i, k) n-k times, the the sequence is graphical

[sonic shadow]

Is it true that $\sum_{i=0}^n{n \choose i} = 2^n$?

[vital dew]

dulg_n

[sonic shadow]

I mean, intuitively, it makes sense

[brave rock]

Yes this follows from the binomial theorem

[sonic shadow]

Ah ok!!

Tyy

[fossil mural]

or double counting: the number of subsets of n things is the same as the sum of (the number of subsets of size i) over all possible i

[agile magnet]

yes exactly

and the converse also holds

if the sequence is graphical

that inequality always holds

[crimson canopy]

thank you. but i don't understand what min(d_i, k) mean

so suppose i have 25 terms, and i take the sum of 1st 6 terms

so min(d_i, k) where k is 6, would be comparing which is smaller? 6 vs value of d_i?

seems...off, when i try to apply to my question above

[agile magnet]

min(d_i, k) would equal k if k < d_i and otherwise it would equal d_i

[dire stag]

How is 42 the answer to b???

wouldnt it be 39 x 2 + 1?

[twilit sundial]

no

then you would've long since drawn all the cards

consider the worst case scenario where

you draw all the clubs

all the diamonds

all the spades

39 cards drawn

then to guarantee three hearts

you would need to draw three more

42

[dire stag]

I got (6 x 5 x 4 ) x 4 - 4

But apparantly, the answer is 6!-4 x 3!

I dont know how, but I now know that I'm screwed, and that I won't pass discrete math with an A

I'm just too unintelligent

[agile magnet]

well the immediate issue here is that 39 x 2 + 1 > 52

[agile magnet]

how did you get this answer?

[dire stag]

3 spots are reserved

so 6 x 5 x 4

4 possible positions for bad

for every possible position ob bad, a new variation of 6 x 5 x 4 has to be calculated

[agile magnet]

idk how "3 spots reserved" gives 6 x 5 x 4

Can you elaborate on that?

[agile magnet]

ah so there's one issue

if you used the letters b, a, d

you don't have 6 choices for the remaining 3 slots

[dire stag]

Hmm

[agile magnet]

right?

[dire stag]

I guess so

[agile magnet]

because you already used those letters

so you have how many letters left for the first slot?

[dire stag]

3

[agile magnet]

second issue is this

right now it seems you are counting the number of words that include bad

you need to count the number of works that don't include bad

so take the total number of words and subtract the number of words that include bad

so now try the problem again with those 2 hints

[dire stag]

3 x 2 x 1 - 4

[agile magnet]

how did you get that?

I presume the 3 x 2 x 1 is from what we talked about before

where did the -4 come from?

[dire stag]

number of words that include bad

-4

subtract them out, and you get the number of words that dont contain the word bad

Sicne there's only 4 possible positions where bad can be placed

[grave sail]

hi, would this channel be approriate to talk about some time complexity for a data structure? im assuming most people here are in CS or at least familiar with big O.

[stray reef]

yeah

post your question

[grave sail]

I've implemented a stack using a singly-headed singly linked list. The top of the stack must be located at the END of the list. To achieve this my push() method is essentially LL_append() and my pop is LL_removeback(). Both functions traverse the list to get to the last node as there is no tail ptr. When analyzing the total time complexity to push N elements, and then pop those N elements I was intially thinking O(N), however some people in my class are suggesting O(N^2), due to the fact of summation of traversal for each time we push, which I think makes sense --- but i'm not entirely sure. TLDR: O(N) or O(N^2) total time for N pushes then pops

[little prism]

is the list empty before?

[grave sail]

yes

[little prism]

lets say N=10. how much would you have to do

[grave sail]

10 pushes, 10 pops?

[little prism]

how much traversing

[grave sail]

each time i push it has to traverse the length of the list to get to the last node

same with pop as its popping from back, and no tail ptr

[little prism]

yes so how much is that for N=10