discrete-math

[hexed temple]

Implies???

[vapid drift]

how to definiton in engligh Like v: if both a and b is true then true

[brave rock]

and

[vapid drift]

i thought upside u is and

[brave rock]

No.

[vapid drift]

can you paste the truth tables for them i dont know what to search up

[brave rock]

$A \vee B$ means ‘$A$ or $B$’.
$A \wedge B$ means ‘$A$ and $B$’.

[vital dew]

boytjie

[vapid drift]

yea thats what i said

im aksing english for implies

[brave rock]

Then I don't know what you're asking, because you just wrote the English word ‘implies’

[vapid drift]

wait a and b for if its true

can it be for false

[vapid drift]

can you do this for implies

[brave rock]

$A \to B$ or $A \implies B$.

[vital dew]

boytjie

[indigo swift]

Not sure if this is the correct place to ask, but I think this would fall into discrete math. Is there a systematic way to select six integers from 1,...,24 such that no number in the six chosen numbers can be expressed as a sum of other of the chosen numbers?

[ivory badge]

can you name one such collection of numbers?

[indigo swift]

I thought that I could use powers of 2, but I can only get 1,2,4,8,16 and for the last number this seems to fail always

[brave rock]

A really silly hint: the sum of big numbers is going to be big

[ivory badge]

consider how binary numbers in n digits can get all the way up to 2^n - 1

so clearly powers of 2 won't work

[indigo swift]

I'm new to binary numbers so I'm not sure I understand your hint

[brave rock]

This has nothing to do with binary.

[vapid drift]

I missed you

[indigo swift]

If we loosen the condition from 24 to 32, then the powers of two will work I think. However I would like to figure out a systematic way to construct such a set from the given conditions.

[ivory badge]

its not a binary thing, I'm just saying it won't work clearly

have you considered starting from big numbers

[meager prawn]

Think harder about this

[brave rock]

You can actually do better than just six with this observation in mind

[indigo swift]

Okay 11,17,20,22,23,24 works, but it took stupidly long for me to find out. How could I have deduced this without guessing and checking?

[brave rock]

24, 23, 22, 21, 20, 19 works too :)

Because they're big numbers and their sums are big (greater than 24)

You can do even better than that. 24, 23, ..., 13, 12 is another such set of 'big' numbers :)

My hint was actually helpful hm

[meager prawn]

An interesting variant:
Let n be of the form 3k+2
Find a subset S of k+1 elements in Z/nZ such that for all a,b in S, a+b is not in S.

Reformulation without Z/nZ: S a subset of {0, ..., n-1} of k+1 elements such that there's no a, b, c in S such that a+b = c [n]

[vapid drift]

please explain to how to solvi

[brave rock]

Hint: there is a formula for the sum of the degrees of a graph

[vapid drift]

number of edges = sum of degrees/2 ?

[brave rock]

I've said all I need to

[vapid drift]

if thats the equation i still odnt know what is going on. I want to understadn

[meager prawn]

It wasn't meant for you, but sure

For anyone looking for a solution, there you go

[vapid drift]

if the ans of that equation is integer value then it exists?

[brave rock]

No.

[vapid drift]

is it if its even it exists

[brave rock]

No.

[vapid drift]

Then what does the answer need to be to exist

[brave rock]

If a graph exists, then that equation holds.

The equation says nothing about a graph existing.

[vapid drift]

its the wrong equation?

[brave rock]

The equation is correct.

I suggest you think about it.

[vapid drift]

what is the relation between edges and degree

[brave rock]

You have already written down the relation between the number of edges and the sum of the degrees

[vapid drift]

how to find edges for this one

[brave rock]

I'm not gonna answer any more questions until you've thought this through yourself.

[vapid drift]

nooooo please

[ivory badge]

well, it was a more efficient method than the stuff I was thinking lol

[vapid drift]

what is the relation to the degree and vertices

[ivory badge]

this relates edges and degrees

[vapid drift]

ok how to know the number of edges

[ivory badge]

that tells you the number of edges if it's a graph

think for yourself a lil

[vapid drift]

theres no more time to think

[brave rock]

Then I guess this will never get solved

[vapid drift]

noooo please

exam in 5 hours

[brave rock]

All the more reason to think

[ivory badge]

you should study well before exams, not just learning material the day of I say hypocritically

[brave rock]

Being a hypocrite doesn't mean you're wrong

[ivory badge]

if you don't know it already you're kinda already taking an L

[vapid drift]

do you guys know the answer?

[ivory badge]

yes, but you'll have to figure it out yourself

[vapid drift]

whats the first letter

is it y or n

[ivory badge]

think for yourself or fail idk :)

[vapid drift]

in the equation of sum of all degrees. does that mean i add all of them even if its repertitve

[ivory badge]

why would you think yes or no?

[vapid drift]

its been 8 hours

[vapid drift]

no

[ivory badge]

edges = sum of degrees over 2

what is the sum of degrees

[vapid drift]

its either 11 or 6

guys please i swear im begging

[ivory badge]

i don't know where you got 6 from

[vapid drift]

okay so its 11

11/2

is 5.5

thats not a integer

[ivory badge]

yes, as was mentioned many hours ago

what now

[vapid drift]

it doesnt existing

if only i knew how to draw something from the number of edges and degress known

[ivory badge]

hard to draw something that doesn't exist

[vapid drift]

interesting how do you know something doesnt exist

[ivory badge]

you just said "it doesn't existing"

why

[vapid drift]

because 11/2 is not integer

[ivory badge]

so why ask this

congrats the problem is solved

[vapid drift]

so what your implying is that since is not an integer ans it doesnt exists

[brave rock]

Is there any graph that has 11/2 edges?

[ivory badge]

that's what you said?

[vapid drift]

no how can a graph have have a edge impossible

wait is the number of vertices always = number of edges +1

[brave rock]

No.

[remote island]

Consider a graph with five vertices and no edges

[vapid drift]

impoosible

[remote island]

WHAT

Let G = ({1, 2, 3, 4, 5}, {})

[brave rock]

Best of luck on that exam

[vapid drift]

how can you have 5 vertices and no edges

an edge is what connects the vertices

[remote island]

As an analogy to a 'real-world' example, consider having a collection of five people, {John, David, Fred, Paul, Murgatroyd}.
You can imagine having a vertex for each of these five people on a graph, and each edge between two vertices must show that the two people represented by those two vertices are friends. So for example, if John and Fred are friends, there should be an edge between the vertex representing John and the vertex representing Fred.
Now, what would the graph look like if no two of those five people were friends?

[vapid drift]

it would not connect

[remote island]

Right, so what would the 'shape' (diagram) of the graph look like on paper?

[vapid drift]

there would be a hole

[remote island]

A hole?

[vapid drift]

does that mean if its odd when you add the degrees there wont be a graph

[remote island]

More precisely, you cannot have a graph where the sum of all degrees is an odd number
Because each edge is counted twice when you are counting the degrees (a consequence of each edge having two endpoints)
But the point of this specific example I wrote just above is something else. It's to illustrate that you can have a graph with some vertices and no edges.
In a more rigorous sense, you can even have a graph with no vertices and no edges, a graph G = ({}, {}).

[vapid drift]

i knew it

how to know degree sequence

[ivory badge]

do you know how to find the degree of a vertex

[vapid drift]

no

to count the number of edges which has that vertx as an endpoint.

[remote island]

Just to be sure that you understand that argument, would you please write down a graph with three vertices and four edges?
Please think about it very carefully.

[vapid drift]

3 is odd hence impossible

[remote island]

Incorrect argument

And what you wrote down is not a graph

You see, try to understand graphs not just as shapes, but by their mathematical definition too

[vapid drift]

its worth 1 poingt

[remote island]

what

1 point?

[vapid drift]

yes

[remote island]

1 point in what context?

[vapid drift]

how to test this

[ivory badge]

I can't tell what you mean to test

[vapid drift]

how to test if its true

if its surjective

[ivory badge]

f:A->B is surjective if for every b in B there is a in A with f(a)=b

[vapid drift]

does that mean that all y values must have only 1 x value

Does this prove its subjective

,rotate

[quiet eagle]

@fossil mural I got my confusion cleared up. Now I can't come up with a way to connect the injectivity of f with the surjectivity of g. Could you give me a small clue for one of the two implications?

[kindred bolt]

can somebody help me with counting

I am going crazy

how do I know when can I use factorial, permutations or combinations. I get that permutations is used when there is no repetition and it needs to be formed in arrangements but I find it hard to recognize when do I need to use factorial or permutations.

[hard stone]

Factorials are used in permutations

nPk = n! / (n-k)!

So for example nPn = n! / 0! = n!

This means that there are n! ways to order n objects

With nCk you just have to divide out by an additional factor of k!, so nCk = n! / (k! (n-k)!)

Hope this helps

[kindred bolt]

is there a difference if I put nCr? cause my syllabus goes that way

[hard stone]

Between nCk and nCr? No, it's just a different letter for the variable name

nCk means you choose k things out of n things (order does not matter, no replacement) whereas nCr means you choose r things out of n things

[weary tiger]

Is it just me or did they forget to define M and N in the theorem statement?

[opal crescent]

they meant P and Q I guess instead of M and N

@weary tiger

seems to fit with the proof

[weary tiger]

yeeah that explanation makes this theorem make more sense

thanks!!

[vague scaffold]

how would you read this?

[iron marsh]

I'm not sure what you mean

[vague scaffold]

I don't know how to read this to understand what it means; I understand there's "Big O" notation here, but I'd like to be able to read this in english to myself

maybe this is a chatgpt question but i just dont want to get an incorrect response. i'm confused enough

[lone linden]

Why do you ask chatgpt for math? You realize it gives false information

Just saying

[vague scaffold]

That's why I figured I better ask humans; it's not quite there with the logic

So, here's the "answer" right above it

I'd like to know how to read a series expansion to understand it's describing this kind of thing. I don't know where to learn the connection between these ideas, I'm not a math guy just a hobbyist trying to learn

[dusky socket]

hello

im having difficulty writing this disjunction as a conjunction

ive gotten this far but i can seem to eliminate the final disjunction

im aware steps 2 and three are literally useless sorry 💀

[ivory badge]

You did use a move like

-(A and B) = -A or -B

[dusky socket]

yeah i think its the de morgan law?

i think i'm supposed to apply it again but i cant figure it out aaa

[ivory badge]

What if, say, we wanted to use A or B to get a statement in terms of and

What’s $\neg(\neg A\land\neg B)$

[vital dew]

The great Sharp

[dusky socket]

oh boy

would it be A|B?

[ivory badge]

Should be yeah

[dusky socket]

oh!

i'm sorry i don't understand how that helps me aksjhd

oh wait

~(~r&(p&q))?

OH

THANK YOU SO MUCH

[ivory badge]

[dusky socket]

AAAAAA

[dusky socket]

whats the difference between an exclusive disjunction and a regular one?

i understand that the exclusive one is like... it HAS to be one OR the other

but why is a "regular" disjunction.. softer?

ah wait i understand

how would i be able to write an exclusive disjunction as a regular one or a conjunction?

[dusky socket]

got it nvm

[solid python]

Hello @everyone

What is partition in relation?

[meager prawn]

context ?

[timber barn]

@snow axle quick question about the previous problem, the really hard way but correct would be finding the elements from a_1 to a_8 lets say and in that way to find the recurrence relation or?

[snow axle]

not hard

could you send the problem again

[solid python]

like we have given some relation r={1,2,3,...n} and how to find partition on that

[meager prawn]

the partition that defines the equivalence classes ?

[solid python]

Yes

[meager prawn]

each set of the partition of a set A by a relation R is a {a in A | a R x} for a given x, which you'd call the representant of the class

[solid python]

Ok

[meager prawn]

such that $A = \bigcup_{a \in A} \bar{a} = \bigcup_{c \in A/R} c$

[timber barn]

like finding a_1, a_2......a_10 so I can more easly find the relation after

[vital dew]

Bezier graduate

[meager prawn]

with the second one being a disjoint union

[snow axle]

are you trying to prove this?

[timber barn]

oh wait wait wrong problem

this one

sorry

[snow axle]

by the equation above, you have a closed form

[timber barn]

I need to find the recurrence relation

there is a short cut I believe

[snow axle]

can’t you get that from the closed form

[timber barn]

but is there a way of finding the first 10 elements so I can find the relation

[timber barn]

I am talking about other way of solving

will it work that way?

[snow axle]

yes, calculate the right side for each n less than 10

[weary tiger]

a, b and c, d are 4 lattice points on the plane such that a, b and c, d cannot be separated by a line on the plane.
consider those shortest taxicab paths connecting lattice points a, b also consider those shortest taxicab paths connecting lattice points c, d.
QUESTION: what is a/the longest distance of overlapping among all pairs of shortest taxicab paths connecting lattice points a, b and connecting lattice points c, d? or what is an algorithm to find a/the such longest distance?

oh, excuse me, to make it meaningful to think/answer, positions of a, b and c, d cannot be unbounded...

[timber barn]

um now I have problems with this

I tried math induction but I think its not equal

[vague scaffold]

This expression is a rule for something I'm playing with, we're only allowed to use whole numbers 1,2,...etc, is there an easier way to say this?

[iron marsh]

@vague scaffold did you make any head way with the projective geometry stuff?

I wasn't able to grasp all of it, but what you were finding was pretty interesting

[coral parcel]

It's definitely false 0 < m < n.

[stray reef]

are you sure you didn't mistype this

[coral parcel]

If m > n, just multiply across, getting m² - mn < mn + n², which rearranges to m² - n² < 2mn, which is always true.

[vague scaffold]

I did make some progress. I am getting close to being able to make some statements that sound educated

[vague scaffold]

This is a good way to write this for my purposes. I thought it was always true too, and then ran into some bugs 😄

I didn't mention that in this system m>n, but it is, which means in our case it should always be true-ish... Even then though, m=5 and n=2 still fails for instance

[coral parcel]

Actually it's true iff sqrt(2)-1 < n/m < 1

[vague scaffold]

what brought you to that? 🙂

might be the last piece of this puzzle

[coral parcel]

I took m² - n² < 2mn and divided through by m², getting a quadratic inequality in n/m.

[vague scaffold]

how strange. i love it

i'll take the time to write my 'conjecture' today and share it. simple, but interesting

[vague scaffold]

So, at the start of this idea, I'd need to write "Let m be a whole number greater than n, where sqrt(2)-1 < n/m < 1" to set up my argument?

[coral parcel]

The "< 1" encodes m > n; you only need one of them.

(Also please don't call your numbers M and N alternately with m and n -- math notation is case-sensitive!)

[vague scaffold]

I think, in math people words, you just said the <1 isn't necessary because if m>n then of course it's less than 1

and i fixed the m/n lowercase for ya 😉

is there a mathy way to generate rationals that ascribe to the sqrt(2)-1 < n/m, or calculate each individually?

[coral parcel]

One approach would be to choose m first, and then pick n between m·(sqrt(1)-1) and m.

[sterile turret]

if |X| > a, then x <-a or x>a if I'm trying to find the inverse of the following, not only do i negate everything but do I also switch or to and?

[iron marsh]

What do you mean the inverse?

[sterile turret]

converse, inverse, contrapositive

[snow junco]

simply |x|<=a no?

Or apply demorgans rule to your statement

^(x<-a or x>a)=(x>=-a and x<=a)

[sterile turret]

yes! okay i got it right

i was unsure about the or/and part

Thank you

[iron marsh]

It's important to note these are all different things

[sterile turret]

understood, when you asked what do you mean the inverse, i was trying to add context if that makes sense

[iron marsh]

Ah, I gotchu.
Personally, I forgot what the inverse of a logic statement is. Unless it's just the negation of a statement, it just doesn't come up that much.

Inverse is also a very broad word that is used all the time. So context is definitely important when asking about it

[sterile turret]

Yea you're telling me, I was searching through the textbook and it pulled up EVERYTHIGN

[iron marsh]

Is this a discrete math textbook?

[sterile turret]

Discrete Mathematics with Applications by Thomas Koshy

[dusky socket]

i don't know how to write "at most" 🥲

[iron marsh]

Are you familiar with how to do exclusive or?

[dusky socket]

got it on a different channel adkjf thank you though!!

yes i think so

but we can only use conjunction disjunctions and negations

this was the correct ans (~p|~q|~r)&(p|~q|~r)&(~p|q|~r)&(~p|~q|r)

i got the hint to write them as conjunctions of conditions

[vague scaffold]

Ok. Here's what I was looking at. I find this strange

whole numbers in the harmonic range always produce a semiperimeter (m(m+n)) of a pythagorean triple

obviously i made n=m-1 so it's the same algebra, but any harmonic range with whole numbers produces a triple

[odd garden]

Can someone explain this to me in simpler terms...

[iron marsh]

I'm not familiar with gamma notation, but I am with big 0.
Based on the if and only if statement, essentially |f(x)| can be squeezed between two constant scalars of |g(x)|, as x gets large.

[fossil mural]

(gamma notation...?)

[iron marsh]

Omega. My bad

@odd garden here's a good example.

Here f(x) is x-sin(x), and g(x) is x.

Note that as a-> infinity, these bounds become better approximations for x-sin(x) as x gets large

Here's a video of the lines as a goes towards infinity. Notice that no matter what, x-sin(x) is always bounded by it for x large enough

Hope this was helpful

[odd garden]

This is for Big O yes?

[iron marsh]

The definition you were asking about. Which is Big Omega

From what I understand, Big O bounds f from above, whereas Omega notation bounds f from below. So this Big Omega just bounds the function from above and below using the same type of function.

[lunar hill]

Why is logic a branch of discrete math?

[iron marsh]

First-order logic is a binary problem: is it true or is it false. Discrete math is simply dealing with math on countable sets.

Also, binary and circuits share a similar language. It's good to learn it

[iron marsh]

I encourage you to check to see if this holds at all for significantly larger numbers (like 1000).
Maybe it was just a coincidence, but seeing if it holds for larger numbers would definitely give it merit.

Furthermore, if you find there's merit to the idea, perhaps you could try to prove it

[earnest basalt]

did I do this right?

[snow junco]

If the green is in the set yes

[earnest basalt]

noice

[earnest basalt]

did I get the duel right?

[iron marsh]

Look carefully. What you wrote is just U (the universal set)

[earnest basalt]

🥶 Your right

[earnest basalt]

does this work?

with a duel we basically reverse the set

my issue is how does () in the problem influence this

🤔 do they even matter with set thoery

[iron marsh]

Multiplication doesn't really mean anything

Okay, if I remember correctly, the dual of a logic statement negates all inner and outer terms, and swaps unions and intersections with each other

[earnest basalt]

ok I see so we basically reverse EVERYthing

what does that mean for NOT tho?

if it negates all inner and outer terms the Not just gets removed right?

[iron marsh]

Yea. Also, note that A-B=A n not(B)

[earnest basalt]

n?

[iron marsh]

Intersect

[earnest basalt]

why would it not be not(A) n not(B)?

[iron marsh]

Well, think about it for a sec

P.s. we aren't talking about duals yet, just how to write set minus in terms of negation and intersection

[earnest basalt]

ok yeah makes sense lmao

[earnest basalt]

does not also get negated with duals?

[iron marsh]

Yes, true gets replaced with false and false gets replaced with true

But this shouldn't be too surprising, because not(not A) is just A

[earnest basalt]

so I should have Not(A n B) * Not(A u B) * Not( B n C) * Not (B u C) n Not ( A n C) * Not (A u C)

[iron marsh]

What is *?

[earnest basalt]

and

wait I'm dumb that's wrong

[iron marsh]

Every time you see a n or u, swap it with the other.
Then negate every term, even compositions of terms

[earnest basalt]

yeah it's just the minuses

[iron marsh]

For example, the dual of
AnB is not(not(A)u not(B))

[iron marsh]

That's why I brought this up, so we can get rid of the minuses

[earnest basalt]

wouldn't the nots cancel?

[iron marsh]

No, not exactly.

We are negating the full term (not(A)u not(B)), it does not just cancel out ( you need to account for Demorgan's Laws).

[earnest basalt]

not(((A∪B)∩ not((A∩B)))∪((B∪C)∩ not((B∩C)))∪((A∪C)∩not((A∩C))))

without making like

any changes just removing the minuses

[earnest basalt]

Not((AnB) U Aub) N ((not(BnC) U BuC n Not(Anc) U AuC

@iron marsh does this work?

[earnest basalt]

duel for this

[odd garden]

Show that log base 2 3 is an irrational number. Recall that an irrational number is a real number x that cannot be written
as the ratio of two integers.

how do I approach this. This in prime and gcd chapter

[weary tiger]

Assume $\log_2(3)=\frac{a}{b}$

[vital dew]

plazzi

[weary tiger]

So u assume that log_2(3) is rational

$\log_2(3)=\frac{a}{b} \Leftrightarrow b \log_2(3)=a$

[vital dew]

plazzi

[weary tiger]

Solution:

[iron marsh]

Ummm, 2^b *3 is not odd

[weary tiger]

Uhr

Uhm

Fck

Yes

[brave rock]

||just consider prime factors, you had the right idea.||

[iron marsh]

Dividing by 2^b will get you there though.

[brave rock]

Why would that do it

[weary tiger]

I did a mistake

[iron marsh]

||2^{a-b} is some integer power of 2, and that is never 3||

[weary tiger]

Wait a second

[brave rock]

||So you need to prove that an integer power of 2 is never 3... boils down to a prime divisor argument hm||

||seems more straightforward to just point out prime divisors immediately||

[iron marsh]

I don't know what you mean by that

[vital dew]

plazzi

[brave rock]

||2^b * 3 has a factor of three, 2^a does not, ergo they are not equal.||

[weary tiger]

Too dumb to memorise the laws for exponents

[iron marsh]

Actually now that I think about it, what they wrote earlier was just wrong, so this argument doesn't matter anyways

[iron marsh]

Now this will work!

[weary tiger]

Yeah $2^b \cdot 3 \neq 2^{\log_2(3) \cdot b}$

[vital dew]

plazzi

[weary tiger]

Math with numbers is hard 😭

[iron marsh]

One small thing worth mentioning, either a or b can be negative (you only need to check if one is), so make sure you address that case (it's easy)

[weary tiger]

This shouldnt disqualify my proof

It should still work

[iron marsh]

It doesn't account for all possible rational numbers.
Your proof works wonderfully when a and b are positive.
Now you just need to address the case when the signs for a and b are different.

[weary tiger]

Let b negative, than we have 1/3^|b|

Or is there any law for negative exponents that i forgot

[iron marsh]

Well 3^{b}<1 and 2^a>=1

So they can never be equal in this case.

There's one final case to check. It's an easy one, but it's worth mentioning.

[weary tiger]

If both <1

Let him prove that

[iron marsh]

Nah, that's not relevant, since -a/-b=a/b, so we don't care about that case

If they have the same sign, we can just assume they are positive from the start

[weary tiger]

Yes, but the last case is the same since 3^b>1 and 2^a<1

[iron marsh]

There is exactly one case where 2^a=3^b. What is it?

[weary tiger]

Since a/b

B cant be 0

[iron marsh]

Good.

All 3 of those cases are sufficient to show this can't happen

[weary tiger]

That was in his definition

[weary tiger]

.

Two integers, and with that i started

[iron marsh]

Yes I got that. The point is that there is one case when 2^a=3^b, but it is worth mentioning that since b cannot be 0, that possibility is excluded.

[weary tiger]

But isn't this case already excluded, since we define $\mathbb{Q}= {\frac{a}{b}| a,b \in \mathbb{Z}, b \notin {0}}$

[vital dew]

plazzi

[iron marsh]

Yes

[chilly dew]

The equality in red is just wrong right

any idea how to finish then

i.e. to prove that
(x^2 + y^2 + z^2)^2 >= 3(x + y + z)
given that x, y, z are positive reals such that xyz = 1

[iron marsh]

yea, that equality is incorrect

I think that just needs to be a greater than or equal to

[chilly dew]

(xy + yz + zx)^2 = 2xyz(x + y + z) + [(xy)^2 + (yz)^2 + (zx)^2] >= 2xyz(x + y + z) + [(xy)(yz) + (yz)(zx) + (zx)(xy)] = 3xyz(x + y + z)

figured it out

[iron marsh]

Cool. Good job on fixing it

[chilly dew]

Thanks!

[iron marsh]

If you don't mind me asking, how did you come to this conclusion?

Specifically the inequality

[chilly dew]

for any real numbers a, b, c it holds that a^2 + b^2 + c^2 >= ab + bc + ca. in my case I took a = xy, b = yz, c = zx

and in general, a_1^2 + … + a_n^2 >= a_1 a_2 + … + a_{n - 1} a_n

[iron marsh]

I did not know that. Cool!

[chilly dew]

as this is equivalent to (a_1 - a_2)^2 + (a_2 - a_3)^2 + … + (a_{n - 1} - a_n)^2 >= 0 which is clearly true

[novel ore]

why do we define the cardinal number as the equivalence class? shouldn't it be related to order or a number in some way?

or is it just that we give the equivalence classes names

which happen to be numbers

[ivory badge]

So, 1) without choice, we can’t always well order a set

That mean no bijection to any ordinal

2. the ordinal version of it is the least ordinal in that equivalence class

[novel ore]

oh i haven't learned what an ordinal is yet

[ivory badge]

Ye, there are cardinals but they’re just representatives of the classes in the way I usually see them

[earnest basalt]

is my duel for this right?

[iron marsh]

Yeah, looks good. You lowercased B and C in some cases, but that's all I see.

[earnest basalt]

thanks man!

[iron marsh]

Oh wait, there is something

Every A,B, and C need to be negated as well

It'll get a little clunky, but duels be like that

[earnest basalt]

wdym?

ok so the other ones need to be negated

[iron marsh]

Remember, every expression, inner and outer needs to be negated

This also includes the sets A,B, and C

[earnest basalt]

I changed the definitions tho

A - B = A n Not(B)

[iron marsh]

This is going to suck, but here we go. For the dual, we swap all the unions with intersections and vice versa, and we negate each expression
Here is a list of every single expression in this:
largest] ~(((AUB) n ~(AnB)) U((BUC)n~(BnC)) U ((AUC)n ~(AUC)))
2nd largest] ((AUB)n ~(AnB)), ((BUC)n~(BnC)), ((AUC)~(AnC))
2nd smallest] AUB, ~(AnB), (BUC), ~(BnC), (AUC), ~(AnC)
smallest] A,B,C

A,B,C should also be negated

[elfin adder]

Hey guys, if I had a graph G such that it had the same number of vertices as edges, would it admit a planar embedding?

[iron marsh]

Does every edge connect their ends to a vertex?

I imagine not, because...such a graph wouldn't be possible

This is a bit above my knowledge, but here's a theorem I found on wikipedia about this.

It is known as kuratowski's theorem

[odd garden]

Can someone please explain the third line where did they get n-1 in the solutions

[iron marsh]

Since both n and k(b-1) are integers and n>k(b-1), k(b-1) can be at most n-1, hence that inequality

[odd garden]

What does it mean if they are integers?

[iron marsh]

Like what is an integer?

[odd garden]

Like what’s the point of substraxting 1

[odd garden]

No but what’s the reason behind it

[iron marsh]

Well that's simply because of what you are trying to prove

[odd garden]

I just can’t understand how we added it

[iron marsh]

that ciel(n/k)=floor(n-1/k)+1

[iron marsh]

Do you understand what I just said here?

[odd garden]

I did understand that all of them are integers but the second part no

[iron marsh]

Since k(b-1) is an integer, it can be (n-1), (n-2),..., and so on, all the way to -infinity

But it can't be n, (n+1), (n+2),... because of the inequality n>k(b-1)

[odd garden]

We replaced “b” by “n”?

[iron marsh]

No

Because again, n-1 is the largest value k(b-1) could be.

Let's use some actual numbers in this.
New problem btw.
Let k be a positive integer (to reduce the possibilities) such that 3>k. Since k is a positive integer, what possible values can k be?

[odd garden]

k-3

[iron marsh]

No no, I am asking about actual numbers

There are only a couple of actual numbers k could be

[odd garden]

2,1,0

no 0

[iron marsh]

Well, not 0, but yes

So k is either 2 or 1.

[odd garden]

yes

[iron marsh]

So that means that 2>=k, right?

[odd garden]

yes

[iron marsh]

That's exactly what is happening here

Replace 3 with n and 2 with n-1

[odd garden]

but in your new problem we can pick between 2 or 1?

[iron marsh]

Of course, but if k is 2 or 1, the inequality k>=2 alway holds

[iron marsh]

In this problem, we have an infinite list of possibilites for k(b-1), but the largest value it could take is n-1 with the same logic we looked at with my simpler problem.

[odd garden]

Okayy

[pale sorrel]

how to show equality between these two power series? m,n range over the integers. is there a nice combinatorial argument?

$\sum (-1)^n q^{(4m+1)^2 + 8n^2} = \frac{1}{2} \sum (-1)^n q^{(2m+1)^2 + 8n^2}$

[vital dew]

dominic0859

[pale sorrel]

im not completely sure of the identity, but i tested out the first 1000 coefficients on python and it seemed to work

[iron marsh]

The only thing you care about is q^(4m+1)^2 and q^(2m+1)^2.

Focus on trying to find a relation between those two

[pliant bramble]

guys if sum of Uk = sum of Un and lets say they start at i = 1 and end at i = n, can i say that Uk = Un

[iron marsh]

The problem suggests that 2*q^(4m+1)^2=q^(2m+1)^2

So...check to see if it's true

[pliant bramble]

for this question

[iron marsh]

No. Easy example: let U_k={1,1,1,1,1...,1} and U_n={n,0,0,0,0,...,0}
Then the sum of U_k is n and the sum of U_n is 0, but these sequences are definitely not the same.

[pliant bramble]

oh yeah

[iron marsh]

I don't like the n,k notation here being mixed with U_k and U_n.
They are representing different things, so it's just bad notation

[pliant bramble]

can you give me any clues for the exercise

[iron marsh]

I'm not sure what it's saying.

[pale sorrel]

i mean it cant be (viewing that equality as one over series). if im summing over squares that are 1 mod 4 i completely miss the squares that are 3 mod 4. but the right hand side sums over all odd squares

[pliant bramble]

it wants the sequence Un

the expression

[iron marsh]

Yea, uh, ignore me

[iron marsh]

This should be helpful: $\frac{n^2+n}{3}=\frac{2}{3} \left(\frac{n(n+1)}{2}\right)$.

[vital dew]

dackid

[pliant bramble]

yea i showed up the sum of k, k=0 to k= n

n(n+1) = 2 times the sum of k

then 3 times the sum of Uk = 2 times the sum of k

i found that Uk = 2k/3

this is why i asked if lets say sum of Vn = sum of Un was equivalent of saying Vn = Un

[opal crescent]

if you denote $S_n = \sum_{k=0}^n u_k$, you have $$u_n = \sum_{k=0}^{n} u_k - \sum_{k=0}^{n-1} u_k = S_n - S_{n-1}$$

[vital dew]

_aplatypus

[opal crescent]

even if that right hand side they gave you wasn't so nice, you could still use that

@pliant bramble

[pliant bramble]

looks like telescoping series

[opal crescent]

very baby telescoping indeed

[pliant bramble]

the answer is indeed 2n/3

thanks

[iron marsh]

I mean if you just want a sequence, 2k/3 does the job

[elfin adder]

yes! i realized that it works since we're not restricted to G being connected

but I think if G is connected, then it will be planar however i'm not too sure how to prove that

[iron marsh]

@elfin adder here's the thing: I really don't think the condition that G has the same number of vertices and edges is strong enough to stop K_5 or K_3,3 from being a subgraph in G

[vast jolt]

Hi everyone, I’ll be starting Discrete math for the spring and I wanted to know if anyone has any good book recommendations or resources.

[ivory badge]

Getting K_5 with a connected graph would be pretty difficult I believe

But the fact that you can’t have like subdivisions is harder to think about. If you had such a graph with n points though then adding another is just dropping it in and connecting it to one of the existing vertices?

The only things I can imagine coming up are (isomorphic to) like n cycles and trees stuck together

[iron marsh]

I stand corrected.

[ivory badge]

*and they’re connected

Since obviously just throw in dummy points if not

You can’t have them as like, minors or such either but you still run into “you can’t make those shapes at all from circles and trees”

[iron marsh]

My logic was to construct a graph G such that it has eithr K_3,3 or K_5 as a subgraph. At the start we have |E|>|V|. But in order to add a new vertex and keep G connected, it must have a corresponding edge, so |E| will always be greater than |V|.

So a connected graph G with |E|=|V| and K_5 or K_3,3 as a subgraph does not exist.

By Kuratowski's Theorem, G admits a planar embedding when |E|=|V|.

Boom!

[ivory badge]

If you tried subdividing the graphs you get the same “no no no the edges increase too”

All you get is like a grammar iteratively replacing points with n-cycle circles and trees

[iron marsh]

I only had enough brain power tonight to pull this off. You're losing me sharp 😅

[ivory badge]

ok imagine starting from a single vertex

And let’s put some open ended edge on it

Only thing we can do is add a vertex to it

Can’t get a 2 cycle since it’s not a multi graph

So now just get a triangle

*this kind of graph will always have a cycle, I think

[ivory badge]

And from here the only real options are to branch off or subdivide the loop?

[native dragon]

isn't no K5 and K3,3 subgraphs too weak of a condition? The theorem demands no subdivisons of K5 and K3,3

[native dragon]

I see no reason why you couldn't draw a K5 and add a bunch of vertices connected to nothing

unless you wanna add the condition that it must be connected

which in this case using minors might be more helpful

[iron marsh]

I guess I'm not familiar with what a subdivision of a graph means.
My bad

[ivory badge]

Yes connected

[ivory badge]

If you subdivided K5 or K3,3 you’d still end up with E > V

[ivory badge]

Re: connected

[native dragon]

Ah I mostly thought that deleting vertices/edges and contractions would either keep |E|=|V| or decrease |E| more quickly than |V| if the graph was connected so there was no way to a K5 or K3,3 minor

[ivory badge]

Well sending like •-•-• -> •-• still has 1 more vertex than edge

[native dragon]

oh oops I mistyped

[ivory badge]

or in reverse, since we want to find a graph with K5 or K3,3 as a minor

[native dragon]

I meant in a sense that it kept the diff btwn vertices and edges consistent

or it loses edges more

because in that case |V|-|E| is 1 before and after contraction

[ivory badge]

You can’t really add onto the K5 or K3,3 graphs to balance it out since you’d just be grafting on a tree if you did it iteratively?

[native dragon]

huh? I'm not?

[ivory badge]

So it’d be in subdividing just the K5 or K3,3 graphs

And that’s gonna keep the V-E difference pretty similar? Especially since edges are greater

Adding in any vertex is gonna add at least one edge

[native dragon]

I was trying to say that all the minor operations can't decrease |V| more than they decrease |E| (unless you start out with a single vertex) so you can't end up with a minor with more edges than vertices

[ivory badge]

I see I see

[native dragon]

If you start out with a connected |V|=|E| graph

[ivory badge]

Acceptable

L taken

My reading comprehension is 0 fr

[iron marsh]

So...what is a subdivision of a graph?

[native dragon]

You subdivide an edge by slapping a vertex in the middle of an edge

If there's some subgraph which you can obtain by subdivding the edges of K5 or K3,3, then the graph isn't planar

a subdivision of K5 would just be what you could get by subdividing its edges

actually that might've been the worst explanation ever

[iron marsh]

So if you take a subdivision of K_5, does that mean that you subdivide every edge in K_5?

Nope. I got my answer. That's pretty easy to understand

[iron marsh]

Okay, so what sharp mentions here properly extends my argument to also show subdivisions of K_5 and K_3,3 will never satisfy |V|=|E|.

I'm with it now

[native dragon]

If you slap a vertex in the middle of an edge, that's one extra vertex, but now that edge goes from 1 edge -> 2 edges

so yeah

although minors work as well

which is what I ended up trying

[iron marsh]

Minors?

[native dragon]

There's a different theorem that says if the graph contains no K5 or K3,3 minor then it's planar

[iron marsh]

What's a minor?

[native dragon]

basically if you can form it by using these operations: 1) deleting a vertex, 2) deleting an edge, 3) "contracting" an edge and replacing it with a vertex, then it's a minor of that graph

[ivory badge]

Basically if you can get it as a subgraph or a subgraph is a subdivision of it

Which is the statement of the theorem dackid posted, planar iff no subgraph is a subdivision of the non planar ones

[ivory badge]

.

[odd garden]

in a) im trying to check if it is transitive when we reach (2,4) I need to check if something starts with (4,...) right? well there is not does that mean it is not transitive?

or because False implies False so it's true?

<@&286206848099549185>

[kindred bolt]

why is counting so complicated?

[true pelican]

Anyone know how to do this problem?

Def of ECS

[elfin adder]

Thanks guys for the help

I proved that if it was a connected graph then it had to be planar

[iron marsh]

Did you need Kuratowski's, or did you have another way of doing it?

[elfin adder]

Pretty much just said something like assume its non planar and connected so it contains a subgraph of K5 or K3,3. Since K5 has 5 vertices, 10 edges, and K,3,3 has 6 vertices and 9 edges, we would need either n-5 or n-6 more edges to make it connected, which leads to n+5 edges or n+3 edges but we only have n, so it must be planar?

Tbh not sure how valid that is but

[iron marsh]

Don't forget it must be a subdivision of K_5 or K_3,3 , not a subgraph

[ivory badge]

Im pretty sure any graph satisfying your conditions would be like, a loop made of n points and sticking (possibly trivial) trees on every point?

[iron marsh]

Getting that extra step is easy once you've shown K_5 or K_3,3 being a subgraph doesn't work

[elfin adder]

sorry yeah i just said a subgraph thats isomorphic to K_5, K_3,3 but subdivision is better

[iron marsh]

I think this handles the first part well

[ivory badge]

Isomorphic isn’t sufficient

Gotta have subdivisions since like

Take K5 and replace one edge •-• with •-•-•

[iron marsh]

Now it's a completely different graph

[ivory badge]

A subdivision of K5

So still non-planar

[iron marsh]

However, the issue that you're always adding one more edge every time you do this is still a problem

[ivory badge]

Ye

[iron marsh]

I'm going to look up the proof for Kuratowski's theorem. I didn't hear of it til yesterday and it seems pretty neat.

[elfin adder]

i mean wouldnt it count as a subdivision if u extend one of tbe vertices for K5 or K3,3?

[ivory badge]

What do you mean

[elfin adder]

like say we’re starting with K5 right

And we extend the outer vertices

oh wait nvm lol

[ivory badge]

Just like draw it

[elfin adder]

we need to split the actual edge to make it a subdivision right

[ivory badge]

No idea what you were trying

[elfin adder]

Yeah me neither LMAO nvm

just had my understanding of edge subdivision mixed up for a second i woke up like 30 min ago D:

[iron marsh]

Can someone help me understand how they got the last claim?

[ivory badge]

Each face needs 3 edges at least

But each edge can only bound 2 faces

So they said, best case scenario, every face has only 3 edges and every edge bounds 2

[iron marsh]

Yeah, I understand that

I'm just not sure where the 2/3 is coming from (I see the 2 faces and 3 edges), just not sure why dividing it like this makes sense.

[ivory badge]

That’s the “best case scenario”

[iron marsh]

And where'd the 6 come from?

[ivory badge]

You’re certainly not getting more than that

[ivory badge]

10*2 = 20, 20/3 = 6 + 2/3

[iron marsh]

Ah...mixed fractions. Haven't seen those in a millenia :p

[ivory badge]

Scuffed proof wiki mixed numbers

Anyhow, I wouldn’t think about silly polyhedron formula tbh

[iron marsh]

Okay, I think I get it. So each edge makes 1/3 of a face, and if we just counted that, we'd get E/3, but each edge needs to be counted twice (since it sees two faces), so we have that E 2/3 is the total number of faces.

Got it

[ivory badge]

The non planar -> it has K5 or K3,3 as a minor is the interesting bit

[ivory badge]

*upper bound on faces

[iron marsh]

Yea, I got it. It's the best case scenario, where every edge is incident to exactly two faces

[ivory badge]

Yee

[ivory badge]

How’d they show this direction though

[iron marsh]

Same direction, I just didn't show the full proof

[ivory badge]

contrapositive moment

[iron marsh]

They didn't prove the other direction, but it's pretty obvious :p

[ivory badge]

LEM moment

[iron marsh]

LEM?

[ivory badge]

Excluded middle

I was hoping to see some way to whittle it down into K5 or K3,3 but that works

[iron marsh]

Actually, how would you prove the other direction. I said it's obvious...but I think I'm wrong about that

[ivory badge]

Well now hang on

That’s just the K5 and K3,3 subdivision bit makes it non-planar side?

Which is ya know, the obvious side

[elfin adder]

Kuratowskis thrm

[ivory badge]

the other direction is the juicy one scroll down

[iron marsh]

Is it actually?

[iron marsh]

That's what this is proving

[elfin adder]

Thats how u prove the “obvious” side

yea

[iron marsh]

So glad I read the other direction :p

[ivory badge]

Planar => doesn’t have the B A D graphs

Is the contrapositive of

Has bad graphs => not planar

Real

We want -Planar => has the EVIL 😈, whose contrapositive would be

No K5 or K3,3 minors => planar

Ya know, the not obvious side

Clown website

[elfin adder]

Bruh 😂😂

[iron marsh]

I mean... it's a wiki. So clown author 😛

[ivory badge]

Check actual Wikipedia they have wild pages sometimes fr

[iron marsh]

Wikipedia always makes my head hurt because the math authors are clearly trying to flex their intellect

[ivory badge]

Also, not the most related comment, but you can turn a graph into a topological space by like

Glue [0, 1] together as described by the edges

So this would be if there’s a subspace homeomorphic to the bad graphs?

[iron marsh]

hmmm

[ivory badge]

@iron marsh https://math.uchicago.edu/~may/REU2017/REUPapers/Xu,Yifan.pdf

at the end

how you would think to look for these subgraphs as minors idk

[thorny maple]

is it O(n) or O(1) me and my friend been arguing for like 30minutes

isnt it O(1) since it only checks onccee????

[brave rock]

O() measures the worst-case scenario.

Imagine you have a list to compare to. What is the worst possible case – what's the largest number of comparisons you would have to do?

[thorny maple]

oh so its n then?

[haughty garden]

It’s constant time per check but you perform at most n checks, so you are performing at most O(n) work

Big-Oh is not exclusively used for worst-case analysis; it’s just convenient because we care about how large a function or algorithm grows regardless of what the input is

[thorny maple]

oh

makes sense

so my friend is right

since O(n) is the answer

[brave rock]

Your friend is indeed right.

[thorny maple]

im stuck on this can any of u guys help me pzl

[iron marsh]

What is k?

It says k=1, but like, what's the point of it?

[thorny maple]

idk just to make us not worry it is euqal to something else i guess

[iron marsh]

But...I don't see k in the formula

[thorny maple]

oh

ohhhh

no c either

[iron marsh]

Like what is k supposed to be?

At the moment, it's just a variable without purpose to me.

I need context for what k is supposed to be

[thorny maple]

v

this is from my prof

only thing i can find relating to this question

[iron marsh]

So it seems like k is a lower bound for what n can be

[thorny maple]

oh

[iron marsh]

Okay sure, that makes sense

Also...the first line just says f(x) is less than or equal to itself

[thorny maple]

like under the proof section

?

[iron marsh]

Yea

The 1st and 2nd line are literally the same equation

[thorny maple]

ya

[iron marsh]

That's kinda redundant don't ya think?

[thorny maple]

i think he just did that so we dont get confusd

like the prof

also the example is liek the same as my question right

[iron marsh]

Pretty much on the nose

[thorny maple]

alr ima write it out tell me if it looks good

i got a midterm tmrw this one concept idk

[iron marsh]

Worth noting, a_0,...,a_n are not guaranteed to be positive in your question

They are just real numbers

You need to adapt that somehow, which is a bit trickier

[thorny maple]

ya idk

im stuck

can u show me how do it plz

[iron marsh]

You're not gonna get very far w/o the triangle inequality. Do you know what that is?

[thorny maple]

nope

[iron marsh]

Okay, then email your professor and ask if they're all positive. For now, just assume they are. If they get back to you, you can adjust it later

[thorny maple]

ima just asume it is

he never answers anyway

[fossil mural]

what do "2", "+", "=", and "8" mean here?

?

[regal gate]

Am I supposed to count all by hand? lol

I'm not seeing anything useful

like I could count them by hand in less than 10 minutes

but this is so stupid, ideally we would want a formula for a chessboard of 8 x n squares, or n x n squares or something like that

[obtuse lance]

hmm I guess take a path, rotate it 180 degrees, this gets you another path, except if it's the fixed path along the diagonal, so there's an odd number of them

now if only we could do some more stuff with modular arithmetic we could construct the solution with the CRT lol

[regal gate]

ok apparently there is a formula for the nxn case

tho I want to try to find it on my own and prove it

[obtuse lance]

maybe we can do by induction

[regal gate]

that's what I have been trying

I was trying to consider n columns and 8 rows

and try to find some recursion

[obtuse lance]

maybe we can do n-1 x n-1 to nxn

[regal gate]

yeah maybe that's easier idk

I also thought like, maybe finding a model of this would be useful

[obtuse lance]

kind of follows that 180 degree board symmetry

[regal gate]

btw

[obtuse lance]

we might want to do nxn to n+2 x n+2 actually, not sure

[regal gate]

its not exactly symmetric

its not actually

the white squares are in rows 1,3,5,7

and black squares in rows 2,4,6,8

[obtuse lance]

by symmetric I just mean in the way I described here

[regal gate]

ah wait yeah

if you rotate then yes

mb

[obtuse lance]

good yeah, that's why I said n to n+2 here actually cause I realized

[regal gate]

Like at first, I thought reflecting through the middle would be symmetric, but it obviously isn't. In that case I did derive a useful recursion, but its just wrong because of that lol

[obtuse lance]

like white/black will not be in equal amounts for odd nxn

[regal gate]

if you rotate the board by 180 degrees, it remains the same always

but tbh, i dont think this is very useful lol

[obtuse lance]

yeah the board is the same

well I reasoned it's odd

cause the only fixed point is the diagonal path

[regal gate]

if its oddxodd, if you rotate by 90 deg its still the same

[obtuse lance]

every other path gets rotated to a new path

[regal gate]

actually, in oddxodd case, you can reflect the board through a line in the middle of the board, and it remains the same

[obtuse lance]

interesting

[regal gate]

ah ok yeah, you can determine the parity in this way

[obtuse lance]

maybe we can work out the 7x7 case by some symmetry

then like add an extra layer and get the solution easily

I think adding an extra layer from nxn to n+1 x n+1 amounts to basically doubling the number of paths or something

cause it allows the path to go either left or right, but not quite cause the boundary

idk I'm in bed and dont want to get up to start drawing on paper lol

[regal gate]

[ivory badge]

You could do something like uhh

How many squares on top row

[regal gate]

I had an idea

but sec I need to think

[ivory badge]

Then how many diagonals on the next, and kinda counting from there somewhat induction-y

The ones near enough the borders are screwier but uhh

You descend a row each time right

[coral parcel]

You can use dynamic programming: First for each square in the first row write down how many paths end at that square (always 1). Then the same for the next row (2 on each square except 1 on the far left), the third and so forth.

After 32 additions you're done.

(Or trade it for about half as many additions and a bunch of multiplications by meeting in the middle).

That takes less than 2 minutes with pencil and paper for the 8×8 board.

[ivory badge]

A similar method works at arbitrary sizes

[coral parcel]

Yeah, but it might become cumbersome at say 42×42.

[ivory badge]

Well when you have odd sizes you might have to watch out for like the uh

Board parity?

Might end up being the same regardless but I don’t wanna check

[coral parcel]

Hmm, yes, if the width is odd and the height is even, the two ends are not symmetric.

[regal gate]

I think my idea should work, and would also work for any rectangular board, but idk why Im getting the wrong answer

idk if Im doing some mistake

in my 8x8 board, the path starts in the left-most column and the left-bottom square is white

so you have four white squares, and my idea was to look at how many paths are there if you start from the first white square, second, third and fourth

pretty sure this is true

assuming like n is big enough, so that 2n-2 is not zero or something

we can see this as the matrix

and this matrix acts on the vector (1,1,1,1), each entry would store p_1, p_2, p_3, p_4...

if you do this 3 times, the vector would now sotre p_1(2)=...=p_4(2)=2

so that you calculate the third power of the matrix, multiply by the vector (1,1,1,1)

and then do dot product with (2,2,2,2)

shouldn't something like this work?

[coral parcel]

I'm not sure I follow your derivation.

I can see as a way to formulate it as powers of $\begin{pmatrix}1&0&0&0\1&1&0&0\0&1&1&0\0&0&1&1\end{pmatrix}$, though.

[regal gate]

do you agree with this and understand what I mean here? @coral parcel

[coral parcel]

No, wait I got that matrix wrong.

[coral parcel]

That's what I don't get. You haven't defined what you mean by p_a(b).

[regal gate]

yeah, I explained very poorly. I'll try to explain it better

[coral parcel]

The matrix I was talking about would be $\begin{pmatrix}0&0&0&1\0&0&1&1\0&1&1&0\1&1&0&0\end{pmatrix}$.

[vital dew]

troposphere

[regal gate]

the black balls mean the square is black

so I define p_1(8)=number of zig-zag paths that start in 1

and similarly for p_2(8),p_3(8) and p_4(8)

and do the same in general for the 2n-th column

if you start from 1, then you can only go to one white square

then you can go to either 1 or 2 (purple). See the blue arrows

if however you start at 2, then you can go at two white squares, etc. (orange arrows)

so you have this formulas

Is this part clear now? Im not good at explaining these things

and the idea, is to apply this over and over again

no, this is not exactly

because its like a linear transformation. So its this matrix

so if M is this matrix, then
[
(p_1(2n), p_2(2n), p_3(2n), p_4(2n))=M\cdot (p_1(2n-2), p_2(2n-2), p_3(2n-2), p_4(2n-2))
]

[vital dew]

Croqueta

[regal gate]

wait I think I read the problem wrong

cuz only one white square in each row

ig their rows are my columns lol, so I didnt read it wrong

lol the recursion is wrong

for p_4

ok yeah my method was correct

I think I looked at a 7x7 chessboard without realizing, and changed the p_4 recursion (when I had it written correct already) xDDD

and changed it

and (p_1(2), p_2(2), p_3(2), p_4(2))=(1,2,2,2) and not (2,2,2,2) (also looked at a 7x7 chessboard there by accident 🤦‍♂️

so the answer is the sum of the entries of this vector

and if you replace the 3 by k, then you are calculating the number of zig-zag paths starting from the 2k+2 column, where there are 8 rows

and if you want more rows (the same argument will work for an even number of rows), just enlarge the matrix in the natural way

ok this matrix is disgusting anyway, computing its powers is not easy I think

,w {{1,1,0,0},{1,2,1,0},{0,1,2,1},{0,0,1,2}}^k

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by Croqueta#3385

[meager prawn]

I think more context wouldn't hurt

[vital dew]

Sciencenjoyer

[quiet eagle]

Hi, I have trouble understanding this proof. First: "Since hat{z} < z, we can apply the induction assumption to conclude that hat{z} has a unique representation".
I don't get how you could apply the induction assumption there, which requires z < b.

[ivory badge]

“Assuming the assertion holds for all numbers 0, 1,…,z-1”

Read it more carefully

[quiet eagle]

Right.. thanks

[ivory badge]

When z = 0 mod b that’s somewhat problematic for their z hat < z assumption tbh

But if it’s a multiple of b, just divide by b and apply it

[oblique hearth]

Hi I had a conceptual doubt related to FFT, I m not sure wherein (as in which channel), this seemed like the most suitable channel.

I do understand the FFT algorithm, wrote the code for it in MATLAB (recursive), got a fair bit of idea of the iterative method. I still don't understand what this figure is supposed to mean. I just can't understand what this means at all, can someone help me out here. Thanks

x_k is the kth element in input sequence, and y_k is the kth output in transformed sequence

[quiet eagle]

@ivory badge I really don't understand, where that weird inequality comes from and why it implies z{hat}_(n-1) = 0

[meager prawn]

$\hat{z}_{n-1} \times b^{n-1} \leq \hat{z}$ (the difference being the other digits of $\hat{z}$)

$\hat{z} \times b = z - (z \ mod \ b) \leq z \leq b^n - 1$

Hence $\hat{z}_{n-1} \times b^{n-1} \times b \leq \hat{z} \times b \leq z \leq b^n - 1$

Therefore, $\hat{z}_{n-1} \leq \frac{b^n - 1}{b^n} < 1$

Since it's an integer, it must be 0

[vital dew]

Bezier graduate

[quiet eagle]

woow thank you so much. Why does this book not explain this proof better? It's on the second page!??

[meager prawn]

Some books are more detailed than others

Some purposefully leave out details to make the reader work for them and engage with the material

[quiet eagle]

This book is specifically for the first year of math

[meager prawn]

Welcome

I guess

Books rarely overdetail afaik

They tend to be rather concise

But I'm definitely not one reading many math books

[quiet eagle]

Haha thanks..

[quiet eagle]

I'm spoiled by that one 1170 pages book, I am reading atm

[quiet eagle]

How else do you learn math?

[meager prawn]

That is one chunky book

[meager prawn]

Actually having teachers giving lectures ?

[quiet eagle]

Luckily pdf's are a thing or else I would be having a hard time with that

[quiet eagle]

But the lectures leave a lot out

[meager prawn]

Yeah

Uni issues

I guess

[quiet eagle]

You don't go to Uni?

Or did I misunderstand

[meager prawn]

It's not quite uni

French system is a bit more complicated

It's basically HS style lecture/learning but undergrad content/level

[quiet eagle]

Like with small classes and the teacher coming around to help?

[meager prawn]

So we're a class of 40 and the teacher knows all of us well, and we see and prove everything in class and correct some exercises, and talk about any problems we might have

Really close to the teachers

[quiet eagle]

WOW, that is crazy

That is the best thing I have ever heard of

I guess that really helps learning math

[meager prawn]

It's the french CPGE (or prépa) system

For the good students (like top 15-20 %)

So the state pumps a lot of money into it on a per student basis compared to the other types of schools

[quiet eagle]

Interesting

[quiet eagle]

So, based on the grades you got in high school?

[meager prawn]

Basically

It's a dossier-submission system

You apply for schools, get ranked, get accepted, put on waiting list, rejected

That same system handles all public school admissions (not just prepa) and some private ones

[quiet eagle]

Wow, you could actually be rejected, trying to study math there

[meager prawn]

It's called Parcoursup

[meager prawn]

Your regional uni is not legally allowed to reject you if you graduated

So people have places guaranteed

Just that uni is kind of garbage, except maybe for one or two parisian ones

[quiet eagle]

Oh really? Interesting

[meager prawn]

It's the other ones, that have a certain reputation, that may reject you. Which is fair since there's only so many seats

[quiet eagle]

Even if full?

[meager prawn]

Hence "full" not really being a thing there on PS.
They tend to overfill

[quiet eagle]

Oh no

[meager prawn]

Then something like 1/3 drop out in the first semester or first year

A stat like that

Basically weeding out the weakest from undergrad studies

[quiet eagle]

Ah yeah, I have experienced something similar during the first semester

[meager prawn]

The technically-graduated-high-school-but-too-weak-for-undergrad folks

[quiet eagle]

I see

[meager prawn]

What country are you in btw ?

Netherlands no ?

[quiet eagle]

I am from Deutschland

[serene trench]

https://media.discordapp.net/attachments/806152264485568552/1133029899276406784/image.png?width=700&height=646

is this right, i have deadass no clue 😂

long story short my prof hasnt said anything for ten days and only threw this worksheet at us 😩no clue what is going on

[foggy cloud]

x rational = p/q now use that to write the last 2 as a fraction

i didnt read what you wrote but if you did that then sounds good

[cunning mason]

can this be simplified:
({b} x A) \cup (A x {b})

where b not in A

[brave rock]

(A u {b})^2 \ {(b, b)} ?

[pastel coral]

Someone who could explain isomorfism between two groups clearly? Because my Discrete Math teacher explains everything in a very weird way. I know it's a bijection of set V onto set W, but in details what exactly does it mean?

Is this a good enough explanation? Or is there more to add to this?

[meager prawn]

Yes. The formal definition is included.
The intuitive one is that two groups are isomorphic if they're the same group up to a renaming of the elements (such as Z/nZ and U_n). i.e. that through that renaming, any property that holds in one group holds in the other (the value of a product, the order of an element, a subgroup being cyclic, etc)

[pastel coral]

Ah yeah right I see, thanks!

[stray reef]

DON'T USE CHATGPT FOR MATH

[pastel coral]

I know for problems I shouldn't do that, but for explaining basic concepts shouldn't be a problem right? Since it's trained on data from the internet...

[stray reef]

treacherous

[pastel coral]

Alright 😂

[fossil mural]

it will produce things that look like explanations from the internet, not necessarily things that are explanations from the internet

[pastel coral]

alright, will take that into consideration next time i'll use it, but that was also kind of the reason i asked here to double check

thanks

[meager prawn]

the problem is that very often, it will spit out some 30 lines of math stuff
28 will be fine, restating definitions and making a plan for the proof, and starting to set things up for the actual mathy part (and then the conclusion)
2 lines in that mathy part will be utter bullshit that says "hypothesis, 7 words of nonsense, hence conclusion" that mean it very subtly doesn't actually do anything
The bullshit part is often obvious to a trained eye, but it's its insignificance length-wise that makes it all the harder to spot, and ruins the entire 30 lines to a non-proof
Hence chatgpt can't do math

[meager prawn]

that's why you get this: it looks good, but it's not actually thinking so it just does garbage

[honest holly]

Chatpgt also has a very distinctive prose that I find very obnoxious lol

[iron marsh]

Here's an example a friend of mine shared with me where ChatGPT doesn't quite deliver.

Can you see what's wrong with the argument that e+pi is irrational?

[honest holly]

It equates rationality with algebraicity

Are any of those words...

[fossil mural]

be more specific, which step is wrong?

[honest holly]

I dont need to be more specific, what i wrote is certainly sufficient!

Actually i dont see anything wrong, i was just primed to see something wrong

The only fault is the poor style as far as i can tell

[ivory badge]

wrong

[iron marsh]

It's near the end

[honest holly]

I don't see it

[fossil mural]

what properties of e and pi does the proof actually use?

[honest holly]

Im going to go CRAZY if you don't just tell me

Please tell me 😦

[fossil mural]

e + pi is algebraic, which contradicts the fact that both e and pi are transcendental

[honest holly]

Oh

[iron marsh]

If this were true, then that pi-pi=0 would contradict the fact that pi is transcendental...which it obviously doesn't.

[stray reef]

my life motto

[wraith patio]

doing a problem sheet on fsa's and this is what i came up with

i've got the correct answer here

and im not really sure where i went wrong

maybe i've made a mistake reading the grammar but this is how i interpreted it:

• Starts with an "a"
• Followed by 5 "b"
• Followed by any string that fits 'w' where
• Followed by 4 "b"

on the answer sheet it all has the option to go back to q6 but isnt that over-complicating it because at that state you can just recursively go a or b instead of needing q7

[analog tinsel]

on the first (quick) look it doesnt seem like yours is missing any word but its a bit less elegant

the yellow one wouldve been what I thought of first

whenever theres {a,b}* you can consider the selfloop with a,b

afaik the only difference between yours and the yellow one is that yours is completely deterministic

almost completely, in our course we said that deterministic ones have to have exactly one transition per letter

[wraith patio]

ok yeah i believe youre correct

i used a nfa to dfa converter

it produces the same answer i believe

[analog tinsel]

yep

[wraith patio]

at the top of my sheet it states Throughout this sheet, ‘FSA’ stands for Finite State Automaton. This could be either deterministic (DFA) or nondeterministic (NDFA). For this sheet, either is acceptable.

so am i right in assuming mine is technically fine but the second real answer is preferable

[analog tinsel]

well I wouldnt say one is better than the other

it doesnt really matter which one one uses as there exists a fairly smooth algorithm to translate a nfa into a dfa

and in general they are equally as "strong"

I am lacking the word

they are basically equivalent regarding what they can and cannot do

[wraith patio]

alright i see, thanks for the help

[analog tinsel]

no problem

[meager prawn]

The set of languages recognized by DFAs is equal to the set of languages recognized by NFAs

[glossy kayak]

https://math.stackexchange.com/questions/4742512/is-there-any-way-to-turn-a-static-number-of-dimensions-of-numbers-into-a-unique?noredirect=1#comment10059057_4742512

[quiet eagle]

b) Given a number $\left(z_{n-1} z_{n-2} \ldots z_1 z_0\right){K_2}$ in two's complement representation with $n$ digits. What does the same number look like when $n+1$ digits are available for the two's complement? Distinguish between positive and negative numbers and prove your answer.
\ \
My answer, the number would look like this: \ $\left (0z{n-1} z_{n-2} \ldots z_1 z_0\right)_{K_2}$ \ Could anyone explain to me what is wrong with this intuitive idea?

[vital dew]

Sciencenjoyer

[ivory badge]

What does a negative number look like @quiet eagle

[quiet eagle]

it just start with a 1

in binary

oh