discrete-math

[empty spire]

but never mentioned what a hypotheses actually is

give me the solution just if you know

[coral parcel]

The amount of effort you're willing to expend to avoid learning anything is staggering. But no.

[empty spire]

you actually dunno

I know implication

I've read rosen's book

watched neso academy's video

but none of them cleared this

[coral parcel]

If you actually knew the answer to the question, why have you spent half an hour begging people to give that answer to you instead of just answering it and moving on?

[empty spire]

why are wasting your time here if you think that you've masted everything in this universe?

fuck off

agree that you dunno the answer, just tried to be cool and oversmart, lol 😅

where have everyone gone now? madafakas 🥱 🤮

[final cliff]

This is a lame way to talk to people

[stray reef]

you sure won't make anyone else want to talk to you if you act as obnoxious as you've been doing for the last dozens of messages

[final cliff]

Like, people here are super willing to help if you aren't rude and make a bare minimum effort to try and learn stuff.

[gritty crescent]

@empty spire Either cooperate when others are helping you or don't bother asking here. This server does not encourage handing out answers.

[empty spire]

if no one knows the ans. then how can they help? 😅

[gritty crescent]

The same subset of users helps countless users in this same channel, if you scroll up. It's not difficult to attest their skills and intent.

They know the answers, they're not keen on handing them out.

[empty spire]

if they don't know how to talk with others humbly then I don't give a fucking shit on their skills

[gritty crescent]

The objective is to help someone learn, and hence it would be more useful that you try to look up things to learn when you're told to do so.

[empty spire]

I just asked a simple question

[final cliff]

Your question is basically answerable by reading what is probably a two paragraph explanation defining what a conditional is.

[gritty crescent]

It seems you aren't faring well on that front either...

[empty spire]

It was just a simple question

[gritty crescent]

And the suggestion was equally simple

As has been pointed out by 3 users so far

[empty spire]

but they didn't gave the suggestion

[gritty crescent]

You're choosing to overlook all of that

[empty spire]

they started to talk with me rudely

That's why I fucked their sexy mom 😐

equal equal

[stray reef]

in the time and energy wasted on this trainwreck of a discussion, you could've read the necessary theory like thrice over...

[empty spire]

@coral parcel hey madafak, I wanna fuck your mom 😐

[final cliff]

You're going to really struggle a lot when you need help if you handle criticism like this often lol.

[gritty crescent]

This may have come across as harsh or intimidating but it really is the answer. Your problem above is really a matter of looking up the definition of an implication, or examples if you still feel confused. This is basic mathematical learning practice, nothing fancy.

[empty spire]

I didn't get help, so I don't need help anymore from these fucking assholes 😐

[gritty crescent]

Alright, I think we're beyond the scope of making this productive.

Take some time to look up the definition of an implication, in your textbook or on the internet. You'll hopefully not have to ask the people here for help when you do.

[tidal tulip]

if i were to write out more of the terms in the differences of powers then would this be accurate

(x^p+1 - y^p+1) = (x-y)(x^p + x*p-1 y + x^p-1 y^2 + x^p-3 y^3 + … + x^2 y^p-2 + x y^p-1 + y^p)

[obtuse lance]

yeah, but when you type your exponents you should really put parenthesis x^(p+1)

also this is a good place to use the sigma sum notation

[tidal tulip]

x^p+1 - y^p+1) =

(x-y)(x^p + x^p-1 y + x^p-1 y^2 + x^p-3 y^3 + … + x*3 y^p-3 + x^2 y^p-2 + x y^p-1 + y^p)

i added one more term just to see the pattern this still looks good yeah?

what’s a clean way to write the sigma notation for this

[obtuse lance]

it's probably better if you try to work that out for yourself, maybe try working with specific examples like p=3 or p=4 if you're having trouble

[spice basin]

How do i need which set is a finite cardinality

by definition, finite cardinality is the set we can finish counting

but it seems unable to be applied in this ws

[stray reef]

why not? set (i) clearly has at most four elements, even if you can't yet tell for sure how many

though actually the biquadratic equation in its definition is not hard to solve

@spice basin

[final cliff]

How many roots can an nth degree polynomial have?

[pastel hollow]

How can I find an asymptotic solution to the recurrence

$$T(n) = 4T(n/4) + 2T(n/2) + C$$
I replaced the $4T(n/4)$ with $4T(n/2)$ and used the master theorem to get an upper bound of $O(n^{\log_2 6})$ and I replaced the $2T(n/2)$ with $2T(n/4)$ to get a lower bound of $\Omega(n^{\log_4 6})$, but how can I find a tight bound?

[vital dew]

EdgarAlnGrow

[pastel hollow]

<@&286206848099549185>

[uneven violet]

Apply Akra-Bazzi https://en.wikipedia.org/wiki/Akra–Bazzi_method @pastel hollow

[narrow trench]

Wow, that's a swiss army knife powerhouse of a theorem if i've ever seen one

[cerulean wind]

fr

[wicked basin]

what does "dont assume the triangle inequality" mean?

[uneven violet]

The triangle inequality in this case means that if you let d(x,y) be the shortest distance between two nodes x and y, then for any nodes x, y, and z, you have

d(x,y) <= d(x,z) + d(z,y).

So detours are always longer for instances of TSP that satisfy the triangle inequality.

@wicked basin

[weary tiger]

can someone tell me the marked question ?

[lilac glacier]

help me please: prove that .... is divisible by 37^2

by induction

I've been trying this

but idk what else to do

[civic horizon]

here is a outline of a solution

1. Note that you can first reduce the "coefficients" of the terms 3^(6n-2), 4^(6n-2), 7^(6n-2) by any multiple of 37^2

2. Then note that by your induction hypothesis you can subtract 728*(3^(6n-2)+4^(6n-2)+7^(6n-2)) from your expression, and now it remains to show that the resulting expression is divisible by 37^2

3. The coefficients of 4^(6n-2) and 7^(6n-2) will be divisible by 37, so the problem simplifies to show that an expression is divisible by 37

4. Finish by noting that 4^6 = 7^6 = 26 mod 37

[distant grove]

hey guys

I am working on some code for an ellipse algorithm

I need some help adapting it so that the centre of it is not 0

does anyone have ellipse algorithm experience

class MidpointEllipseAlgorithm {
    fun compute(p1: Coordinates, rx: Int, ry: Int) {

        val idp = Coordinates(0, ry)

        var xkp1 = idp.x
        var ykp1 = idp.y

        var lxkp1: Int
        var lykp1: Int

        var p1k = (ry * ry) + ((rx * rx) / 4) - (ry * (rx * rx))

        println("($xkp1, $ykp1)")

        while (
            (2 * (xkp1 + 1) * (ry * ry))
            <
            (2 * ykp1 * (rx * rx))
        ) {
            p1k += if (p1k >= 0) {
                xkp1++
                ykp1--

                lxkp1 = xkp1 - 1
                lykp1 = ykp1 + 1

                (ry * ry) + (2 * (lxkp1 + 1)) * (ry * ry) + (rx * rx) * ((ykp1 * ykp1) - (lykp1 * lykp1)) - (rx * rx) * (ykp1 - lykp1)
            } else {
                xkp1++

                lxkp1 = xkp1 - 1
                lykp1 = ykp1

                (ry * ry) + (2 * (lxkp1 + 1)) * (ry * ry) + (rx * rx) * ((ykp1 * ykp1) - (lykp1 * lykp1))
            }

            println("($xkp1, $ykp1)")
        }

        var p2k = (ry * ry) * ((xkp1 + 0.5) * (xkp1 + 0.5)) + (rx * rx) * ((ykp1 - 1) * (ykp1 - 1)) - ((rx * rx) * (ry * ry))

        while (
            true
        ) {
            if (xkp1 == rx && ykp1 == 0) {
                break
            }

            if (p2k >= 0) {
                ykp1--
                lykp1 = ykp1 + 1
                lxkp1 = xkp1

                p2k += (rx * rx) - 2 * (rx * rx) * (lykp1 - 1) + (ry * ry) * ((xkp1 * xkp1) - (lxkp1 * lxkp1))
            } else {
                xkp1++
                lxkp1 = xkp1 - 1
                ykp1--
                lykp1 = ykp1 + 1

                p2k += (rx * rx) - 2 * (rx * rx) * (lykp1 - 1) + (ry * ry) * ((xkp1 * xkp1) - (lxkp1 * lxkp1)) + (ry * ry) * (xkp1 - lxkp1)
            }

            println("($xkp1, $ykp1)")
        }
    }
}

fun main() {
    MidpointEllipseAlgorithm().compute(Coordinates(0,0),8, 6)

    println()
}

I am wondering how I would adapt it so I accept a parameter and it draws from that coordinate instead of from 0 , 0, ie adapt it so it conforms to a coordinate plane of a computer instead of a mathematical plane

can some1 help

[distant grove]

nvm figured it out

apologies

[dark oyster]

How can I solve this by generating functions

[cerulean wind]

try differentiating the geometric series

[distant bobcat]

Does anyone know if finding the spectrum of any given matrix is bounded in polynomial time? I know it holds for sparse matrices, but Im sure if it holds in general.

[worldly knot]

how is the answer 171?

this is converting from postfix, to prefix notation

[stray reef]

@worldly knot i am getting neither 171 nor -0.34 here

do you have an answer key that says this expression evaluates to exactly 171?

actually, do you still need help with this at all?

[worldly knot]

yeah i actually got it now, thanks tho!

[worldly knot]

is there a way to get the answer the fastest here?

i actually tried doing it manually but i wasnt sure whether it would be the shortest or not

[versed nimbus]

Anyone here

I need help with discrete please I have an exam tomorrow

Anyone here

[wide vine]

Maybe I am sending you down the wrong path but why do I feel like this is one of them graph algorithms where you find the shortest distances between in this case 8 cities. Like a traveling salesman type problem.

me replying to someone that posted at 4:03pm and it is 9:20pm

[worldly knot]

this quiz is actually on the topic of Dijkstra Shortest Path Algorithm

but with the examples that we had, I do not know how to apply it on this given situation

[worldly knot]

this is the graph that ive got that has the closest answer so far, 153.8

but the answer is 147.1

[austere cedar]

You are not looking for a path of minimal length going trough every city. You are looking for a minimal spanning tree in this graph, because that is when every city is connected with every other city with minimal total cost. So you can use any Algorithm for Minimal Spanning trees to compute the optimal solution (I hope you know at least one for it).

[outer rune]

Hey Discrete Mathers

im taking a course in Discrete Structures right now and I am having a hard time understanding this topic. Can someone recommend me a good resource for learning?

If it makes any difference, here is what the scope of my Discrete Structures class covers

[wide vine]

what is "this topic"

Are saying you are having a hard time with the entire course because that is a bit hard to just give you a direct resource on

[outer rune]

oh sorry well the course just started and we only did 3 topics so far:

Divisibility and Modular Arithmetic
Integer Represenations
Primes and Greatest Common Divisors

im mainly struggling with Divisibility and Modular Arithmetic

Integer representations is pretty straightforward but i feel like i will drown in the coursework unless i understand the divisibility and modular arithmetic stuff

[wide vine]

do you have a book for the course?

[outer rune]

I have a zybooks thing

[wide vine]

I think you might be able to find some playlist of videos that cover various topics in "discrete" math

[outer rune]

its like a website

[wide vine]

we used that

[outer rune]

LOL

fml

[outer rune]

do you have any recs

[wide vine]

my class only did like 6 or so chapters (then I just started trying to finish the rest)

[outer rune]

mines a bit diff

1 sec

this is mine

[wide vine]

well the units might be out of order

Oh yeah

[outer rune]

and theres subsections

[wide vine]

what is under number theory

[outer rune]

this is the unit my class is currently on

[wide vine]

Okay so it is the same as my stuff

[outer rune]

oh lit

[wide vine]

My prof just had everything

[outer rune]

so whats the move boss

my prof is trash

no disrespect to her but like yeah i cant really understand anything

[wide vine]

never finish it though as we didn't need to do that topic

my course was all online and never really had a prof

all self guided

[outer rune]

ohh

wow

howd you do on it

and do you feel like you really understood the topic>

?

[wide vine]

Yeah because she assigned us problem sets

[outer rune]

yeah theres problems in the zybooks

[wide vine]

Also does your prof unlock your answers?

like the end of section questions

[outer rune]

and ive done some of them but i feel like my conceptual understanding of discrete structures so far isnt that great

you mean this?

theres a bunch of this crap but i cant answer it

like on the website i cant answer it

[wide vine]

Other than graphs we actually didn't do any of those topics in my discrete class. I did end up doing graphs, trees, and growth of function

[outer rune]

oh

[wide vine]

Yes those

[outer rune]

darn it

so should i just answer them on a separate page or smth

[wide vine]

your prof should be able to unlock them unless they use them as a problem set for a grade

[outer rune]

ohh

so ill ask

[wide vine]

but here is an example of one

[outer rune]

LOL ITS THE SAME EXACT THING?

Dude

i have the same problems

[outer rune]

the literal same problems

[wide vine]

it will show "solution"

[outer rune]

ojhhh

i dont have that button

[wide vine]

My prof never bothered to unlock the solutions for the units we didn't cover so I don't have the solutions for self study 😦

but yeah ask your prof to unlock those

[outer rune]

darn

will do

[wide vine]

assuming they won't be using it for a grade.

[outer rune]

besides that, any other resources that might be helpful

[wide vine]

Well there is a full youtube playlist that are calle "discrete math" but not sure how well it will align with your course

discrete math is so vague and broad

[outer rune]

darn

guess ill die

[wide vine]

https://www.youtube.com/playlist?list=PLl-gb0E4MII28GykmtuBXNUNoej-vY5Rz

[outer rune]

this class is literally graded on a midterm, final, and zybooks

[wide vine]

maybe this

[outer rune]

thx ima look rn

also did you have to do proofs at all?

[wide vine]

but seems you are not getting into set and logic stuff so like half the playlist won't be of use

we did like 1 proof by induction

I want to finish the proofs unit as we never had to do it for our course

most we ever did was learn about "mathematical proof by induction" for like series

[outer rune]

i have no idea what that means

[wide vine]

something like proof (n)(n+1)/2

[outer rune]

oh

[wide vine]

for the sum of integers

[outer rune]

oh the series thingy

[wide vine]

yeah

[outer rune]

i remember using that in calc

[wide vine]

but like my class never had really any proofs

[outer rune]

ok great

im hoping mine is the same

also thanks for the yt link i found vids that are helpful

[wide vine]

best bet is just look up videos as you go

[outer rune]

oh also

[wide vine]

some of that graph and tree stuff is interesting and can be confusing

[outer rune]

is there any prereqs for taking this course

[wide vine]

nope

[outer rune]

LIT

[wide vine]

I don't think so

[outer rune]

i felt like i was missing some info tbh

but thats good

[wide vine]

some of their proofs on the site might be unclear until you have a video explain it

[outer rune]

a | b means a goes evenly into b right

[wide vine]

I believe so

I believe it reads "a divides b"

[outer rune]

and if a | b, then b is a multiple of a

yeah

[wide vine]

yeah

[outer rune]

im so interested in learning this but having an ehh professor makes it more difficult

the class is so boring

[wide vine]

zybooks is really unmotivating

[outer rune]

yeah the textbook is written so badly

like its a pain to read this

[wide vine]

it is also very unmotivating and can basically be gamed if you don't really care

you can keep trying or see the solution (not sure if the prof can see that)

My zybooks was just completion.

My schools other discrete class used this book

I took the online course and technically was a lower level but only course I could take but I guess they are suppose to be very close in content.

seems like it should have most of your stuff

@outer rune what exactly is under "growth of function"

I did that unit I believe and if it is what I think it is then this video was really helpful

https://www.youtube.com/watch?v=0oDAlMwTrLo

@outer rune Best bet is get the prof to unlock those problems and come back to #discrete-math for help and browse maybe some textbooks or youtube videos as you go.

I mainly got by with zybooks and their problems at the end of the section but I did make use of youtube videos and coming here for help

[outer rune]

thanks for all this info ima take a look at that textbook

do you have the download for it

[wide vine]

I could probably help whenever you get to units 3, 6, 7 (if those are required) as those are the ones I actually finished

[wide vine]

just looked up "kenneth rosen discrete mathematics and its applications pdf" and you should see a download but I didn't say this

But really you just need to push through and if you get stuck come back with the specific problem and someone should be able to help you out.

[outer rune]

lmao 🤐

[outer rune]

will do boss

thanks for the help

[worldly knot]

could someone tell my why this is transitive?

[wide vine]

these are directed graphs right?

[worldly knot]

yeah

[wide vine]

why do you think it isn't transitive

[little prism]

we have (1,0) and (0,3) but not (1,3)

[wide vine]

oh true

that is weird

[worldly knot]

seems like a mistake tbh

[wide vine]

(a, b) (b,c) then (a,c)

[worldly knot]

idk

yeah thats transitive

[wide vine]

and yeah (1,0) (0,3) then if it is transitive (1,3)

thats unfortunate

[worldly knot]

i guess i should contact my teacher then?

[wide vine]

sounds like it

[worldly knot]

this seems to be false, is it?

[wide vine]

I feel like this is just something you check for each value in this case

[clear topaz]

Who can help me with my math problems in junior high school

[wide vine]

given the set size and what not

Like I don't know if it is true in general (didn't check) but given the domain is only J5

as long as they both map at to the same number for the same input on the domain I would say they are the same I suppose along that domain

[clear topaz]

the intersection of the parabola y=-x^2+mx+c and the primary function y=kx+b is point a (-1,0), B (m+2, n), (point a is on the left side of point B) to find the values of C and n (expressed by the formula containing m)
(2) passing through point P (m, 0) as the vertical line of the X axis and intersecting the parabola at point Q, can ∠ AQB be a right angle? If yes, request the coordinates of point p; If not, please explain the reason
(3) let the other intersection of parabola y=-x^2+mx+c and X axis be point C, and if the tangent value of ∠ ABC is 2/3, calculate the value of M

help！

the qusetion three

[worldly knot]

ohh makes sense

[wide vine]

wrong channel :/. I recommend asking in one of the help channels

[clear topaz]

ok

[worldly knot]

same thing happened here @wide vine

how is it transitive o.o

[wide vine]

it is the same question

idk why they gave you the same question and how it would be transitive

[worldly knot]

oh shoot didnt notice, was reviewing

maybe someone could assist me with this? idk how the answer is 1000

[wide vine]

seems like 5*10*20

,w 51020

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

each 5 brands of liquid detergent

have 10 brands to pick of floor wax

and those then have 20 brands of soda crackers

although I never really did the whole combination and permutation stuff but that seems the logical behind the question

[worldly knot]

bro what.. the solving is actually that simple? wth

so the items on top are just filler pretty much?

[wide vine]

actually that is a good question 👀

maybe it might be like

(5 c 2) * (10 c 3) * (20 c 3)

,w (5 c 2) * (10 c 3) * (20 c 3)

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

.....

5 c 2 = 10

10 c 3 = 120

20 c 3 = 1140

,w 101201140

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

okay so maybe it isn't that

I guess maybe it is fluff or I just don't know how to work with combinations

[worldly knot]

i see

[wide vine]

not sure if it was just 5 * 10 * 20 or if there was some underlying combination stuff and I just ignored it. Never really touched on that topic in my discrete course :/

but now that you mention the a,b,c i feel like it must be important for the list he is writing

he needs 2 of liquid, 3 of floor wax, 3 of soda crackers

so the question would be how many list can he make that are unique from 5 liquid, 10 wax, 20 soda crackers.

I mean that is imagine what they are looking for but not sure how that is computed

[worldly knot]

maybe better to switch this onto #probability-statistics haha

[wide vine]

because my number is how many ways you can write

1 liquid, 1 wax, 1 soda

I believe

[worldly knot]

ohhh gotcha

[wide vine]

from the given totals

yeah maybe ask in #probability-statistics and see what they say

[worldly knot]

yeah just speedrunning some topics to review and then ill go in depth later on ^^

[wide vine]

i mean I believe they deal with combinations and permuations in stats

[worldly knot]

yeah i believe they do

[livid drum]

From each of the three categories, he picks exactly one brand and sticks with it. (suggested by the question wording and obviously the answer).

It is as simple as 5 into 10 into 20.

[wide vine]

Wait yeah

I guess it doesn't make sense for him to buy 2 different brand of the same product

okay that makes more sense

So even though he is getting 3 or whatever amount of that item

it doesnt matter seeing they will all be the same brand

[worldly knot]

OHH OKAY

that makes a lot of sense

i was really confused with the wording of the question

[hot valley]

Hi guys! Do you guys know why this is transitive? I tried to map it but (4,4) doesn't have a partner.

[wide vine]

wdym "(4,4)" doesn't have a partner

some relation/graph in a directed graph if you have something like

(a,b) , (b,c) then (a,c) should also be in the graph

so if a -> b -> c then a -> c

I would recommend drawing this out in the form of a graph by first making vertex/nodes of the input set

which looks like

{1,2,3,4}

and then draw all their directed connections

also (4,4) is by itself transitive I believe you can call transitive if you are only looking at itself seeing it points back to itself. 4 -> 4 -> 4 .....

but you use the term to describe the whole graph but (4,4) doesn't need a "partner" as it just points back to itself

[hot valley]

Can you explain more how (4,4) itself is a transitive? :))

[wide vine]

well if you only are considering a graph with only (4,4)

4 points to 4

and that same 4 points to 4

and you already have (4,4) in your graph

but transitive in summary is just like

a -> b -> c then you require a “shortcut” from a->c to be called transitive.

my book had this defintion

R is transitive if and only if for every three elements, x, y, z ∈ A, if xRy and yRz, then it must also be the case that xRz.

[hot valley]

So for example, R= {(1,1), (2,2), (3,3), (4,4)} this set is a transitive since it points to the same number itself?

[worldly knot]

those are reflexive

[hot valley]

But can it can also be transitive?

[wide vine]

yeah but they also follow the property of being transitive

[worldly knot]

this should be the easiest definition for a transitive ^^

a,c tho**

[wide vine]

yeah

[worldly knot]

hey brandon u got an idea with merge sorts?

[wide vine]

what about them

[worldly knot]

finding the highest number of comparison

for an array with n number of elements

[wide vine]

The merge sort algorithm's runtime is O(N log N). Merge sort divides the input in half until a list of 1 element is reached, which requires log N partitioning levels. At each level, the algorithm does about N comparisons selecting and copying elements from the left and right partitions, yielding N * log N comparisons.

This is what I have done in some notes but tbh I can't remember it much

oh I guess that really didn't even answer "highest number of comparison

I would assume whatever worst case of merge sort would be highest number of comparsions

can't speak much as I only learned this from a first CS course and not from some data structures and algorithms course

so very surface level on the analysis end. Most of the course was just learning c++ at a basic level compared to doing anything interesting with it

[worldly knot]

yeah pretty much this was what i was thinking, but it seems like the value is still wrong tho

[worldly knot]

u still know a lot more than a lot of us regardless

this is the question and pretty much got it wrong

[wide vine]

I wonder if it also depends on how "merge sort" is defined

I remember one of my problems was something similar to this but with binary seach and how many comparisons.

[wide vine]

What i find interesting is the answer is double

,w 96 log_2(96)

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

,w 2(96*log_2(96))

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[worldly knot]

oh huh youre right

why is it double tho

hmm

[wide vine]

Not sure which makes me just wonder their implementation of the merge sort and what they call a "comparison".

But online seems to suggest it should be ~633 based on whatever the most standard implementation and description of a comparison.

[worldly knot]

gotcha, they mustve had something of their own xd

didnt see doubling in any of my notes

but now I got this

so what its asking for is how many permutations could i get of the 53 people for the 24 member positions?

[wide vine]

omg... this screams HS stats all over again reee

[worldly knot]

hahaha

[wide vine]

,w (18 choose 8) * (22 choose 8) * (13 choose 8)

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

nvm

wait

that is it

combinatorics

[wide vine]

yeah so take the combinations of each and multiply them

and seeing it is a list

we don't really care about order

just that we get 8 from each district

[worldly knot]

WOW THANK YOU.. i actually forgot about the binomial coefficient

am i doing something wrong here?

the given wants me to find how many students checked atleast one of the three, which should be the total population of those who answered which is 44?

[wide vine]

Venn diagrams 🗿

[worldly knot]

yeah it's pretty much a mix at this point xd

but this should be one of the easier lessons but idk why it's 55

(100-44)-1?

[wide vine]

how did you get 4

44

what numbers did you add

[worldly knot]

18 + 17 + 9

[wide vine]

key word is "at least"

so look at your union

of the circles

ie

the cross over

unless you are saying

9 is the total size of that circle

or just the outside?

and I can't read the middle number

[worldly knot]

just the outside.. hold on

it's 2

[wide vine]

okay

,w 18+17+2+2+1+9

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

well

oh

you don't have

You are missing the middle between circle 1 and 2

but it should be the whole thing

[worldly knot]

OH wait lol i actually transfered this graph cuz it was in the way of the question

[wide vine]

sorry

it should be the total population of these

minus like all the duplicates between the cross over

,w 28+26+14-2-2-1-8

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

I think I had this exact type of question but it was never actually given to us

But you just need to not double count people that are here

so

we know it is

similar type of problem

but you need to make use of your total population

and then you can do some Set union and intersection stuff to compute the other stuff

But following this problem is pretty much the same idea but different numbers

[worldly knot]

oh gotcha i double counted on my other attempt and didnt subtract

damn thank you so much dude

[worldly knot]

whyd we get 8 instead of 6?

[wide vine]

I just thought you said it was a 8

okay anways

it should be

,w 28+26+14-6-2-1-2(2)

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

there

@worldly knot

so you take the sum of the 3 circles (knowing we are overcounting because they intersect)

,w 28+26+24

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

then you delete the duplicates

the 2 between circle 1 and 2 was counted twice so we must subtract a 2

the same logic follows for 6 and 1

the middle 2

was counted 3 times

and we only need 1

so we need to remove 4

,w (28+26+14)-6-2-1-2(2)

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[worldly knot]

gotcha!

could we also do

,w (18+17+9) + (6+2+2+1)

[vital dew]

Results provided by WolframAlpha

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

Requested by HamtraoL#3664

[wide vine]

yeah sure

Seeing you knew those numbers refer to the outside

[worldly knot]

yup pretty much! thanks a lot

[quaint notch]

Hey guys, hope everyone is ok 🙂
Got another question from me haha

1. Let X partially ordered set. Prove that if each subset of X (non-empty) has a first and last element then X is linearly ordered finite set.
2. Is this true if there's only first element (no last)

so what I've been thinking is, since X is non-reflexive, and assume we have 2 elements we can't compare between, we could look at the subset of X that contains those 2 only. since we know we have a first and last element. x < y or y < x for sure. so that's our contradiction and since we have a first element, and our group is well ordered we are done.

for section 2 im not too sure. it won't be finite anyway, but not sure if it's linearly ordered too

[buoyant zephyr]

Can an alphabet set contain another set within it? (Talking about strings, automata, and languages.)

[final cliff]

Yes

Well at least I'm pretty sure in most places that's how it will be. Sipser defines an alphabet to be any nonempty finite set. So, that includes stuff like sets containing other sets and junk.

[buoyant zephyr]

Thanks c:

[west vessel]

If there was mathematicians would be out of jobs

[hot valley]

Hi guys. Do you know why this is not one-to-one function? -2 and -2 fits in the set of integers...

[wide vine]

Because for example f(2)=f(-2)

Which makes it not one to one

One to one maans

[obtuse lance]

specifically it's two to one, cause the two values 2 and -2 map to the one value 4

[wide vine]

a != b

Then

f(a) != f(b)

Is what function that are one to one hold

Where a and b are in the set of the domain

Any even function is automatically not one to one following that definition

[hot valley]

how abt if the given is like this? how come that this is one to one?

[wide vine]

Because no two inputs map to the same output

[obtuse lance]

try working it out, start from f(a)=f(b) and see if this implies a=b

[wide vine]

Adding to this assuming some x,y which are said to be different. such that x != y

Add +1 to both sides

x +1 != y+1

Which is just

f(x) != f(y)

[wide vine]

Which follows this definition of one to one

[hot valley]

I get it now! thank uu!

[wide vine]

Not sure if they told you but some people and text use injective and surjective instead of one to one and onto (respectively)

And bijective meaning has an inverse

[junior dawn]

I fail to see how the existence of Kleene's T Predicate does not contradict the halting problem.

"In computability theory, the T predicate is a particular set of triples of natural numbers that is used to represent computable functions within formal theories of arithmetic. Informally, the T predicate tells whether a particular computer program will halt when run with a particular input, and the corresponding U function is used to obtain the results of the computation if the program does halt."

This predicate seems to be able to determine whether a program halts on a given input, but the halting problem says that this is impossible? What am I missing here?

[quaint notch]

Hey all,
I need to prove or disprove wether (RxR, <) isomorphic to (QxR, <) where < is there the right dictionary order, meaning that
(a,b) < (c,d) <=> (d > b) or (d =b and c > d)
I'm thinking about showing that both are well ordered sets but then I'm not sure if those sets are same size. I think RxR is א and also QxR so I could prove it's correct. am I right?

[formal flicker]

Which relation is correct the above or the below?

[quaint notch]

Lower I believe.
Let A = 1, B = 2, C = 3, D = 4

Top is {(1,3),(2,4)}
Bottom is {(1,3),(1,4),(2,3),(2,4)}

[worldly knot]

maybe someone has an idea?

so to my understanding, I was given a probability, and with that probability, i gotta find the probability of ten throws?

[tidal tulip]

how do you prove if n^2 is a multiple of 4 then n is even? the book basically says since n^2 is even then n is even, but you can have odd * even = even so i don’t see why n^2 has to be even since it’s not apart of the assumption?

i think i got it

hold on

is this proof correct?

proof:

assume n^2 is a multiple of 4

then

n^2 = 4k = 2(2k) for some k in Z.

so n^2 is even

then n is even because if n were odd then n^2 is odd.

QED

[silver panther]

Yeah nice

[tidal tulip]

okay awesome. thanks! @silver panther

[outer rune]

With this information how do i determine n

i got n = -54 but im not sure if its right

ok so update i realized the answer is -51 but im still not sure how to do the problem

i would appreciate any assistance

[wide vine]

okay I have an idea for this one

so first

you have

(85/122)

that is the odds of getting snack eyes

that means 1- P

is

(37/122)

so do

,w ((85/122)^10)(37/122)(37/122)

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

okay

now we need to know how many ways you can make such a combination

well rather permuation

which that you have

(snake)(snake)(snake)(snake)(snake)(snake)(snake)(snake)(snake)(snake)(not snake)(not snake)

you need to figure out the total amount of ways you can permute those probablities

and multiple the percentages by that number

,w (12 choose 2)

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

,w (12 choose 2)*((85/122)^10)(37/122)^2

@worldly knot if you need it as a percentage just convert it

but that should be it

[vital dew]

Results provided by WolframAlpha

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

Requested by Brandon7716#6524

[wide vine]

https://math.stackexchange.com/questions/3868197/is-there-an-equation-for-permutations-with-different-numbers-of-element-availabl This article explains the math behind (12 c 2) being equivalent.

[fervent chasm]

There are 51 students taking a course, and the available grades are Z, P, C, D, HD. Show that
at least 11 students will get the same grade.

how to do this

ans

[hard citrus]

Pigeonhole principle

[hot valley]

is this reflexive only?

[cerulean wind]

what have u tried?

[cerulean wind]

no

[mild temple]

plz search "binomial theorem" for the statement. you'd observe that the general term of the sum in the statement matches that in your question with a suitable and simple algebraic substitution.

[fervent chasm]

tnks

[zenith oyster]

@coral parcel Thanks to your help I have learned more and passed my course in Algorithms, you are a god of math.

[haughty pond]

Hey friends, I have a question of graph theory.

I'm no mathematician tho

Imagine an infinite graph, who's every vertex has 4 connections

Let's define $g(n)$ the number of unique vertex reachable in $n$ steps divided by $n^2$

[vital dew]

K_

[haughty pond]

Has anyone an idea how to determine $g(n)$ for $n \gg 1$ ?

[vital dew]

K_

[stray reef]

an infinite graph in which each vertex has degree 4?

is that all that is known?

@haughty pond

[haughty pond]

yep

it's to map a physical problem onto that

[stray reef]

then i am pretty sure the problem is impossible as stated

you cannot even get a big O estimate on g(n)

[haughty pond]

AH

[stray reef]

because the number of nodes in distance at most n could be quadratic in n but it could also be exponential in n

[haughty pond]

Because I can't assume any "degeneracy" of path because I don't know it

sorry i forgot something

[stray reef]

like here

this graph would produce an exponential g(n)

[haughty pond]

I want to know the number of reachable vertex in n steps minimum

the minimum is important

[stray reef]

so you want the number of vertices in distance exactly n?

[haughty pond]

tl;dr yes

[stray reef]

still can be exponential or linear

depending on what your graph is like

[haughty pond]

:(

[stray reef]

you said you had a physical problem

[haughty pond]

Yesp

[stray reef]

perhaps it would be best if you posted that here

[haughty pond]

Yep

[stray reef]

http://xyproblem.info/ after all

[haughty pond]

I have data from a physical foam. From tomography picture, I extract data, what data, "nodes" and "struts" i.e. some points in space, and the rods in-between those points.

I'm trying to calculate $g(n)$, which is a "topological equivalent" of the pair-correlation function. So, $g(n) =$ number of unique reachable vertex in n steps $/n^2$.

My graph is obviously finite in my data-set, but, i'm trying to extrapolate to know the behavior of big foams.

[vital dew]

K_

[stray reef]

and you have reason to believe that this graph is 4-regular?

[haughty pond]

Oh yes, i'm able to extract the vertex order, thus its connection, and it's 85% 4-order

And from physical theory, the polyhedral shapes of cells makes it 4-order.

[stray reef]

and do these vertices actually correspond to locations in space?

[haughty pond]

yep

[stray reef]

in this case one would expect g(n) to be asymptotically constant, but i personally can't think of any algorithm to calculate it that would not be just plain breadth-first search

[haughty pond]

And I already made the algorithm for it aha

So, for my shy dataset of 4000~6000 vertices

it's long, but it does work.

But i'm just doing up to $n=6$ right now

[vital dew]

K_

[haughty pond]

And i'd like to know for what kind of behavior i'm looking at for $n\gg 1$ because if it's going to a constant or to 0 it's not the same for my interpretations

[vital dew]

K_

[haughty pond]

I hope it's understable

[fervent chasm]

help 😦

[stray reef]

it should go to a nonzero constant.

[haughty pond]

Can you explain me why ?

[stray reef]

well i am assuming your nodes are distributed approximately uniformly in space, since it's a foam you're looking at

i am also assuming edges connect mostly vertices that are close by

[haughty pond]

ye

yep

[stray reef]

which means the vertices in distance n should roughly form a sphere of radius n*(edge length)

[haughty pond]

Exactly

that's why i have the $1/n^2$ "normalization"

[vital dew]

K_

[stray reef]

yeah so a quadratic divided by n^2 is constant

[haughty pond]

Can I prove that it's going to a constant, and maybe, determine the constant ?

[stray reef]

maybe? i don't know.

[haughty pond]

Thanks a lot still 💌

[formal flicker]

Can someone explain how the first circle part end up turning into the second circled part?

[mint bane]

trying to prove the well ordering principle - my idea right now is to first state that in a single element set, the minimum is obviously the only element; then for a two element set you can see it as the union of two single element sets, so in the union there must be a minimum (since the only possibilites are x < y, x > y, or x = y)

then since every set can be seen as the union of sets containing its elements you can build your way up like this for a set of any size

i dont wanna look at the actual proof yet but am i on the right track?

[slender iris]

what's 2 mod 7? is it 2?

[mint bane]

why do you think it's 2

[urban mantle]

Hello. I need to somehow apply Kruskal algorithm on just a set of points. I am have an algorithm that can be applied to a set of ordered edges, but how to do it here?

My point was to just brute force every possible closest pair of nodes and treat them as edges list, but it is just takes too much time

O(n^2/2 - n) if to be clear

and takes too much space

[stray reef]

maybe a delaunay triangulation would help?

[urban mantle]

Oooo

I found a whole new level of complexity

this will help a lot

Thanks @stray reef

[mint bane]

bump

[wide vine]

what is the definition of the "well ordering principle"?

if it is "every non-empty set of positive integers contains a least element" here was my take. Not sure if what I am about to say is the same logic you are thinking. Say you have some finite set of any size. You divide up the set into sets with 1 element each. You work left to right and will just union 2 sets with 1 element at a time. With sets with only 1 element you can easily determine the minimum. Now you assign that minimum to that unioned set and union again with the next single element set and determine the new mimumum. Keep doing this process until you have your original set and then you have your least element.

Example A = {3,5,7} => {3} {5} {7}. Compare set {3} {5} and see that 3<5 and then union {3} U {5} so that you have {3,5} and {7} with knowing that 3 is the least element of {3,5} you union with {7} and we know that 7 must be the least element so then you compare 3 <7 and union {3,5,7} and now you have that 3 most be the least element.

or does it extend to infinite set?

Not sure how my logic would work with infinte sets or if it still does

[cerulean wind]

prove it in what setting? just that every set can be well ordered by some order relation?

[wide vine]

im still not sure what the well ordering principle is after looking it up

this is what wiki had and idk if it aligns with others "In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. "

[final cliff]

Any non-empty set of positive integers contains a least element like you said.

[wide vine]

I wonder how my logic holds for infinite sets then.

like if I am given an infinite set I don't think my strategy is viable or if anything i stated was a proof. What things do you even take for granted with trying to prove it?

[cerulean wind]

this idea will only ever result in finite sets. you will never be able to achieve an infinite size set in this manner. similar to how induction only shows something for finite values

[wide vine]

don't you have to start off by what it even means to be "at least"

in the context of numbers

wll

well* intergers

[cerulean wind]

even if you did, it just wont extend to an infinite set.

take N for example and apply the same reasoning

[wide vine]

don't you define the next integer in the context of a previous integer

in some set way or something

[final cliff]

Let A be a nonempty set of positive integers. Suppose A has no least element. What happens if 0 is in A? What happens if all integers less than k are not in A, can k be in A?

Well ordering of the positive integers is equivalent to induction.

You can show A is empty to get a contradiction using induction.

That gives you a contradiction that shows no such A can exist.

Idk if you can do it without some form of induction.

[raven grove]

can someone help me construct a formula to find the nth term in this sequence?

[final cliff]

Like, induction follows from axiom of infinity if we're sticking with zfc. So, how the proof works out probably depends on what axioms/theorems you have at your disposal.

[cerulean wind]

anyways, the well ordering principle on the naturals follows from induction as doot dooter mentioned. it also follows from the fact that every finite set of integers has a minimal element, again, via induction

[cerulean wind]

do you know about characteristic polynomials?

[raven grove]

no

[cerulean wind]

generating functions?

[raven grove]

nope

[wide vine]

hopefully it is possibly. I don't what conditions make it true you can take a recursive definition and make it closed form.

[cerulean wind]

it is

@raven grove, do you know any linear algebra?

[raven grove]

no I don't I am taking discrete math before linear algebra

[cerulean wind]

welp, ive exhausted all the methods ik of solving this other than guessing and induction. i dont know or feel like trying to motivate generating functions or characteristic polynomial methods for solving this, but i suggest you start there

[wide vine]

maybe they just want you to play with the sequence and see what you can make of it?

[cerulean wind]

this is really similar to the fibonacci sequence

[raven grove]

it asks to find the first 7 terms of the sequence which i did, then it asks for a formula, then it asks me to prove the formula using inductio

induction

and yes it is its the fibinacci sequence but it has subtraction in it

[wide vine]

i never even knew that had a closed form

[cerulean wind]

called binets formula

i honestly wouldnt be suprised if it was the fibonacci sequence but descending instead of ascending

[cerulean wind]

do you mind sharing the first seven terms? im feeling lazy

[raven grove]

1,1,0,-1,-1,0,1

seems to be a pattern

[final cliff]

After 0 it becomes negative of fibonacci I think?

Oh wait maybe I'm being dumb lol

[raven grove]

it continues pattern

just do not know how to make a formula to find the nth term

[cerulean wind]

1,1,0,-1,-1,0,1,1,0,-1,-1

[final cliff]

It's periodic I think, so you can do some goofy piecewise mod answer lol

[raven grove]

like for every 3rd term its 0 mod 3

it will be zero if n is 0 mod 3?

[final cliff]

No like a_n=1 if n=0 or 1 mod 6 and so on.

Idk what exactly counts as a closed form solution here?

[wide vine]

well whatever it is you said you need to prove it by induction so maybe that is a hint?

well nvm...

[raven grove]

i do need to prove by induction maybe proof by cases?

[final cliff]

Could it be something weird like $\frac{(-1)^{floor(\frac{k+1}{3})}}+(‐1)^{floor(\frac{k+2}{3})}{2})}$?

But like offset?

[wide vine]

https://oeis.org/search?q=1%2C1%2C0%2C-1%2C-1%2C0%2C1%2C1%2C0%2C-1%2C-1&language=english&go=Search

[raven grove]

i think it is something simpler

[final cliff]

God damn latex

[raven grove]

does this question seem hard or easy?

[final cliff]

Graphing this looks like your sequence but offset along the x axis

[raven grove]

i have no clue what floor means so how could my professor expect me to know this?

[final cliff]

Idk but floor is pretty standard in discrete math

[raven grove]

never learned it

[final cliff]

You did precalc?

[raven grove]

yeah

[final cliff]

I feel like I saw floor in precalc or maybe before.

Mmm, asking your prof what all is allowed might help?

Mods, piecewise, floors etc all seem like they would work to express this sequence.

[mighty flame]

am I allowed to do like a foil type operation when working with boolean logic? like would this be valid?

(p ∧ ~q) ∨ (~p ∧ q) <=> (p ∨ q) ∧ (~p ∧ ~q)

[final cliff]

So ya know: https://en.m.wikipedia.org/wiki/Floor_and_ceiling_functions

[raven grove]

even tho this is not the formula i expected it to look like this

ive been proving these kind of formulas using induction so i thought maybe the sequence might have a formula that looks like this

[final cliff]

Foil is just from the distributive property and some other stuff. You can check the equivalence you had in your post via truth table.

[final cliff]

Oh yeah so you want a sum like that?

[raven grove]

if it can be expressed like a sum

[final cliff]

Yeah so when you add terms for this G sequence I'm pretty sure it probably telescopes.

So, you should see a bunch of junk cancelling out when you try and write a sum like that.

[raven grove]

so it cant be written like a sum?

[final cliff]

No I'm saying I think it can.

[mighty flame]

ik it prob varies from class to class but theoretically if it isnt an explicit law but I can prove it is logically equivalent via a truth table that SHOULD mostly be fine right?

[final cliff]

It also depends heavily on what you're doing in class so I don't really wanna tell you something wrong.

But in boolean algebra you have the distributive property so some foil like law will follow.

[mighty flame]

that makes sense

[final cliff]

Try it this way, write out your equations for G_1, G_2, G_3, G_4, ... G_n, G_(n+1) all vertically with some ...'s and stuff. What happens when you add them all? You get a big sum = some other sum, but in the rhs sum almost everything cancels except a few terms (this is what I mean by telescoping).

I could be screwing something up. I was just fooling around with that idea is all.

[wide vine]

you know the normal distributive law right?

[final cliff]

Idk if I'd call adding up all the terms a closed form solution though.

[raven grove]

tbh i have no clue what to do lol

[wide vine]

just call (p and !q) something else and follow the law above and then back sub it

[cerulean wind]

closed form is $$G_n = \frac{i}{2^n\sqrt{3}}\left(\left[1+\sqrt{3}i\right]^n-\left[1-\sqrt{3}i\right]^n\right)$$

[wide vine]

This site list one about the mods among a few others

https://oeis.org/search?q=1%2C1%2C0%2C-1%2C-1%2C0%2C1%2C1%2C0%2C-1%2C-1&language=english&go=Search

i think i put in the correct sequence

[vital dew]

c squared

[final cliff]

Lmao

[cerulean wind]

sry, that looks better imo

[wide vine]

so now to use induction

🙂

[final cliff]

If that's the answer that's really rough lol

[cerulean wind]

ye

[raven grove]

it cant be

[cerulean wind]

it is

generating functions for the win

[raven grove]

theres no way

[cerulean wind]

way

[raven grove]

im not that smart lmao

[final cliff]

I like this one but offset by one lol

[wide vine]

where did you type that?

[final cliff]

Desmos

[wide vine]

copy and paste it

and add $$

[cerulean wind]

dont think that works

[final cliff]

I literally just screenshotted desmos because latex was a pain

[wide vine]

desmos gives latex

[final cliff]

The graph is off by one

Along the x axis

[cerulean wind]

i meant the copy paste thing

[final cliff]

Oh okay lol

[raven grove]

whats the formula for this then

[wide vine]

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

[vital dew]

Brandon7716

[cerulean wind]

another closed form: $$G_n=\frac{-2}{\sqrt{3}}\sin\left(\frac{\pi}{3}n\right)$$

[vital dew]

c squared

[cerulean wind]

what are we counting?

[raven grove]

number of blue triangles

so it goes from 1 to 3 to 9

[cerulean wind]

um

[raven grove]

formula should be S(n) = 3^n-1 right

[cerulean wind]

small blue triangles? or ALL blue triangles?

[raven grove]

small ones

[cerulean wind]

then yes

[raven grove]

so why is this one so easy and the other sequence is so hard

[cerulean wind]

has a regular structure to it

or, more regular

the previous one had some period six structure

but sometimes fractals and recursive type structures are easier to deal with

[raven grove]

it looks exactly like the fibonacci sequence tho

[cerulean wind]

fibonacci sequence is equally as hard to find a closed form for, just like G_n

you can generalize the formula for any sequence of the form x_{n+2} = ax_{n+1} + bx_n given initial conditions

[raven grove]

is this a closed form of the fibbonacci sequence then?

[cerulean wind]

no

look up binets formula

similar in flavor to the one i produced

[raven grove]

is this related to the fibbonacci seqeunce

[cerulean wind]

yes

[raven grove]

the sum that i just posted?

[cerulean wind]

it is the closed form for the fib seq

wait

what are you talking about

[cerulean wind]

this is not a closed form for the fib sequence

,w binets formula

[raven grove]

the question says recall the fibonnaci sequence as seen above then it asks to prove that sum

so it must be related somehow

[cerulean wind]

you prove this via induction

not with the closed form. that would be kinda brutal

[raven grove]

yes which I did, prove base case is true, then assume its true when n=k then examine what happens n=k+1

that is induction right?

[cerulean wind]

yea

[raven grove]

i just find it weird how the g(n) sequence is so complicated compared to the other sequences i just posted

[cerulean wind]

,w Binet's Fibonacci Number Formula

[vital dew]

Results provided by WolframAlpha

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

Requested by coycoy#4831

[cerulean wind]

this is what i was refering to

[raven grove]

ohh the golden ratio

i never learned this but i was taught just a little about the golden ratio

[agile bobcat]

i got this really wild form|la for fibonaccis but i forgot it

[junior dawn]

Think this belongs here actually... How can you construct semi-computable sets?

[upper oar]

Hi all - I'm a first year in uni, taking discrete math for the first time. I came across this question and got stumped - I got as far as finding a function that shows a one-to-one correspondence between S and Z+ (which is f(x) = -x-2) but as far as the question is concerned this doesn't constitute for a full proof

Any pointers where to go from here?

[pale epoch]

why is this not a full proof?

[upper oar]

I'm really not sure - it only awards 2 points for finding the function

I can post the model solution here, but I can't really understand it myself

I guess the part after finding the function is just proving that it's one-to-one, but I don't fully grasp the part after that

[narrow mesa]

from what i can see it only proves that the function is one-to-one

[pale epoch]

you also have to show that it is onto, so that every element in the positive integers has a preimage

(sorry, i had to look up the word one-to-one)

alternatively you could show that the function has an inverse (if you know that a function has an inverse if, and only if, it is one-to-one and onto)

funnily in this case, f is its own inverse

[light heath]

for number 7 im not sure what proof method to use or if I want to do a direct proof then is there any axioms or known theorems I could use for this problem?

[narrow mesa]

well

u can suppose without loss of generality that x<y

[narrow mesa]

with this in mind min(x,y) = x

and (x+y-|x-y|)/2 = (x + y - y + x) / 2 = (2*x)/2 = x

so they are equal

[light heath]

this is my solution

[narrow mesa]

my solution is the same, i just assumed without loss of generality that x<y so that i wouldn't have to solve both cases

[narrow mesa]

i'm not really sure it's correct to say here without loss of generality. WLOG is usually used whenever you want make an arbitrary assumption that does not the generality of your result. in your case, "analogous" would be better i think.

[light heath]

alright thanks

[upper oar]

Mhm... Thank you

[pastel hollow]

"More generally, every graph G may be expressed uniquely (up to order) as a disjoint union of connected graphs."

What does "up to order" mean?

[narrow mesa]

it means that when u determine the uniqueness of the disjoint union of connected graphs u shouldn't take into consideration the order in which u put the graphs in the union

[pastel hollow]

so "order" doesnt refer to the number of vertices in the graph here?

[narrow mesa]

no

[pastel hollow]

ok thanks

[pastel hollow]

I'm trying to prove this by induction on the number n of vertices in the graph. Suppose it's true for k < n. Then consider a graph G with n vertices. If it's connected, then it's the disjoint union of the single graph G. Otherwise, its vertex set can be partitioned into two nonempty disjoint subsets X, Y with < n elements. Let E_X = {e \in E | ends(e) \subseteq X} and E_Y = {e\in E | ends(e) \subseteq Y}. Then the graphs G_X = (X, E_X) and G_Y = (Y, E_Y) can be expressed uniquely as the disjoint union of connected graphs. By taking the union of all of these graphs, we can express G as a disjoint union of connected graphs. But how do I show that this representation is unique?

[silent hawk]

hellooo

[wide vine]

👋

[shrewd beacon]

Help

[stray reef]

m*sk 🤮

...have you made any progress so far or did you just want someone to give you the answer

[jaunty plume]

What does the n and k notation mean

[stray reef]

binomial coefficient, most likely

a.k.a. n choose k

[civic horizon]

Pretty sure its zero

By jensen you get that the sum is upperbounded by sqrt(n)*2^(n/2)

I doubt equality or anything close to it holds though, as the binomial coefficients arent very close to each other

[stray reef]

would that not just give you that a_n ≤ 1

[civic horizon]

Yes

But the bound is quite bad as the equality case in jensen is when all the numbers are the same

So i would expect the sum to be bounded by 2^(n/2)*(n)^(1/2-epsilon)

[keen geode]

isn't it just... 0?

I mean, 1/(2^n/2*(n)^1/2) just con verges to 0 as n goes to infinity

so you're multiplying a sum by 0

[shrewd beacon]

So you're saying The sum doesn't diverge? It's a constant finite value. ?

[shrewd beacon]

Well we solved it in a help channel.

Using this

[keen geode]

no, I'm saying that because this equals to zero as n goes to infinity, then we don't need to consider how the sum evolves as in any case we'll be multiplying whatever the sum is equal to as n goes to infinity by 0.

[shrewd beacon]

I think you're talking about the CS inequality not Jensen's

[keen geode]

I'm probably wrong though

[shrewd beacon]

That's not correct. 0*infinity is an indeterminate case.

So we can't just write (tends to)0*inf=0

[keen geode]

Yeah you're right

[shrewd beacon]

Yup. But the answer is zero lol

[keen geode]

😂

Well, if it was a multiple choice question I would've got it right I guess

Shame we don't have those here at all

[shrewd beacon]

The answer is correct but the logic, not so much.

Pretty disappointing answer tho

[keen geode]

yeah, I suppose

[civic horizon]

You can use jensen as well

sqrt(x) is concave

[formal flicker]

Is my proof accurate?

[stray reef]

no, it is circular.

[split ginkgo]

I am reading this blog https://towardsdatascience.com/a-new-computational-fabric-for-graph-neural-networks-280ea7e3ed1a
and they keep on talking about cell complexes. Is it the same thing as https://en.wikipedia.org/wiki/Simplicial_complex ?

please tell me if this is the wrong channel to ask

and ping reply would be nice

[slow patrol]

dont know if this is the right place to post sorry

I need to know all the possible 5 digit combinations using the numbers 1-25 (each number is a different thing )
The numbers can be repeated as long as they are not of the same set.
Example for not repeating: 123 is ok but not 321 or 231,132,213, ect. ( as in the order does not matter as long as it still equals the same amount/ thing in a group )
basically trying to find the total amount of recipes possible with a set of 25 items and only a maximum of 5 that can be combined including repeating, meaning four of 1(a) and one of 2(b) = a single combination. while five of 1(a) = a single combination aswell

with just two numbers im able to get 6 different combinations with the maximum combination being 5. meaning, 1a 4b = ( 1 recipe ) 2a 3b = ( 2 recipe ) 3a 2b ( 3 recipe ) 4a 1b ( 4 recipe ) 5a ( 5 recipe ) 5b ( 6 recipe )

[silver panther]

Professor confirmed?

[silver panther]

Calculus of Limits theorem... you can only calculate the limits via a product or sum of two limits if both limits converge

[unique elm]

Hey y'all ...

Does anyone have any resources for discrete math (mostly asking abt notes)

Smthng similar to paul's notes for calculus

[wide vine]

Discrete math is a bit vast so any topics you are looking for?

[unique elm]

Intro to proofs and set theory mainly

[wide vine]

Ik they have an ocw discrete math course with notes

[unique elm]

Idr the rest of the content my course covers lol

[unique elm]

Paul?

[wide vine]

Nah mit has a book full of notes for their discrete math course

But you are looking for proofs and set stuff

https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/pages/readings/

I don't see any sets in there though specifically

[unique elm]

Yeah i think that'll do

Tysmmm

Appreciate the help

[wide vine]

Or consult some book on topic. Rosen

Discrete math book talks about sets

And a bit about proofs

[shrewd beacon]

Yep

[silver panther]

Sweet

[weary tiger]

hello i'm just curious,, what would be the symmetric difference between two empty sets?

given A = ∅, B = ∅

what is A ⊕ B?

[stray reef]

work through the definition of symmetric difference

$A \oplus B = (A \setminus B) \cup (B \setminus A)$

[vital dew]

Ann

[stray reef]

so $\varnothing \oplus \varnothing = (\varnothing \setminus \varnothing) \cup (\varnothing \setminus \varnothing)$

[vital dew]

Ann

[weary tiger]

isee,,

thanx

[keen geode]

Is this correct?

I'm just starting to get into set theory

[hard oriole]

Yes.

[keen geode]

Alright cheers

[vale cairn]

I'd say it's not clear what you're taking the complement in

like I don't think this is right or wrong without context to be pedantic

In any case yes that's what A \ B is

[keen geode]

what about this?

Does this work in a general case, whatever the universal set is?

[vale cairn]

It is not obvious what is meant

[keen geode]

How can I make it clearer?

[vale cairn]

Depends what you want to say

But personally I think it's always better to just say like A\Z or something for the complement in A unless it's very clear from context (and your messages are devoid of any such context)

[keen geode]

Ok fair enough, gotcha

Like this?

[vale cairn]

Well write {x in C | x not in Z} ig

[keen geode]

alright cheers

[light heath]

Hey can someone check my solution to number 22

[vale cairn]

I don't see how your 'existence' is a proof

Have you basically just asserted the statement is true

[tidal tulip]

can someone check my proof

Prove A u (B1 n .. n Bn) subset (A u B1) n .. n (A u Bn)

Proof:

Prove A u (B1 n .. n Bn) subset (A u B1) n .. n (A u Bn)

Let x in (A u (B1 n .. Bn))

then x in A or x in (B1 n … n Bn)

then (x in A) or (x in (B1 n B2 n .. n Bn))

then (x in A) or ((x in B1) and (x in B2) and .. and (x in Bn ))

then by distributive law

(x in A or x in B1) and (x in A or x in B2) and .. and (x in A or x in Bn)

then x in (A u B1) n (x in A U B2) n … n (x in A u Bn)

then x in (A u B1) n … n (A u Bn)

done

then the reverse direction is this proof reverse

[vale cairn]

I guess it works but I'd probably be inclined to make it slightly more concise

Well you seem to be using distributive law and stuff in English and I'd probably just be more informal with the logical deduction (or use actual zeroth order logic / smth formal rather than English)

[tidal tulip]

how would you rewrite it to be more concise i don’t see any examples to riff off of

[vale cairn]

Ig one might write smth like "Let x be an element of A u (b1 cap... Bn). Then x is in A or x is in all the bi.
If x is in A, then for each i, x is in A cup Bi and hence x is in their intersection.
Meanwhile, if x is in each Bi, then x is in each A cup Bi,hence in their intersection as desired.
This covers all cases. "

Though of course it depends on style i guess

[tidal tulip]

so it’s the same proof as mine just more succinct

[vale cairn]

Yeah, I mean I suppose there's only really one way to prove this aha

Well, i guess one could try the contrapositive

[tidal tulip]

i was worried about these two lines
(x in A or x in B1) and (x in A or x in B2) and .. and (x in A or x in Bn)

then x in (A u B1) n (x in A U B2) n … n (x in A u Bn)

we’re those fine

and then the last line i kind of “factored out the x” and said x in <all that stuff>

[vale cairn]

Yh that seems fine

[tidal tulip]

k cool

i like yours bc it’s less writing

[vale cairn]

I think in my experience people are less formal with this sort of thing than one might expect

Ig more important is just clarity

[tidal tulip]

k ty for checking

[vale cairn]

Np

[tidal tulip]

i’m trying to prove

A x ( B n C) subset (A x B) n (A x C)

i get stuck here are my steps how can i finish?

(x,y) in (A x ( B n C))

x in A and y in (B n C)

x in A and y in B and y in C

(x,y) in (A x B) and y in C

[vale cairn]

if x is in A and y is in B then (x,y) is in A x B

But similarly (x,y) in A x C

[tidal tulip]

how is (x,y) in A x C again

[vale cairn]

everything is symmetric in B and C so by the same logic as it being in B

[tidal tulip]

i’m not understanding can you spell it out more?

(x,y) in (AxB) and (y in C)

is what i have

(x in A) and (y in B) and (y in C)

which is either (x,y) in A x B and y in C

or

(x,y) in AxC and (y in B)

not sure how to finish it off

[wide vine]

what are you oringally trying to prove?

was it this

A x ( B n C) subset (A x B) n (A x C)

[tidal tulip]

yes

[wide vine]

Are you saying the thing on the left is a subset of the thing on the right

[tidal tulip]

yes

[wide vine]

They are equal though right so I guess you could call it a subset?

Anyways

[tidal tulip]

yes

i’m proving that direction first

[wide vine]

Well on the left do you see how you will always have an element in A for x in some tuple (x,y)

[tidal tulip]

yes

[wide vine]

and on the right you stuff you see how the same thing would happen for some given tuple called (x,y)?

[tidal tulip]

(x,y) in (A x ( B n C))

x in A and y in (B n C)

x in A and y in B and y in C

(x,y) in (A x B) and y in C

is what i see

[wide vine]

Okay well unironically

my old hw has this same question

Do you want the answer or do you want to use the given defintions

[tidal tulip]

answer so i can see how it’s done. i got stuck above

[tidal tulip]

reading

[wide vine]

They start off with Ax (B n C) and use the following defintions

[tidal tulip]

what is idempotent law

[wide vine]

and show how it is logically equivalent and thus the same as (A x B) in (Ax c)

[tidal tulip]

ok reading. i got lines 1,2 in the proof then stuck so studying the proof