discrete-math

[twilit sundial]

which then gives $2^{n+1}>(n+1)^2$

[vital dew]

elrichardo1337

[wide sentinel]

Why is this anti symmetric ?

[twilit sundial]

hint: how does it fit the definition of antisymmetry?

[silver ermine]

If (6,2) exist it breaks, think more from here. and read the definition again

[cerulean radish]

It satisfies the definition

[wide sentinel]

Well, if x related to y, then y related to x, then x = y. In this case 2 to 6, but 6 doesnt go to 2

[wide sentinel]

how

[cerulean radish]

That's not the definition

If x is related to y and y is related to x, then x = y

[cerulean radish]

This is the definition of antisymmetry

[wide sentinel]

Wait isnt that what i said

"Well, if x related to y, then y related to x, then x = y"

[cerulean radish]

No

[wide sentinel]

im confused

[cerulean radish]

You are saying that y should be related to x when x is related to y

There is no such assumption in the definition

[mighty scarab]

"Well, if x related to y, then y related to x, then x = y"

[vital dew]

ekafeman

[mighty scarab]

that's what it reads like

(I just used the tilde because it's one of the many symbols that exist)

[vestal bronze]

liar, you like the tilde

[silver ermine]

read the definition word by word

10 times, maybe with a dictionary

[cerulean radish]

Mfw implication is not associative

[agile magnet]

The first "then" here should be an "and"

[elfin heart]

I need some help with the following: Consider the set {-4, -2, 0, 2, 4}. I want to figure out all the possible numbers of the form a + b + c with a,b,c distinct elements of that set, and for each possible value, I want to know how many different ways we can get it. For example, we can get 0 as -4 + 0 + 4 or -2 + 0 + 2 and nothing else

The only way of solving this I can think of is to brute-force it. Is there any other way of doing this?

For example, I know the answer to this problem if instead of a+b+c with a,b,c distinct, we are interested in values of the form a + b with a,b distinct. Is there a way to use this information in order to make it easier to solve this?

[grand totem]

Ignoring the x = 0 typo (I'm sure that's supposed to be x = y), that is indeed (equivalent to) antisymmetry if we associate to the right here, i.e. x ~ y -> (y ~ x -> x = y).

[agile magnet]

I don't think

but one thing you can do is make your life easier by proving an upper bound on the possible value of a + b + c

and then similarly prove a lower bound on a + b +c

then you only have to brute force numbers between those

from there you could argue that you don't need to check for sums of odd numbers

[agile magnet]

you could use this as a black box

say you want to test if a + b + c = d

then fix c

find a + b that add up to d - c

and combine answers appropriately

[edgy lintel]

The second attempt is me trying to work from the books example

my thinking was r squared should be a multiple of three but i couldn't properly show how

sorry the question was prove sqrt(3) is irrational

[harsh girder]

@edgy lintel I believe the same idea holds for sqrt(3) as it does for sqrt(2). This error doesn't arise for rational roots like root(4) since that is simply 2/1 and thus satisfies the definition of a rational number. So consider the proof as follows:

Assume sqrt(3) is rational. Then there exists a p and q such that sqrt(3) = p/q and q does not equal 0. Wihout loss of generality assume p/q is in lowest form (or reduced form i.e no common factors besides 1). Well then squaring both sides yield 3 = p^2 / q^2 and this implies 3q^2 = p^2. Well then 3 is a common factor and we have reached our contradiction and sqrt(3) is therefore irrational.

Not 100% sure but that should be on the correct track.

[wide sentinel]

Ah I see yeah, that should be an and like the other person said

But even then, nothing on that screenshot represents the definition of anti symmetry ?

[wide sentinel]

I think I might be cooked man, atp I can only memorise variations of questions and hope for the best ☠️ understanding the underylying logic has me finished

everyone else in the lecture seems to click with things so fast

[hard citrus]

how to simplify this boolean algebra expression? ad+c'b'+b'd'+c'a'

[coral parcel]

@hard citrus

[hard citrus]

there must be something else, my lec told me it should be the sup of 3 products with 2 literals each

[silver ermine]

Everything can be abstracted as some structure in some sense, every structure that does't violent the definition are called met the definition/be the defined thing in this case are called being anti-symmetry so everything that exists and can be abstracted(such as graphs) and not violating the definition of anti-symmetry can be called anti-symmetry. If I can be abstracted by some explanation as some structure which doesn't violent the definition of anti-symmetry then I'm anti-symmetry as well.

Another example, an empty set {} is anti-symmetry.

References:

predicate logic:https://en.wikipedia.org/wiki/First-order_logic

[silver ermine]

@wide sentinel You can see the definition is longer

[true venture]

If I have g(x) = 1/(1-2x) the image of g(x) under the mapping g(x) -> g(x/(1-x^2)) would be (1-x^2)/(1-x^2-2x) right?

[silver ermine]

So the word g is overloaded and the pre-image can be R i guess

If the following notation "->" can be read as "=" it will be more familiar to me

If so It would be like (1-2x)/(4x^2-4x) i guess?

How did you get that fomula

[true venture]

The way I got my formula, is thinking of f(x) = 1/(1-2x) and g(x) = x/(1-x^2) then f(g(x)) = 1/(1-2(x/(1-x^2))) which can be rearranged to (1-x^2)/(1-x^2-2x).

I was thinking that the "g(x) under the mapping" meant the same thing as the way I got f(g(x)) above but I guess they mean different things?

[silver ermine]

so lets say you get g_1(g_2(x)) when i read as g_2(g_1(x)), where you called g_1 as f there

I think "a set S under a mapping f" means there is a corresponding image set T such that f: S->T.

[true venture]

Ok, thanks

[silver ermine]

I think here "=" should't be used, whenever we use "=" to describe mapping we need a word(it's like the predicate but not sure) such as "f"/"f(g(x))" but here isn't such a "f" so your notation looked correct. @true venture

[true venture]

Ok, I will have to look into mapping more.

[silver ermine]

so in this sentence g(x) -> g(x/(1-x^2)) there isnt explicit word/placeholder for the mapping we are talking about, both g(x) and g(x/...) are representing some sets like pre-image and image

[true venture]

But this answers my question, being that what I had written as f(g(x)) is different than the statement about g(x).

[true venture]

The mapping statement is a comment on from the oeis,
Written in full "Image of 1/(1-2x) under the mapping g(x) -> g(x/(1+x^2))."

I misunderstood that statement to be what I was doing with f(g(x))

[silver ermine]

The image became a pre-image later in this case.

I'm cs major so i might be wrong tho

OK now i get you, all good

@true venture you can try google "under the mapping" to force search including these words

[silver ermine]

I'm afraid i misled you @true ventureneed someone else to explain.

[true venture]

No worries.

[wide sentinel]

Ohhh okay

[wide sentinel]

alr i see

Thanks for the response, i'll try those questions again

[silver ermine]

After some more readings, i think your original way is correct, but according to the definition here you might have to find out a set or an interval corresponding to the image set of (1-x^2)/(1-x^2-2x). But still i hope someone who is familiar with those can confirm.

[silver ermine]

which i think is R{0}

@wide sentinel I found something about the graph representation

https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/A_Spiral_Workbook_for_Discrete_Mathematics_(Kwong)/07%3A_Relations/7.01%3A_Denition_of_Relations

[ashen terrace]

Could someone please point me in the direction of the correct topics to research to be able to awnser a question like this. (i have no previous knowlage). Many thanks

[wide sentinel]

I think my main issue is simply approaching the relations questions

I know that equal is symmetric yet I got a lil nervous and said no for some reason ☠️

for S

Because the way I was thinking was that min(B) has to be a different number, but at the same time i was thinking the relation cant even exist if min (A) and min(B) dont hold the same number

so if the relation exists it will always be symmetric

anti symmetric was fine but the answer they gave was different than what i expected

[little prism]

thats linear algebra

[coral parcel]

That's basic linear algebra, just with a finite field instead of R or C as the field of scalars. But the computations go just the same way apart from that.

[wide sentinel]

Yeah im gonna read up and watch more videos on digraphs

[shell yew]

bro this explains the whole a^phi(b) = 1 for gcd(a,b) = 1 thing

since the set of elements of the natural numbers modulo b whose gcd with b is 1 equipped with multiplication is itself a group

[ashen terrace]

@little prism @coral parcel

Thanks

[shell yew]

how does the 3 mod 4 part work here?

[proud robin]

there is a demonstration of it by Hirschhorn derived from the jacobi triple product

but i honestly don't remember, if you are interested it's able to find it online

[winter yarrow]

Hello! I have a question about the Graceful Tree Conjecture. I am reading about it at the moment and I saw that it was proven for a lot of special cases and tree configurations (most of which are not very popular such as bananas or firecrackers)

Do you guys know of any other special tree configurations where the conjecture is still unproven? Looking online is not really helpful since those obscure trees are not really talked about.

Thank you!

[supple jetty]

I think this is technically discrete math, i'm like 90% there with understanding this im just a little confused by one part

"It says that a(i) = 1 if any only if i is an element of A"

But it seems to me that in the examples that it gives, like: " a=[01101001] encodes the set A={0, 3, 5, 6}," it's the zeros that encode for the elements of the set? if a(i) = 1 only when i is an element of A, wouldn't A = {1, 2, 4, 7}?

[pale monolith]

The text says "we write a_w-1 on the left and a_0 on the right" which results in it working out

But that is a bizarre convention

[supple jetty]

OH i see now, it's totally backwards, it's just a coincidence that the 0s line up with the encoded numbers

like wtf yeah why do it that way

[severe path]

Is it possible to define a DFT over an arbitrary ring as long as you choose a unit with order N?

[severe path]

and if so, are there any ways to actually compute the prime?

[weary tiger]

I wanted to ask about overflow/underflow errors, precision, floating point numbers and round off errors because I'm kinda confused on how to apply these topics to math problems and how they work

despite learning this in uni

[faint umbra]

did you have a specific question

[weary tiger]

not really since the notes just covered the general idea of the topics

[faint umbra]

well

if there's a way you can compute something that avoids those erroes, we generally prefer to compute it that way

ig the most simple example i can think of is binary searching

are you familiar with the process?

[weary tiger]

No, I haven't learned about binary searching

[faint umbra]

uhm

ok lets just say then i wanted to compute something like

$(x^{100})^{1/50}$

[vital dew]

catgirl pee

[faint umbra]

and suppose this x value is large

now if i proceeded naively and simply started with x^100, i would surely overflow

then if i take the 50th root of my overflowed result i wouldn't get an accurate value

instead we can just simplify the expression to x^2 and compute this directly, which will use far less bits than x^100

[faint umbra]

ig i can just tell you, in binary searching we're interested in a value mid = (left + right) / 2

where left, mid, right are all variables, and mid is just taking the average of left and right

now left + right can overflow

so the common way to circumvent this is to write

mid = left + (right - left) / 2 instead

(right - left) / 2 is small, so adding left to that quantity is small,

[weary tiger]

okay

got it

[winter yarrow]

I would really appreciate any help

[rain bronze]

see this video

https://www.youtube.com/watch?v=v5KWzOOhZrw

[coral parcel]

The question seems a bit backwards. It's not like named classes of trees just hang around waiting for things to be proved about them. Instead, it seems likely that most of the special classes you found got a name because someone discovered a proof that the conjecture is true for them.
For example MathWorld https://mathworld.wolfram.com/FirecrackerGraph.html cites the concept of a "firecracker graph" to the same paper that showed they are graceful, and it sounds like the grace is the most interesting thing there is to say about them.
So if you dream of proving the conjecture for some class of trees that haven't been proved yet, the strategy is not start by picking an existing class that still needs a proof, and then attack that class specifically. It is to start by coming up with a proof that is stronger than what is currently available. Then you get to invent a name for the kind of trees that your proof works for -- and if your result is considered interesting enough by other people thinking about graceful trees, they may even start to use the name you came up with ...

[winter yarrow]

That makes sense, thank you! Do you know how I could find all the classes for which the conjecture was proven? I am looking at A Dynamic Survey on Graceful Labeling by JA Gallian but it seems to be missing a few cases

[coral parcel]

Other than being an expert in the area who follows the literature, such survey papers are your best bet. Sometimes you can be lucky and one of the experts actively maintains a website that's kept up to date with the newest results, but it's hit and miss how to find such a site unless Google happens to be your friend.

[misty iris]

is anyone familiar with pigeonhole pricniple?

[coral parcel]

I'm sure someone is. But see https://dontasktoask.com/

[weary tiger]

so apparently these are equivalent (n,m are integers >= 2)
i cannot prove it, can someone give a hint?

they both are valid solutions to the same problem

[analog tinsel]

go ahead ask

[misty iris]

well im having trouble finding the N and k
when given a problem i find it hard determining N and k

[analog tinsel]

what is N and k in your case

[misty iris]

During a month with 30 days, a baseball team plays at least
one game a day, but no more than 45 games. Show that there
must be a period of some number of consecutive days during
which the team must play exactly 14 games.

[analog tinsel]

no way lmao

[misty iris]

what

[analog tinsel]

I had to teach this exact question 2 weeks ago

it comes every year in our course

[misty iris]

well time to teach it again ig lol

[analog tinsel]

do you already know the solution ?

[misty iris]

no

i know the answer number

but thats it

[analog tinsel]

there is no answer number ?

or what do you mean by that

[misty iris]

i meant to say i know what is the answer

[analog tinsel]

there is no real answer, the answer is a proof

[misty iris]

yea

[analog tinsel]

or wdym

so you know the solution?

[misty iris]

yes

[analog tinsel]

now youre confusing me

anyways

[misty iris]

that was a brain fart

[analog tinsel]

so regarding pigeon hole principle I usually try to start with the end in mind

whats the basic argument of the pigeon hole principle ?

[misty iris]

not sure

[analog tinsel]

whats your understanding

[misty iris]

of what

[analog tinsel]

pigeon hole principle

[misty iris]

tbh all i know is that if we have 3 boxes and we want to fit 4 pigeons we fit 2 in 1 hole

and by that we get k+1

[analog tinsel]

okk thats the main idea

in general when you have two sets X and Y and you have a function f:X->Y then there is at least one y in Y such that f(x) = y for at least ceil(|X|/|Y|) , x's

but what you said is enough

[misty iris]

but we also have ceil

yea

[analog tinsel]

so basically, when you have objects that we wanna put into boxes and we have more objects than boxes then at least one box has to contain at least a certain amount of elements

now the boxes usually are some type of category

regarding integer valued variables , what could these categories be ?

[misty iris]

quick question before this

[analog tinsel]

yeah

[misty iris]

if we have 5 pigeons but only 3 boxes do we fit them like this:
1
1
3

or
1
2
2

[analog tinsel]

well usually youd wanna spread them as evenly as possible

but the pigeon hole principle allows for both

it says "at least one that has at least x amount"

[misty iris]

oh ok

[misty iris]

no idea

[analog tinsel]

well what do you assign to those variables usually

[misty iris]

so what do i asign the boxes and what do i asign the category?

[analog tinsel]

no I mean

when you have variables

a,b,c,d,e

from N

they have values

now if for example we said we only allow values 1,2,3

[misty iris]

ok

[analog tinsel]

then what do we know ?

[misty iris]

so how do we fit 1,2,3 into a,b,c,d,e?

[analog tinsel]

doesnt matter

the pigeon hole principle gives us a conclusion independent of how the objects are distributed into the boxes

[misty iris]

im so lost

[analog tinsel]

do you agree that at least two variables have to have the same value ?

in this situtation

[misty iris]

how

[analog tinsel]

I dont understand what you dont understand

we have 3 possible values and 5 variables

we assign one of 3 values to each variable

in all cases there at at least 2 variables that have the same value

thats what the pigeon hole principle tell us here

[misty iris]

i was asking if we need to do this

[analog tinsel]

and I said

it doesnt matter how we fit them

[misty iris]

if yes then i wouldve asigned them

[misty iris]

thats true

but it matters if we asign them

[analog tinsel]

yes but you asked "how"

and that is irrelevant

the pigeon hole principle talks about existence

[misty iris]

yea thats true

[analog tinsel]

okk

so you agree that having 3 values and 5 variables we have to have at least 2 variables that have the same value assigned to them ?

[misty iris]

yes

[analog tinsel]

great

now

just to be sure

to check your understanding

does the pigeon hole principle tell us that there are at least 3 variables that have to have the same value, when we have 3 values and 5 variables ?

[misty iris]

so we can have them like this for example: 1a, 2b, 3c, 1d, 2e

erm

[analog tinsel]

our domain is {a,b,c,d,e} , the range is {1,2,3}

so the pigeon hole principle says

there is at least one r in the range

such that

at least ceil (|Domain| / |Range|) elements from the domain get mapped to y

so thats ceil(5/3) = 2

so the answer would be no

since we have a counter example with what you provided for example

[misty iris]

wait a sec

[analog tinsel]

so not for all cases there is a r in the Range that gets assigned three elements from the domain

[misty iris]

so we only use ceil (|Domain| / |Range|) when we want to fit more than 1 pigeon in a hole?

[analog tinsel]

I dont understand your question

this "formula" tells us that there is at least one element in the range, r in R , that is assigned to at least ceil(|D|/|R|) elements from the domain

so for example if D < R then this is 1

[misty iris]

oh nvm

[analog tinsel]

uhh

1

for D not empty

but that wouldnt make much sense anyways

so yeah

ok maybe another question before moving on

let A = {a,b,c,d,e,f,g} and B = {1,2} and f : A->B a function

what do we know for sure

by the pigeon hole principle

[misty iris]

idk

[analog tinsel]

check this out again

you have to understand this

[misty iris]

that we will fit c, d, e, f, g in 1 and 2

[analog tinsel]

otherwise the prove will seem like magic

[analog tinsel]

no

[misty iris]

how

1a, 2b is known for sure that will be like that

[analog tinsel]

no

again

the pigeon hole principle doesnt talk about the specific assignemnt

it makes a different statement

[misty iris]

we can have 1c or 2c, 1d or 2d, 1e or 2e, 1f or 2f, 1g or 2g

[analog tinsel]

thats not what the pigeon hole principle is about

[misty iris]

then im lost

[analog tinsel]

read this again pls

[misty iris]

i dont understand it

[analog tinsel]

what do you not understand

about it

so what exactly

[misty iris]

there is at least one y in Y such that f(x) = y for at least ceil(|X|/|Y|) , x's this part

[analog tinsel]

ok so in other words

if you map from X to Y

[hybrid mica]

@everyone sorry to disturb yall kno circle theorem

[misty iris]

bruh

[analog tinsel]

then you know for sure that one element in y is assigned to at least ceil(|X|/|Y|) values from X

do you understand this ?

[misty iris]

wdym by this

[analog tinsel]

it generalizes the concept of "if I have 3 pigeons and 2 holes, through one hole at least 2 pigeon have to pass"

do you know what a map or function is ?

[misty iris]

function yeah

wait

yk how can u make this simpler for me

[analog tinsel]

everyone can ask questions

[misty iris]

he tried to mention everyone

[analog tinsel]

oh that

oh yeah

bruh

lol

[misty iris]

...

[analog tinsel]

no I dont

I could try to use fuzzy language

[misty iris]

by showing me an example

[analog tinsel]

instead of math

I already showed you an example

5 variables

3 values

now another one

[misty iris]

now but u solve it

and tell me how u solved it

[analog tinsel]

no

[misty iris]

ok what

[analog tinsel]

well

I dont understand how this would benefit you in understanding the thing

we went through an example

thoroughly

5 variables

3 values

assign one value to each variable

so by the pigeon hole principle there is at least one value that gets assigned to at least ceil(5/3) = 2 variables

that is what I said earlier

and you agreed to understanding it

then to check your understanding I said

A = {a,b,c,d,e,f,g} and B = {1,2} , and f : A -> B a function

what do you know by the pigeon hole principle

[misty iris]

i do understand this

[analog tinsel]

what exactly do you not understand

[misty iris]

i think we already went over this

[analog tinsel]

no

your answer implied that you didnt understand yet what the pigeon hole principle was about

so I wont go on to the proof

it would be pointless

[misty iris]

ceil(7/2)=4

[analog tinsel]

correct !

and what does the 4 tell us

it says, that either 1 or 2 is assigned to at least 4 variables from A

thats the entire thing

[misty iris]

ik

i get that idea

[analog tinsel]

we cant say if 5 get assigned to one of those two

but we know for sure that 4 will

[analog tinsel]

bruh

so why didnt you answer it right away

[misty iris]

well i thought it was harder than it seemed

[analog tinsel]

ok great

now

back to the original question

I dont have so much more time left

but well finish this

do you see how the pigeon hole principle could be of use here

thinking of the variables

and their assigned values

[misty iris]

not really

[analog tinsel]

what do you wanna show here ?

[misty iris]

During a month with 30 days, a baseball team plays at least
one game a day, but no more than 45 games. Show that there
must be a period of some number of consecutive days during
which the team must play exactly 14 games.

just wanted to have the problem closer

[analog tinsel]

ok

what is the essence of what we wanna show

[misty iris]

well the answer to this is inside the problem

[analog tinsel]

ok look

I have to go

I am sorry

the main idea is

you want to show that there is one day until which you had some amount of games , lets say that number is d_i

you know d_i is at least i

and at most 45

now you wanna show there is some i < j such that d_j = d_i +14

all you have to figure out now is what values the d_i and the d_i + 14 can take

then you have an increasing sequence of variables

no you have two such sequences

and a certain range they get values assigned from

[misty iris]

ill try to work on it

[analog tinsel]

if you understood the pigeon hole principle you should make it from here on

[hybrid mica]

wat

[tame bronze]

This is for the master theorem, what is the "2nd term" they're talking about? Not sure what they mean by terms

ping if you reply please

[twilit sundial]

the second term in that equation

[tame bronze]

b^d?

[twilit sundial]

cn^d log_b(n)

[tame bronze]

why would that make the 2nd term dominate the 1st

i can see that you can replace the d with log_b a but other than that I'm not sure

[twilit sundial]

log times a polynomial dominates polynomial of the same degree

[tame bronze]

could you elaborate and show what you mean sorry using the formula i showed

i can't picture that in my head with what's given above

[twilit sundial]

f(1) is a constant, so f(1)n^d grows as a polynomial

log_b(n) is increasing, so log_b(n) n^d grows faster than a polynomial of degree d

if we take the ratio of these two we get log_b(n)/f(1)

as n grows large that ratio gets bigger and bigger

(thus the reciprocal of that ratio goes to zero)

and the one with the log dominates

[tame bronze]

Ah ok, but how does the a = b^d show that, there is no a in the equation

Since if it were a > b^d it would be something else

[twilit sundial]

it says that n is a power of b

maybe that has smth to do with it?

[tame bronze]

alr ill look into that thanks for the help

[twilit sundial]

np

[tame bronze]

sorry but @twilit sundial what does it mean when they say "n is a power of b"?

does that mean n^b is possible or that n can be found when b is to the power of some number

[twilit sundial]

n=b^k for some integer k

[tame bronze]

ah ok thanks

[twilit sundial]

np

[wide sentinel]

Should I put my entire course on a double sided cheatsheet ? 😭

Discrete maths is a little different, no ? It's not like a calculus exam where you can just paste all the past paper questions into the cheatsheet and follow instructions

[cerulean wind]

good for practice/study but probably impractical to use

[wide sentinel]

Yeah... probably only definitions will help

[cerulean wind]

i usually put weird examples/counter examples on mine if i’m allowed a note card as well. sometimes hw problems i had trouble with or thought were important too

[weary tiger]

Need help understanding absolute and relative errors and how to solve these questions

[ashen bane]

Can someone help me with catalan number question

Going from 0 to 2, in 20 steps, without going less then 0

[wide sentinel]

Can anyone help me with this question? Genuninely strong induction is killing me. Apparently we should try the induction step to reveal what the base steps are or something

I can't find any good videos on it either

[analog tinsel]

It would be helpful if you provided a clean version of the exercise

It is hard for me to read that

[analog tinsel]

What exactly is your question?

[olive cobalt]

Hey, I am working on the following problem. I think I have the solution but, I am not sure if it is correct. There are two things specifically that I am not sure about.

(1) I am not sure if I defined the first premise correctly. According to Chegg, the first premise I defined is (nor r or not f) -> (s and l). But, this would imply that if it rained and it's not foggy, the sailing race and lifesaying demonstration will happen. But, that seems incorrect.
(2) I am not sure if I can do the simplification in step 5. In the YT video from Kiberly Brehm and the textbook, they only simplify when the statement is standing alone. I am not sure if it is legal to simplify when it it's in if then clause.

Any help is appreciated!

[neon harbor]

(A and B) -> C does not decompose into A -> C and B -> C, but (A or B) -> C does

And the premise you defined as (nor r and nor f) -> (s and l) is incorrect. That they would continue the event even when it's raining doesn't matter, this is math, anything goes

[olive cobalt]

Okay. This makes sense. It felt wrong to do the simplification there

[neon harbor]

The other steps look correct, but you should fix your premise, and then break apart the implication in step 4 correctly, preferably in two steps

[olive cobalt]

So, the statement (nor r or not fog) --> s and l is just saying that the event can't happen if it's both rainy and foggy

Rains, Is Foggy --> event does not happen
Does not rain, Is foggy ---> event does happen
Rains, Is not foggy ---> event does happen
Not rain, not foggy ---> event does happen

[olive cobalt]

So, would it look like this rewritten? :
4) (7r or 7f) -> (s and l) premise
5) 7r -> (s and l). simplification of 4
6) r. Modus Tollens on 5 and 3

or am I still missing a step here?

[neon harbor]

Hmm, almost, but not quite. If it's not both raining and foggy, then we know for sure the event happens. But if it's rainy and foggy, the premise is false, so we can't use the implication. The event may or may not happen. We don't have an implication (rainy and foggy) -> event doesn't happen

[neon harbor]

That looks good, but for clarity you could consider adding a step from (not r) -> (s and l) to (not r) -> s

[olive cobalt]

Okay. You are suggesting that (nor r or not fog) --> s and l looks like this:

Rains, Is Foggy --> Not defined
Does not rain, Is foggy ---> event does happen
Rains, Is not foggy ---> event does happen
Not rain, not foggy ---> event does happen

But, if you are looking at the truth table, it looks like that. I am still a little confused 😅

[fossil mural]

yeah that's the same thing, it's just, a slightly different perspective

for instance if it doesn't rain and it's foggy, then if "(nor r or not fog) --> s" is true, then the event happened - reflected in the truth table by F T F being F, and F T T being T

so the only row where the outcome is T is the one where the event happened

if it does rain and it's foggy, then "(nor r or not fog) --> s" is true either way, which means that just knowing that it's true is not sufficient to determine whether the event happened

[neon harbor]

It's definitely confusing, but when looking at the truth table here, you need to look at the rows where the rightmost column is T, since you know the implication itself is true. Then you know f and r are true. This leaves two rows, so there isn't enough information to determine what s is

Instead of thinking with truth tables, I like to think of implications as paths or functions. If you have an implication A -> B, you know that you can get to B if you have A. If you don't have A, you can't immediately get to B, but there may be other paths to B

[olive cobalt]

Okay. I think this is making a lot of sense! I had this misconstrued in my head. Thinking about this way helps a lot!

[olive cobalt]

Just one last thing. What is this step called? I can't quite connect it to the rules I have learned

[fossil mural]

idk if there's a specific name for it, but the reason is basically that (s and l) -> s

[olive cobalt]

Okay that makes sense. Is there a reason you could apply that on the right side and not the left side. (like you mentioned here)

[fossil mural]

well you can, but you'd do it the other way around

if A -> C, then (A and B) -> C

because to chain two implications together it has to be "A -> B and B -> C"

[olive cobalt]

Oh I see. But, you can't decouple A and B beause it's part of a condition. It would break the meaning

[fossil mural]

if you have (A and B) -> C, then just having A isn't enough to use that implication, because B might be false

whereas with A -> (B and C), if you have A it's entirely valid to get B and C from the implication, then ignore the C and just conclude B, so A -> B

and if (A or B) -> C, then just an A is sufficient, because that's how "or" works

[olive cobalt]

This makes a lot of sense. Thanks for taking the time and helping out, bee and sheddow!

I am really grateful for this community. Self learning this through YT videos is only possible because of this wonderful community!

[lost wharf]

Boss energy limited pays a current dividend of $0.5, which is expected to grow at a rate of 4% indefinitely. The required rate of return agreed by Boss shareholders is 6%. What is the current value of the Boss share based on the constant-growth dividend discount model (DDM)?

[coral parcel]

That's definitely not "discrete math", and is probably a question of finance terminology rather than of mathematics.

[weary tiger]

no way, is that John Deepwoken?

[tired moat]

Curious about this. So for the first part, I know it's a permutation for any b and any invertible a. But how do I get the cycle structure?

I tried writing this permutation as a linear recurrence. $x_{k+1} = a x_k + b$ and solve that, but I got stuck

[vital dew]

Faputa

[tired moat]

Is there a nice way to see the solution without setting it as linear recurrence and solving it?

[little prism]

there is a closed formula for h(h(...(x))). not sure if that will help but it is what I would try

[tired moat]

I have tried this as well, I get a kind of a geometric series. The problem is... In both the cases (recurrence approach and that geometric series) I end up having to calculate 1/(a-1)

But a-1 may not be invertible

[slender elm]

I'm struggling with this question.
We have a bipartite graph $G$. We have a matching $M'$ with n > 0 more edges than a matching $M$. We take the symmetric difference between $M'\M$ and $M'M$, and call this $M''$. Is it true that in the new graph $G'$, with the same nodes as in $G$, there are exactly n node disjunct augmenting paths?

If I label the n edges that M' has, that M does not, from 1 to n, I could consider them one by one. I take the first edge k, so now M' has 1 edge more than M. Whenever I consider M'', it will only have the edges that belong either to M' or M (thus, the other n-1 edges that I left out will not be in M''). As the M was not maximal, there will be an augmenting path in M''. But, since I do not consider the other n-1 edges, each of these augmenting paths will be disjunct and there will be exactly n.

Does this make any sense or is there something wrong in my reasoning?

[high drum]

Could someone help with my discrete hw?

[final cliff]

It's a bit easier for people to gauge if they can/want to help if you post your qs

[high drum]

Can anyone help with this

[coral parcel]

What is your problem with it? You have the definition of A(m,n) right there, so just apply it to m=1, n=1.

[urban berry]

anyone able to help me with a graph theory proof?

[cerulean radish]

Don't ask to ask

[dreamy dew]

When we say x is an element of A union B, we can mean x is in A\B or A intersect B or B\A, but when we say x is not an element of A union B we mean x is not in A\B and A intersect B and B\A right

[coral parcel]

To say that x is not in A union B is to say that x is not in A and x is also not in B.

[pearl ermine]

need help with this. do i have to solve this using PIE? also does xn = n for some odd n means xn = n for at least one odd n?

[verbal zephyr]

"pi" is just a symbol, probably used here because it's the greek letter for p and "permutation" starts with a p. It doesnt have anything to do with 3.14...
The phrasing "for some ..." is a bit ambiguous imo, but if we take it literally, you should let n be some odd integer and compute the number of permutations with x_n = n. It's not hard to show that this number does not depend on n, so you could just take n=1 without loss of generality.

[pearl ermine]

i know its very ambiguous, but if i interpret it as x_n = n be odd at every instance, then the num of permutations become 6, and if i interpret it as "at least", then it goes beyond 2000.

the answers are miles apart

[verbal zephyr]

What do you mean by "at least"?

If only x_1 = 1 then there should be 720 such permutations, right?

Oh

wait

Yeah that makes more sense

What is the number of permutations such that there exists an odd n with x_n = n

[pearl ermine]

we can imply the same for other digits -> 3 5 and 7

[pearl ermine]

"an" odd n, thus implying at least 1 odd n right? and permutations are found out using PIE here if i am not wrong?

[verbal zephyr]

Whats PIE?

[verbal zephyr]

Yeah, I'd say at least one odd n.

[pearl ermine]

principle of inclusion exclusion

[verbal zephyr]

Ahhh yeah

I though you were asking about the symbol pi LMAO

[pearl ermine]

not at all. im mainly confused about what the question wants, as it so stupidly ambiguous. Im assuming it wants where at least 1 odd x_n = n exists, because the previous answer 6 wont make sense, they wont give something that easy.

[verbal zephyr]

Yeah I agree, the answer should be somewhere between 720 and 5040

[pearl ermine]

indeed

[dreamy dew]

Which definition of union is correct?

[brave rock]

Both are correct

Both describe the same thing.

In mathematics when we write "or" we do not mean exclusive or, and x is in A u B iff x in A or x in B.

[verbal zephyr]

I have a question: say I have some satisfiable boolean formula. I want to find the maximal subset of variables that agree among all satisfying interpretations. Is there a name for this problem?

[ashen bane]

moving from (3,6) to (8,8) without surpassing y=x+3?

im stuck with this

[shell yew]

fun fact:
the computable reals are order isomorphic to the rationals

[cerulean radish]

Wouldn't you need a bijection between R and Q?

[fossil mural]

no, computable reals

[cerulean radish]

Ah right

[brittle iron]

i have some troubles to prove this identity

any help?

[agile magnet]

Noncomputable numbers are fun to think about

[agile magnet]

ok so t^k is fixed so pull that out of the product. Write 1 / (1 - t^i) as an infinite sum via geometric series formula. That should make things clearer hopefully

[pearl ermine]

hey need help with a combinatorics problem anyone here?

[pale monolith]

Just ask don't ask to ask etc

[brisk cipher]

Hi, can I ask a question regarding graph theory?

[pale monolith]

yes

ask away

[agile magnet]

just ask, don't ask to ask

[serene iron]

First, the probability of selecting $ k $ elements from an $ n $-element set, where the $ k $th selection is the first time a duplicate occurs, is given by:

$$
\frac{\binom{n}{k-1} (k-1)!(k-1)}{n^k}
$$

This equation represents the selection of $ k-1 $ elements, multiplied by all permutations of these $k-1$ elements, and then the $k$th selection which must be one of the previously selected $k-1$ elements.

The expectation of $k$ is given by:

$$
E(k)=\sum_{k=1}^n{\frac{\left( \begin{array}{c}
n\
k-1\
\end{array} \right) (k-1)!(k-1)k}{n^k}=}\sum_{k=1}^n{\frac{n!(k-1)!(k-1)k}{\left( n-k+1 \right) !\left( k-1 \right) !n^k}=}\sum_{k=1}^n{\frac{k\left( k-1 \right) n!}{\left( n-k+1 \right) ^k}}
$$

---

Then I got stuck. I need to use the Stirling formula to find the answer for this:

$
n! = \sqrt{2\pi n} \left( \frac{n}{e} \right)^n \left( 1 + \frac{1}{12n} + \theta \left( \frac{1}{n^2} \right) \right)
$

How do I derive to this? $$ E(k) = \sqrt{\frac{\pi n}{2} - \frac{1}{3} + \theta \left( \frac{1}{\sqrt{n}} \right)} $$

[vital dew]

Aku

[serene iron]

please help me

@agile magnet

[serene iron]

had a typo

$$
E(k)=\sum_{k=1}^n{\frac{\left( \begin{array}{c}
n\
k-1\
\end{array} \right) (k-1)!(k-1)k}{n^k}=}\sum_{k=1}^n{\frac{n!(k-1)!(k-1)k}{\left( n-k+1 \right) !\left( k-1 \right) !n^k}=}\sum_{k=1}^n{\frac{k\left( k-1 \right) n!}{\left( n-k+1 \right) !n^k}}
$$

[vital dew]

Aku

[cerulean wind]

two graphs G1 = (V(G1),E(G1)) and G2 = (V(G2),E(G2)) are isomorphic if there is an edge preserving bijection between their vertex sets, i.e., a map f : V(G1) --> V(G2) such that if (v1,v2) is in E(G1), then f(v1,v2) is in E(G2)

see if this helps

[analog tinsel]

Isnt this true by definition of graphisomorphisms?

[pearl ermine]

hey can someone help mm through this problem? i do not understand what the question is asking for and what does n(A U B U C) mean in this context. quick

[coral parcel]

By the definition in the problem, n(A ∪ B ∪ C) would mean the number of different subsets of A ∪ B ∪ C, or in other words 2^|A ∪ B ∪ C|.

[pearl ermine]

ok thanks, but what is the question exactly asking for

how do i even start

all i know is 2^100 subsets of A and 2^100 subsets of B

[coral parcel]

Right. So if you call the union of all three sets D, the assumption is that 2^100 + 2^100 + 2^|C| = 2^|D|, in other words 2^101 + 2^|C| = 2^|D|.

There's only one way to make this true with integer values of |C| and |D|.

(The sum of two powers of 2 is a power of 2 if and only if ...?...)

[pearl ermine]

if C is also of the same power it seems

[coral parcel]

Yes. So what are |C| and |D|?

[pearl ermine]

C is 101 and D is 102? because of 2 * 2^101?

[coral parcel]

Yes.

[pearl ermine]

wouldnt any other value of Cs power make it so that both D and C are integers? like 100?

[coral parcel]

If |C|=100, then 2^|D| would need to be 2^100 + 2^100 + 2^100 = 3·2^100, and that cannot be a power of 2 due to the uniqueness of prime factorizations (aka the "fundamental theorem of arithmetic").

(You can see that the sum of two different powers of n is never a power of n, either by a bit of algebra, or just by imagining the addition in base n).

[pearl ermine]

i see, yes it does follow as such

ok so there are 2^102 subsets where elements of A and B and C are present, correct?

continue

[coral parcel]

Yes. What's relevant is that you know that A, B and C are all subsets of some set with 102 elements, and also |A|=|B|=100 and |C|=101.

You want to minimize 2^|A∩B∩C| which is essentially the same as minimizing |A∩B∩C|.

No, wait, it just asks you to minimize |A∩B∩C| directly. Sorry.

[white delta]

{∅} ⊆ ∅ is false

Why?

[coral parcel]

There's an element of {Ø} that is not an element of Ø -- namely Ø.

[pearl ermine]

so accumulating all elements of the subsets of A B and C would give a total of 102 elements, in any circumstance irrespective of the subset i choose from A,B and C?

u there?

[white delta]

Thank you, I understand now

[coral parcel]

I'm not sure I understand what you're saying there.

By this time in the problem we're done counting subsets.

The only thing we needed to think about counting subsets for was to find the sizes of |C| and |A ∪ B ∪ C|.

[pearl ermine]

lets make sure we are on the same track -> A has 100 elements, B has 100 elements, C has 101 elements, and the adding up all the elements from the subsets of these three sets give max 102 elements (A U B U C), correct?

[coral parcel]

Correct.

And the problem asks you to find out how few of those 102 elements can be in common between all three sets A, B, C.

[pearl ermine]

how can there be a lower bound? if i select from all the elements of all 3 sets A B and C, then all of the selected elements of A U B U C would always be common with all three sets. no elements would be left out.

[coral parcel]

Hmm, if we say (for concreteness) that A ∪ B ∪ C is {1,2,3,4,....,102}, then how can you choose 100 elements for A, 100 elements for B, and 101 elements for C, such that there are fewer than, say, 25 elements in A∩B∩C?

Note well that what we're minimizing is A∩B∩C, not A∪B∪C.

[pearl ermine]

oh so we are minimizing the elements that we select from A B and C such that they have as less common elements possible between their overlapping regions?

my bad its what the question wants

ok then continue

[pearl ermine]

am i correct?

[coral parcel]

It's probably more useful to think of: instead of selecting from already-existing sets A, B, and C, we're trying to make sets to call A, B and C by selecting some of the elements of {1,2,3,....,102} to put into each of them ... but such that we have the smallest possible three-way overlap between them.

[pearl ermine]

yes this seems more correct

its supposed to be solved using PIE

(one of the ways)

ok can you guide me through the answer?

[coral parcel]

Inclusion-exclusion is probably overkill. I'd advise you to just think about it freestyle for 10-15 minutes.

Hint: ||Instead of minimizing the number of elements in the intersection, try getting as many of the numbers as possible to be outside the intersection.||

[pearl ermine]

can a subset have the same element multiple times?

trying to reduce the area of overlap between A and B = smaller intrsection, A = 1 - 100, B = 3 - 102, im confused about C

[coral parcel]

No, a set either contains an element or it doesn't -- it has no concept of "how many times"..

Can you choose C such that it eliminates some of the numbers 3,4,5,...,100 that are in both A and B?

[pearl ermine]

well A U B gives 102 elems by the approach i went , which is essentially A U B U C

[pearl ermine]

yes but then wont it exceed the A U B U C set size threshold 102?

[coral parcel]

Why would it?

You can't eliminate all of 3,4,5,...,100 but you do have some freedom to select C.

(In fact there are exactly 102 different ways you could pick a C -- do you see why?)

[pearl ermine]

ok lets say C has 1 - 102 elements (since it must intersect with the rest 2) i eliminate few elements that are in A int B, from C then remaining elements are also in intersection A B and C but the intersection pool is reduced, is that what u mean?

u there?

@coral parcel

[coral parcel]

Huh? We already know C must have exactly 101 elements. The only choice is which of 1,2,3,...,102 make up C.

Did you read my hint from before? How can you make as many of the numbers 1,2,...,102 as possible not be on the intersection of A, B, and C?

[pearl ermine]

i read your hint, yes but ill get to it, answering this question -: Can you choose C such that it eliminates some of the numbers 3,4,5,...,100 that are in both A and B? , well if i replace the numbers hat are both common in A and B then i have to replace them with numbers that are mutually exlcusive to A or B
here they are 1,2 ... 102 -> assuming I removed 3,4,5,6 (could be any overlapping ones)

so possible intersection size is 101 (size of C) - 4 (numbers that are mutually exclusive to A or B 1, 2, 101, 102) = 97

am i correct? was this the gist behind what u said?

[coral parcel]

Yes, 97 is the answer I get too.

We choose 100 numbers to be in A, and the remaining 2 numbers to not be in A.
We choose 100 numbers to be in B, and the remaining 2 numbers to not be in B.
We choose 101 numbers to be in C, and the remaining 1 number to not be in C.
The intersection A cap B cap C consists of everything except elements that are missing form at least one of A, B, and C.
It is clear when counting in this way that there cannot be more than 2+2+1 = 5 numbers missing.
But it is also easy to choose A, B, and C such that 5 numbers will indeed be missed, just by making sure to exclude different elements from each set.
So the minimal size of the intersection is 102-5 = 97.

[gusty swallow]

intersection?

[coral parcel]

Whoops yes, fixed. Thanks.

[pearl ermine]

bruh your one seems more fluid and consistent. thank you for the help.

[coral parcel]

That comes with practice.

[edgy lintel]

im confused wouldnt log2(3) be a rational number?

oop nvm

how is my work?

[plush sigil]

quotient of two irrationals can be rational

[edgy lintel]

with the numbers given did i get the proof right?

[plush sigil]

wdym, of course the quotient of these two is irrational but you didn't prove it

[coral parcel]

Suppose r = p/q, but instead of taking logarithms, just raise both sides of 2^r to the qth power.

[sand pelican]

Hi, I want to ask if Z_n defines the set {0,1,...,n-1} or the equivalence class of integers mod n?

[coral parcel]

That depends on which book you're reading. :-)

Texts that assume their readers will go on to study abstract algebra almost always define it as equivalence classes.
Some other books (mostly aimed at high schoolers or non-mathematicians) define it as {0,1,...,n-1}, such that they won't need to explain equivalence classes.

Fortunately, the two representations are equivalent -- every equivalence class contains exactly one of the numbers {0,1,...,n-1}, and each of those numbers is an equivalence class.
And this correspondence respects the definitions of arithmetic in Z_n used in the two cases, so you can go back and forth between these views without running into trouble.

[sand pelican]

This clears up a little bit more, I was actually confused why the Klein 4-group (denoted as Z_2 x Z_2) has some matrices with entries -1, may be that "-1" is just "1" then, isn't it?

[coral parcel]

Hmm, most likely what you're reading says that the group Z_2 × Z_2 is isomorphic to the group of diagonal 2×2 matrices (with ordinary real entries) that have ±1 on the diagonal, under matrix multiplication?

(This works because Z_2 -- no matter whether we consider it as {0,1} or {Evens, Odds} -- is isomorphic to the group with elements {-1, 1} and multiplication as the operation).

[edgy lintel]

ty trop i think i got it

[sand pelican]

If we consider it as {Evens, Odd}, then the Klein4-group can also be denoted as Z/2Z x Z/2Z, right?

[coral parcel]

Sure.

[agile glen]

Does this sequence prove this pattern? I can't induct for some reason i don't understand why. Nth element can be modeled by. a func. g(x).

In fact, this sequence follows the normal sequence with the + - for odd and even numbers odd : n(n+1)/2 eve: -n(n+1)/2 . But i don't understand how one can come to this conclusion through induction without knowing about this property in advance??

[twilit sundial]

sum of first n positive integers is extremely well known

one of the CLASSIC first examples people go over when introducing induction

[cerulean wind]

what, precisely, is your question?

[agile glen]

how can I derive that this sequence has closed form of sum of arithmetic sequnce for even and odd. Without knowing that this sequnce has this property. Say I want to find the general formula for this sequnce. What are the steps I should take to come to such conclusion

[cerulean wind]

you note that $S_n$ satisfies $S_{n} = S_{n-1} + (-1)^{n+1}n^2$ for $n>1$ with $S_1=1$. Then you can use telescoping series:
$$S_n - S_1 = \sum_{k=2}^{n}(S_k - S_{k-1}) = \sum_{k=2}^{n}(-1)^{k+1}k^2$$
so that $$S_n=1+\sum_{k=2}^n(-1)^{k+1}k^2=\sum_{k=1}^n(-1)^{k+1}k^2$$

[vital dew]

c squared

[agile glen]

but terms do not cancel out? each successive term is bigger than the previous. Or the fact that it can be expressed that way is sufficient for proof?

[cerulean wind]

try $n=5$. you have
$$(S_2 - S_1) + (S_3 - S_2) + (S_4 - S_3) + (S_5 - S_4) = S_5 - S_1$$

[vital dew]

c squared

[cerulean wind]

@agile glen

[agile glen]

jeez

[cerulean wind]

what about it is jeez? lol

[agile glen]

Seems kinda easy but I don't get it

[cerulean wind]

what dont u get?

[agile glen]

the logic of this proof

shouldn't we do it like this?
$$ \text{Let} g(x) = x^2 \cdot (-1)^{x + 1} $$
$$ \text{Then } S_1 = g(1) = 1 \text{ which is the base case} $$
$$ \text{Assume } S_n = \sum_{k=1}^n g(k) \text{ has a closed form} $$
$$ S_n = \frac{n(n + 1)}{2} $$
$$
\text{Thus,} \
\frac{g(n) \left( g(n) + 1 \right)}{2} + g(n + 1) = g(n + 1) \left( g(n + 1) + 1 \right)
$$

[cerulean wind]

you need a definition for the sequence S_n in order to carry out any sort of proof.
what is your definition of S_n?

[vital dew]

src.main

[cerulean wind]

S_n is not the sum of the first n natural numbers

why do you think that S_n = n(n+1)/2?

[agile glen]

because we sum from the 1 until n'th element. and as we use 2 elments we need to div by 2

[cerulean wind]

no, its

1^2 - 2^2 + 3^2 - 4^2 + ... + (-1)^{n+1}n^2

there is no division going on here

[cerulean wind]

this matches the sequence in the picture you supplied here

so in order to prove that the sequence has that specific closed form, you first need a definition of the sequence.

via observation, it satisfies the recursive relation $S_1 = 1$ and $$S_{n} = S_{n-1} + (-1)^{n+1}n^2$$ for $n>1$

[vital dew]

c squared

[agile glen]

yes, there is no division. But n n + 1 / 2 is arithmetic progression's' closed form. And we have arithmetic progression of some sort through fn g(x)

[cerulean wind]

its not an arithmetic progression due to the (-1)^{n+1} term

[agile glen]

that's why I thought that this is the way and we just replace n with g(n)

[cerulean wind]

besides, that would be the sum of the first n squares

you are using the wrong formula for two different reasons

[cerulean wind]

if you want to do this by induction, you need to show that

$S_n = \sum_{k=1}^{n}(-1)^{k+1}k^2$ for all natural numbers $n$ using this base definition of $S_n$

[vital dew]

c squared

[agile glen]

because we have a sequence from 1 to n which is tranformed by this function g(n) hence this is arithmetic progression?

[agile glen]

and that's why I tried this by induction and failed

[cerulean wind]

no. why are you so insistent on using g?

g doesn't fit in to this nicely

[agile glen]

because that was my first approach and i don't know how to do it otherwise lol)

and i see that it does not work

and I dont know why

[cerulean wind]

so, g is just being used as a wrapper function, a concise name for the general term (-1)^{k+1}k^2

[agile glen]

yes, exactly

[cerulean wind]

okay fine, really no need for that since its a short formula, but your guess at what S_n is here is completely off

its not an arithmetic progression

[agile glen]

it is? because it fits nicely with n(n +1)/n for odd and -n(n+1)/n for even numbers

[cerulean wind]

the difference between consecutive terms is not constant

[agile glen]

ohhh

[cerulean wind]

that is the definition of an arithmetic sequence

the difference between consecutive terms S_n and S_n-1 is (-1)^{n+1} n^2

which is why your attempts failed

[cerulean wind]

try to understand this.
all i did was define S_n and perform some algebraic manipulations

there isn't even any sort of logical argument going on

just symbolic manipulation

[agile glen]

i went this route because of this

i thought let me find and prove the closed form for left side

and since the right side is arithmetic i went this route on the left as well

[cerulean wind]

the sequence S_n itself is not arithmetic though

you can algebraically manipulate things to get it into the right hand side

[agile glen]

yeah, this completely went over

and I tried doing it with arithmetic

[cerulean wind]

the way you do that is to group terms in the sum together and use the difference of squares formula

for instance, 1^2 - 2^2 = -(2^2 - 1^2) = -(2 - 1)(2 + 1) = -3

[spare zodiac]

Yo I have a question maybe someone could help: find all X such that X∈Z
16x^(2)+1=k^(3)

[valid gale]

1+1=2

omg

[obtuse lance]

https://math.stackexchange.com/questions/5914/integral-solutions-to-y2-x3-1

[spare zodiac]

ty for helping

[pearl ermine]

hey how does the right hand side equate to the left hand side here?

[obtuse lance]

factor out the n! and then look at how the indices start from a different number

[pearl ermine]

starting from k=0, the first term becomes n! an the rest remain same with just the signs flipped which is essentially what subtracting does. Got it thanks.

[silver ermine]

guys

I'm reading about hashing

can someone explain this to me as i'm 10

Nvm it's a typo

[tight hound]

How do you compute the number of connected graphs without the restriction?

It seems to me that thinking of your original problem in terms of graphs might be overcomplicating it

Thanks

Hmm

[mental mirage]

damn this is related to graph theory it was a nt problem for math olympiads i did

ya but iirc the nt sol was just m^2+1=(m+i)(m-i) , and working in Z[i]

hmm interseting

its the like gaussian integers thing

[tight hound]

How does that lead to a solution for this problem?

[mental mirage]

i forgot exactly but like it was something like product of m+i now observe (i+1)....(i+p-1) already has ig a nice expansion?

wait it was evan chens handout lemme see

[tight hound]

Hmm ok

[mental mirage]

ah wait so like u have the plynomial P(x)=(x+1)....(x+p-1)

now u can prolly consider like

the powers of x

which are 0 mod 4

1 mod 4

2 mod 4 and 3 mod 4

so in 1 mod 4 and 3 mod 4 ig those sum to 0 through pairing

and so only 0 mod 4 and 2 mod 4

ahhhh waiit P(x)=(x+1)...(x+p-1)x is always 0 mod p

if x is integral

so by that i think we can show all the middle coeffiients is 0 mod p

like newtons method of differences

ya i think this is identical to x^p-x in F_p[X].

by that all middle coeffiients is 0 mod p

so (i+1)...(i+p-1)i mod p = (i^p-i)

and like ig u can cancel out the i

so i^(p-1)-1 basically

rest is easy

so ig the answer is (i^(p-1)-1)^2

and basically p=3(mod 4) is the hard case

in which ig it comes out to 4?

ohk nice!

ya

[thorny crystal]

would it be allowed to assume FTSOC that the hypothesis is false and then find an example that proves my assumption of the hypothesis being false was incorrect. thereby proving the original statement is true

please ping if yall could

[pale monolith]

doing this doesn't prove that it holds for all sets, just that it holds for that specific set

[thorny crystal]

No but saying that it contradicts my original statement means that it has to be the other possible truth value then indefinitely, no?

[pale monolith]

your hypothesis is "For all sets A,B,C bla bla bla". The opposite of this is "There exist sets A,B,C such that not bla bla bla"

the hypothesis holding for some A',B',C' does not mean "There does not exist A,B,C such that not bla bla bla"

it means "There exists A,B,C such that bla bla bla"

[clever sail]

the contradiction of smth being false is it being true in all cases not just one, cause the arrow means implies (so it has to work for every case)

but with the other way around when you assume something is true, you only need to prove one case of it being false for a contradiction. so its not the same

[drifting sand]

Assuming twac that this is false means assuming

There exist sets A, B, C such that AxB = CxB but A=/C
is true. No single example will disprove this statement

[drifting sand]

Directly disproving this statement as it stands would be done via counterexample (tho i dont think its false if x here is just cartesian product)

[thorny crystal]

so @clever sail @drifting sand @pale monolith you guys think the statement is true?

[drifting sand]

Pretty sure it's true

also woah fellow uw student hi

AH wait

counterexample, $B=\varnothing$

[vital dew]

Sara

[drifting sand]

Then A and C can be anything

u need B nonempty for this to hold

[clever sail]

yeah

[mental mirage]

ok so if u dont know this lemme explain

consider the polynomial P(x)=x(x+1)....(x+p-1)

this is always =0(mod p)

and also consider G(x)=x^p-x

feramrt lil says this is always =0(mod p)

so P(x)-G(x)=0(mod p) always

for integers x

now observe deg P(x)-G(x) <=p-1

And there is a well known lemma that if a integer polynomial with degree atmost p-1 is always divisible by p

all of its coeffiicents are as well

by that we basically get to that

the polynomial part was only this

and gaussian integers u dont really need to know much except , i will just replace things so that u can understand gaussian

say i have two complex numbers a+bi and c+di

where a,b,c,d are integral

and say (a+bi)(c+di) is real

if i define a+bi=x+yi(mod p) iff a=x and b=y mod p

then observe i can say (a+bi)(c+di)=(a mod p+ b mod pi)(c mod p+dmod p i)(mod p)

This is essentially what i did over there i reduced the compelx numbers to mod p

yaa

[mental mirage]

like a+bi and c+di represented the other one

ya so its = x^p-x(mod p) over guassen as well

[tepid pecan]

can someone check my working?

[wraith summit]

looks fine to me. you forgot a set of parentheses in step 2 but remembered to include them in the next step so its all good

[blazing rose]

Why does this hold?

The integers are also countable but have non-well founded subsets for example the set of all negative integers

[odd heart]

Yeah, I'm not sure what they're going for.

You can define an ordering of the integers in which every subset will have a smallest element (although it won't be the ordering we're used to), but you can also define such an ordering on every set (assuming we're accepting the axiom of choice)

So (un-)countability doesn't affect whether it's possible

[blazing rose]

Yea true

Basically the same pattern I would construct my bijection in

[odd heart]

Yeah,pretty much. Given a countable set, you can "transfer" the ordering from the naturals using the bijection, getting a well-founded ordering.

For an uncontable set you can't do that, but that doesn't mean a well-ordering doesn't exist at all

[blazing rose]

This would be a good ordering to Argument geometrically abt the countability of rationals. What I am wondering about is, what about elements like (2,2), (3,3)? Would the function describing this pattern not also map those to 1 in N which means that f: N x N -> N wouldn’t be injective anymore?

[fossil mural]

...ok wait, is your question about the countability of N x N, or the countability of Q

[blazing rose]

Oh yeah sorry

[fossil mural]

if you want N x N then you can just enumerate (1,1) (1,2) (2,1) (1,3) (2,2) (3,1) (1,4) (2,3) (3,2) (4,1) etc. and stuff like (2,2) isn't a problem because that's a different pair to (1,1)

[blazing rose]

I meant f: N -> Q

[fossil mural]

well it's actually fine that it's not injective, we just need it to be surjective

if you can list the rational numbers with repeats, you can then just delete all the repeats (keep only the first time that any given number appears) and you get a bijection

which in fact is exactly what the order in that image is doing

2/2 was just skipped

[blazing rose]

Ah I see

But what about the constraint of a function being totally defined? For every input there must be an output right

[blazing rose]

I actually meant f:Q -> N

[fossil mural]

well yes but we can just like, shift the rest of the sequence over

[blazing rose]

Ah okay makes sense

Thanks a lot :)

[fossil mural]

you do actually have to check that you don't then run out of rational numbers, because a surjection f : N -> X doesn't imply that X is infinite

but there are clearly infinitely many rational numbers so

[blazing rose]

Yes

[void shard]

My most illegal proof for Sum of Cubes series

1^3 = (1*1)*(1)
1^3 + 2^3 = (1*1 + 2*2)*(1 + 2)
1^3 + 2^3 + 3^3 = (1*1 + 2*2 + 3*3)*(1 + 2 + 3)
...
You know the rest

[coral parcel]

That looks like just an assertion rather than a proof. And what it asserts is false ...

[pearl ermine]

im seriously confused with this question, i do not understand how combinatorics is involved in this question. can someone help? since we are only considering about post lunch, the way they are signed pre lunch wont matter right?

[coral parcel]

"Counting ways that something can happen" is what combinatorics is, no matter how bizarre and ad-hoc the circumstances.

[fossil mural]

well if she signed a racket before lunch then she isn't going to sign it again after lunch, so it matters which rackets she signed

but you're right that the order that she signed rackets before lunch isn't important

[pearl ermine]

k but how is this related to adding components like this:

[fossil mural]

it isn't

writing down formulas like that just for the sake of it isn't combinatorics

the reason you think it is is that often formulas like that are counting some kind of object, which is what combinatorics is

[pearl ermine]

k but im asking bout the semantic meaning behind this

in relation to the question

[fossil mural]

oh did you mean that that formula is supposed to be the answer to the question

[pearl ermine]

yes

but i dont understand how

[fossil mural]

hm

it looks like the assumption is that she might not sign all of the rackets?

wait no that doesn't make sense

oh i get it

...no i don't

that might just be wrong actually??

but ok i can explain some of what they were going for

the reason "8 choose k" is showing up is that we're picking which rackets weren't already signed before lunch

any subset of rackets 1-8 is possible, for instance if we assume that for each racket we want to exclude she signed it as soon as it arrived

then we have an extra factor to account for when the 10th racket arrives

oh wait i get it now, they're right

the 10th racket might have already been signed before lunch

or it could appear in any of the k+1 "spaces" around the k other rackets that are being signed

[fossil mural]

the reason the order of the k rackets isn't relevant is that the rackets will be signed in descending order of number, because they arrived in ascending order and she always signs the one that arrived most recently

so the only order uncertainty is the 10th racket

[pearl ermine]

bro how did u assume thhat they arrived in ascending order, this is another confusion of mine

and is the possibility k + 1 transformed to k + 2 because of the possibility that the 10th racket hasnt arrived at all? but how would u draw out this assumption from the question?

[coral parcel]

The problem says "given that the order of rackets' arrival is fixed", so we can decide to use the number of arrival to identify each racket.

[coral parcel]

k+1 of the cases are for when the 10th has not arrived yet -- it can arrive at different time during the afternoon, relative to the k signings of rackets that arrived in the morning.
The last 1 is for the case where the 10th arrived and was already signed before lunch.

[pearl ermine]

yea but the arrival order isnt stated, could be like 4 3 5 6 1 7 8 9 right? in any order

[pearl ermine]

ahhh i see so the 10th was signed and removed off early before signing # 9 , thats why it wasnt included, understood the rest ty

[coral parcel]

No because we're using "1" to mean "the racket that arrived 1st", and 2 means "the racket that arrived 2nd" and so forth.

All the nodes in a clique need to have different colors.

[pearl ermine]

oh ok i get it, but by any chance is there any possibility of overcounting any sequence, by this method?

[coral parcel]

Not as far as I can see -- but you really ought to think it through enough to convince yourself that every possible order of afternoon signings will be counted exactly once.

[pearl ermine]

since combinations are being employed instead of permutations, each set would be counted once only, it seems it would negate the chances for sequences being overcounted.

[pearl ermine]

could we have done it without assessing the 10th racket individually and combining it altogether like 9CK instead of 8CK?

[coral parcel]

That would not account for afternoon-signing sequences such as 8 6 4 3 10 2 1.

[short geode]

How many subsets $A \subset B \subset {1,2,3,...,n}$?
is there a closed form of $\sum_{i=0}^{n}2^i {n \choose i}$?

[vital dew]

tomer_k

[little prism]

each element of {1,..,n} is either in A, in B\A or in {1,..,n}\B

[short geode]

Thats clever, thank you

[olive cobalt]

Hey guys, I am working on this problem and I am stuck. I am proving something that is obviously not true using propositional logic. I know logically that if A is a subset of B, then A and B is A. But, in my proof, I somehow proved that A and B = B. Can someone point where I am going wrong here?

I suspect it is to do with me switching from instantiatoin but, I can't quite put my finger on it. Because I am using the rules of inference for propositional logic for the problem.

[fossil mural]

that is a correct result given your premises

$\forall x ((x \in A) \land (x \in B))$

[vital dew]

bee [it/its]

[fossil mural]

this implies that both A and B contain literally everything

and your conclusion, that B contains literally everything, is a valid deduction from that

none of this has much to do with what $A \cap B$ is in the case that $A$ and $B$ \textit{don't} contain everything

[vital dew]

bee [it/its]

[twilit pendant]

how to be good at Combinatorics ? like i study a lot but still bad at it

[fossil mural]

$A \cap B = B$ isn't the statement you proved, it would be the statement $$\forall x (((x \in A) \land (x \in B)) \iff x \in B)$$

[vital dew]

bee [it/its]

[olive cobalt]

Hm... Gotcha. I think I see the problem.

[olive cobalt]

Thanks for the help bee. I don't quite see the way to solve the problem yet. But, I am pretty sure I can get there!

[pearl ermine]

hmm problem is that lets say we start with 9C9, 10 can appear anywhere, and using combinatorics in this way doesn't account for the different positions for 10, so ultimately assessing it individually gives us more flexibility to integrate the possibilities where 10 may arrive at different positions, and even if we go with k + 2 possibilities for placing 10 anywhere between the gap, then including 10 in the combination renders useless, am i correct?

[vital dew]

hidingandseeking

[fossil mural]

basically it's saying that all of the edges in G, between vertices that are in H, are also in H

so for instance if you have the graph with two vertices and an edge between them

you can have the subgraph of that where you just get rid of the edge, but still have both vertices

but that isn't an induced subgraph, because in G those two vertices have an edge between them, and in H they don't

so any subset of the vertices uniquely determines an induced subgraph: you only delete the edges that would be going to vertices that don't exist anymore

there isn't really much reason to write that as an equivalence because the forward direction is already part of what a subgraph is

so the important part is the backwards direction

[coral parcel]

That sounds broadly right, yes.

[whole urchin]

Anyone that can help me with math?

[clever sail]

post question

[shadow lion]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[twilit sundial]

math discord users ask a good specific question challenge (impossible)

[shell yew]

I was thinking about what would happen if there were two successor functions instead of one, what do you guys think?

(n is basically like 0 or an empty string)

[shell yew]

you could even define tetration for this if you wanted too

(ab)^^(aba) = (ab)^((ab)^^(ba)) = (ab)^((ba)^(ab)) = (ab)^((ba)*(ab)) = (ab)^(baab) = (ba)*(ab)*(ab)*(ba) = (baab)*(ab)*(ba) = (baababba)*(ba) = abbabaabbaababba

[pearl ermine]

i need help with (b) I do not understand the mechanics behind solving it via 1 to 1 correspondence, and is the way i solved it correct? -> min sum could be 101, and max would be 606, constructing a probability distribution graph, which would presumably be a rectangle, i took the rounded up value of the midpoint which is 354.

[fossil mural]

the graph is definitely not a rectangle

a sum of 101 requires all of the dice to roll 1, which is a 1 in 3,919,911,741,000,425,436,580,141,602,948,346,923,222,862,262,837,729,229,258,431,798,216,982,848,864,256 chance

[pearl ermine]

how? each sum has an equal probability

[fossil mural]

whereas something more in the middle like 350 is significantly more likely because there are so many more ways it could happen

[pearl ermine]

yes but averages are taken in such instances if i am not wrong

[fossil mural]

...?

well like, if it was a rectangle, the chance of a sum of 101 should be 1/500ish, right?

and it's nowhere even close

i ran this 100,000 times and the most extreme results i got were 278 and 429, which each occurred once, and 354 occurred 2370 times

[pearl ermine]

area under the probability distribution graph gives the probability of an event, and as to my knowledge it seems as though it would be a rectangle, so 1/2 of the area lies at 353.5, and since s is an integer any shift to the right would make the probability greater than 1/2.

[fossil mural]

well it's not a rectangle

why would it be a rectangle

[pearl ermine]

because all of the sums are equally probable

[fossil mural]

no they aren't

[pearl ermine]

from 101 to 606

[fossil mural]

think about what it would actually mean to get a sum of 101

[pearl ermine]

i think the my statement only holds true for max and min values, but the intermediaries may have more paths to them , like rolling 2 dice, only 1 way to get 2 or 12, but 3 ways get 6 -> 4,2 5,1, 3,3, and so on so the probabilities are skewed for some integers.

[odd heart]

Also this is a discrete distribution so it doesn't have a pdf

[pearl ermine]

is this what u were trying to say?

[fossil mural]

yes

there are way more ways to get 350 then there are to get 101, so 350 is more likely

[pearl ermine]

ah my bad

k but then how do i solve this using 1 to 1 correspondence?

[fossil mural]

i mean i don't really get what you mean by "using 1 to 1 correspondence" but i think i do know what the solution is

[pearl ermine]

it says : there is a 1 to 1 correspondence with -> {the rolls with sum greater than 353} to {the rolls with sum less than 354}

man im confused

[fossil mural]

ah ok yes that makes sense

well if you have like, the one way you can roll dice to get 101

if you just invert all the dice (swap 1 and 6, swap 2 and 5, swap 3 and 4)

you get the one way you can roll dice to get 606

all of the 101 ways you can get a sum of 102 (all 1s except a single 2), correspond to the 101 ways you can roll dice to get 605 (all 6s except a single 5)

this "flipping" operation on the dice sends x to 7 - x, so the effect on the overall sum is that you get 707 - s

so you keep going until you reach 353, where flipping it makes the sum 707 - 353 = 354

and the point is that this transformation preserves the probability

the chance of a sum of 105 is the same as the chance of a sum of 707 - 105 = 602

adding it all up, the chance of a sum <= 353 is the same as the chance of a sum >= 354

because "a sum >= 354" is the same as "a sum <= 353, and then we invert all the dice", so it's the same probability

looking at it in terms of a graph - the insight here is that, even though the graph isn't a rectangle, it's still symmetrical

so we can just cut it down the middle and get half on each side

[pearl ermine]

why do we even need to bother with the flipping operation? what is the speciality or purpose behind its implementation in this case?

[fossil mural]

well it's the reason that it's symmetrical like this

and if you look at a case where it's obviously not symmetrical, like "the dice are biased and have a 50% chance of rolling 6 and 10% chance of anything else"

if you try to run the same "flip" it now changes the probabilities, the chance of 606 and the chance of 101 aren't the same because if you flip something with 6 in it it becomes less likely, and that's "why" it isn't symmetrical

similarly if we just remove 5 from the dice, rolling 605 is actually impossible now, but 102 is still possible, so again it's asymmetric

[pearl ermine]

yes, it seems flipping any sum formed, adding it with its flipped version always results to 707 no matter what, the flipping operation matches the summation of numbers that are equidistant from the midpoint

but how did u figure out the reflective symmetry which would end up giving 1/2, is it just by dividing by 2, why so?

[fossil mural]

well the reason you get 1/2 is that you end up dividing it into two equal pieces, "sum <= 353" and "sum >= 354"

[pearl ermine]

with 353.5 being the midpoint, i see ... thank you

[rich sparrow]

hi what do i do when i got this i know how to do the truth table but not when i got this

any idea @fossil mural

?

[vivid osprey]

I'm very new to this, but I'm reading in some lecture notes about the connection between permutations and the determinant. Consider the set ${1,2,3}$ and the permutation ${2,1,3}$. Then they use the notation $\sigma=213$ and write $\sigma_1=2, \sigma_2=1$ and $\sigma_3=3$. Then later on, they talk about transpositions, but without introducing any notation for a transposition. Specifically, in proving that a permutation cannot be expressed as both an even number of transpositions and an odd number of transpositions, they write $\sigma=\tau_1 \cdots\tau_n=\rho_1\cdots\rho_m$, where $\tau_i,\rho_i$ are transpositions, but what does $\tau_i$ mean for example?

[vital dew]

Philip

[odd heart]

The phrase "$\tau_i,\rho_i$ are transpositions" is shorthand for "for every $i\in{1,2,\ldots,n}$, $\tau_i$ is a transposition, and also for every $i\in{1,2,\ldots,m}$, $\rho_i$ is a transposition"

[vital dew]

Outsider

[odd heart]

I'm not sure there's notation for transposition, since it's just a permutation that fixes all but two elements.

And in this particular argument it doesn't matter what each of the transpositions does specifically

[vivid osprey]

ok, I agree, this is a bit weird, but I think I understand. I wrote above \sigma_1=2, \sigma_2=1 and \sigma_3=3 for the permutation {2,1,3} of {1,2,3}, so the first two are in fact a transposition, or?

maybe that doesn't make sense either

It looks odd to me, since the permutation here I would say consists of a single transposition, not two.

[odd heart]

Ah yes, there's confusion in notation, because the $\sigma_1,\sigma_2,\sigma_3$ aren't 3 separate permutations, it's how they denote what this particular one permutation ($\sigma$) does. And then each of the $\tau_i$ is a separate permutation (transposition)

[vital dew]

Outsider

[odd heart]

I now see what your question was actually about, sorry..

So yeah, unfortunate and ambiguous notation.

And yes, the permutation that moves 1 to 2, 2 to 1, and leaves 3 in place, is a transposition.

[odd heart]

So basically the lower indices in the first part and in the second part have different meaning here (first they denote the elements of your set, to indicate the values of sigma at those elements; and in the second part the lower indices are used to enumerate the transpositions into which you decompose sigma)

[vital dew]

Outsider

[odd heart]

Or possibly \sigma(2) = 1, I can never remember in which direction those notations go

But either way it's about the values of sigma at individual elements of the permuted set

[vivid osprey]

right, thanks 👍 I understand now I think. \tau_i denotes some function (a transposition), not an evaluation as in \sigma_1=2

[odd heart]

Yeah

[magic hill]

What is the meaning of the small circles?

[cerulean radish]

Most likely composition

[twilit pendant]

can i have an example of a surjective but not injective function

such that |A| = |B| like if it's from N it also goes to N

N -> N

[cerulean radish]

Consider f: N -> N given by f(0) = 0 and f(x) = x-1 for x > 0

I am assuming by N you meant nonnegative integers

@twilit pendant

[twilit pendant]

natural numbers

[twilit pendant]

do u have another example

😅

because this is what our teacher gave us

[cerulean radish]

What's wrong with that example? So that I know which one you would like more

[twilit pendant]

N was an example we can also be in R->R or anything

[cerulean radish]

You could also consider f: R -> R given by f(x) = tan(x) when tan(x) is defined and f(x) = 0 for other x

[twilit pendant]

oh well that sounds cool thanks

[coral parcel]

An even simpler example would be f(x) = x³-x as a function R->R.

[rich sparrow]

anyone familiar w this?

[clever sail]

which part are you confused on?

[rich sparrow]

i need to solve a gentzer system and idk how to say that this is a alpha formula or b formula

this exercie dont look at the words on the side

[clever sail]

$\neg$ means not, $\wedge$ means and, $\vee$ means or

[vital dew]

chipotle

[rich sparrow]

im trying to understand when i use the b formula or a formula

yes i know that

[clever sail]

so do u get what this table is saying

[rich sparrow]

i dont understand this

what is b1 and b2

@clever sail u there?

pls tell me

ill try to figure the formulas after

[clever sail]

well the table is basically just giving logical equivalences

so like not not A is the same value as A

A1 and A2 means both A1 and A2 are true independently

etc

are u familiar with that stuff?

[rich sparrow]

yes

[clever sail]

ye then i dont rlly know how to help further perhaps someone else does

or maybe try #proofs-and-logic

[rich sparrow]

ill try im rly desperate cant find much on internet

[clever sail]

youll prob find someone in this server who can help

jst ask around

[rich sparrow]

is there a general chat

where i can ask for everything

[clever sail]

there are help channels and also #discussion #math-discussion #serious-discussion

[upbeat flame]

joe

[shell yew]

would it be true to say that the completion of the lexographic order on Q x Q would just be Q x R but with the ordering of irrationals squeezed in between the {q} x R's?

[unique halo]

can anyone help me out with this

[cerulean radish]

!status

[lofty cloud]

What step are you on?
1. I don't know where to begin.
2. I have begun but got stuck midway.
3. I got an answer but I was told that it's wrong.
4. I got an answer and would like my work checked.
5. I have a question about someone else's work/solution.
6. I have completed the problem and don't need help anymore. Thank you.
7. None of the above

[unique halo]

1 and 2

[cerulean radish]

If you have some work, you could show it