discrete-math

[main spade]

I think I already told this but yeah. Here we are only thinking about colors as priority . Yee so either we focus on number of balls or just color

[spare slate]

if only color can be used to distinguish, then yes

[main spade]

Okay THANK YOUUUU

[spare slate]

[main spade]

I got so depressedddd

From yesterday

Cuz no one was understanding

What I was trying to mean

[main spade]

And finally u appeared

🥹

[spare slate]

didn't realise it was that hard to understand what you were saying tbh

🤨

[main spade]

Idk bro

Everyone kept telling me 19C4

Someone in other server told do manually and cry

[spare slate]

rip

[paper scaffold]

does anyone have a list of combinatorics formula here

the go to

[viral chasm]

To more appropriately ask this question, a more precise thing to ask is, "If I were to go through this book and the contents within it, would I be lacking any introductory math knowledge and if so, what else would I need to read and do to get that knowledge?", apologies for the more vague question from before.

[robust monolith]

The question is ok, but I think you can't share this book. <@&268886789983436800>

[willow oriole]

Yeah @viral chasm please don't post links to PDF copies of texts as discord will nuke us

[viral chasm]

Oh rip, sorry, whenever I look up the book that's the first thing that comes up so I thought it'd be fine, apologies 🙏🙏🙏

[slow tangle]

ive gotten my account restricted for posting a pdf of a pirated book

discord automatically flags some texts when u post it lol

try not doing it

[fluid quail]

how do yall study discrete math

cant understand it even tho i study

[paper scaffold]

Rote memorization and practice I guess lmao

The authors of formulas didn't understand the entirety of discrete maths

If you ask gauss bout how the dijkstra algorithm works he won't give ya the correct answer

[deft knot]

wonder why proof by induction was removed from my highschool course but now i have to learn it xD

also wondering when can we do a proof by induction?

[dull viper]

chinese remainder theorem 😭

[brisk spear]

where would u recommend studying graphs from? books/yt channel

[sturdy fox]

Bruh

[dull viper]

What😭

[sturdy fox]

New theorems bruhh

You are a scientist

[verbal whale]

Random question. idk if this is normal but i recently started studying discrete math for comp sci. And after 3 chapters in 4 weeks (number theory, induction, logics) rn learning sets, I got like 50-60% avg. idk if that is normal and anyone got tips/recourses I could use to help me out

[true venture]

Given any word/string with letters in some finite alphabet, let s be the set of all letters appearing in that word. Then let c be the size of the largest subset of s such that all letters in the subset are linearly ordered within the word.
For example: 1212331, s is {1,2,3} and the subsets of s {1} {2} {3} {2,3} all have letters appearing in order, so c = 2.

For words with s={1,2,3} I'm stuck on how to count words with certain values of c.

For context this was just something I thought of, but kinda an interesting way to refine all 3^n words of length n into classes by values of c.

[haughty garden]

sounds like you might want to be computing the longest subsequence of distinct letters of some sort

[true venture]

Oh that sounds cool, is that something that's been studied?

[haughty garden]

one approach is to compute the number of subsequences with k distinct letters; you can binary search for optimal k

https://cs.stackexchange.com/questions/140926/number-of-subsequence-with-k-distinct-characters

[true venture]

I'll look into that, I was trying to count these words

Ideally finding a generating function

[true venture]

For the word 321, what would be the longest subseq of distinct letters? 321?

[haughty garden]

yea 321

[true venture]

I see the letters forming the largest subset is maybe that

It's like the longest non-continguous subsequence of ordered letters

[flat grotto]

here do I have to convert A^c intersection B to ¬xE(A^c intersection B) ?

[pine marlin]

No

You need to show if x is not in A then its also not in B

[flat grotto]

yes but im not sure how i can make do if I'm given = an empty set

i understand what i am trying to prove

[pine marlin]

It means no element can be in both A^c and B

[flat grotto]

yes I know what it means, I am asking in my proof what is my first step here, since normally I am not given something like S = an empty set, or S = anything in general

normally it is something like: show given S that ...

[pine marlin]

Assume x is not in A

And show that its not in B

[flat grotto]

thanks that makes sense

i think I did it right, or the idea is right atleast, but the form/structure is not valid:

it feels a bit all over the place

but im not sure if thats a byproduct of going from formal proofs to rigorous

like can I take whole lines as = ?

if I have A^C = B^C
can I go line by line with that?
Like:

xE A^C = xE B^C

¬xE A = ¬xE B
...

[pine marlin]

It doesn't nake sense to equate to statements

You can say instead x in A^c = B^c which is both x in A^c and A^c = B^c

[flat grotto]

what about what I sent above where = an empty set?

[pine marlin]

Also not how you should write this

You are comparing objects to statements

[flat grotto]

so how would i do it there

[pine marlin]

Instead write with words or with set builder notation

With words: \newline
"There is no x such that ..." \newline
With set builder notation: \newline
${ x | .... } = \emptyset$

[vital dew]

ExpertEsquieESQUIE

[flat grotto]

id love to but i dont think we have the availability to do so

we are somewhat strict on inference and such step by step with laws & direct reasons

[pine marlin]

You can give reasons while writing like that

[flat grotto]

thats true, i think i should do that more

something I know as a fact I need to be explicit with if its a bi-implication and implication

Like this for example

This is i think a textbook/standard rigorous proof for us

i know it basic but i dont want to have to zoom out of a massive one lol

[pine marlin]

Yeah, you can get some practice while noting every little thing

Eventually you can just say these things without elaborating further

Ot depends on your level and the level that is expected from you

[queen coral]

If anyone can help me in #help-8 it would be greatly appreciated, the problem is from a discrete math class

[paper scaffold]

wtf is this about

can someone help

[astral cedar]

I would look at the numbers up to 2999 and look at how many choices there are for each place: $299*9$
And then the numbers 3000 to 3200 and so on

[vital dew]

Leyla

[paper scaffold]

still don't quite get it lmao

[astral cedar]

Ah, yes I read it wrong. I read it as not containing any 6.

You can look at certain ranges of numbers separately to make it easier - use your knowledge from Combinatorics.

The first range to go for is that from 1000 to 2999. In there all numbers are valid which have a 1 or 2 in first position and a 0-6 in each of the remaining positions. Giving a total of $277*7$ numbers.

Then repeat the same for the ranges 3000-3199 ($27 7$) and 3200-3239 (4*7) and finally 3240-3244 (5)

[vital dew]

Leyla

[coral parcel]

Think in base seven: 3244 - 1000 = 2244.
So just convert 2244 from base seven to the base you're answering in (that is, base ten).

[paper scaffold]

why base seven in particular

build the context

[coral parcel]

Because base seven has exactly the digits 0,1,2,3,4,5,6 which are allowed in the problem.

[paper scaffold]

oh damn I see now

hmmmm it's lowkey similar to what I did with hexadecimals

and octals

[fiery gazelle]

show that the chromatic polynomial P_G (k) for a graph G has degree |V(G)|.

i may be wrong in my intuition but my reasoning goes like this:
a chromatic polynomial is calculated by counting the number of choices of colorings each vertex in G has for k colors. so, atmost every vertex can have k choices of colorings, which leads to the polynomial being k^|V(G)|. this upper bound is also achieved by an edgeless graph.
again, in the worst case the color choices for each vertex may keep getting diminished: fixing a vertex v, it has k choices. then it's neighbours must have (k-1) choices. now we keep considering the common neighbourhoods of all of these vertices we have previously considered to see that each of them has a diminishing number of choices,i.e, we just make the graph complete. so it has the chromatic polynomial
k(k-1)(k-2)...(k - |V(G) + 1), which has degree |V(G)| and this was the most constrained case.

i may be sloppy in my argument, but it's only my intuition, not a proof. i want to ask if this is the right way to think about it.

[kindred lantern]

hello, does anyone have any knowledge about solving precedence graphs for conflict serializability? (more of a cs topic, but still related to graphs)

[flat grotto]

Why is the first part done here?

I do not understand why we need to show the implication, I understand how, but not why, mostly because I do not see when it used in the proof later on.

can we not show that (x,y) exists in id(S U T) <=> (x,y) exists in id(S) U id(T) then use the definition of set equality?

Directly, I mean

[earnest wasp]

Reviewing homework and noticing that it says Neither is a proper subset here. How? B is a set containing 3 (8 mod 3) which is definitely in set A. am i missing something?

[cloud rampart]

$A$ is a ``proper subset'' of $B$ if $A \subseteq B$ and $A \ne B$

[vital dew]

cloud ☁

[earnest wasp]

Yeah B is a proper subset of A though no?

Cause it asks if either are

[cloud rampart]

if it's simultaneously true that $A \subseteq B$ and $B \subseteq A$, that would imply that $A = B$

[vital dew]

cloud ☁

[earnest wasp]

Yeah my teacher says to ignore the signs and just assume it means "a subset". Weird but I went along with it.

More so asking about the 3rd question. Given the context of the set provided

A cant be a proper subset to B since it has sqrt(10)

[cloud rampart]

what do you mean by "signs"?

[earnest wasp]

\subseteq

[cloud rampart]

A does not have sqrt(10)

[earnest wasp]

omg

its sqrt9

so 3

Im an idiot nvm

[cloud rampart]

if it was true that A had sqrt(10), then your answer to question 1 would be incorrect

[earnest wasp]

Yeah Idk how i miscalculated it

Thanks

[sly flame]

i’m taking CS logic and we did a counting unit a few units ago, I have a test coming up and that’s 100% the hardest part on it. Does anyone have a good recommended video for first year counting to relearn? I try doing questions but I basically get every single one wrong

i’m posting this in the discrete channel because our prof told us it is very very similar

[earnest wasp]

Whats the counting unit look like for cs logic, like combinations and permutations?

[sly flame]

yes exactly that

i sort of understand it until it comes to doing the intersection thing when adding them both

or subtracting the union

[coral parcel]

Hmm, so you can write a proof, but you still feel you don't understand "why"?

You might try to rephrase your proof to be more direct ("Let u be an arbitrary vertex. Then the Hamiltonian path starting at u [...] and therefore u is by definition not a cut vertex. Since u was arbitrary, this shows that G has no cut vertices").

But if that doesn't help, it might be that you're somehow expecting too much from "see why"?

[earnest wasp]

Ah ok i might be able to help with this, shoot me a question on it that confuses u and ill try explain it

I can also send my professors ppt that covers it if u want

[sly flame]

that’s the issue it’s tons of stuff

i need like a video that goes over all of it

for starters i’ll send last years final question

right now id think the first part is (3^n) choose k

and then the second part 3^(n-2)

but i know that is completely wrong

I also now understand why we use cardinality of union A and B and then subtract cardinality of intersection A and B

i just don’t get how to make the formulas for the intersection

[earnest wasp]

Ok so i think theres gonna be 2 sets here. One being the number of strings length n, with only0,1,2 and have a certain(k) amount of 1s. Two being number of strings length n that start with 01

Idk how to do the formatting thing but for the first set we can do n choose k to find how much places can have a one in it

Damn honestly dawg thats all i got im doing simpler stuff in my class

Maybe trevtutor has videos on it

[sly flame]

ah shit

okay

thank you for trying

are you taking discrete math or a cs course?

[cerulean wind]

(n C k) 2^(n - k) + 3^(n - 2) - (the number of strings that start with 01 and have k 1’s)

[sly flame]

tysm

but do you know of any video

that could help me with this?

[cerulean wind]

no

[sly flame]

okay

[cunning plank]

ur missing overcount in this

[cerulean wind]

ah, yea.

[cunning plank]

because there could be strings that start with 01 AND have k 1s simultaneously, so these cases must be subtracted to remove the overcount

and this happens in (n-2 choose k-1) ways

[cerulean wind]

wait

[cunning plank]

*2^something

[cerulean wind]

i state this

[cunning plank]

for the rest of the digits

[cerulean wind]

at the end

[cunning plank]

oh mb i didn't see it

[cerulean wind]

lol

thought i was missing something else

[cunning plank]

nah u got it right mb

[boreal fossil]

Hey would any of you guys be willing to work through some problems with me over call at some point? Im super far behind and generally terrible at math.

[grand crown]

Post them for now, people will help if they know how to do it

[boreal fossil]

Ok thank you

[random sparrow]

we have the following statement that we want to prove: $$\sum_{i=2}^{n+1}\frac{4}{i^3}<2-\frac{2}{(n+1)^2}$$
base case, show it works for $n = 1$: $$\sum_{i=2}^{n+1} \frac{4}{2^3} < 2 - \frac{2}{(1+1)^2}$$ we get that $$\frac{4}{8} < 2 - \frac{2}{(1+1)^2}$$ it holds because $$\frac{1}{2} < 2 - \frac{2}{4}$$ because $$\frac{1}{2} < \frac{3}{2}$$ inductive hypothesis: we assume it holds for $n = k$: $$\sum_{i=2}^{k+1} \frac{4}{i^3} < 2 - \frac{2}{(k+1)^2}$$ Inductive step: we show it holds for $n = k+1$ \ we have $$\sum_{i=2}^{n+1} \frac{4}{i^3} = \sum_{i=2}^{(k+1)+1} \frac{4}{i^3} = \sum_{i=2}^{k+2} \frac{4}{i^3} = \frac{4}{(k+2)^3} + \sum_{i=2}^{k+1} \frac{4}{i^3}$$ it follows that $$\sum_{i=2}^{k+2}\frac{4}{i^3}=\frac{4}{(k+2)^3}+\sum_{i=2}^{k+1}\frac{4}{i^3}\implies\sum_{i=2}^{k+2}\frac{4}{i^3}<\frac{4}{(k+2)^3}+\left(2-\frac{2}{(k+1)^2}\right)$$

[vital dew]

Renato

[random sparrow]

I ned some help with induction

[haughty garden]

(k + 2) > (k + 1) and since k + 1 > 1, we have that (k + 2)^3 > (k + 2)^2 > (k + 1)^2; now reciprocate

[random sparrow]

What???

@haughty garden

[haughty garden]

(k + 2)^3 > (k + 1)^2 so 1/(k + 2)^3 < 1/(k + 1)^2 and so you have that 4/(k + 2)^3 < 4/(k + 1)^2

now you can combine two terms together to get what you need

[random sparrow]

idk if that's valid

[haughty garden]

oh it’s even easier than that. You have that (k + 2)^3 > (k + 2)^2 so when you reciprocate, the signs flip. So you can show that the RHS < 4/(k + 2)^2 + (2 - 2/(k + 1)^2). Now you just need to compare 2/(k + 1)^2 with 2/(k + 2)^2

[random sparrow]

can you make a drawing

@haughty garden

[haughty garden]

I am on my phone rn

But gimme a second

[haughty garden]

ok so i ended up getting it, you want to prove that [2 - \frac{2}{(k + 1)^2} + \frac{4}{(k + 2)^3} < 2 - \frac{2}{(k + 2)^2}.] This is equivalent to proving that [-\frac{2}{(k + 1)^2} + \frac{4}{(k + 2)^3} < -\frac{2}{(k + 2)^2},] which is equivalent to proving that $4/(k + 2)^3 < 2/(k + 1)^2 - 2/(k + 2)^2$ which is equivalent to proving that $2/(k + 2)^3 < 1/(k + 1)^2 - 1/(k + 2)^2$. Combine fractions and do a bit more simplification to get to a statement that is trivially true

[random sparrow]

ye

[haughty garden]

yeh it's a bit of a pain

i thought there would have been a cleaner way but i got the wrong inequality in my working

¯_(ツ)_/¯

[random sparrow]

it's tricky but not difficult xD

easy to mess up the inequality thingy

i messed it up like 3 times in a row and couldn't understand why i was getting contradictions when trying to prove the inequality

[random sparrow]

i appreciate the help ❤️

[keen thunder]

are nondenumerable sets different from sets that are not denumerable?

[hybrid quiver]

How do u construct multigraphs as sets?

Arent there issues with duplicate

[hybrid quiver]

Help me out

[pine marlin]

Multigraphs or Multisets?

[hybrid quiver]

Former

[pine marlin]

You have a set of vertices and a multiset of edges

[hybrid quiver]

What is a multiset?

[pine marlin]

A set which allows duplicates

[hybrid quiver]

Dont sets by definition not allow dupls?

https://tenor.com/view/side-eye-dog-suspicious-look-suspicious-doubt-dog-doubt-gif-23680990

[pine marlin]

Yes

But you can model these with sets

[hybrid quiver]

Go on

[pine marlin]

Something like a multiset is an equivalence class of functions where two function f,g are equal if they have the same domain D and you can compose with a bijection h:D-->D to get g from f

The idea is that the values the function takes tell you the elements that are in the multisets

And it doean't matter the order the elements are because of the equivalence relation

For example if you want the multiset {1,1} it can be the set that contains the only function f:{1,2} --> {1}

Maybe a different way to phrase what I did here is that a multiset is any potentially infinite tuple where order doesn't matter

[random sparrow]

im studying for my algebra exam that is in tuesday, good luck though

[weary tiger]

How exactly are tuples defined? If I have 3 sets A,B,C is A X B X C = (A X B) X C?

I feel like this is not the case since one leads to a triple while the other leads to a ordered pair consisting of an ordered pair as the first element

I read discrete math by epps and I remember the book saying the two were not equivalent, but in a book about set theory by the open logic project it states that a triple A X B X C can be thought of as ((a,b),c)

[grand crown]

you can construct a bijection between them two, so they're effectively equivalent

[weary tiger]

So it is the case that they are different?

[coral parcel]

You can treat them either as the same or different, depending on what's most useful in your context, as long as you're consistent about it.

[prisma lily]

i guess most people would consider them different though

[west hedge]

after you have functions you can also just start using a general definition of product that doesn't rely on an ordering of the factors

[coral parcel]

But there'll still be some seams showing, because (at least in a formal development from set theory) you need to have 2-tuples before you get functions!

[rapid gyro]

It's a shame there's no channel specifically for advanced logic, but DAE know about linear logic? I was just wondering how you guys understood the ⅋ connective. Intuitively, I interpret it as requiring that A and B be used one at a time — based on its relationship to implication — but somehow it also represents a parallel computation? I asked Tom7 and he says he gave up trying to make sense of it. And he's the guy who introduced me to it!

[coral parcel]

"Advanced logic" mostly goes in #foundations.

Par is weird, yes. I've tried to figure out a good intuition for it many times, but never really reached one that gave me the desired sudden-flash-of-understanding-everything feeling.

"A and B must be used one at a time" (meaning in distinct branches of the proof tree) is the best I've been able to reach too, but that feels unsatisfyingly non-semantic.

[rapid gyro]

Yeah, the "one at a time" interpretation almost seems intuitive, but according to the construction rules, I could give you A ⅋ B even if I only have one of A or B?

[cinder hornet]

Why? Asking for a friend 🥴🫨

[willow oriole]

Its a terms of service violation? All discord servers have an obligation to ensure that they're not facilitating privacy. Failure to meet this obligation can face consequences up to and including discord deleting the server and banning everyone who was in it

[random sparrow]

can i get some help

[cunning plank]

what is (a:b)

is this a/b?

or is it gcd(a,b)

[winged delta]

Interesting that it's 2ab^2 and not 2a^2b^2

[random sparrow]

gcd

[random sparrow]

wdym?

[winged delta]

If it were 2a^2b^2, that would be the cross term of (a^2+b^2)^2, and the other side would have the other two terms

[hybrid quiver]

why do we need path ?

isn't it strong enough to just say walk ?

[haughty garden]

you can say that but if a walk exists between two distinct vertices in the graph, then a path also exists so it is enough to define connectivity in terms of path existence

[hybrid quiver]

but isn't walks more general so better

[haughty garden]

i wouldn't say it's necessarily better as a definition

it depends on what you intend to do with the definition; if you intend to work with walks, then sure -- you can use that definition. I think conventionally, we just like working with paths

[neon harbor]

It depends on what you mean by a definition being better; you mean easier to prove, or easier to work with? In this case it doesn't matter if you use walks or paths, but in general it's easier to prove that an object satisfies a weaker definition, but a stronger definition allows you to do more, once you have proven it

[weary tiger]

Greetings.

I was wondering whether a set B exists such that for a non-empty set A, A×B = A

[cerulean wind]

what are your thoughts so far?

and what do you mean by equals?

strict equality?

[weary tiger]

Yeah

I don't think it should be possible to find one but just making sure

[cerulean wind]

not in general, no

[grand crown]

do you want B to work for any set A, or do you want to find A,B pairs where that is true

[cerulean wind]

the former is what i mean by not in general

and even like, in the specific case, this shouldn't be true

[weary tiger]

The former yeah

[cerulean wind]

if you weaken your notion of equality to say, bijective correspondence, then the answer is true in general

[weary tiger]

Thank you both

[cerulean wind]

isn't the converse true as well? these are equivalent definitions i think

[burnt terrace]

obviously, since a path is a walk

[hoary solstice]

Discrete is cringe tbh and yet it’s gonna be so important to my degree :/

Continuous time signals > discrete

Z transform is cringe!

[hidden totem]

yeah why don't computers just use continuous signals instead of discrete, smh

[grand crown]

z transforms are less pretty but theres some cool things that come out of them

reduced-order observers are easier to implement in discrete than continuous bc u dont have to approximate a derivative, u just work with next states

aliasing is kind of a cool phenomenon too tbh

this is actually why when you stare at a spinning object, it looks like it's slowly "going backwards" sometimes

[odd heart]

Some do! https://en.wikipedia.org/wiki/Analog_computer

[prime quiver]

ts the only way

[runic lava]

,rccw

[copper drift]

Guys, I am starting discrete math next semester. I don't really like the professor that has been assigned to me. Could I get any resources for self studying this subject? I always have been believing that discrete math is super difficult because it has proofs and all.

[hybrid quiver]

which one do you need help with ?

[sly flame]

anyone have good videos for proof by induction?

[olive swift]

Proof by induction

And by cases

[hybrid quiver]

Do you not understand the concept or the general structure of the proof or do you just want questions?

[olive swift]

Both of them (the concept and the general structure of this proof

[hybrid quiver]

so to understand the concept think about it like a domino you know that if for example the 100 domino falls down then the 101 domino. Right?

[olive swift]

yes

[hybrid quiver]

and you know how if 99th domino fall down then 100 domino fall down right?

You see how you can keep going down until the first domino right?

[olive swift]

Yes

[hybrid quiver]

So if you wanna prove that any domino falls down, you just have to prove that the first domino fall down

This makes sense

?

[olive swift]

yes

[hybrid quiver]

So when it comes to an induction proof, it's essentially trying to prove that an infinite amount of dominoes fall down and it follows the exact same pattern

First, you wanna approve that the first domino fall down

And then you wanna prove that if any domino falls down, the one after it falls down, proving that it follows a sequence

Does this make sense?

[olive swift]

I dunno

[hybrid quiver]

i fixed typos read again

[sly flame]

general structure, this is for a first year CS logic class assignment. I was able to tackle one question but the second part includes sigma notation and trying to self teach that through GPT makes 0 sense to me

its not really specific questions I kind of want to learn a general structure to it

base case is very very easy but I can't get the second part

[hybrid quiver]

do you know what a for loop is ?

[sly flame]

yes

of course 😺

[hybrid quiver]

$\sum_{i=k}^{n} x_i$ is $\$
sum = 0 $\$

for x in range(k,n):
$\$
sum+= list[x]

[sly flame]

I understand sigma notation but not how it is used in the question in tandem with inductive proofs

I'll send the question one second

[vital dew]

mq

[sly flame]

b

[hybrid quiver]

are you able to do base case ?

[sly flame]

yes

very easily

12 =< 50

[hybrid quiver]

alright give me a min to try the problem

[sly flame]

I did a but it aws with help from gpt heavily

we have done one example in a lec so its pretty confusing

[hybrid quiver]

ok it seems alright

but

you see how if you have a sum

you can take out the top term

so as an example

[sly flame]

the upper bound?

[hybrid quiver]

$\sum_{i=0}^{n+1} x_i = x_{n+1} + \sum_{i=0}^{n} x_i$

[vital dew]

mq

[hybrid quiver]

this make sense ?

[sly flame]

let me think about it one sec

[hybrid quiver]

are you able to visualize what the sum is?

[sly flame]

I kind of get it

[hybrid quiver]

$\sum_{i=0}^{n} x_i = x_0 + x_1 + x_2... x_n$

[vital dew]

mq

[sly flame]

this makes sense yes

[hybrid quiver]

so if instead of going up till n you can go up till n-1 and just add the n term it self

[sly flame]

ah

okay

that makes sense

so for n + 1 we are going up to n and then adding the n + 1 term

[hybrid quiver]

$\sum_{i=0}^{n} x_i = x_0 + x_1 + x_2.. x_{n-1} + x_n = (x_0 + x_1... x_{n-1}) + x_n = sum_{i=0}^{n-1} x_i )+ x_n$

[vital dew]

mq

[hybrid quiver]

stupid ass discord text is not functioning

[sly flame]

loool

[hybrid quiver]

let me gpt the text

[hybrid quiver]

yes

suppose i am adding up the first 5 integers

this is the same as adding up the first 4 integers and then just adding 5 at the end

[sly flame]

mhm

[hybrid quiver]

so in this case what you pretty much always want to do

[sly flame]

gotcha...

[hybrid quiver]

on the inductive hypothesis right where you have n+1

[sly flame]

but you always use k + 1 or whatever right?

[hybrid quiver]

yea

you prove base case

and then you prove that it being true for k implies it being true for k+1

so if you want to prove this being true for k+1 then you would get

[sly flame]

and then proving for k + 1 proves if for everything?

because its arbitrary

[hybrid quiver]

yes

[sly flame]

so do I need to prove k?

[hybrid quiver]

no

because you prove the base case you can assume it's true for k

[sly flame]

ahhh

so then whats the general form for solving a question

[hybrid quiver]

if you don't understand let me explain why

if you prove for n=1

then when proving for n = 2 you can assume n=1 is true

if n=2 is true

then for proving n=3 you can assume n=2

etc. etc.

[hybrid quiver]

so

you have this sum

[sly flame]

mhm

[hybrid quiver]

this is your k+1 case right =

?

[sly flame]

tes

[hybrid quiver]

and you remember how i told you you could take out a term ?

[sly flame]

correct

[hybrid quiver]

like the n+1 term in the sum

[sly flame]

yes

[hybrid quiver]

so what happens if you do that ?

[sly flame]

:D

uhhh

sum of n then add n+1 term

when subbed into

so

f of n+1 times g n + 1

• the sum to n

[hybrid quiver]

this

right ?

[sly flame]

yes

wowowowo i got it right lmaoo

[hybrid quiver]

great

[sly flame]

and then from there...

[hybrid quiver]

you assume this is true for n right ?

[sly flame]

yes because we did the base case

[hybrid quiver]

so you can substitute the sum from 3 to n with the Right handside

[sly flame]

bc we just assume everything from 3 to n is true?

[hybrid quiver]

?

wdym

[sly flame]

i dont get the substituting for the right hand side

[hybrid quiver]

so

you're trying to prove an inequality right ?

a+b < c

this is what you're trying to prove

[sly flame]

yes

[hybrid quiver]

you know that a < then say d

because this is the case of n which you assume to be true

[sly flame]

mhm

[hybrid quiver]

so if you prove d + b < c then you definitely prove a +b < c

because

a+ b < d + b < c

[sly flame]

yeah

that makes sense

[hybrid quiver]

so if you sub in d, and then prove it, then you're done

if you want to prove 5 is smaller than 10 and you show 5 is smaller than 7 and 7 is smaller than 10, then your done!

[sly flame]

wait so we are assuming n is true because of base case right

[hybrid quiver]

yes

[sly flame]

so then if that sum is smaller than RHS

we...

[hybrid quiver]

are done

[sly flame]

er

uhh

like

[hybrid quiver]

so the main step is subbing in d and then proving it's smaller than RHS

this is what it should look like

because you assume this is true

[sly flame]

hmmm

so wait

when we rewrote the sum

we got the fn + 1 times g n+1, but wheres the first term come from

[hybrid quiver]

here

you split the sum and you get a smaller sum + the last term

[sly flame]

mhm

[hybrid quiver]

if you have the sum of the integers from 1 to 5

is this not the same as the sum of the integers from 1 to 4 and then you add 5 at the end ?

[sly flame]

yes

[hybrid quiver]

that's exactly what you're doing

[sly flame]

okay i think I get that

just

where does this come

because isnt the sum

just n

[hybrid quiver]

yes so you sub in

[sly flame]

ohhhhh

n

[hybrid quiver]

we assume this is true right ?

[sly flame]

yes

[hybrid quiver]

so you see it now

[sly flame]

kind of lmaoo

[hybrid quiver]

good, the rest is just basic algebra

it won't immediately make sense

but you do 2-3 examples and it'll come through

[sly flame]

mhm

im just not understanding where the first term is coming from

[hybrid quiver]

ok so you agree we have this right '

[sly flame]

so we have left hand side base case is less then RHS

so then we want to find something that is less then LHS

uh

[hybrid quiver]

so if i want to show 5 is smaller than 10

[sly flame]

yes

[hybrid quiver]

i have to find something bigger than 5 agreed ?

[sly flame]

yes

[hybrid quiver]

and show that is smaller than 10

for example 6

[sly flame]

but less than 10

[hybrid quiver]

exactly

so the entire proof is showing smaller than 10 once you sub in

[sly flame]

I know this might be tedious but can you name which parts are our "10" "7" and "5"

if that makes sense

[hybrid quiver]

sure

this is 5

this is 7

this is 10

[hybrid quiver]

YOu want to show this (5) is smaller than 10

[hybrid quiver]

so you take 6 which you know is bigger than 5

and show that is smaller than 10

[sly flame]

god this is just not clicking at all lmaoo

[hybrid quiver]

so let me guess this is your confusion when we are doing this substitution we are kind of assuming it already is smaller than RHS no

[sly flame]

uhhh its the whole smaller than and larger then and knowing why one is larger than the other

or smaller

[hybrid quiver]

ok let's say i have 3 objects

Box A, Box B, Box C

I tell you that Box B is bigger than Box A

and that Box C is bigger than Box B

what can you deduce about whether Box A is smaller or bigger than Box C ?

[sly flame]

I understand that part

its just finding how one is bigger than the other

[hybrid quiver]

so you agree with this so far ?

[sly flame]

that is splitting up sum of n + 1 right

[hybrid quiver]

can you vc ?

[sly flame]

yes

that would be great

[versed kindle]

#proofs-and-logic message im pretty sure for any n amount of equivalence classes the answer is just how many unique unions there are between the equivalence classes. does anybody know a combinatorics formula that fits this?

[proud flicker]

well its called bell number

[versed kindle]

ty :)

[prisma lily]

hi
in principle (c) should be wrong here right?

[grand totem]

This sounds suspiciously like they meant to say the right thing considering only the exactly part is problematic

But taken literally yeah I agree it should be wrong

[prisma lily]

okay and

what if they try to make the argument that (c) written in propositional logic is an implication with a false premise

[prisma lily]

^

[coral parcel]

"Hence" is not generally a word that is used to express merely a truth-functional implication.

"if A then B" is just an implication.
But "A hence B" claims that A is true and therefore B is true too.

[grand crown]

it kind of sounds like you want a product of sums form, maybe a karnaugh map would help?

[prisma lily]

makes sense

thank you for your help, troposphere, neverbloom

[final shard]

Ive a question regarding preparing for discrete maths exams. How do you prepare for discrete maths exams as this isn’t a computational subject and the questions in exams are always going to be unique?

[dire bough]

practice

[proud flicker]

i just go over seminar problem sets and hope there'll be smth similar

[worn salmon]

hey everyone, can one of you explain about zero order hold?

[pine marlin]

Context?

[lilac hawk]

Hey everyone!

My name is Sylvain, I'm 21 years old, and I just dropped what might be either the most historic proof ever to hit Discord ... or a fun mathematical adventure that'll make us all laugh together. Either way, we're in for a good time!

Quick context: I had some rough times in high school, but I kept studying independently. Since then, I've been diving deep into online resources—including some amazing YouTube channels—and now here we are.

Fair warning though: My article is written with genuine effort, but it's definitely not professionally polished. I'm French, so I'll do my best to answer questions quickly !

Why I'm posting this:

I know the Goldbach Conjecture is basically the modern impossible problem—thousands of amateurs have tried. But here's the thing: I haven't found anyone who can actually prove my proof is wrong yet. So... I'm bringing it to Discord!

The core idea: This is a proof by strong induction showing there are always enough prime numbers to write the next even number as what I call a "telescopic sum of 3 primes"—starting from the hypothesis that all even numbers since 6 can be expressed this way.

The main argument (super condensed):

On the relationship between n and ug: By induction hypothesis, I have enough primes to express ug as a telescopic sum. At rank ug+1, I prove that if we consider n+1 for ug+1, there are enough primes to do it—but here's the key: we don't actually need n+1. The inequality only involves n, so ug+1 is already covered. This sidesteps the prime gap problem entirely.

Why a telescopic sum always exists for ug+1: We can compute ug+1 - (c-b) and it lands on some term in the sequence. Even in the worst case (when the next prime is just before ug), we fall back on u₀. So by strong induction, every element can be written as a + b.

On the "paradox": Someone might ask, "Can't we express ug+2, ug+3... all from n?" No—I'm using the heredity principle: I'm not claiming we can reach infinity from n. I'm saying that anywhere in the sequence, there are always enough primes before uₖ to express uₖ+1.

Quick example: ug = 12, ug+1 = 14
Maximum prime available: 11 (n+1 = 13, but we don't need it!)
14 - (11-3) = 6 = u₀
And 6 = 3+3
So 14 = (11-3) + (3+3) with 3 as the pivot.

Check it out: The full paper is here → https://doi.org/10.5281/zenodo.17770842

Now come at me with your questions ! Either we celebrate something historic, or we have a blast finding the flaw. Win-win.

Here's a quick schematic of the idea—hope it helps visualize the telescopic sum concept and how the induction actually flows. Let me know if anything needs clarifying !

Should I create a dedicated thread for this so we can keep all the discussion organized ? That way questions, objections, and clarifications stay in one place and don't get lost in the general chat.

Let me know what works best for everyone!

[winged delta]

Either we celebrate something historic, or we have a blast finding the flaw. Win-win.
Or we play a nice round of “ignore the crank with the AI generated post”

[grand crown]

Is that entire message also ai generated

[lilac hawk]

I'm using AI for English because I'm bad at foreign languages, but I actually wrote the French article myself. I didn't just ask chatGPT to solve it for me, Goldbach 🤣

[grand crown]

i see okay

[primal grove]

can someone help me understand this :
What is the probability that a five-card poker hand contains at least one ace?
my thought process is well, we know that we must have at least one or more aces in the hand so lets get the minimum out the way>
4 ways to chose 1 ace => 4C1
ok now we have at least one so we can multiply by the remaining combinations of cards>
51 ways to chose remaining 4 cards => 51C4
there is 51 left because the other aces can still be chosen except for the 1 ace that we already chose.
and divide that by the total sample space of 5 card combinations in a poker deck leaving us with :
(4C1 * 51C4) / (52C5)

but this is wrong apparently

[coral parcel]

You're overcounting hands with more than one ace, namely once for each ace in the hand that can be "the" ace.

For example, ♠3 ♠4 ♠7 ♠A ♥A gets counted once as ♠A + {♠3 ♠4 ♠7 ♥A} and once as ♥A + { ♠3 ♠4 ♠7 ♠A}.

(The easier way to count correctly is to count the hands with no aces, and subtract those from the total number of hands.)

[lone bear]

Guys

Can u guys help me with discrete mathematics?

AM COOKED AF

[primal grove]

interesting, yea the compliment works great thank you!

[earnest wasp]

with what

[crystal plaza]

does anyone here tutor discrete math. Specifically groups and everything related to that? if so please send me a dm. Im willing to pay the amount you need

[quick folio]

For questions about groups, feel free to direct them all to #groups-rings-fields and there are plenty of people there willing to help

[timber elm]

First: If a connected graph G contains three blocks and k cut-vertices, what are the possible values for k? I believe it should be 1,2 or 3. k=1 when all three blocks share the same cut vertex. k=2 for three block row up together. k=3 when B1 and B2, B2 and B3, B3 and B1 share the cut vertex. Is that correct?

The second question: Prove that if G is a graph of order n ≥ 3 such that deg v ≥ n/2 for every vertex v of G, then G is
nonseparable. I believe when I suppose v is a cut vertex and know that there must be u and w adjacent to v, then in G-v, We have deg u+ deg v<=n-3 because u is in H1, w is in H2, and the sum of degree should exclude u, v, and w. Is that a correct statement. I use that to prove it, but I want to confirm whether I made mistake here

[hybrid quiver]

loop free graph is just a graph with a edge to itself right ?

[coral parcel]

A loop-free graph doesn't have any edge that begins and ends at the same vertex.

[hybrid quiver]

oh ye that's what i meant

graph theory has so many definitions haha

does it get better ?

[random frost]

hey guys, I'm 4 weeks behind in my discrete maths course and it's causing me the worst headache

[dry pagoda]

CRAM

[midnight tapir]

https://tenor.com/view/best-of-luck-to-you-brother-vegapatch-giants-gaming-good-luck-best-of-luck-gif-23930239

[random frost]

thank u guys 😭 do u have any tips?

[pine marlin]

take a rest if you don't feel well

and start giving what you need to study a short read

once you feel better then try to catch up

[vital dew]

Civil Service Pigeon

[spare slate]

[midnight tapir]

Start reading

[hybrid quiver]

spend the week-end just grinding

commute to the library at 9 am

, bring your own food

and just study study study

[winged delta]

The problem claims that no two rows are equivalent under the operations, but row 6 equals row 4?

I imagine it's meant to be 1 5 2 3 4 3

[crystal plume]

ive been working on this problem for a bit

suppose you have a tube two units wide, and infinite height. Recall that a triomino is a L shaped piece of three unit squares. Suppose triominos are rotated uniformly random, and dropped into the tube. After dropping k randomly oriented triominos, what is the expectation of the height of the stack of triominos in the tube?

this is the solution i had - pls tell me if it's correct/wrong and why. i discussed with some others and we all got differnet answers. there are 16 possible combos of the block falling and the block under it, (4x4). if we make a table 14 of these combos add 2 blocks of height, and 2 add only 1, when it fits perfectly into the hole (this still adds 1). this means the expected addition in height is 15/8. so i got 15/8k

[spare slate]

looks like I missed a "no" too

this should be fine:

[vital dew]

Civil Service Pigeon

[dense gyro]

Hi, does anyone understand logic circuits and simplifying complex ones with laws?

[grand crown]

instead of asking if anyone knows, it’s easier if you post your question

If it’s a concept you don’t understand, it’s good to be specific

[dense gyro]

omg wait you're right 😭

I just don’t understand how it was simplified in the example, even when looking at the definitions of the laws

[hybrid quiver]

What would be a standard course after discrete math ?

[pine marlin]

if you want the same things then probably things like combinatorics, set theory and logic

[hybrid quiver]

Set theory and logic courses do not exist at my university.

Nor does combinatorics

[pine marlin]

sus uni

[hybrid quiver]

my uni is good 😠

well except in this

[cloud rampart]

might help to write out the reault of the circuit in algebraic form

[grand crown]

There might be set theory or logic in the philosophy department

[hybrid quiver]

there isn't

I checked

[grand crown]

dang

[dense gyro]

I wish, I don’t think he posted the result of it in algebraic form in the notes :/

[grand crown]

axiomatic set theory is a philosophy class here

Maybe take a graph theory class

[hybrid quiver]

no graph theory either

[cloud rampart]

you can do it yourself

[hybrid quiver]

well maybe in cs department but then there is language issues

[grand crown]

maybe it’s easier if you give us options

what does your school have

[grand crown]

Your school is not a discrete math school

Maybe abstract algebra but I think you already took that

cs would probably be your best bet tbh but if there’s langauge issues that might be hard

[hybrid quiver]

it has a lot more courses in mathematical stats and numerical analysis but i don't think they're relevant, i can share if you think there would be anything interesting

[grand crown]

umm like I personally find those interesting but probably not discrete subjects

I’m taking a couple of “discrete math” classes next sem but they’re all in CS

[hybrid quiver]

hmm alr, i'm doing exchange next year

so hopefully more courses offered there

i'll aim for combinatorics

let me send you waht they have

[twin arrow]

hello I am about to read this and would like any recommendations you have on how I should learn youtube channels other great books or blogs on math or a free website where I can do more problems
https://digilib.stekom.ac.id/assets/dokumen/ebook/feb_ffa40f116d4322d430e4d4ff287f156f5b2aff8c_1659617647.pdf

[hybrid quiver]

Can someone check my proof ?

The separation and linear code is the same.
Proof:
Consider d(x,y) =  Mathjax  as our separation.
d(x-y,0) =  Mathjax 
Therefore w(C) is at maximum sigma.
Suppose w(x) =  Mathjax  <  Mathjax 
d(x,0)  Mathjax 
Contradiction!

[narrow mountain]

.

[hybrid quiver]

<@&286206848099549185>

[clear swan]

Have you considered rereading what you sent?

[hybrid quiver]

ah my bad lol, it rendered differently

[clear swan]

I'll let someone else help if they can since I'm vaguely familiar with this, but not anywhere near enough to help.

[smoky birch]

Exactly what kind of help do you need?

The proof is correct but it lacks sufficient rigor, that's the only thing I can think of to improve it

[rugged sky]

Can somebody help me to solve the following problem: there are n sticks of the length 1,2,…,n. How many incongruent triangles can be formed by using any of three sticks

[hidden totem]

have you tried to see under what cases you can and can't make a triangle? also do you know your side-side-side triangle congruence theorem?

[hybrid quiver]

Could you tell ne how you would phrase it ?

[molten kraken]

In my uni, the real analysis course is considered the 'continuation of the discrete math course'

The set theory, combinatorics, graph theory, etc. courses all have the discrete math as a pre-requisite, but I would consider them better direct successors than the analysis course

[past rivet]

That’s quite interesting to me because analysis is very much “continuous math”

[molten kraken]

Lmao, ya

[frozen island]

What is discrete and continuous

[little prism]

integers are discrete. there is "space" between them. they dont get arbitrarily close to each other. thats not the case for the real numbers. they are continuous

discrete math deals with topics involving finite or at most countable things

combinatorics and graph theory are two classic examples

[empty meteor]

Two theory I made

https://docs.google.com/document/d/1PAJQhPBhb-tpxFDTXscwIhikJTVTHUdvEAf_pUKA24E/edit?usp=drivesdk

https://docs.google.com/document/d/1gOy-d4K-JOiqJyddDi6q3G1229FIkbYAjhJSoVerq_M/edit?usp=drivesdk

[spice finch]

hi can some1 plsss help w this concept

i genuinely dont get any of it

[lapis finch]

can i ask help here

[spice finch]

twin can u help m e

[lapis finch]

bro

[spice finch]

pls

[lapis finch]

have u done booths algo

[spice finch]

huh

idek what that is

[lapis finch]

twin im lost too dw

[spice finch]

dw???

chat i have my final on saturday

[lapis finch]

my final is due in 8 hours

it's a take home portion

[spice finch]

brah thats fire

[lapis finch]

fr bro

i dont have one damn clue whats going on in this class

I pay attention every class and I swear he pulls stuff out of his cheeks

i dont know ANYTHING

[spice finch]

what r those symbols

[lapis finch]

wtf are these greek synbols

fr

[spice finch]

what amjor is this for

[lapis finch]

its discrete math

thats why im here

[spice finch]

WHAG

[lapis finch]

cs T_T

[spice finch]

no way

thats my class

[lapis finch]

pain

well i cant do these image sets

i literally cant do this

[spice finch]

is this real analysis

[lapis finch]

#real-complex-analysis

[fossil mural]

that makes me feel like they're using "discrete maths" to just mean, like, "introduction to proofs"

[lapis finch]

thats literally what the professor said LMAo

introduction to proofs word by word

the proofs have to be so accurate because of that

[spice finch]

twin can u help me

[fossil mural]

$\mathbb{R}$ is like, the single most archetypical example of something that is \textit{not} discrete and therefore has no place in a ``discrete maths'' class

[vital dew]

bee [it/its]

[lapis finch]

pls just help me instead 😭

[spice finch]

lmfao

[fossil mural]

i mean there's no reason i couldn't help both of you at the same time, if you can be more specific about what exactly your problems are

[lapis finch]

i cant do these image sets nor the inverse

especially the inverse sets

[spice finch]

tyty i need help understanding how A1 and A0 work and then where they get the exponenets basically the whole property

[fossil mural]

well basically the idea is you just, split the number into two parts

like if we take an example in decimal because that's easier

say you want to multiply 425099 * 238698

[lapis finch]

[fossil mural]

then you would have A_0 = 425, A_1 = 99

[spice finch]

yes and then they have 2^n or somwthing which i dont get

[fossil mural]

...to be honest i don't quite know what you're expected to do here either

ok wait, does f'' mean the image or the inverse image

[lapis finch]

yes

image

the -1 makes it an inverse image

[fossil mural]

well if you just said "A = A_0 + A_1" then that's not correct, because 425 + 99 is 524, not 425099

but what is true is that 425099 is 425000 + 099, which is 425 * 10^3 + 99

("10^3" is just 1000)

[spice finch]

oh

[fossil mural]

more generally, multiplying by 10^n adds n zeroes on the end

(they're multiplying by 2^n instead because they're doing it in binary instead of decimal)

[spice finch]

n is how many characters r the split right

this is just making the original value how is it actually multiplying?

[fossil mural]

oh alright, that makes it easier than i was thinking

so

uh

...wow there is so much going on here

[fossil mural]

well that's the next part

[lapis finch]

sos fr

[fossil mural]

once we have a = 2^n A_1 + A_0 and b = 2^n B_1 + B_0

we can now rewrite ab = (2^n A_1 + A_0)(2^n B_1 + B_0)

and then expand it out

$ab = 2^{2n} A_1 B_1 + 2^n A_1 B_0 + 2^n A_0 B_1 + A_0 B_0$

[vital dew]

bee [it/its]

[fossil mural]

uhhh

oh i see

and then we mess with it a bit more

because if you expand out $(A_1 - A_0)(B_0 - B_1)$, it's $A_1B_0 + A_0B_1 - A_0B_0 - A_1B_1$

[vital dew]

bee [it/its]

[spice finch]

yeah so how is the 2^2n come

[fossil mural]

that $A_1B_0 + A_0B_1$ is the part we actually want, because this is $2^n(A_1B_0 + A_0B_1)$

[vital dew]

bee [it/its]

[fossil mural]

well we multiplied the two $2^n$s together

[vital dew]

bee [it/its]

[fossil mural]

and $2^n \cdot 2^n = 2^{2n}$

[vital dew]

bee [it/its]

[spice finch]

uhhh

[spice finch]

how does this work

cuz we dont do A0(B0)

[fossil mural]

...right, sorry, i was being imprecise

[fossil mural]

the middle part here, the stuff with 2^n in front of it, is A_1 B_0 + A_0 B_1

[empty meteor]

Guys I might found a new philosophical theorem holy

[fossil mural]

$ab = 2^{2n} A_1 B_1 + 2^n (A_1 B_0 + A_0 B_1) + A_0 B_0$

[vital dew]

bee [it/its]

[lapis finch]

damn i still cant do ts image sets and inverses

[fossil mural]

but then we can rewrite this as \ $ab = 2^{2n} A_1 B_1 + 2^n ((A_1 - A_0)(B_0 - B_1) + A_0B_0 + A_1B_1) + A_0 B_0$

[vital dew]

bee [it/its]

[spice finch]

i still dont get what 2^2n is lik i get the split and the multiplying with 2^n

but 2^2n makes no sense

[fossil mural]

oh right sorry, i kind of got distracted

[lapis finch]

please bee i neeeeed thissss

https://tenor.com/view/ishowspeed-meme-trying-not-to-laugh-laugh-homeless-gif-9458928528704746136

[fossil mural]

ok so if we look at (i) first

[lapis finch]

alr alr

[fossil mural]

the first issue is that the set contains some things that aren't integers

but the inputs to $f$ have to be integers, because they said $f : \mathbb{Z} \to \mathbb{Z}$

[vital dew]

bee [it/its]

[lapis finch]

okay

are those excluded then?

[fossil mural]

...which makes it kind of a weird question to ask but i think what they want you to do is just completely ignore the things that aren't integers

so yeah just get rid of those

[lapis finch]

ok

whats next after that

[fossil mural]

for everything else... since they're just listing out the elements of the set, you can just, apply $f$ to all of them, one by one

[vital dew]

bee [it/its]

[lapis finch]

bro how

none of this looks right

[fossil mural]

so figure out $f(-2)$, $f(-1)$, $f(0)$, $f(1)$, $f(2)$

[lapis finch]

i keep getting the null set for half of them somehow

[vital dew]

bee [it/its]

[lapis finch]

wait just for question 1?

[fossil mural]

and then put all of those in a set

and that's the answer

[fossil mural]

yes

[lapis finch]

what about the inverses?

bro i need help with like 5 or 6

[fossil mural]

well if we think about my example from earlier again, where we have 425099 * 238698

think about the component of the answer that comes from 425000 * 238000, which is apparently 101150000000

clearly this has something to do with 425 * 238, but we have three zeroes on both of the input numbers, so we actually have to add 6 zeroes in total

so it's 10^6 * 425 * 238

[lapis finch]

beeeeeeeeeeeeeeeee

[fossil mural]

uhh, yeah i guess that makes sense, those are harder

um

well i guess for (v) you can just, do kind of the same thing but backwards, go through the set and trying to solve each one

so solve f(x) = -5, then f(x) = -3, then f(x) = -1, and so on

...although that would take a while

[lapis finch]

yeah

can we double check i guess? idk if i can do those right

[fossil mural]

i think there's a faster way but it's weirder to explain

[lapis finch]

pls do

[fossil mural]

i'm not quite sure what you mean but, uh, probably?

[lapis finch]

like for 6 I got a square root result

i got 0, and then sqrt 2

[fossil mural]

we still only care about integer inputs to f, so we can just compute all of the small ones, like f(0), f(1), f(-1), f(2), f(-2), etc

if you keep doing that you'll eventually find that they all start becoming really big

and at a certain point you can stop because you're never going to find a number between -5 and 5 by continuing to go further out, you'll just keep getting large numbers

[lapis finch]

interesting

so i just need to be within the limits

[fossil mural]

yeah that seems right

or wait hang on

[lapis finch]

what about -sqrt2?

[fossil mural]

you've got the right idea but you're missing something-

yes exactly

-sqrt(2) is also in the set

because we want all of the solutions to $x^2 + 3 = 5$ i.e. $x^2 = 2$, and those are $\sqrt{2}$ and $-\sqrt{2}$

[vital dew]

bee [it/its]

[lapis finch]

I see

then with 7

I get -2,-1,3,4

do i have to find it in the range -3 and 5?

I did 8 as well but it has square roots again which looks weird

and in set notation

[fossil mural]

yep that's correct

[lapis finch]

nice nice

[fossil mural]

well it's specifically (-3, 5], so 5 is included and -3 isn't, but yeah, you're looking for inputs to f that make the output in that range

[lapis finch]

i see i see

[fossil mural]

yeah that one is going to have square roots in it

it makes sense as a thing to happen because g squares its input, so if you do g backwards you're going to end up with square roots, which are just squaring backwards

[lapis finch]

-sqrt2 and sqrt2 in brackets is what i got

[fossil mural]

which brackets?

[lapis finch]

like this

[-sqrt2,sqrt2]

[fossil mural]

yep that's correct

[lapis finch]

for 9 I think

I would use {} though

because all I get is -3

[fossil mural]

...uh

well i mean

[lapis finch]

that one took a while

[fossil mural]

the answer is {-3}

so i'm not quite sure where you're getting the empty set from

unless you just meant {} as in the type of brackets

[lapis finch]

no because f(0) = -3

i meant that

i worded it bad same thing though

[fossil mural]

well yeah, and that's the answer

[lapis finch]

and then last one for 10

I got -4, -3, 0, 5

I got 0 twice

[fossil mural]

....uh

i can see how you got -4 and -3, but where did 0 and 5 come from

[lapis finch]

f(-1)

i think?

[fossil mural]

oh yes of course

you're right, i just forgot that negative square roots existed

so yeah that is correct actually

[lapis finch]

nice

[spice finch]

could u pls help me with this textbook example instead

[lapis finch]

so this is correct

[spice finch]

i dont think im understanding the concept entierely

after i saw that

[fossil mural]

yes

[lapis finch]

alright great

the other questions are proofs but ill get to those later

i appreciate it

[fossil mural]

...well that's a bit difficult to help with because i'm not quite sure what you mean by "the concept"

like, are you confused about

1. how to even do this method of multiplying numbers
2. why it actually works
3. why we care about it
   ?

[spice finch]

i get the splitting and then i get the part where u take A0 and multiply with B1 etc

and that you have to recursively call it

but when i saw this i didnt get how they got their numbers like 2^4

and how they did their work in terms of what we were doing

[spice finch]

^

[fossil mural]

well the $2^4$ is just from the $2^{2n}$ thing we were talking about earlier

[vital dew]

bee [it/its]

[spice finch]

oh

should i js memorize this

instead of figuring out how it makes sense

[fossil mural]

because to get $(1100)_2 \cdot (1000)_2$ from $(11)_2 \cdot (10)_2$, you add two zeroes on the end to deal with the two zeroes from the $(1100)_2$, and then add two more to deal with the two zeroes from the $(1000)_2$, which is four in total, so $(1100)_2 \cdot (1000)_2 = (11)_2 \cdot (10)_2 \cdot 2^4$

[vital dew]

bee [it/its]

[spice finch]

what does that 2 subscript mean its js showing its in binary right

[fossil mural]

yeah

[spice finch]

i still treat the problem the same way?

[lapis finch]

base 2

[spice finch]

y is bro still here

[lapis finch]

i was gonna ask something but then it felt trivial

[fossil mural]

yeah

just with 2 instead of 10, basically

[spice finch]

ohh ok ty i think ill js memorize that instead of actullay figuring it out

[spice finch]

lol

[gusty wedge]

idk if this is the right channel to ask

but i am getting no clue in what to do

if its 1 to 1000

instead of 1 to 1024

[grand crown]

As in, you know how to solve it for 1024 but not 1000?

[gusty wedge]

yeah

as 1000 is not power of two

i searched google found nothing

only josephus problem i discovered

tried ai too nothing there

[grand crown]

If you always start on the same side before opening every other, do you see how to answer it there

[flat grotto]

It does not matter here

[flat grotto]

well i think you can actually do it if you basewise it

but its 1024 mostly so it oscillates i think, otherwise it wont work if its 1000

so you have 2 passes we can agree on that, so:
1st pass you eliminate every odd number.

2nd pass you start from 1024 (eliminating it) and do the same thing essentially, but taking note that you eliminated every odd one, and are skipping some closed even lockers too. So effectively you are eliminating the multiples of 4.
closed means you are going to open it
So,
1024 - closed
1023 - already opened
1022 - skipped
1021 - already opened
1020 - closed
.....
4 - closed
3 - already opened
2 - skipped
1 - already opened
end

its worded to trick you

unless u learnt some bombastic method to solve that i think doing it manually is fine

[gusty wedge]

I see thanks

[gusty wedge]

Yeah i could do it brute force way

I though i was missing some secret technique

[versed nymph]

Do you have the answer?

I think I saw this somewhere. (Most prolly AIME).

[gusty wedge]

Yeah its from 102 combinatorics

Problem

Book

If you want i can share screenshot of soln

[grand crown]

It wouldn’t be brute force really

The point is that the binary representation would work

The first pass through, you open all the doors whose binary ends in a 1

The second pass through, you open all the doors that end in 10

Third pass through, 100 etc

so the last door opened is just the highest power of 2 that’s less than 1000

that’s only if you start at the same side each time, but the extra issue here is that we switch sides each time

see if you can figure out a way to adapt this logic to that setting

[sinful sun]

Bro I'm tweaking

[steel heath]

yo wassup guys

I'm really new to combinatrics and probability, why is ts so tuff 💔 💔 💔

[hybrid quiver]

it is tuff because it is not soft

[stable temple]

do graph isomorphisms preserve the number of triangles ?

i tried checking the adjacency matrices to see if u can find a permutation for them, it looks like there isnt a permutation but i dont know how to prove it

is there an easy way to check for isomorphism between graphs

[little prism]

yes

[little prism]

no

[stable temple]

thanks

[stable temple]

i tried for n = 1 to 5, and it looks like it holds for 1, 4, 5

[grand crown]

is |G| the number of vertices?

[stable temple]

yes

im thinking this holds for G where $\binom{|G|}{2}$ is even

[vital dew]

ffflick

[stable temple]

or at least, we can reduce it to these graphs, because if the number of edges is odd, then you cant possible make them isomorphic right

[grand crown]

right exactly

the edge counts wont line up

[stable temple]

but, im not sure whether this is enough

[grand crown]

yeah thats the tricky part

it would be nice if we could find a construction for any 4k or 4k+1 vertices

[stable temple]

why 4k/4k + 1?

[grand crown]

that's exactly when the binom coeff is even

|G| (|G| - 1) / 2

[stable temple]

ohh okay

[grand crown]

|G| (|G| - 1) is always even, and only one factor can have 2 as a divisor, so we need it to have 4 as a divisor

[stable temple]

that makes sense, i'll think about this a bit more then

[grand crown]

some properties of complement graphs:

each degree d flips to n - d

cliques turn into independent sets and vice versa

also, if a graph isnt connected, then its complement is, so we need our graph to be connected

(and the complement to be connected)

[stable temple]

so basically, we want to "distribute" the edges among the vertices so that each vertex gets at least one edge, and the sum adds up to |G| choose 2

for n = 4k, we can do (n/2)(n/2) + (n/2)(n/2 - 1)?

so n = 4 = 1 + 1 + 2 + 2 (v1 has 1 edge, v2 has 1 edge, v3 has 2 edges, v4 has 2 edges), when we take the complement we get 2 + 2 + 1 + 1

kind of similar for 4k + 1

e.g. 5 = 1 + 1 + 2 + 3 + 3 or 9 = (4 x 3) + 4 + (4 x 5)

[stable temple]

did i cook ?

[proud flicker]

that doesn't prove that the graphs are isomorphic

well there's no construction to prove it for

[gusty dome]

hi

[carmine vector]

Hi

[rocky torrent]

guys i am gonna make a statement

i think i am too re***d and stupid for discrete math

i just stopped to understand ANYTHING

[hybrid quiver]

67 is a prime

[jovial sail]

SIX SEVEN

[hybrid quiver]

me describing my score on the test (6/7 out of a 100)

[jovial sail]

floor 6/7

[timber elm]

Prove or disprove: If G is a connected graph with cut-vertices and u and v are vertices of G such that d(u, v) = diam(G), then no block of G contains both u and v. Is that statement correct?

[versed mountain]

Im solving this question by assuming towards contradiction that f is not injective. I need to show that g is not equal to h but I'm not sure how to use the assumptions to get to that

[spare slate]

Consider defining $g$ and $h$ to be constant maps.

[vital dew]

Civil Service Pigeon

[desert bluff]

Hello, anyone here familiar with this style of Bernstein proof?

Needed help understanding the last part of the proof where they conclude P~Q

[quick folio]

The A_i’s and B_i’s are meant to be the set of all elements in A and B that eventually get sent to something outside of C and D if you apply f enough times

So, when you remove all the A_i’s and all the B_i’s, what you are left with by construction are all the things in C and D that always stay inside C and D no matter how many times you apply f. This is what P and Q are, and using this definition you can verify that they are equivalent

[desert bluff]

I don't quite get it. Initially I thought the point of applying f and g alternatively was to basically 'connect' the 'orphans' of Set A, to B, and then force the so initially A_1 is the 'orphan' set, which we connect to B_1 using f, we then disconnect elements in B_1 from A_2 which were meant to be connected to it via the mapping g. We continue doing this exhaustively till infinity

Is this intuitive understanding correct?

[quick folio]

What do you mean by orphan?

[desert bluff]

Since g(B) is a subset of A, 'orphan' refers to set of elements in A that do not get mapped to with elements in B via g

[quick folio]

Hmmm, okay, yes that is the rough idea of what the proof is doing

That is right

[desert bluff]

This is sort of what I understood using Gemini, not sure if the thing Hallucinated or I didn't understand it properly 😅 but I would like to understand the motivation behind applying f and g alternatively

What are we intuitively trying to achieve?

[quick folio]

I will be back in half an hour

[desert bluff]

Sure, that works 😀

[desert bluff]

NVM I think I understood what is happening here. Please correct me if I am wrong.

I think we are trying to define completely new mapping say h from A->B where h is defined as follows:

For every A_i, h=f. And for P=A-UA_i, h=g^-1

This makes sense to me since for every A_i, we have B_i defined and is equal f(A_i) for the remaining, since A_1 is a subset of A_i therefore P is a subset of A-A_1=C so we have a g^-1 already defined for us

After we have exhausted the A_i through mapping using f, we map the remaining using g^-1

[tawdry rock]

Anyone knows a book about recurrence relations?

[stable temple]

im not so sure how to do this one

obviously we need hall's theorem, and i learned about the defect form of hall's, but this looks like we need the opposite of a defect if that makes sense

[coral parcel]

I don't know about "defect form", but it looks like that's just a matter of giving each person two distinct "job slots" and then using Hall's theorem to assign jobs to job slots instead of directly to people.

(Each set of k job slots will come from at least k/2 different persons, so there will be at least 2¸k/2 = k jobs available to distribute between them, as needed by Hall).

[quick spade]

Are those discrete

[grand crown]

wdym by “those”?

[quick spade]

It’s these

[grand crown]

what r u referring to exactly

the entire function?

or the things u highlighted

or the things u wrote

[quick spade]

Both

[tacit breach]

cool!

[sinful tundra]

what does this mean? I'm confused with all the brackets. wht is it saying?

[spark field]

Not [p implies (q and p)]