discrete-math

[pale epoch]

and indicate where you are using hypo

[orchid widget]

ye np, will do on the test haha, this is just a quick practice problem that I stumbled across

thank you

[lyric quartz]

I got an exercse to find the order of groups of symmetries of the platonic solids, they haven't been mentioned in the book yet. Does someone have a hint to solve this non physically? I don't have any platonic solids laying around here...

Just looking at an image of a tetrahedron I can find rotations along the lines through a vertex and the middle point. And reflections along the planes through two rotational lines. But how do I know i have got them all?

Especially when looking at the icosahedron

[stray reef]

there is a trick

imagine a collection consisting of 3 objects:

• a vertex
• an edge having this vertex as one of its ends
• a face having this edge as one of its sides

you might call this a "flag"

[lyric quartz]

ah and i find the possible flags?

[stray reef]

cause if you highlight these on a diagram of the polyhedron it kinda sorta looks like one

sort of

yeah basically

any symmetry of the polyhedron takes flags to flags obviously

and in fact if you take a particular flag and look at where it goes under a symmetry

that will actually uniquely determine the symmetry in its entirety

[lyric quartz]

ok, so for the tetrahedron there are 4 vertices, each with 3 edges and 2 faces, so there are 24 symmetries?

And how would I show that these translations mappings? of flags are actual rigid motions, so only reflections and rotations?

[stray reef]

they're not translations

but like, you're looking at platonic solids

every flag is the same

[lyric quartz]

I didn't mean translation, guess i meant mappings or something

oh i meant transformations

[lyric quartz]

what about 4D? Because then the flags are also the same, but I guess looking at just flags isn't enough

So why is looking at flag enough for 3D and just looking at flag poles enough for 2D?

[stray reef]

4D... you'd need flags to include cells as well

basically they would go up to the highest-dimensional facet

[lyric quartz]

ok

[stray reef]

i dont have any fully formal justification for this

[lyric quartz]

Thank you Ann, I have identified 8 trivial rotations of order 3, 3 of order 2, the identity of order 1, and 6 reflections of order 2. What other symmetries am I missing?

Is this just brute force or is there any "abstract" way to find this out? Because how are you going to do this for higher dimensions?

[stray reef]

dunno of anything better tbh

[lyric quartz]

ok 🙂

[lyric quartz]

I found a combination with order 4, so I guess I found a new one

[upbeat ruin]

I'm making a adjacency matrix for this one, and I'm multiplying them together, but I'm stuck on how to multiply a A^4 and A.

[lyric quartz]

A^5?

[opal crescent]

what's the issue here ?

[upbeat ruin]

Yeah

Im trying to find A^5

[opal crescent]

ok yes

yeah I'm still not sure what your problem is

like you got A^4 somehow right ?

[upbeat ruin]

Yeah

Here I'll take a pic of what I've done

[fossil mural]

,rccw

[upbeat ruin]

Ty

[opal crescent]

well you know how to multiply two matrices, your results seem correct for A^2 and A^4

so what's special about A^5 for you ?

[upbeat ruin]

Well before I was multiplying two of the same matrix

But don't I have to, now, multiply A4 and A together

[opal crescent]

yes

the way of computing the multiplication doesn't change

whatever matrices you may have to multiply

[upbeat ruin]

Right but usually you multiply a row by a column

So do I multiply a4s row by a's column

[opal crescent]

you can do A^4 * A or A * A^4

the result will be the same

[upbeat ruin]

Ohhh right

Makes sense, didn't realize that

[lyric quartz]

Matrix multiplication is not commutative in general

But it is associative

[upbeat ruin]

Well thank you for your time. I might be in here again because my final exam for discrete is this sunday lmao

Thank you

[opal crescent]

final on sunday wtf

[upbeat ruin]

Its online

[opal crescent]

ah ok ^^

[upbeat ruin]

And technically its not a final, its just the last exam

So 👍

[lyric quartz]

What I learned when I got to know about matrix multiplication is to write both matrices next to each other with the second moved up. Then every cell is the sum of the left row times the right column

[upbeat ruin]

Oh alright

Yeah I'm doin the question right now so I'll see if i get it right

[upbeat ruin]

Yeah

Weirdly enough my calculation says that that way gives me a 67, but doing it the opposite (left column * right row) gives me 69

[lyric quartz]

probably a calculation mistake?

[upbeat ruin]

Yeah probablyyyy

Yeah it was

I got it right so Im good to go

[lyric quartz]

If you want to get an intuitive way on what a matrix multiplication is; I liked this video https://www.youtube.com/watch?v=XkY2DOUCWMU

[upbeat ruin]

Seems pretty interesting tbh tho I'm not the biggest math guy

I think one of my biggest gripes while learning this was how long it took to make a matrix

[lyric quartz]

It's an entry video series into linear algebra. I like how he shows the meaning behind it pretty concisely.

[upbeat ruin]

If its linear algebra I may need it later on then

Ima get goin now, thank yall for help

[lyric quartz]

good luck

[elfin furnace]

Is this how to correctly use de Morgan’s to simplify this expression

[agile magnet]

You're really close but there is a big mistake. Note that $\overline{\overline{x}y + z} \neq \overline{\overline{x}} + \overline{y}\overline{z}$. It would help if you used some parentheses to see that $\overline{(\overline{x}y) + z} = (\overline{\overline{x}y})\overline{z}$ and simplify from there (remember your distribution laws!)

[vital dew]

Spamakin🎷

[agile magnet]

but overall you seem to have the right idea, just a mistake

[half bane]

if f:N->N holds that for all even n f(n)<f(n+1) and for all odd n f(n)>f(n+1) prove that f(1)!=1 (note that we assume that 0 is a natural number)
tbh I dont even know how to solve it, I think for that to hold f must be one to one. but the exercise didn't say that.

[ivory badge]

what if we just alternated like, 2, 3, 2, 3, ….

[half bane]

we can also have 0, 1, 0, 1, ...

and here f(1)=1

[ivory badge]

Right?

I dunno

Are you sure you have the whole exercise

[stray reef]

hold on

!xy

[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]

i think you're missing some condition here

[half bane]

its in a different language but i will translate it

f:N->N is called zigzag if for all even n f(n)<f(n+1) and for all odd n f(n)>f(n+1).
prove that f(1)!=1

[stray reef]

what language

[half bane]

i think they have an error in the exercise

hebrew

[stray reef]

ok nevermind

[half bane]

xd

[stray reef]

so it says nothing else except that?

[half bane]

yes

[stray reef]

and 0 ∈ N?

[half bane]

ye

[stray reef]

then yeah 0, 1, 0, 1, 0, 1, ... is a CE...

[half bane]

i think the question should either have f is one to one

or

they want us to show that f(1)=1 doesnt always hold

[umbral mesa]

can someone explain why the answer is existential instantiation:

[ancient ermine]

If anyone is free to help with a very quick question about a generating function I opened a ticket at #help-12

[ruby bough]

hello

can anyone help with this

[near kiln]

So what I understand is that the cartesian product of A itself is n squared, and to get all subsets of a set (using powerset), it is 2 to the power of n. Since it asked for a subset of a relation, which is a subset of the cartesian product of AxA (for example), it needs to get the power set of the relation, which is simplified as 2n squared. (Am I correct?)

[ruby bough]

to be completly honest i have skipped most classes of this course so your words are like a completly different languange to me lol

[weary tiger]

i think he means replace the n with any number in the first and last one

f(2)=positive or negative 2

[ruby bough]

i checked on gpt and co pilot and they said that it is not a valid function

[weary tiger]

@forest bear am i correct?

[ruby bough]

so if there is a +- sybmol after the equal that means that it isnt a function same thing with the last one coz it is asking for any interger greater than n and since we dont know what n is it cant be a function?

i looked at the question again and guessed that since they all dont have n

[ruby bough]

i).
is not a function since it returns two items
ii).
it is a function since it returns one item
iii).
it is a function since it returns one item
iv).
it is not a function since it returns an unkown item

is this solution correct?

not the tiniest bit of a clue

again no idea i have skipped most of the classes to discrete math

not to fk around but coz i was at work

i just need some quick answers coz i need to submit the file in a couple of hours

[weary tiger]

-4 right?

[ruby bough]

but i really appreciate your effort in helping me understand

[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.

[ruby bough]

the answer is not an integer?

[weary tiger]

damn im incorrect then

either way tryna help

[faint umbra]

given non negative integers $k>0, n_i$ where $i\in I$ is a finite indexing, with $\sum_I n_i = k$ are there any nice results / simplifications to compute $\sum_I \binom{k}{n_i}$? i did a stupid

[vital dew]

chebyshev's infinite pee norm

[faint umbra]

I'm writing a program and I'm wondering if I can reduce the amount of 1) computations of binomial coefficients or 2) reduce the space complexity from k^2 from having to memoize

[lyric quartz]

In a book on abstract algebra, there is an exercise to prove there are no nonzero integers such that a^2 + b^2 = 3c^2 and it gives a hint to look at Z/4Z. But uh can someone hint on why (and how) I can use that hint? 😛

[faint umbra]

sorry this should be to compute $\prod_I \binom{k}{n_i}$

[vital dew]

chebyshev's infinite pee norm

[fossil mural]

there's a homomorphism from Z to Z/4Z

[lyric quartz]

Thank you, I don't understand where to go but I will try

[mental pecan]

For a little bigger hint: if there were integers satisfying that equation, they would still satisfy it after reducing mod 4. This makes your search space much smaller

[lyric quartz]

But isn't Z/nZ only closed for addition? And why the mod 4 and not some other modulo?

[fossil mural]

no, Z/nZ has multiplication too

you might be thinking of the fact that it doesn't have division unless n is prime? so for instance 2 * 2 = 0 mod 4, so there's no multiplicative inverse of 2 mod 4

[lyric quartz]

I thought all classes had to be coprime to n for multiplication to be closed

Oh wait Z/nZ has a well defined multiplication but does not have inverses for multiplication

[stray reef]

does not always* have inverses for multiplication

[lyric quartz]

That's what I meant ;p

Well, it never has an inverse for [0]_n

[mental mirage]

man why do ppl say things like Z/4Z here rather than simple mod 4 just makes simple things look scarier -_-

anyways

use fermarts infinite descent method

4|a^2+b^2+c^2

this forces a=b=c=0(mod 2)[just check this]

Let (a_1,b_1,c_1) be one solution which minimizes |a_1|+|b_1|+|c_1|

we know (a_1/2,b_1/2,c_1/2) also works

contradiction

or if u know that all prime factors of a number of form a^2+b^2 where (a,b)=1 are of 4k+1

u use that to directly end the prob

[lyric quartz]

This was only a small paragraph about the cyclic group Z/nZ. Not that many theorems.

[mental mirage]

i didnt use any theorom except simple modulo arethmetic

;-;

u can even do mod 3 and finish it

[lyric quartz]

Well I don't know Fermat's infinite descent method

[mental mirage]

its really a tehcnique

u dont need to

[mental mirage]

this idea basically

[lyric quartz]

Ok thank you

[near kiln]

f1(x) = x² + 3x + 5
f2(x) = x - x²

What's (f1 • f2)(x)?

[stray reef]

well, do you know what it means to multiply two functions together?

[near kiln]

x(x²) + x(3x) + x(5) -x²(x²) + -x²(3x) + x²(5) ?

[near kiln]

I think so

[stray reef]

task failed successfully

[near kiln]

teach me pls

[stray reef]

you have answered way more than i asked and you did it in a deliberately complicated, "DO 100 THINGS AT ONCE INSTEAD OF 1" way

what i wanted to hear was:

multiplying two functions means multiplying their values at every point.

i.e. $(f_1 \cdot f_2)(x) = f_1(x) \cdot f_2(x)$.

[vital dew]

|Ann⟩

[stray reef]

you posted a worked solution earlier, and you said all of it confused you. this step was one of them.

therefore you also said this step confused you.

yet now the confusion has evaporated...

[near kiln]

What does it mean?

[stray reef]

what does what mean

[near kiln]

how do I multiply their values at every point? also what is the does "values" mean in this sentence?

[stray reef]

value means output

and if you notice

RIGHT BELOW that message, i wrote down what it means symbolically

$(f_1 \cdot f_2)(x) = f_1(x) \cdot f_2(x)$

[vital dew]

|Ann⟩

[stray reef]

i can repeat myself 17 more times if you didn't read it the first time

[weary tiger]

the little x after means that it's taking x as input just as if the whole thing were one function

if that's what you're confused about idk

[near kiln]

So I have to get the value of f1 and f2 first?

[weary tiger]

chad username btw

[near kiln]

thanks

[weary tiger]

yeah if the exercise gives you f_1 and f_2 just multiply them i guess, i'm not sure what the exercise asks

not sure sometimes dot is multiplication

[near kiln]

yeah, it said "product"

[stray reef]

i'm a she.

[weary tiger]

i've definitely seen dot for composition but not for multiplication

[stray reef]

please edit your message.

@weary tiger please edit your message so it no longer misgenders me.

@weary tiger bit scummy to outright delete your msg instead of owning up to & correcting your mistake, hm?

[near kiln]

I figure it out, I lack understanding in foil method

[lyric quartz]

I thought about my question from earlier for a while and I think I understand it now. I have finished the exercise.

[icy saffron]

Great.

[lyric quartz]

Am I allowed to mix congruence classes like this?

[terse wyvern]

you are not mixing congruence classes, the congruence class for the exponent is different from the congruence class of the base

[coral parcel]

(By the way, you can use Euler's theorem to see that 7^4==1 (mod 10) without going through the actual calculation -- that is useful when the modulus is larger than in this example).

[lyric quartz]

I got another exercise, i think, that touches Eulers Phi function

[plain shoal]

hello guys, i have discrete math exam in two weeks and i need a YouTube playlist or a website that i can read of it, with all the concepts explained in a good way, is there anyone that can recommend something

[lyric quartz]

What literature did your lecturer advise you to read?

And how should we know the subjects that you are tested on?

[little prism]

discrete math is such a big topic that a lot of courses on it may be very different. read through your own course notes

[weary tiger]

Simple graph with 5 vertices of degrees 1,1,1,2 and 3

Is this correct??

[brave rock]

That is a simple graph with the description you gave, yes

[weary tiger]

Thanks

[lyric quartz]

ah right, since 7 is coprime to 10, [7]_10 is in (Z/10Z)*. Wait is (Z/nZ)* always cyclic? (searching...) Apparently not but it is for n = p^k or n = 2p^k for oddsome prime p.

[pale monolith]

Only for odd prime p

And 1,2,4

[lyric quartz]

Thank you

[coral parcel]

It doesn't need to be cyclic here; Lagrange's theorem is enough to tell us the order of every element divides phi(n).

[lyric quartz]

oh right, but I haven't seen Lagrange's theorem yet in the book

[analog tinsel]

hey everyone !

Just wanted to reassure myself. It has been quite some time since I last was in touch with big O notation. I didnt find any clear examples online and didnt wanna read throught a bigger chapter on this in some books.
The following is correct, right ?

$n^2 / 4 \in \Omega(n^2)$

Thanks in advance!

[vital dew]

barış

[analog tinsel]

So in general I am not 100% sure if something that is in the order of n^k , like a fraction of n^k , is in Omega of (n^k)

afaik this should be true, since there exists a nonnegative constant c , namely 1/4, that causes n^2/4 to grow at least as fast as c * n^2 , for all n

[coral parcel]

Correct.

[analog tinsel]

Thank you very much!

[mental hull]

Can anyone confirm this identity? A friend of mine and I discovered it and are trying to double check it’s validity

Or whether it’s some identity Euler discovered back in the day or something

[viral crown]

$$(x+1)^n = \sum_{i=0}^n \binom{n}{i} x^i$$
$$x\to k-1$$
$$k^n=\sum_{i=0}^n \binom{n}{i} (k-1)^i$$

[vital dew]

valley

[viral crown]

binomial thm!

[mental hull]

It’s an extension of this problem I did, 99% sure it’s true but I’m curious as to if it’s a known identity

[mint folio]

yes it is a different way to show the binomial theorem

[mint folio]

as shown here the common version is on top and yours is on bottom

Good job on redeveloping it though that's always fun to do

[stray reef]

$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k} b^k$

[vital dew]

|Ann⟩

[mental hull]

Didn’t connect the dots between this and the binomial theorem

Very cool tho

[odd heart]

Good times

[dusk bramble]

i prefer ncr over the brackets

[stray reef]

to each their own but your taste is bad

[dusk bramble]

ahhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

[quaint verge]

could someone plz breakdown that fat equation for me

[dusk bramble]

if like

u have to choose 3 people out of a group of 9

9C3 it is

[quaint verge]

ohh okay thanks i get that bit

but then the rest?

[quaint verge]

yeah that makes sense

[dusk bramble]

uhat rest?

[stray reef]

are you ok with it being broken down in a more visually comprehensible manner

as in not with that road thing but something else

[quaint verge]

i mean sure whatever works works

[quaint verge]

like past the equals

[stray reef]

ok right so

[dusk bramble]

thats the formula

if u are familar'th permutation

u'd get it

[stray reef]

you're not helping

[dusk bramble]

or else

learn it

it can be easily derivated too

but that takes too mucb brain

[dusk bramble]

https://tenor.com/view/spongebob-crying-spunchbop-gary-sad-gif-23822800

[stray reef]

@quaint verge ok so first off are you familiar with factorials from a combinatorial pov

[dusk bramble]

sanskar?

yo

he indian

let me do the talking

[quaint verge]

yeah

to an extent

[quaint verge]

what does that even mean bruh

[stray reef]

@dusk bramble you are literally saying "if you knew this you would get it". that's literally the most unhelpful thing possible to say to someone asking for an explanation

[dusk bramble]

@quaint verge jee?

[dusk bramble]

alrigt

algirh

alright

[quaint verge]

yeah basically called me dumb wow :/

[dusk bramble]

nah

im tellling what u need

[stray reef]

ok alright so

[dusk bramble]

didnt neccesaarily said that

[stray reef]

@dusk bramble can i deliver my explanation w/o interruptions from you please

[dusk bramble]

go on

[stray reef]

ok alright

[fossil mural]

"i'm trying to understand this thing"
"alright then, so what you need is to understand this thing"
not helpful

[dusk bramble]

@quaint verge are u in 11

[quaint verge]

oh my days

i appreictae you high but Ann's helping me out🙏

[dusk bramble]

👍

[stray reef]

so let's imagine that we want to count the possible arrangements of, say, 4 red balls and 11 black balls (for a total of 15) in a row

where balls of the same color are indistinguishable

you ok with this setup?

[quaint verge]

alright sure

yep

following

[stray reef]

now if the balls were all different from each other, we would have 15! different arrangements, yes?

[quaint verge]

yeah got that

[stray reef]

right

but then look at the 4 red balls

[quaint verge]

wait wouldnt it be 15!/4!11!?

[stray reef]

yes it would, and that is what i was building up to.

[dusk bramble]

i lost my sons car

[stray reef]

what part of "no interruption" was unclear

[quaint verge]

oh right yeah i got that bit but the giant equation threw me off like crazy

[dusk bramble]

alright

[stray reef]

well the thing is we are still essentially doing the "arrange shit in a row" thing

only now there's k things of one type and n-k things of another, for a total of n

it's the same logic

[quaint verge]

OHHHHHHH

so

wait

for this example itd be 15C4 or 15C11

so if it was 15C4 = 15!/4!(15-4)!

holy shit i got it

that was way simpler than i thought

thanks for the help!

[dusk bramble]

bro

[quaint verge]

chilllll im slow but when it clicks it clicks

[dusk bramble]

i didnt knoe u asked that

[quaint verge]

and idk what happened to your sons car but ive got nothing to do with it🙅‍♂️

[stray reef]

...

[dusk bramble]

ok sons car

[quaint verge]

really appreciate you Ann🙏

[stray reef]

you're welcome

[weary tiger]

Is there a formula to find the total no. of subgraphs w/o actually drawing them ?

[coarse zodiac]

am i good?

[rare scaffold]

2^n

[urban girder]

Suppose I give you a string of numbers recursively as follows:

a_1 = 1

a_n = a_{n -1} n a_{n - 1}.

i.e. a_2 = 121

a_3 = 1213121

If a_n has size k, how many unique letters are in a_n?

I claim its O(loglogk). Is this true?

[hollow viper]

How does one generally prove a set is uncountable?

[fossil mural]

...that's way too vague, that's basically the same as asking "in general how do you prove things"

i guess two obvious things you can do are assume it's countable and then somehow derive a contradiction, or find an injection into it from some other uncountable set

[hollow viper]

Thanks

[pearl ermine]

hello, I am having trouble in understanding in why does 41 mod 3 give me the number of crates that I can stack whose height are 4 feet, it says 41 mod 3 gives 2 which somehow gives the number of crates whose height are 4 feet, and also 3 feet and 6 feet crates have the same divisor (3) so we do 41 mod 3, i am confused at this portion. Can someone kindly help explaining it?

[meager prawn]

you want the sum to be 41
That implies it must also be equal to 41 when taken mod 3
But it's 3x+4z+6y, so mod 3 that just gives 4z because 3x=6y=0 mod 3
Hence 4z = 41 = 2 mod 3, but 4z = z so z = 2 mod 3

[pearl ermine]

no need to explain the derivation of the equations, i have already understood how they are derived beforehand, but i am still confused about the implication of 41 mod 3 here, why mod 3? why not 41 mod 4 or 41 mod 6? and why does the remainder give the me the number of crates that I can stack whose height are 4 feet? a bit of depth would help.

[meager prawn]

3 and 6 have 3 as a common divisor, which does not divide 4
So this lets you find information because it gives you a simpler equality that is not trivial

[pearl ermine]

im sorry but the explnantion did not help, i wanted to know why does the divisibility matter in this case? why not 41 mod 4 or 41 mod 6? and why does the remainder give the me the number of crates that I can stack whose height are 4 feet? ? your answer touched none of those sadly.

[meager prawn]

mod 3 specifically because out of 3x, 4z, 6y, 2 of them are 0 mod 3 so that lets you extract information easily
Doing mod 4 or mod 6 only makes one value vanish, not 2, so it's not as efficient to get information

[meager prawn]

the reaminder gives it to you because, again
The sum mod 3 reduces to 4z, but 4 = 1 mod 3 so 4z = z mod 3
So z = 41 = 2 mod 3, hence z in {2, 5, 8}

[pearl ermine]

please, your answer doesnt meet the criterion i provided, doing mod 4 or mod 6 only makes no value vanish 41 mod 4 is 1 and 41 mod 6 is 5, and why is it supposed to be 2, u seem to not understand my question, i can clearly see with my eyes that it is 2, but the solution doesnt provide any significant reasoning behind its claims, and the variables x y z are introduced later and its the 2nd time im clarifying that explanations pertaining to those variables need not be explained, i am aware of their origins, the solution itself answers in terms of 3 4 and 6, not other fancy variables with them. Please read the question carefully bfore answering.

[meager prawn]

"the variables x y z are introduced later"
Yes but it's clear you're trying to count the number of solutions to 3x+4y+6z = 41 so you can introduce them earlier to see why this is done.

Then mod 3 is natural since it's what eliminates the most things so it's the easiest information to access
Then it's just a bit of bruteforcing

afaik the only things you're confused about are why we're looking at it mod 3 specifically, and why it gives the number of 4ft crates
The first I've already explained as being the number that intuitvively maximizes how easily you can extract information from the reduction
The second comes from just phrasing the question as a math problem rather than a word problem

If it's not that then yeah, I don't see what precisely your question is since you're asking so many things it becomes unclear for which things you've said "yeah I know that that's clear" and for which you've said "I don't understand that"
Especially when you drop a 6 line sentence and expect it to clarify things

[pearl ermine]

@meager prawn "The first I've already explained as being the number that intuitvively maximizes how easily you can extract information from the reduction" -> can u kindly explain this statement for me? what this long abstract sentence means? an example will definitely help if u dont mind.

[meager prawn]

mod 3 gives you very concrete information in the form z=2 mod 3
if you look mod 4, you get 3x+2y = 1 mod 4, which is harder to make use of
mod 6 you get 3x+4z = 5 mod 6 which is also harder to use, because these are 2 variable equalities
And besides mod 2, any other value would yield a 3-variable equality which isn't exactly useful to narrow down the space of potential solution

[pearl ermine]

41 mod 4 gives 1 and 41 mod 6 gives 5, not 3x + 2y, so how wont that help? they are both producing numbers after all at the end of the day.

i am trying my best to understand here

[meager prawn]

you obtain a constraint on your potential solutions (x, y, z) : 3x+2y = 1 mod 4
How helpful is it to more easily find the set of solutions? Not that much
It's something, sure, but it's not as practical as the much simpler z=2 mod 3

[pearl ermine]

no offense but what u said here completely wen over my mind, i am a beginner trying my best to understand so kindly bear with me.

[meager prawn]

4=1 mod 3

[drifting quiver]

hi guys

Anyone good at discrete math?

[meager prawn]

for each number n, you can consider your equation 3x+4z+6y = 41 and looking at it mod n
it gives you some information, like
x=1 mod 2
z = 2 mod 3
3x+2y = 1 mod 4
3x+4z = 5 mod 6
etc
From a practical point of view, to help determine the solutions, this is useful to narrow down the search space. hence the first 2 are useful because they tell you something very concrete, "x is odd", "z is 2 more than a multiple of 3"
The last 2 are hard to use because, for example 3x+2y = 1 mod 4
Even for a fixed x, what do you get? 2y = 1-3x = 1+x mod 4? That's not giving you much, besides x = 1 mod 2, and then you can get some information about y for a fixed x. But that's unwieldy

[pearl ermine]

i still dotn understand how is 41 mod 3 supposed to give me the number of crates that I can stack whose height are 4 feet and why would i choose 41 mod 4 over 41 mod 6, please ignore any references to equations or quantities like 3x 4y or 6z, im asking you to do so, because the intial lines of the answer do not address any such claim. They come later on.yet they somehow explain why they took the path, but im unable to grasp their explanantion.

think of the solution like this

ignoring the rest

[meager prawn]

They just say "number of 4 crates" rather than z
They just claim "so" it will be 41 mod 3
They don't explain it because they hold it to be obvious
Proving it would require going into the details

[pearl ermine]

ok simply explain to me from the question how: "the number of 4 crates must be congruent to 41 mod 3, (which is basicvally the same as 2 mod 3)" how did they discover this so randomly? that would do (if possible) some help

[meager prawn]

it's not random
it's what I'm saying
They expect (at least that's my understanding of it) the underlying reasoning to be obvious for the reader so they skip over it, because pointing out the divisibility relations is enough for them to deem it explained

Remember that a proof need not, and often should not, look the same as what you write when working it out
That doesn't mean this is a good proof
But that means you shouldn't expect to find the same order in it

[pearl ermine]

"They expect (at least that's my understanding of it) the underlying reasoning to be obvious for the reader so they skip over it, because pointing out the divisibility relations is enough for them to deem it explained" - Im unaware of this relation and have been questioning all throughout to understand the mechanics of it for so long, and this seems to be the problem, can you kindly explain it to me?

[meager prawn]

3 divides 3 and 6
"Divisibility relation"

[meager prawn]

hence 0=3=6 mod 3 and the equality 3x+4z+6y = 41 reduces to 4z = 41 mod 3

[pearl ermine]

bro this is wonderfully articulated, the type of explanation that i was looking for all this while, gave me a lot more insight into the solution, thanks, just a small cherry on the cake is absent - 41 mod 3 (which is similar to 2 mod 3) -> how does it indicate number 4 feet crates here, how doesn't it indicate 3 feet or 6 feet crates?

@forest bear

[meager prawn]

oh well that face explains a lot of things

[pearl ermine]

wow, and the reason why we keep took 2,5, and 8 is because they gave the same output remainder, so that is why it is x, x+3, and x+6 but we dnt go beyond x + 6 because it told us that it number of crates has to be less than 10? am i right?

[viral crown]

[meager prawn]

I for instance, came in assuming you had better foundations regarding modular arithmetic and understood the idea of the solution

oh that's neat

[pearl ermine]

i was already aware of the derivations of these equations just the way u described just now, but didnt know that derivation of 41 mod 3 or 2 mod 3 would arise from these very equations themselves, the confusion arose from the explanation of 41 mod 3 at the start, and i mistook it for something else, neither did they display it like u did. I thank you sincerely for bearing with me for so long and your efforts in uprooting this confusion.

sure

[pearl ermine]

@pure trench hey one last question, would be still getting valid outcome (e.g. number of 3 feet or 4 feet or 6 feet crates) if we did mod 4 or mod 6 instead of mod 3 (referring to your lengthy answer with detailed explanation)

[meager prawn]

that's what I was explaining around this time

[pearl ermine]

ah so using mod 4 and mod 6 provides valid output, but since they are mired with other expressions like 3x+2y = 1 mod 4
3x+4z = 5 mod 6? so its difficult to make anything meaningful out of them? right?

but one of them like x=1 mod 2 still works just fineif i am not wrong

so any "mod n" would work provided they dont giver any mixed expression as their output right?

cool cool so any "mod n" with the equation 3x + 6y + 4z = 41 would work provided they don't give any mixed expression as their output right (like 3x+2y = 1 mod 4
3x+4z = 5 mod 6)?

[lyric quartz]

I am a little stuck. Using Bézout's identity for coprimes how do I go from ax + by = 1 to kx + l 2y = 1 if x is odd?

[brave rock]

Who says this is true? It seems you are missing some context.

I certainly don't understand the statement

[lyric quartz]

Of gcd(a,b) = 1 and a is odd then gcd(a,2b) = 1 right?

[brave rock]

Yes

[lyric quartz]

Can I show that with Bézout's identity?

[brave rock]

You can

Let me give you a hint.

Let a = 2n + 1 and suppose xa + yb = 1.

Now 2nxa + 2nyb = 2n

So what can you add to this to have this sum be 1?

You should be able to take it from here. Maybe even try to make the sum -1 instead of 1.

Rearrange and be satisfied.

[lyric quartz]

Ah cool, thank you. Let me try to write it out. My a and b aren't simple variables, but I guess I can just substitute

[brave rock]

You have called them a and b so I have called them a and b.

[lyric quartz]

Yeah thanks, I didn't want to make the question that specific, I will try it out 🙂

Well wasn't that more specific
a(2m + n) + bn = 1 and with n is odd.

[lyric quartz]

Had to take a break. But essentially it was multiply the whole equation with something odd + 1 and then subtract the odd thing. It worked, now i need to simply my equation... or just \box

[true iris]

hi someone can just see if i can do this exercise :translation= Justify this equation

i want to begin with geometric sum formula

[uneven violet]

Yeah, geometric sum formula could be good. Then what?

Here's a hint: Show that the polynomial on the left-hand side has the same roots as the polynomial on the right-hand side.

[true iris]

i now that z^n=1 give e^2ikpi/n for all k in Z

i dont now what to do after this

or we assume that z= e^2ikpi/n all k in Z

this is from z^n=1 give z=e^2ikpi/n so z-e^2ikpi/n=0

[frigid hazel]

This is trivial as u implement z as r•Exp[i•θ] in polar coordinate system.

[true iris]

you can explain more because i don't have the idea in my mind

[uneven violet]

What about my suggestion of proving that the two polynomials have the same roots? The polynomial on the RHS has the n-1 roots e^(2ilpi/n) for l = 1, ..., n-1. If the polynomial on the LHS has the same roots, then since they both have the same leading coefficient, then they are the same polynomial.

Let $P(z) = \sum_{k=0}^{n-1} z^k$. You need to prove that $P(e^{2il\pi/n}) = 0$ for all $l = 1, \ldots, n-1$. For this purpose, try using the geometric sum formula, i.e. $P(z) = \frac{1-z^n}{1-z}$ (for $z\neq 1$).

[vital dew]

OneTrackPony

[true iris]

so to prove that is equal to 0

[uneven violet]

Yeah, for z = e^(2ilpi/n), you want P(z) = 0.

[true iris]

but just how do you now that "The polynomial on the RHS has the n-1 roots e^(2ilpi/n) for l = 1, ..., n-1."

because of this "this is from z^n=1 give z=e^2ikpi/n so z-e^2ikpi/n=0"?

[uneven violet]

When a polynomial appears in factored form, it's easy to see its roots. For instance, the polynomial (z-a)(z-b)(z-c) has the three roots a, b, and c.

The polynomial on the RHS is precisely a product like this

[true iris]

ahhhh yeaahh

you are right ,thank you for help me

[uneven violet]

you're welcome

[pearl ermine]

can comebody help me explaining this? how?

[stray reef]

find two sets of 5 numbers from this set, A and B, such that:

• the product of A = the product of B
• the sum of A is even while the sum of B is odd

maybe 6*2 = 4*3 might be relevant!

[pearl ermine]

can u explain me this magic? they did something like 1 * 2 * 3 * 4 * 5 * 6 * 7/12 with poor explanantion of how

[stray reef]

wym? what magic?

[pearl ermine]

this is the solution i don tunderstand how

[coral parcel]

The 12 in the denominator is either 3·4 or 2·6.

[stray reef]

1. Providing the product of the chosen numbers is equivalent to telling the product of the unchosen numbers.
2. The only possible products that are achieved by more than one pair of numbers are 12 (as 3*4 or 2*6) and 6 (as 1*6 or 2*3).
3. But in the second case, the sum of the two (unchosen) numbers is odd...
4. (...and so the five chosen numbers have odd sum too.)
5. Therefore, the first must hold, and the product of the five chosen numbers is equal to 7!/12 = 420.

@pearl ermine can you name the earliest step that confuses you?

[pearl ermine]

all 5 to be honest but lets start withb the first one -"Providing the product of the chosen numbers is equivalent to telling the product of the unchosen numbers." the question doesnt state whether zack told his product to Claudia, so how would this help?

[coral parcel]

The question does state what the result would be IF he told the product.

The goal is not for Claudia to find out the product, but for us, the readers to do so.

[stray reef]

he still did choose a set of 5 numbers and that set has a product

[pearl ermine]

yes but how does that help? the question doesnt say that he told any of his products to caludia. how is claudia then supposed to figure the product out, i guess by subtracting each possible the product of combination of 2 set integers, she can dedeuct it from the total to get all the possible products, thats it.

it doesnt do anything more

[stray reef]

i think you are confusing yourself here

what if the problem instead said

"Zack told the product of his set to Claudia. Claudia then said, 'I cannot deduce from this info if the sum of your set is even or odd.' What is the product of Zack's set?"

[pearl ermine]

"Providing the product of the chosen numbers is equivalent to telling the product of the unchosen numbers." -> can u give me an example how?

[stray reef]

the product of the chosen numbers, times the product of the unchosen numbers, is always 7! (i.e. 1*2*3*4*5*6*7). so either product can be found by dividing 7! by the other one

so for example "The product of the chosen numbers is 504" and "The product of the unchosen numbers is 10" can be derived from each other

this is simple so don't overthink it

btw why do you have literally every single pronoun role

[pearl ermine]

i identify as all of them

[tawny mist]

Please help with these questions

[pearl ermine]

"The only possible products that are achieved by more than one pair of numbers are 12 (as 34 or 26) and 6 (as 16 or 23).
But in the second case, the sum of the two (unchosen) numbers is odd..." why does products attained by more than 1 pair matter honestly? i dont get it

[coral parcel]

If there was only one pair that gave the product, then Claudia would know exactly which five numbers Zach was thinking of, and then she would obviously be able to figure out whether their sum is odd or even.

So the only way Claudia can not know whether it's odd or even is if there's more than one way to get the product.

[lyric quartz]

Is $\leadsto$ notation for a forgetful functor or just functor? My book used it in the context $\mathsf{Grp} \leadsto \mathsf{Set}$

[vital dew]

WanderingLethe

[fossil mural]

i don't think i've ever seen that symbol before in any context and i really doubt it has a standard meaning

[lyric quartz]

Ok, I couldn't find anything about the notation

[pearl ermine]

did u derive this understanding from -" If he told claudia whats the product of the chosen number was it would not be enough information for claudia to figure out whetehr their sum would be odd / even"?

[coral parcel]

Yes.

[lyric quartz]

Well this is mostly an algebra book, so functors aren't mentioned for another 400 pages... But then doesn't use that arrow, I guess the author didn't want to use an arrow as it was only used for functions and morphisms. (although a functor is a morphism as well)

[pearl ermine]

i dont understand the product of those numbers could have been any product of any 5 numbers why 7!/12 ?

[coral parcel]

Do you understand that if Zach chooses 5 numbers, then the product of the 5 numbers he chooses times the product of the 2 numbers he doesn't choose is always 7! ?

[pearl ermine]

yes sure that part is ok

but why 12, there could have been other product pairs like 7 * 5, 5 * 6 , 6 * 3 and so on

[coral parcel]

So once we have concluded that the product of the two numbers he didn't choose has to be 12, the product of the numbers he did choose must be 7!/12.

[coral parcel]

If he chose 1,2,3,4,6, then he would tell Claudia "my product is 144". Then Claudia could compute that the product of the two numbers he didn't choose was 35. But the only way to make 35 as a product of two numbers not larger than 7 is 7·5, so Claudia would know that 7 and 5 are the numbers Zach didn't choose. Therefore Claudia would know that the numbers he did choose was 1, 2, 3, 4, 6, and she could then compute 1+2+3+4+6 and see whether that is odd or even.
But the problem tells us that Claudia wouldn't be able to know whether the sum of Zach's numbers is odd or even.

[pearl ermine]

bro thank you so much this gave me a much clearer insight to the problem, but 6 also produces the same double pairing, so why did we divide by 12 and not 6? (asking cause didnt understand its explanantion from the solution)

tha will do it

[coral parcel]

If Claudia knows the non-chosens are either 1,6 or 2,3, then she knows the chosens are either 2,3,4,5,7 or 1,4,5,6,7.
But 2+3+4+5+7 and 1+4+5+6+7 are both odd, so in that case Claudia would confidently be able to say "the sum of your numbers is odd" even without knowing exactly which numbers they are.

[pearl ermine]

ah i see zack does tell his product to her, but she would not be able to deduce whethee the sum of the chosen numbers is odd or even, by addition. so that is why we divide it by 12. I sincerely thank you for meticulously dissecting the solution for me.

[leaden gulch]

practically unreadable

yea it’s just an editor error that i’m being dramatic about

[pearl ermine]

The probability that a multiple of 864 = 2^5 · 3^3 is divisible by 1944 = 2^3 · 3^5 is the same as the probability that a multiple of 2^2 = 4 is divisible
by 3^2 = 9. can someone explain me how?

[uneven violet]

You didn't say what probability measure you use on the integers, but note that if 864k is divisible by 1944, then k must be divisible by 9 (because 1944 has a factor 9 that 846 lacks). Similarly if 4k is divisible by 9, then k must be divisible by 9.

So the set of multiples that give rise to the first event is the same as the set of multiples that give rise to the second event. Whatever probability measure you use, the twos sets (which coincide) have the same probability.

[pearl ermine]

i seriously cant comprehend what u said "(because 1944 has a factor 9 that 846 lacks)." 846 also has a factor of 9

[uneven violet]

I looked first at the powers of 2. Here 864 has 2^5, which is more powers of 2 than what 1944 has, which is 2^3. So the powers of 2 are not a problem.
Then I looked at the powers of 3, where 864 has the factor 3^3, while 1944 has 3^5. So 1944 has two more powers of 3 than 864.

Two powers of 3 is 3^2, which is where I got the 9 from.

[pearl ermine]

i see that was insightful, can u explain me the solution of this:

how they equate those probabilities

[stray reef]

uhhhh

this entire problem seems super poorly informed

how are we "choosing randomly" from a countably-infinite set?

@pearl ermine what textbook did you get this from

[pearl ermine]

104 number theory problems, the author has provided such poorly configured explantions, anyone would puke.

[stray reef]

it's not even about the explanation, it's the problem itself

... can you toss me a pdf tho

[pearl ermine]

would u mind explaining me solution kindly?

no offense

[stray reef]

no, bc the solution is as bullshit as the problem

[viral crown]

no legal ones but if you look up "104 Number Theory Problems [Andreescu].pdf" who knows what u might find

[pearl ermine]

so u also didnt understand the solution right?

[fossil mural]

HMMT is apparently the Harvard-MIT Math Tournament https://www.hmmt.org/www/archive/52 with this particular problem appearing as question 4 of the "algebra" problems https://hmmt-archive.s3.amazonaws.com/tournaments/2002/feb/alg/problems.pdf and the "solution" given here https://hmmt-archive.s3.amazonaws.com/tournaments/2002/feb/alg/solutions.pdf with the answer 1/9

[stray reef]

i can try to explain what my issue w/ this setup is, if you want.

[fossil mural]

and yeah this question is just wrong or at best confusingly written, under the standard definitions of... how probability works... it does not make sense to pick a natural number uniformly at random

[pearl ermine]

i dont how they equate the probability wiht 4 and 9

[stray reef]

goatmilk

the issue is not that they're equating some probabilities

the issue is that the probabilistic experiment makes no sense in the first place

[pearl ermine]

whoa, how so?

[stray reef]

the problem posits a random sample from the sample space S = {864k : k ∈ N}, which is countably infinite (it is not finite, but it is a subset of N).
the question that begs itself is: what probability measure does this sample space come with?

with a finite sample space, without further specification, you could assume a uniform probability measure -- i.e. each of the n possible outcomes gets assignedd probability 1/n

but this won't work with a countably infinite sample space

you can't assign the same probability to all outcomes in this case -- they won't add up to 1 no matter what

(either all of them have probability 0, then their sum is 0 and not 1, or they all have some positive probability and their sum is +∞)

[pearl ermine]

should have caught it at first sight, yes it is true, that 864 k extends to infinity (considering no restrictions ot the number of multiples), so the probabilty messes up.

but did u understand how they equated the two porabibilites with one another? like proability of 4 being divided by 9 is the same as theose two numbers being divided?

[stray reef]

it's garbage in garbage out

it actually absolutely positively doesnt matter how or why they equate two things neither of which make any sense

[coral parcel]

Let's be a bit charitable and assume the author meant something like the limiting probability when choosing uniformly between multiples of 864 less than N, as N goes to infinity.

[pearl ermine]

bruh.. meaning wrong question and answer printed on textbook?

[coral parcel]

It happens; textbook authors are human.

[pearl ermine]

need help

arte they all 1?

[stray reef]

as in, are you asking whether p=q=r=s=1?

@pearl ermine you're gonna have to show us your work, and not only your answer

[pearl ermine]

yes this is what i think would be the answer, didnt do any roughwork for it

[stray reef]

so it's a random guess, is what you're saying.

that guess is wrong. do some actual work here, or tell us you don't know how to start.

[pearl ermine]

k then, i dont know how to start

[stray reef]

ok, so what i would do here is clean up the notation a little bit.

first, instead of A, B, C, D and E it will be more convenient to name your sets A_1, A_2, A_3, A_4 and A_5.

S_2 is then the set of all points which appear in at least two of the A_i.

if we let $T_m$ mean the set of all points which appear in \textbf{exactly} $m$ of the $A_i$, then we have that $S_2 = T_2 \cup T_3 \cup T_4 \cup T_5$ and this union is disjoint.

[vital dew]

|Ann⟩

[stray reef]

do you understand so far?

[pearl ermine]

what on earth is this

[stray reef]

i am introducing some new sets

i am introducing four new sets, to which i am giving the names $T_2, T_3, T_4, T_5$

[vital dew]

|Ann⟩

[stray reef]

and i am declaring that $T_m$ shall consist of all points which belong to exactly $m$ of the five sets $A_i$

[vital dew]

|Ann⟩

[stray reef]

does this make sense to you, yes or no?

it's my set, i do what i want with it.

i don't know which of these is goatmilk's issue:

• she does not understand what i am saying
• she does understand what i am saying, but not why i'm saying it or how to proceed
• she is completely stupefied because of letting her own math-phobia take over

@pearl ermine you there?

[pearl ermine]

yes im here

looking through your answer

[pearl ermine]

ok continue

@stray reef understood continue

[stray reef]

alright

[pearl ermine]

btw disjoint means no element are in common betwene t1, t2, t3 and t4, right?

[stray reef]

yes, but there are 2 issues with what you said just now

1. uppercase T, not lowercase t.
2. (and this is the more pressing issue!) it's T_2 through T_5, NOT T_1 through T_4.

T_1 is a thing but it doesnt interest us

but anyway yes these T_m are disjoint

it should be obvious why

if it is not obvious then tell me as such

[pearl ermine]

ok why are they disjoint? if u dont mind

[stray reef]

there is no element for which, say, the statements "x belongs to exactly 2 of the A_i" and "x belongs to exactly 3 of the A_i" are both true at once

do you understand this? y/n

[pearl ermine]

yes i understood

[stray reef]

ok

now here is the idea

[stray reef]

in order for this equality to be true, you will need every element of S_2 to be counted exactly once by the sum on the right-hand side.

[pearl ermine]

yes, which is the premise behid principle of inclusion exclusion

[stray reef]

right now, the sum on the RHS counts the following:

• elements in all 2-way intersections, p times each (for each pair of A_i)
• elements in all 3-way intersections, q times each (for each trio of A_i) [in addition to however much they have been counted earlier]
• elements in all 4-way intersections, r times each (for each quartet of A_i) [in addition to however much they have been counted earlier]
• elements in A1 ∩ A2 ∩ A3 ∩ A4 ∩ A5, s times [in addition to however much they have been counted earlier]

so for example, take an element $x \in T_2 \cap A_1 \cap A_2$ --- meaning an element that belongs to exactly 2 of the $A_i$, and those $A_i$ are specifically $A_1$ and $A_2$. \textit{(this is not strictly obligatory, but such concretization can make reasoning a little bit simpler further down the line --- the problem is symmetric enough that it doesn't matter which $A_i$ you pick for this)}.

then $x$ will be counted by only the term $p #(A_1 \cap A_2)$ and by no other, so $p$ times in total.

[vital dew]

|Ann⟩

[stray reef]

does this make sense to you? y/n

[pearl ermine]

a bit of explanation would help. are T1 T2 T3 T4 T5 intially empty?

[stray reef]

"initially"? what do you mean by "initially"?

also there's no T_1

[pearl ermine]

i mean are these T labelled sets empty?

[stray reef]

at no point did i say any of them were empty

it's possible to come up with scenarios in which some or even all of them turn out empty

but in general they are not

so these scenarios do not interest us in any way whatsoever

[cunning egret]

I'm not exactly sure what to do with this one

im thinking of contradiction but i can't exactly frame my argument

I guess i can assume f(n) to be uniquely determined upto, say k
so there exists m<k st f(m)=f(k)
now f(m-1) uniquely determines f(m) which is f(k) hence f(k-1)=f(m-1) but this is a contradiction since f(n) was uniquely determined upto k

but where induction

[coral parcel]

In general, "induction" proofs can always be rephrased as "let k be the smallest integer that this doesn't hold for, and then ... bla bla bla ... contradiction".
That's essentially what you've done here.

A straightforward induction formulation would go like:

Suppose f and g are two functions that both satisfy the recursive definition. Then by induction on n, we have f(n)=g(n) for all n: ...

[pearl ermine]

ok continue then

[stray reef]

ok alright

so, the conclusion thus far is that all elements of T_2 are counted exactly p times. are we good on that?

[cunning egret]

ah, so i just induct on k to prove it for all pos ints
my brain just didn't think of that cause it seemed too trivial

thanks tropo

[stray reef]

so to continue in a similar way

take x in T3 cap A1 cap A2 cap A3

this is now counted by 2 types of terms:

• n(A1 cap A2), n(A2 cap A3), n(A1 cap A3) -- coefficient p on each
• n(A1 cap A2 cap A3) -- coefficient q on each

so the total is now 3p+q

[pearl ermine]

this is because they are present in at least 2 of them?

[stray reef]

idk what either instance of the word "they" means in this sentence

can you please rephrase

(sorry, was a little busy)

[pearl ermine]

because the elements are present in at least 2 of them? oh btw u didnt substantiate on the necessity of taking extra sets labelled T1, .... T5 , just crossed my mind

[stray reef]

T2 through T5...

also i am literally using them

[coral parcel]

When you define something in a proof you don't need to "substantiate the necessity" of doing precisely that. The only justification needed is that it leads to a proof that works in the end. Even if there might be other things you could have defined instead which could lead to a different proof that also works.

[pearl ermine]

ok continue then

[stray reef]

so thus far we have concluded that:

• elements of T2 are counted with coefficient p
• elements of T3 are counted with coefficient 3p+q

are we good on both of that?

[pearl ermine]

sure

[stray reef]

i mean, do you understand not only why these are true but also how i derived them?

bc i was now going to invite you to continue the same reasoning (but longer) for elements of T4 and T5, and find the coefficients with which those are counted.

then we would continue.

[pearl ermine]

i understood them but hazily

ok why did we take T1 T2 T3 T4 T5 in the first place? can u tell?

lets go step by step

[stray reef]

for the n'th time there is no T1. you have not been reading the things i say attentively enough to catch that.

the reason i introduced these T_m is because the coefficient w/ which a point is counted by the RHS actually depends only on how many of our original five sets it belongs to

which is why i split them up based on that property

[stray reef]

then maybe we should have gone over them a few more times and i could clear the haze

[pearl ermine]

its too complicated i guess for me

I sincerely thank you for your relentless effort. I appreciate them with my utmost regard.

[stray reef]

this is so over the top it starts sounding fake

[viral crown]

seems like a product of culture differences

i think it's genuine

[pearl ermine]

thank you for understanding

[pearl ermine]

didn't know showing gratitude would be looked down upon. I did so because I assumed you wouldn't consider delving into the crux of the problem to make me understand, that too for this long.

[stray reef]

i am not looking down on the display of gratitude in and of itself, sorry that i sounded that way

i am not used to such intense displays of gratitude

[pearl ermine]

np, I expounded my stance

[muted moth]

I have to solve the following problem using the general Pigeonhole Principle: Considering we have to distribute 200 balls in 100 bins such that no bin is empty and no bin has more than 100 balls inside it, a claim is made that there will exist a subset of bins such that the balls contained in them will amount to exactly 100. How can this be proved?

[muted moth]

nvm

got it

[lyric quartz]

is this some archaic stuff or do i not know english?

[fossil mural]

not archaic but those are indeed uncommon words

[lyric quartz]

ok

[muted moth]

I have been trying yet not being able to understand why is the number of compositions of $n$ into $k$ parts equal to the number of weak compositions of $(n - k)$ into $k$ parts?

[vital dew]

tommy

[hollow wigeon]

Basically, the difference between a (strong) composition and a weak composition is that compositions don't allow 0 in any of its parts while weak compositions do. Thus, we can define a bijection between compositions and weak compositions: Given a composition, we can subtract 1 from all k parts. This decreases the sum of all parts decreases by k and may leave some parts equalling zero. Therefore, since this can be done for every composition, the number of compositions of n into k parts must equal the number of weak compositions of (n - k) into k parts

[muted moth]

got it! thank you!

and are you familiar with the result that obtains the total number of (strong) compositions for an arbitrary number of parts?

my prof told me that it was equal to

$$\sum_{k = 1}^{n} \binom{n - 1}{k - 1} = 2^{n - 1}$$

how's this result obtained?

[vital dew]

tommy

[muted moth]

I am familiar with the property that

$$\sum_{k = 0}^{n} \binom{n}{k} = 2^n$$

[vital dew]

tommy

[muted moth]

he made a vague statement that since the sum starts from 1 and not 0 in this case, we compensate for this by subtracting 1 from the final result. what does that mean?

I have also tried to look it up online, but no proper explanations are available

[viral crown]

hi, on my phone so i’m sorry for no latex. (n, k) is n choose k

one way to show this is to use the binomial theorem. first note that k(n, k) = n(n-1, k-1), which can easily be directly verified. then by the statement of the bnt recall we have (x+1)^n = sum_{k=0}^n (n, k)x^k. then differentiate to get n(x+1)^{n-1} = sum_{k=1}^n k(n, k) x^{k-1}. set x = 1 and we get n2^{n-1} = sum_{k=1}^n k(n, k). by our little lemma, we get n2^{n-1} = sum_{k=1}^n n(n-1, k-1). divide both sides by n to get the answer as desired.

[viral crown]

so, closing thoughts

a result that “looks” like this will usually be able to be obtained by manipulating the binomial theorem

in this case the n-1 in the exponent is a hint to differentiate it

the clue that gives it away is of course the identity we used in the important step

how would one come up with such an identity on the fly? idk! but this form feels very natural to me - you’ll learn useful things like this the deeper you get into math

[fossil mural]

...you can also just reindex the way the prof said...?

[fossil mural]

so let's take $n = 3$ as an example, then this would be $\binom30 + \binom31 + \binom32 + \binom33$

[vital dew]

bee [it/its]

[viral crown]

sure, but i feel like directly obtaining it gives more insight into the structure of the problem

[fossil mural]

and if we put in $n = 4$ here, we get $\binom{4-1}{1-1} + \binom{4-1}{2-1} + \binom{4-1}{3-1} + \binom{4-1}{4-1}$, or in other words, $\binom30 + \binom31 + \binom32 + \binom33$, it's the exact same sum

[vital dew]

bee [it/its]

[muted moth]

thank you for response @viral crown and @fossil mural

it was really helpful!

i think i get the gist of what's going on

[viral crown]

ofc!

[twilit sundial]

i'm not sure i follow exactly why they pick what they do to induct on in this proof

is it bc inducting on number of edges implicitly constrains the max degree of any one node?

(assume simple graph)

this feels like it's missing some details

[mental pecan]

Yeah it’s missing a lot

What is k here? I don’t know

[twilit sundial]

k i think is the index they're inducting on for number of edges???

ugh this is all so frustratingly obtuse

cs professors try to teach math challenge

[mental pecan]

An easier induction would be to claim instead if Delta = max deg G is <= k then G is k+1 colorsble

[twilit sundial]

oh wait the slides have alternate proofs with them making much saner choices on what to induct on

[mental pecan]

Then fix k and induct on the number of vertices in G

Oh good

[twilit sundial]

are we implicitly assuming "x" is fixed in this case or

[mental pecan]

Not in the og proof you sent

[twilit sundial]

oh lmao

[mental pecan]

You induct on x I think

Never mind I have no idea

[twilit sundial]

ah here's a much more safe and sane one

[mental pecan]

k is out of nowhere

[twilit sundial]

where they actually induct on max deg

they kinda rushed the end of this class lol

these are some proofs they didn't even get to in lecture

and they have one for inducting on vertices like you described

this is not explained well at all: why is it that "the remaining edges can be handled by hypothesis"

oh wait im an idiot lmao

as the union of bipartites

certainly that works

lol

[coral parcel]

Those are some fairly obfuscating proofs, I'd say.

[twilit sundial]

yea way too many asspull steps that aren't properly motivated

[viral crown]

this proof reads like it has an ego

[coral parcel]

If the max degree of a graph is any node is x, then the graph is (x+1)-colorable
Any presentation of a proof of this ought to start with the dead simple algorithm:

1. Go through the nodes in an any order you like.
2. When you come to a node, give it some color that you haven't yet assigned to one of its neighbors. There will always be a color you can pick there because you have more colors to pick between than there are neighbors to avoid.
   Now presenting this as a formal induction proof might need to turn the process inside out to some degree, but there's no point is completely hiding the simple underlying argument.

[twilit sundial]

literally 😭

this is only one of MANY boneheaded pedagogical decisions they make in this course

[stray reef]

i mean imo that algo description is proof enough

[viral crown]

i’ve noticed that graph theory is like fairly often taught poorly

[stray reef]

unless you're like, doing intro to proofs so 100% rigorous everything

[viral crown]

combinatorics in general is imo

[twilit sundial]

nah this class is just like "INDUCTIONINDUCTIONINDUCTIONONEVERYTHING"

when it's not always the best approach

it's like if you told a math student all the proof buzzwords and told them to do a class based on it

[viral crown]

i mean exploiting induction isn’t the worst approach

[coral parcel]

I agree, but figured perhaps the point was to show how the formal induction structure can represent various kinds of intuitive proof structure.

[viral crown]

a lot of graph theory problems admit proofs by copious horrific torrid amounts of casework

[stray reef]

would they prove even+even=even inductively as well

[coral parcel]

But the more I look at them, the crazier they seem. Why on earth induct on the x or the max degree instead of just inducting on the number of nodes in the graph?

[twilit sundial]

perhaps i exaggerated a bit, although i don't think that's beyond them LMAO

and the notations are rather confusing as well

[coral parcel]

Oooh, I think they're secretly using m to mean "the number of edges" here.

[twilit sundial]

there is absolutely no indication on how x increments tho 😭

or

is that just bounded by m

we go from what is presumably x=0 to

???

[coral parcel]

In the first proof x doesn't have to increment in an orderly way. It can be a completely new x for each instance of the induction step.

[twilit sundial]

hmm how would that work

[coral parcel]

But they're being criminally remiss in not explaining when the variables are bound.

[twilit sundial]

yeah 😭

so just pick any x that works?

for m=5 i could pick x=1000000?

[coral parcel]

It's horribly stated, but I think what they're actually proving is:

For all m: [ For every graph G with m edges, G is ([max degree of G]+1)-colorable ]

[twilit sundial]

ah that would make more sense

i had already taken an upper div course in the actual math department with a good amount of graph theory so i was like

[coral parcel]

They then state an "inductive hypothesis" that sounds like they're doing long induction, but they're actually using only ordinary mathematical induction.

[twilit sundial]

"am i just stupid" in this first year course for cs majors

ok yea that inductive hypothesis is

wack

what the hell

the more i look at it the worse it gets

[coral parcel]

Are you sure the context is not "this proof was written by a struggling student; please criticize it"?

[twilit sundial]

these were provided directly by the prof

i'm trying to review for a final off of these

and they are not helping

😭

[coral parcel]

(Just because they're employed as a professor doesn't mean they even like -- or are particularly competent at -- the random undergraduate topic they've been assigned to teach).

[twilit sundial]

yea figured as much

cs prof trying to teach a frankensteined math course basically

what the hell does case 2 even mean

prime obfuscation

[coral parcel]

It's already very misleading that they keep stating "inductive hypothesis" before "inductive step". Assuming the induction hypothesis is part of what you do IN the induction step; it has no existence outside it. Attempting to state it separately puts the cart completely before the horse understanding-wise.

[twilit sundial]

yea when i first learned induction in MS there was no distinction between "hypothesis" and "step"

hypothesis is part of the step, yea

[coral parcel]

Yes, case 2 there is horrible. I think, again, they must secretly be using the letter x to mean some function of whatever graph we're looking at, but without ever saying that in so many words.

[twilit sundial]

"union of x bipartite graphs"

and then they handwave it all away in the base case of all places

also what even is y LMAO

are they secretly fixing x or smth

or is this the same idea as the coloring one

[coral parcel]

I suspect what the're trying to express is something like "oh, just round n up to the next power of 2, then get log(n) bipartite graphs, and then discard the nodes you don't want".
But that doesn't fit into the standard mechanical induction-proof schema, so they get themself tied into knots by trying to shoehorn the "discard the unwanted nodes" postprocessing into the induction step.

[twilit sundial]

hmm that sounds like it might be it

[coral parcel]

The sane approach would be to prove

K_{2^m} can be expressed as the union of m bipartite graphs
as a lemma, by induction on m, and then extend to general K_n in a separate argument without induction.

[twilit sundial]

i hope this shit doesn't show up in large quantities on the final

although from what i've seen the exams tend to be on the easier side

otherwise literally nobody would be able to get some of these questions correct LMAO

in any case, thanks for your help lol

[stray reef]

yeah but thats not bureaucratic enough now is it

[twilit sundial]

https://math.stackexchange.com/questions/1344024/k-n-as-an-union-of-bipartite-graphs this explains it way more clearly lmao

[twilit sundial]

why does that work? how do we ensure we don't lose entire bipartites when discarding the excess nodes?

[coral parcel]

If we do, then so what? Having too few bipartite components is not a problem -- after all, the graph without edges is bipartite, so you can just top off with some of those if your construction doesn't give you enough by itself.

[twilit sundial]

so for example i could just slap on some K_{1,1}s?

[coral parcel]

No, just slap on some graphs without any edges at all.

[twilit sundial]

hmm

[coral parcel]

The graph with 12345 nodes and 0 edges is a perfectly good bipartite graph.

[twilit sundial]

bc 2-colorable?

[coral parcel]

Yes, "2-colorable" and "bipartite" are synonyms.

[twilit sundial]

oh aight aight

too used to only seeing bipartites that actually have edges lol

ok i think that clears up all the confusion i had, thanks again 👍

(my final is in 4 days, you might see me in here a lot these next few days lmao)

[coral parcel]

But you could also just take a single edge away from one of the bipartites, and declare that to be a new bipartite unionee in its own right.

[twilit sundial]

ah yea

god i'm also too used to only dealing with complete bipartites 😭

[coral parcel]

(Looks like the claim as stated doesn't even promise those bipartite graphs will be edge-disjoint, even though that's what the construction delivers).

[twilit sundial]

the handout that goes with these slides does say the bipartites need not be edge disjoint

so yea lmao

[coral parcel]

Here's a different view of the same construction:

1. Label all the nodes with different binary strings of length x.
2. For n=1,2,3,...,x, let bipartite graph number n connect nodes where the first difference between their labels is at position n.
3. This produces bipartite graphs, beause the edges in graph n all go between nodes with 0 at position n to nodes with 1 at position n.

[twilit sundial]

and then we can remove edges to produce new ones as necessary?

[coral parcel]

Huh. Why would you do that?

[twilit sundial]

if we "need more"?

or wait we don't need to do that here do we

[coral parcel]

Oh, sorry, I wasn't even thinking of the "get enough subgraphs" angle here, since I felt we had disposed of that.

[twilit sundial]

oh lol

does this cover those cases where we don't have powers of 2

[coral parcel]

Yeah, as long as you select different labels for each node.

[twilit sundial]

oh cool cool

[coral parcel]

If there's not a power-of-two number of nodes, some possible labels will go unused, but that doesn't matter.

[twilit sundial]

yea

explicitly constructing it makes it a lot clearer holy shit

thank you

[coral parcel]

Hmm, since we're not requiring edge-disjointness we could just say that subgraph number n connects all pairs of nodes whose labels differ at position n, no matter whether that's the first difference or not.

Then all of your bipartites will be complete. :-)

[twilit sundial]

:o

tried it for n=5

think it makes sense now

thanks again, now i really need to go sleep lmao 😭

[twilit sundial]

wait uh one more question before i actually go to sleep

what do we do in the cases where we don't use all the "bits"

say, n=5 and x=4?

this would hypothetically be able to accomodate up to 16 bipartite subgraphs

the construction there would only get up to 4? so the rest i could fill in with the "empty" (edgeless) ones or ones just connecting a single edge, etc.

[coral parcel]

Just pick some 4-bit labels -- they don't need to be the binary numbers from 0 to 4 (or 1 to 5).
Some of the bipartite subgraphs may end up being edgeless, but I don't care about that.

(I also assume it is allowed for some of the bipartite graphs being the same -- the claim wouldn't be true otherwise, because you cannot possibly split, for example, K_2 into 17 different bipartite summands).

[twilit sundial]

aight i'll see what sleeping on this does

thanq

[pearl ermine]

hey the question i have here is can the same result (420^2250) be acheived if any other integer divisor other than 420^2 , was removed from here? Based on my understanding, a divisor was removed so that pairs can be made from those divisors which multiply to 420^4, which then happen 526 times.

is the choice of removing 420^2 strategic here?

[lyric quartz]

The pair (420^2, 420^2) is not a pair of distinct divisors, so you would have to divide n^1125 n^563 by 420^2

If n was not a square number you would have an even amount of divisors, I guess, and all pairs would be pairs of distinct divisors

[pearl ermine]

ah so there are two 420^2 so we need to remove one of them so that the result falls within valid conditions? but would the same result (420^2250) be acheived if any other integer divisor other than 420^2 , was removed from here?

[lyric quartz]

I made a mistake, see above

[pearl ermine]

can u correct it?

[lyric quartz]

I already did n^1125 -> n^563

Like the solution says if d is a divisor, so is n/d. The pair (d, n/d) has the property that d * n/d = n. So if we multiply all such pairs (not just the distinct ones) we get n^1125.
But since the pair (d, n/d) = (n/d, d) we have multiplied every divisor twice. So the product of distinct divisors is sqrt(n^1125) = 420^2250

With that solution we don't even have to bother with an odd number of divisors

[lyric quartz]

I got an exercise to show that G x H in the category of abelian groups is also the coproduct. But I am kind of confused when I have to use all groups are abelian and that G x H is the product. And so I am kind of stuck, anyone got some hints? I have tried to write out some compositions of homomorphisms and sums of elements, but non gave me insides in the problem

[pearl ermine]

very smart solution

[lyric quartz]

So I think I want to show that mu has to be defined mu(a, b) = j_G(a) + j_H(b), but I don;t get how

[pearl ermine]

k but in the presented solution, would removing any number other than 420^2, give the same result as before? like 420, or 420^3?

[lyric quartz]

no, because (420^2, n/(420^2)) = (420^2, 420^2) is not a pair of distinct numbers

420^2 = sqrt(n)

[pearl ermine]

this and for pairing up numbers that form 424^4 right? because we cant form pairs with 1125 (odd)

[lyric quartz]

Since there is an odd number of distinct divisors you have 562 pairs + 420^2, which is not in any pair

[coral parcel]

That's probably a better question for #category-theory or one of the advanced algebra channels.
But there's really just one thing that makes sense to try for µ here, namely µ(g,h) = j_G(g)+j_H(h).

[pearl ermine]

bescially what i said right?

[lyric quartz]

Oh ok, I thought this was pretty basic Algebra stuff

[coral parcel]

You could get away with it in #groups-rings-fields, I think, but it's not really on target for "discrete math".

[lyric quartz]

Ok will ask there

[lyric quartz]

Got an exercise with a question and the hint is "No. Can you construct a counterexample?" Not like I had the choice to not read the hint...

[coral parcel]

Stick it to them by giving a proof instead.

[empty vale]

just a quick question which i think i already solved

i gotta find all the possible distinct rectangles

author says that there are 7c2 rectangles but i don't think this is true

since we can't pick any 2 dots on the first row, we must pick dots of distance different than 2

otherwise we would be building squares, this is correct right?

[fossil mural]

well in that case you would get a square

squares are rectangles so that isn't a problem

[empty vale]

are they? the more you know

i thought a rectangle had to have 2 different sized sides

[coral parcel]

The task does not seem to say that the quadrilateral must be a rectangle, though.

[empty vale]

no, i already know how many quadrilaterals are there, that was the first question, they are (7c2)(7c2)

[coral parcel]

Okay.

[empty vale]

the rectangle question is the one i thought was wrong

[coral parcel]

Yeah, my answer would be 21 because a square is (in the understanding I prefer, at least) a special case of a rectangle.

[empty vale]

right, thanks for the help, then we can pick 2 of the 7 dots and for each of them there are corresponding dots on the second row to build our rectangles, then the answer is 7c2

[gritty garnet]

Let $\\A = {2,3,8,12,18,24,36,72}, \\ B = {18,24,36 }\\$ and let $R$ be the relation on $A$ given by: $\xRy \iff y = kx, k \in \mathbb{Z} \ \$

1. Show that $(A, R)$ is a poset \\
2. Construct a Hasse Diagram for (A, R) and determine the least upper bound and greatest lower bound of B, if they exist, Is (A,R) a lattice?

[vital dew]

milanesa de pollo

[tight hound]

What is the issue here? Seems like a direct problem if one knows the required definitions

[gritty garnet]

I dont know how to tackle it

what definitions

partial ordered set?

has to comply with antisymmetric, transitive and reflexive relations

[muted moth]

what does this mean?

$$(a_1, ..., a_n) \preccurlyeq_2 (b_1, ..., b_n)$$

[vital dew]

tommy

[muted moth]

also, i think it is important to mention that $a_i$ does not mean elements of the same set

[vital dew]

tommy

[muted moth]

for some context, i am familiar with lexically-ordering relations between order pairs, but not with such relations between order-n tuples.

[opal crescent]

where have you seen that ?

[muted moth]

i wrote it down in my notes while in a lecture

[opal crescent]

well we can't guess what your lecturer meant really just from that

relation symbols are ultra context specific

cause ppl use the same symbol all the time

@muted moth

[muted moth]

this is about lexicographically ordering relations

i studied them under the study of partially ordered relations and posets

[muted moth]

this symbol specifically is causing a lot of trouble for me as well

[opal crescent]

well I hope you wrote its definition somewhere in your notes

[muted moth]

yeah

first, the definition made some assumptions that lets A and B to be two posets under their own generic relations

then it considered the ordered pairs in the set $A \cross B$

[vital dew]

tommy

[muted moth]

which simply implies that the definition is considering any relation from A to B

it said that $(a, b) \preccurlyeq (a', b')$ if $a \preccurlyeq a'$ and $b \preccurlyeq b'$

[vital dew]

tommy

[muted moth]

then it went on to generalise this idea from an ordered pair to an order-n tuple

[stray reef]

note that this relation is not lexicographic ordering

[muted moth]

yes

it is after this step that i encounter then

them*

[stray reef]

can you post the thing that's causing you trouble again

[muted moth]

hold on

let me take my laptop

my mobile is killing me rn

yeah

it says that

$(a_1, ..., a_n) \preccurlyeq_k (b_1, ..., b_n)$ if $a_i = b_i$ for $1 \leq i \leq k - 1$ and $a_k \preccurlyeq b_k$

[vital dew]

tommy

[muted moth]

yeah

this is what it is i think

[stray reef]

... can you take a screenshot of the entire page

[muted moth]

yeah

it's a bit messy

sorry for that

is it clear or should i click another one

for some context, the prof was giving examples from the poset $(\mathbb{N}, \leq)$

[vital dew]

tommy

[muted moth]

that i keep referring to (2, 3) and (3, 2) pairs

did you understand something or have i got something wrong here? @stray reef

[stray reef]

ok so it looks like $\preccurlyeq_2$ means specifically ``first components are the same, and $\preccurlyeq$ on the second component''...

[vital dew]

|Ann⟩

[stray reef]

i'm still confused what you are actually asking lol

[muted moth]

lol

i am gonna try one last time

you can ask whatever you want

[muted moth]

my problem is with the way this thing is defined and how it applies on the pairs (2, 3) and (3, 2)

because 2 and 3 are not the same

[muted moth]

that's why i asked it's meaning in the first place

[stray reef]

then $(2,3)\preccurlyeq_2 (3,2)$ is false as written

[vital dew]

|Ann⟩

[muted moth]

funny thing is these pairs are related

i have asked from my peers

[stray reef]

...

[muted moth]

all of them wrote the same thing but none of them gets it

[stray reef]

this is highly strange

[muted moth]

i think at this point i should mail my prof

because i don't think it feels right

he must've made a mistake here

[proven ibex]

shouldn't this b here be an e?

because the 1-equiv class of I (the output of state A with input 1) is e

[shrewd obsidian]

a crumb of context

[proven ibex]

We’re trying to find the equivalent states given the DFA on the left in blue

And we’re doing this by considering the refinement of k-equivalence states in green

[shrewd obsidian]

oh i see

yes it should be e

[proven ibex]

Ok my lecturer just made a mistake then

[spark gazelle]

does anyone know how I find the longest path between 2 nodes in a peterson graph

[stray reef]

!xy

[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]

does "path" mean the same vertex can't be visited twice

@spark gazelle

if yes: 4-0-1-2-3-8-5-7-9-6 seems to be the obvious maximum length path

[agile magnet]

Yea I guess the key idea is remembering that the Petersen graph has Hamiltonian paths

And now the next question is does it have a Hamiltonian cycle 👀

[prime pond]

can someone here help me in #help-14

i think this problem is impossible

[prime grotto]

call a set $S \subseteq \mathbb{N}$ weak additive closed if for all a,b $a\neq b$ both in S, we have that $a+b \in S$.\
for a given n, how many sets S are there of card. n such that N-S is w.a.c?

[vital dew]

HSF

[stray reef]

it feels like min(S) cannot be 3 or higher

[prime grotto]

yeah it can't

some values i got are
0 : 1
1 : 2
2 : 4
3 : 8
4 : 12

[coral parcel]

What is the X that suddenly appears in "X-S"?

[prime grotto]

oh yeah i'm dumb meant N

[gritty garnet]

How to find the isomorphism

[cerulean wind]

rotate a bit, stretch some things a bit.

you want to find an edge preserving bijection between the two vertex sets.

[gritty garnet]

Yeah they look pretty much the same if you rotate 90 degrees to the right the first graph

Vertex 6 is e

[cerulean wind]

right

and then you just keep going like that

[gritty garnet]

I need more help

[cerulean wind]

well, where are you stuck

[gritty garnet]

,rotate

[gritty garnet]

C is 3

I think

Is there a better way of doing this

[coral parcel]

There's no (known, polynomial-time) algorithm for this, so visual intuition and ad-hoc trial and error is the way to go in practice.

[prime grotto]

maybe try
F to 9
H to 7
B to 8
A to 5
C to 3
I to 4
D to 2
G to 1
E to 6
and check if the relations are maintained

[coral parcel]

(There are at least 6 different isomorphisms, two of which indeed map 3 to C).
((I think those 6 are all of them, but may have missed something)).

[cerulean wind]

you need to make sure that whatever your map is, it takes edges to edges. so for instance, f(H) = 7 and f(B) = 8 is good because the edge {H,B} is taken to the edge {7,8}

[prime grotto]

there are like 15 edges to check

[prime grotto]

thanks

15-16 seems closer

[cerulean wind]

i think its 15. the hexagon is 6, then there are 9 more connecting edges

[prime grotto]

well still it's quite a bit of edges to check

[coral parcel]

Whoops, yes, 15, I miscounted twice 🤦

[gritty garnet]

A cannot be 5

Look at degree of A and degree of 5

Oops mb

Both degree is 3 for both vertex

Okay

Okay I understood, tysm

For this graph which will be the highest and lowest degree vertex?

A and g?

[agile magnet]

do you have doubts in your answer?

[gritty garnet]

No

But how do I form an adjacency matrix for this?

Do I need to count the degree for each vertex

Also this is unweighted acyclic

How would adjacency matrix work here