discrete-math

[idle hazel]

thanks

ill try my best

[vital dew]

ᴇɴᴏsʜɪᴍᴀ ᴛʜᴇ 𝟻𝟺ᵗʰ

[idle hazel]

[dense glade]

Does anyone get the idea here because I'm little lost

[coral parcel]

Are you lost on (a) or (b)?

[dense glade]

on a

[coral parcel]

Start by expanding the definitions of "commutative" and "f".

[dense glade]

I'm not getting the function

though

isn't the every ordered pair made of 8 digits?

like for example (0,0,0,0,0,0,0,0) x (0,0,0,0,0,0,0,0) --> Z but what would be (a1,a2)?

[coral parcel]

(0,0,0,0,0,0,0,0) is one of the 256 elements of A.

Each of a1 and a2 is one of those.

So one possible (a1,a2) would be ((1,0,1,0,1,0,1,0), (1,1,1,1,0,0,0,0))

Writing (0,0,0,0,0,0,0,0) × (0,0,0,0,0,0,0,0) does not make sense, though. The × needs to operate on two sets, and (0,0,0,0,0,0,0,0) does not (for our purposes here) denote a set.

[dense glade]

ah I meant

an element from the set

o

so now

if these are (a1,a2) ((1,0,1,0,1,0,1,0), (1,1,1,1,0,0,0,0))

ah I see so

the function value would be in this instance

4

[coral parcel]

Yes.

[dense glade]

ok this is obviously commutative

[coral parcel]

Yes.

[dense glade]

its also transitive

[coral parcel]

What would that mean here?

[dense glade]

I'm goanna write it symbolically first

then say what it means

OK so I think whats its saying for example

if the difference in positions between (a1,a2) is 4 and (a2,a3)=4 then the difference between position between (a1,a3)=4

[coral parcel]

Hmm. That's not even true. For example a1 and a3 could be the same string, so the distance between a1 and a3 is 0.

Moreover, even though I can see some sense in your interpretation, "transitive" is not generally used about functions.

[dense glade]

yeah it just about the relation

I miss interpreted it

how can u prove

that its associative though

[coral parcel]

It isn't.

[dense glade]

the def says: for all a,b,c if f(f(a,c),b)= f(a,f(c,b))

[coral parcel]

Right.

So "associative" is not applicable to this function either, because the output from f is not the right kind of thing to give as one of the inputs to f.

[dense glade]

yeah

[coral parcel]

In other words, (b) is a bit of a trick question.

[dense glade]

yeah I found it on last year's final

and It's quite tricky

[idle hazel]

Its so funny to see a crying frog talking about math

Haha

[dense glade]

I have a question and it's probably dumb one but I'm a little bit confused. for mod 3 [0] is the residue class where 3 divides the elements of [0] evenly, but how is this equivalent to [3], shouldn't this be we remainder 3?

[coral parcel]

3 cannot be a remainder: 3 divided by 3 is 1 with remainder 0.

With a common definition of residue classes we have $$\begin{array}{l} [0] = { 3n + 0 \mid n \in \mathbb Z } \{} [3] = { 3n + 3 \mid n \in \mathbb Z }\end{array}$$ and these are just two ways of writing the same set.

[vital dew]

Troposphere

[dense glade]

yeah the set will be the same

but you need different values of n

to get the same values

I guess this doesnt matter

[coral parcel]

Right: The set doesn't remember which values of n goes with each of its elements.

[simple vale]

I have the following exercise:

Having this permutation f so defined (see the image below) determines f^2 and the inverse permutation of f.

I know how to do the inverse but not the squared permutation

[muted gate]

can you see that f(1) = 5, f(2) = 3, and so on?

[sour arrow]

1 → 5 → 6
So in the squared permutation, 1 → 6

[muted gate]

maybe that will help you with determining the composite

[muted gate]

because you'll notice that f(f(1)) = f(5) = 6

like kaynex showed

[simple vale]

So, in the end, the squared permutation should be this?

where 1 -> 6, 2 -> 1, 3 -> 5, 4 -> 4, 5 -> 7, 6 -> 2, 7 -> 3. Right?

[rich tiger]

I'm struggling with:

1. Images
2. Fields
3. Proof by contrapositive
4. Proof by contradiction
5. Induction
6. Cardinality
7. Bijective/injective/surjective stuff
8. GCD's and the Euclidean Algorithm
9. Reflexive, Symmetric and Transitive stuff.
   can someone help me go over these 😭

I watched like 5 videos on induction i still dont get it

[dense glade]

That's the entire course

[pale epoch]

thats a lot of stuff

i suggest going through it one by one and trying to formulate concrete questions

i know that is hard, but the process will also make you interact with the material more thoroughly

and if you have concrete questions, people here can help

[rich tiger]

sadly thats only half of it 😭

[rich tiger]

true

we can start with fields

okay hmm let me find a question

okay something like this

ik theres like 5 field axioms but

i dont understand some of them

like commutativity and distributivity etc

[weary tiger]

hi

can someone help me get started on this problem

I was saying that if x is in c, then x is in d U a. but then if y is in b, then y is in Dc, which is not in D. then, the intersection of c and b is everything except for D

but what if the elements in B are not in A?

[ember obsidian]

@weary tiger that question has no bearing on the logic required

also the logic isnt in the required format (element proof)

[weary tiger]

does this mean that every possible element exists in a, b, c, d?

is this the right format? I'm not rly sure what element proof means tbh

to you or if anyone else is interested in looking it over:

[ember obsidian]

this is what element proof is

[weary tiger]

2nd proof is better than the first

[ember obsidian]

lets say u wanna show X is a subset of Y

u take any element in X then show it must be an element of Y

[weary tiger]

hmm okay

I think I've seen that done a couple of times

[weary tiger]

is this a fair assumption?

[ember obsidian]

im not sure what that means

ur saying every object is in at least one of those sets?

if so then thats not necessarily true

[weary tiger]

yes that's what I mean.

[ember obsidian]

but it too has no bearing on the required logic

[weary tiger]

then how can I be comfortable with not B being equal to A

wdym

[ember obsidian]

u wanna show C cap B is a subset of A

follow the element proof format

[weary tiger]

isn't that intersection though?

[ember obsidian]

take any element in C cap B then show it must be an element of A

[weary tiger]

like I would have to know that B intersects C, which means B is A

[ember obsidian]

namely, smth like "let x be any element of C cap B"

[weary tiger]

oh do I start with what I am supposed to prove?

i thought it started with the supposition

[ember obsidian]

no, we're following the format for showing a set is a subset of another

this is what element proof is
lets say u wanna show X is a subset of Y
u take any element in X then show it must be an element of Y

[weary tiger]

okay I'm rethinking it now

im trying

[ember obsidian]

to recap

u wanna show C cap B is a subset of A
follow the element proof format
take any element in C cap B then show it must be an element of A

[weary tiger]

how can I know x in B is in A if I only know that an element in B is also in D complement?

[ember obsidian]

remember what we started at

we let x be any element of C cap B

[weary tiger]

okay

so we are crutching on the C supposition

[ember obsidian]

we eventually wanna show x is in A

now what does this say about x?

we let x be any element of C cap B

[weary tiger]

x is in c, b

[ember obsidian]

pls use correct casing

[weary tiger]

I do not know what that is

is there a guide for proper chat etiquette?

[ember obsidian]

capital vs lowercase

[weary tiger]

x is in C, B ?

[ember obsidian]

yeah

[weary tiger]

okay, apologies

[ember obsidian]

ie x is in C and x is in B

from the other info we have, what can we conclude from x being in C?

[weary tiger]

it is in D union (?) A

[ember obsidian]

yes, x is in D cup A

in turn what does that mean about x?

[weary tiger]

x could be in D or A

[ember obsidian]

x is in D or x is in A

now put this on the backburner

[weary tiger]

okay

[ember obsidian]

recall x is in B

from other info, what can we say about x?

[weary tiger]

x is not in D

[ember obsidian]

x is in D^c, from which that follows

[weary tiger]

yes

[ember obsidian]

now consider the new facts we got so far

x is in D or x is in A
x is not in D
what can we now say about x?

[weary tiger]

oh i feel stupid

x is in A

[ember obsidian]

we now conclude C cap B is a subset of A

[weary tiger]

thank u so much

what do you suggest i do in the future

like this feels so much easier now

but it was a brick wall before

[ember obsidian]

no prob. u can prob find many more set proof problems online

i have a few typed somewhere

https://cdn.discordapp.com/attachments/817801636968792125/956115171754016778/150414892225134592.png

prove if $A\sse B$ then $A\cup B=B$ and $A\cap B=A$

[vital dew]

RokabeJintaro

[weary tiger]

would you be okay to walk me through a couple

[ember obsidian]

i can help for the last one i sent then i need to go

[weary tiger]

okay

[ember obsidian]

namely A cap B=A

[muted gate]

Let $G = (V, E)$ be a graph with $n$ vertices and let $t(G)$ denote the number of triangles in $G$. Prove that: \

$$t(G) \geq \frac{\abs{E}}{3n} \left(4\abs{E} - n^{2}\right)$$ \

[vital dew]

texaspb

[muted gate]

can somebody help me start this proof? I don't even know what definitions or results I could be using

i'd appreciate any sort of guidelines

[weary tiger]

so i would say that if x is in a, then x is also in b by the supposition

or like where would i want to start with this

since im not showing a subset this time

[ember obsidian]

X=Y if X is a subset of Y and Y is a subset of X

so equalities (usually) demand two subset proofs

[weary tiger]

okay

I found a video online, I think I'm gonna follow along with it

ty again for the help with the previous problem

[ember obsidian]

yw, gl on my posted problems

[weary tiger]

ty

[severe swan]

Am I doing this correctly?

You roll a fair die once. Let A be the event that the roll comes up as 2, 3, or 4, and let B be the event that the roll comes up as an odd integer.

What is P(A | B) ?

A) roll is 2, 3, or 4

1/6 + 1/6 + 1/6 = 3/6 = 1/2

B) roll is odd
1, 3, 5
3/6 = 1/2

P(A | B) = P(A ∩ B) / P(B)

(3/6) / (3/6 ) = 1

3 is the only number that is the same for A and B
P(A ∩ B): 1/6 / P(B): 3/6

1/6 / 3/6 = 1/3 Answer?

[vernal cypress]

Hi, can anyone help?

[fair jungle]

Yes, but its nested within a for loop that repeats |V| times.

Shouldnt it be O(|V|x|E|)?
Sorry for the late reply.

[alpine grove]

is this permutation/combination question?

[muted gate]

this looks like a PHP problem

[coral parcel]

O(|V|×|E|) would be a valid bound, but O(|V|+|E|) is a tighter bound and also valid. The body of the inner loop repeats at most twice for each edge (namely once when each of its endpoints is moved to L), so the total number of iterations is at most 2|E|, no matter how those 2|E| are distributed across vertices.

This assumes you have a representation of the graph where you can efficiently find all the edges incident to a given vertex. But if you don't have that already (say, if you're given the graph in the form of a single randomly ordered list of edges), it's usually easy to start by constructing it.

[fair jungle]

yes, i do have an efficient representation. But why is O(|V|+|E|) tighter?

I understand the total number of iterations is 2|E| but why is it added.

What i mean is, how can i identify, in the future, for different algorithms, when to use a +, and not a x

I was just taught that if its nested, its multiplied. :/ How to spot when the bound of O(ab) is not as tight as O(a+b)

[vernal cypress]

can u help?

[coral parcel]

What you're really after is an upper bound for how many times each operation inside the inner loop is executed. It always works to multiply upper bounds for the number of iterations for the outer and inner loop what you have found separately, which why it's a good fallback. But a more careful analysis can sometimes give a better bound.

For example, if we consider complete graphs on n vertices, we have that |V|×|E| is about ½n³, whereas |V|+|E| is only about ½n², and therefore grows smaller.

[fair jungle]

😮 ok ok i understand now

[coral parcel]

In general if you can choose between a sum and a product, the sum will always grow smaller: As long as a > 2 and b >2 we'll always have ab > a+b (and the behavior for small a and b is irrelevant for asymptotic analysis).

[fair jungle]

Its just deriving the sum that poses an issue for me

I mean, how did the 1/2 n^3 come? I assume its through graphing? is there any way to know when the sum is tighter and a better upper bound?

[fair jungle]

This assumes you can choose between a sum and a product, but if u dont know that the sum is a tighter bound, how can you choose between something you dont know?

[coral parcel]

If you don't know, then you don't know it, of course.

But it's hardly deep mathematics that the product of two not-small numbers is larger than their sum.

[fair jungle]

Yes, but for example, in the algorithm i sent, how can you "derive" the O(n+m) without wikipedia telling you?

[coral parcel]

It sounds like you expect it to be a mechanical process.

It isn't.

It's based on understanding how the algorithm works.

[fair jungle]

alright, so the code having two nested for loops irrelevant then , only the computation it does is relevent?

[coral parcel]

It's not "irrelevant", but it doesn't mean you're duty-bound to use a particular canned procedure either.

The two nested loops are an essential part of how the algorithm does what it does; you can't hope to understand it without also understanding those loops.

[fair jungle]

Im confused. If its not a mechanical process, how can one ~~prove ~~ calculate that its O(n+m)? I understand how the algorithm works, but i dont make the link between summing.

[coral parcel]

Finding a proof of anything is almost never a mechanical process.

"Calculate" sounds like a mechanical process. I'm telling you that you're not supposed to follow a mechanical process.

It's not a matter of learning a pre-cooked recipe for analyzing an algorithm where you start by writing the algorithm down and then follow prescribed steps brainlessly until you reach something with a double line under it.

You need to understand how the algorithm works.

[fair jungle]

It maintains a map of vertices and their degrees, repeatedly "removes" or rather considers the minimum vertex present on the subgraph as removed, updates the degrees of the neighbors on the map, and does this until the subgraph produced is null.

[coral parcel]

Um, yes, good.

[fair jungle]

How can i make the jump to "analyzing the algorithm" now?

[coral parcel]

Didn't you tell me that you understand that the total number of times through the inner loop is at most 2|E|?

[fair jungle]

yes, because you must update the neighbors for each vertex. And so you will be looking at the (V_i ,V_j) and then eventually (V_j ,V_i), but its an unodered pair so we are looking at the same edge twice

if i understand correctly 😕

[coral parcel]

Yes.

But then what is your question? The only thing you seem to be asking for is which cookbook recipe would have told you to look for precisely that property. And the answer to that is THERE IS NO COOKBOOK RECIPE.

[fair jungle]

I just want to understand why its O(n+m)

[coral parcel]

Didn't you tell me that you understand that the total number of times through the inner loop is at most 2|E|?

[fair jungle]

yes

what does that have to do with it?

i dont make the link

[coral parcel]

O(|V|) + O(2|E|) = O(|V|) + O(|E|) = O(|V|+|E|).

[fair jungle]

and its O(|V|) + O(2|E|) because?

[coral parcel]

O(|V|) is the number of times the program executes some step outside the inner loop. O(2|E|) is the number of times the program executes some step inside the inner loop.

The number of times the program executes any step is the sum of these.

[fair jungle]

and why exactly isnt it the product?

[coral parcel]

sdf.lkwehrtogfjwethwrg

If you're putting some marbles into a bag and N of the marbles are red and M of the marbles are blue, then what is your best estimate of the total number of mables in the bag? N×M or N+M?

[fair jungle]

suppose i was in kindergarten. I just want to know why we add N and M to get the total number of marbles

thats my question

Like why add

[coral parcel]

For the exact same reason that in kindergarden you ADD the number of red marbles to the number of blue mables to get the total number of marbles, instead of multiplying those numbers.

[fair jungle]

But the marbles its commutative, it seems to me that its distributed within the code

[coral parcel]

The number of steps ever executed by the algorithm is the number of steps it executes outside the inner loop added to the number of steps it executes inside the inner loop.

Addition is commutative no matter what is is you count. Marbles, apples, dollars, computational steps, that doesn't matter.

[fair jungle]

Yes, but if a loop is nested within something else, isnt that distributive? I mean, the for loop to look in the neighbors is going to be launched |V| times sounds like distribution to me. I just want to know why im wrong

[coral parcel]

If you want to count how many cars are crossing the bridge per day? Count the number of cars that cross it from east to west, then count the number of cars that cross it from west to east. Add those number.

OR: Count the number of red cars that cross the bridge, and then count the number of cars that are not red, and then add THOSE numbers.

Or count how many cars have a male driver and count how many cars have a female driver, and add those numbers.

If you want to count how many instructions the program executes? Count how many instructions it executes in the inner loop, and count how many instructions it executes outside the inner loop, and then ADD THOSE NUMBERS.

[fair jungle]

but for example two, the inner loop executes m instructions, and outside it executes n instructions, and the answer is O(nm)

[coral parcel]

No.

If you have a set of ANYTHING AT ALL -- marbles! cars! instructions! apples! -- and you split it into two groups that you can count separately, then the total number of things you have is ALWAYS the sum of your two counts. Never the product.

[spring zephyr]

You count the steps inside the for loop and multiply that with n

[coral parcel]

Unless the two counts are either both 0 or both 2.

[fair jungle]

okk i get it, the 2|E| is the total of all executions of the inner loop within the program

?

[coral parcel]

Yes.

[fair jungle]

ok i think i understand

https://tenor.com/view/patrick-star-spongebob-squarepants-wow-mindblown-gif-13169052

Thank you mate for ur explanation

[coral parcel]

Phew.

[high ermine]

Hi, can anyone help me with this $\sum_{k=1}^{n-1} \frac{1}{k(n-k)}=O(\frac{log(n)}{n})$?

[vital dew]

LearTsura

[high ermine]

nvm, $\frac{n}{k(n-k)}=\frac{1}{k}+\frac{1}{n-k}$

[vital dew]

LearTsura

[dense glade]

how many ways can we pull 3 aces and2 jacks? my answer is :

(13C1)(4C3) for the aces and (13C1)(4C2) for the jacks so (13C1)(4C3) * (13C1)(4C2) but the answer is just (4C2)*(4C3)

What did i do wrong?

[balmy jay]

I guess the answer is just doing: there are 4 aces and 4 jacks in a standard deck of 52 cards so from 4 aces, we choose 3 and from 4 jacks, we choose 2. So (4 choose 3) * (4 choose 2) in total

I don't quite understand how you're getting (13 choose 1) * (4 choose 3) for the aces

[onyx fable]

Does anyone know the recursive fomula for 3,12,27,48,75...?

[obtuse lance]

looks like 3n^2

[idle hazel]

How do you figure it out so fast

[white hawk]

cus 3*2^2

3*3^2

I think

[idle hazel]

Yeah but 48??

[obtuse lance]

they were all multiples of 3 so I divided out 3 and was left with squares

[white hawk]

oh weird

[idle hazel]

I figured that out but 48 confused me

[white hawk]

48 is n = 4

[idle hazel]

I see now

[white hawk]

(or -4 perhaps)

[idle hazel]

[white hawk]

3n^2=48

then just solve for n

thats how i got 4

[obtuse lance]

in my head I didn't know if 3*16=48 immediately but I knew 16=2*8 so I put the 2 with the 3 to make 6*8 which I knew was (7-1)*(7+1) = 7^2 -1 = 49-1 = 48

ok that last part is a meme, I memorized 6*8 as a kid lol

[weary tiger]

is c an answer choice?

[obtuse lance]

also when I first went through it I just skipped the 4th term and knew 75 was 3 quarters so that's all the evidence I needed

[obtuse lance]

wrong channel try #prealg-and-algebra

[white hawk]

haha flashbacks to dad forcing me to learn all the mult. tables

[obtuse lance]

take finite differences of it until it goes away

each time you take f(n) and go to f(n+1)-f(n) the degree of the polynomial decreases

[clever kraken]

can someone help

[weary tiger]

does anyone have an answer for this question

when I do it I end up with 0

lol

[light heath]

for number 42 would you guys agree with my response. Does it leave any ambiguity?

[remote cosmos]

what do you mean you end up with 0?

[remote cosmos]

first start with your base case

(which should hold true)

then state the hypothesis,

and show it holds for the n+1 case

at some point you have to plug in your hypothesis help you prove it

[dim sage]

Hello.

Is there anyone completely familiar with Discrete Math?

Need a tutor for 3-5 hours who can help me brush over concepts and clear my understanding regarding certain topics.

^^ PAID

Please ping me if you're able to ^^

[queen tapir]

Hello. I have a question about Rabin crypto. https://crypto.stackexchange.com/questions/13022/why-is-this-authentication-procedure-using-rabin-crypto-not-useful For this top answer, I dont understand why it works with probability 1/2? x^2=d mod N should have 4 solutions for N=pq. So shouldn't the probability be 1/4?

[jolly jay]

Does anyone know an approximation to the number of surjections? Or a lower bound?

A lower bound that is not f(x)=6.9

[coral parcel]

Which surjections?

[manic coral]

Can someone help?

I think this is so obvious that I cannot even start

[umbral tendon]

Hi, I've been working on a proof for surjectivity. I would like someone to tell me if the proof is correct.

For the function to be surjective every element of the function's co-domain is the image of at least one element of its domain.

So we can prove by counterexample by saying 2x^3 + 3 = 100 and after solving the equation we end up with 3.647 which lies outside of the range of the domain of x [0,1] so there exists a an element in the co-domain that doesn't have an element in it's domain therefore the function is not surjective.

[robust mango]

@umbral tendon Yes

Correct.

[jolly jay]

An approximation to the number of surjections from X to Y.

The first two terms of the sum given by the exclusion-inclusion principle might be it, no clue

[muted gate]

guys in this example if he wanted he could've done the bipartition $(V_{1}, V_{2})$ with $V_{1} = {v_{1}, v_{2}, v_{3} }$ and $V_{2} = {v_{4}, v_{5}, v_{6} }$ instead of the one he did, right?

[vital dew]

texaspb

[obtuse lance]

not if they're numbered the same way

[muted gate]

I just noticed

[obtuse lance]

v1 and v2 are connected with an edge, so they can't be in the same set

[muted gate]

every vertex in V1 has to connect with one in V2

yeah

[obtuse lance]

cool

[muted gate]

ok

now I get it

thank you

[obtuse lance]

👍

[coral parcel]

It does sound like a typical inclusion-exclusion problem, yes.

More specifically, inclusion-exclusion can be used to count the maps that are not surjections.

If |X|>>|Y|, taking the first few terms would probably give fairly good bounds.

Alternatively, there are some explicit approximations at https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

... from which you can compute the number of surjections as $|Y|!\genfrac{}{0pt}{}{|X|}{|Y|}$.

[vital dew]

Troposphere

[north bay]

What do I do in Simplex Method when one of my restrictions is x >= 3 for example
I only know how to apply the method when the variable is greather or lower than 0

oh wait

nvm

got it

[simple vale]

I've got a group (first image), that is symmetric on 7 objects, and a permutation f (second image). I have to determine what's the cyclic subgroup <f> of the group generated by f. I know what's a cyclic subgroup (third image) and that to find it i just have to execute the binary operation on the elements to see if it is indeed a cyclic subgroup, but the exercise poses the question like there is only one cyclic subgroup. Can someone explain to me how it works?

[pale epoch]

there is no third image

but each element of a group generates a cyclic subgroup by repeatedly multiplying that element with itself

in finite groups you are guaranteed to arrive at the identity at some point and then you are done

[simple vale]

Right, i forgot to send it

[pale epoch]

so there is only one subgroup generated by f

it contains the elements id, f, f*f, f*f*f, ...

[simple vale]

So in this case the identity should be "1" and it is intended to be my "stop" signal when searching for subgroups, i mean that when i repeat the binary operation and i reach the identity it means that no matter how many times i do the operation, i'll always get the same results. Right?

[vernal cypress]

Hi, can anyone help?

[pale epoch]

yes, hence the name cyclic

if f^n = 1, then f^(n+k) = f^n*f^k = 1*f^k =f^k

so you can reduce the exponent modulo n and the elements just repeat

you can also just do this and see it for yourself

once you reach 1 with positive exponents, you are done

[placid mason]

This is a nice problem, represent the people as a complete graph on six vertices, red edges for "people who know each other" and blue edges for "people who don't know each other". Your task is to prove that there is a monochromatic (one coloured) triangle in this graph

A good start is just to try things out. Pick your favourite vertex. It has five edges going out, and analyse each case: when three of those edges are blue, two are red. Or when four are blue, one red, etc.

[dense glade]

does anyone know how to answer d?

[pale epoch]

try building such a tree with less vertices

[elder berry]

How does one show the following sum?

[vital dew]

peaceGiant

[elder berry]

So the above is just binomial expansion... Nevertheless, is the above the answer to the following question?

[vital dew]

peaceGiant

[whole field]

@elder berry what does the arrow mean

[elder berry]

It's an implication arrow

whenever (x, y) is in the relation, then so is (y, y)

[whole field]

hmm

[elder berry]

Here is my write-up of the solution, I am looking for someone to verify it (confirmed)

[elder berry]

(by the term confused relation, I am indeed referring to the above relation with the said property)

[bitter meadow]

Werid question. Im a comp/physics major with a little bit of coding experience (like two classes) and have finshed calc 1,2,3 and ODE. I need to take discrete math but it conflicts in my schedule so the head of the department wants to throw me into the grad level course. Is it mostly math not coding and would I die? Bc I dont want to get slaughtered in the course

[tidal tulip]

what’s the topics in the course?

@bitter meadow

[sick dirge]

Hey, so I have a different proof than my textbook, so was hoping if someone can help me check if it is right. The question is to show that if $az^2 + bz + c = 0$ and $a, b, c$ are odd, then $z$ is irrational. Here's my proof: By the quadratic formula, we have that $z$ is irrational if and only if $b^2 - 4ac$ is not a perfect square. Suppose for the sake of contradiction that it is a perfect square. Then, since it is odd, then by a previous theorem, it must have the form $8N + 1$. However, substituting $a = 2k + 1, b = 2m + 1, c = 2n + 1$, we have $b^2 - 4ac = 4k^2 + 4k + 1 - 4(4mn + 2m + 2n + 1) = 4[k(k + 1) - (4mn + 2m + 2n)] - 3$. The term in brackets is even, so this number has the form $8N + 5$. Hence, contradiction. Is this right?

[vital dew]

PhenomPlasma

[unreal stump]

Yea That's correct @sick dirge

Well you changed variables(should be 4m^2+4m+1-...) but the general idea is correct

[sick dirge]

Ah I mixed up my letters. My bad. Thanks!

[vital dew]

texaspb

[stray reef]

inputs?

did you mean entries?

[muted gate]

yes

Let $\textbf{A} \in {0, 1}^{n \times n}. \text{ Suppose that at least } 2n \text{ entries in \textbf{A} are 1}$. Prove that \textbf{A} has two entries such that one of them is strictly above and to the right of the other.

[vital dew]

texaspb

[muted gate]

great

now it's cool

[stray reef]

also just to clarify

you meant that there are two ones of which one is strictly above and to the right of the other, yes?

@muted gate

[muted gate]

yes

[stray reef]

hm

consider the sw-ne diagonals in your matrix

there are 2n-1 of them

pigeonhole

[muted gate]

what is sw-ne?

[muted gate]

okay, gotcha. the trick is to just find what are the pigeons and the pigeonholes right

I always mess this up

[stray reef]

southwest-northeast

[stray reef]

didn't i already basically lay out the holes for you tho

and it should be p obvious that the pigeons are 1s

[muted gate]

okay

thank you so much

[frosty musk]

why is 27 and not 29

29 => 1st digit 9 choices, 2nd, 10, 3rd 10

[nimble sequoia]

for c?

[frosty musk]

yes

actually

the answer to a is 990

[nimble sequoia]

2 of the digits are 4 so they only have 1 option each
since you need exactly 2 4s the other digit is any number except 4 so there are 9 possibilities

[frosty musk]

that means that it's 10 * 10 * 10 - 10

[nimble sequoia]

then you can either have 44x, 4x4 or x44 so there are 1 * 1 * 9 * 3 = 27 possibilities

[frosty musk]

yes exactly

it can be 0

ty

.close

[nimble sequoia]

np

[frosty musk]

how?

this one I understand:

10 * 9 * 8 * 7, but since the table can be rotated in 4 ways, it overcounts by a factor of 4

so the answer to 1. is 60, 6! = 480, 60 = 480/8, so according to this 6! overcounts by a factor of 8?

but i don't see how i could have come to this

idk how to solve this either

[fickle turret]

How come i can use absorbtion law in this given
a v b v c v (!a ^ c ^ b) given
a v b v !c absorbtion

[frosty musk]

occupied

[spring surge]

bride next to the groom is from b g 0 0 0 0 to 0 0 0 0 b g
5 places, we can switch them so X2 and we arrange all what's left 4! times. Final a) answer is 5 x 2 x 4!

[vital dew]

waris

waris

[cold topaz]

i'm not sure how to answer c : \ .. please ping me if c is answered

[muted gate]

you didn't post anything

[cold topaz]

i did : | .. using the bot

[muted gate]

oh ok

didn't see

[cyan prawn]

Revising for an exam coming up, think I'm getting the hang of things but could use some help 🙂

For showing this is a semi group, would I show that multiplication on A is a binary operation by something like (e^xπi) * (e^yπi) = e^(x+y)πi

and x+y is an element of R, therefore it's binary?

Also if so can I then just say it's a semi group as I've proved that and since multiplication is associative on C? (and is there a better way to word this)?

One more, if I want to show its a monoid, would e^0πi be the correct identity element? That would work out as 1, correct?

[severe swan]

How can I solve this?

Cats Fluffy and Tigger have decided to have one kitten in 2022, a 2nd kitten in 2023, and a 3rd kitten in 2023.

Let A be the event that they have at least one female kitten and one male kitten.

Let B be the event that they have at most one male kitten.

If p(A)=x/8 , what is the value of x ?

If p(B)=x/8 , what is the value of x ?

If p(A∩B) =x/8 , what is the value of x ?

[pale epoch]

looks good @cyan prawn

semigroup is just associative?

[cyan prawn]

Semigroup is the operation is an associative binary operation yeah

[pale epoch]

ok yeah, it inherits associativity from multiplication in C (or addition in R)

thats the best argument as well

also notice that e^0πi = 1

so this agrees with the monoid structure of (C, *)

[cyan prawn]

Also if someone could explain what's going on here a little better to me, confused by a few things. Firstly is it known that e^10πi/5 = 1 because there's a pattern in the set?

[pale epoch]

thats eulers theorem

[cyan prawn]

And then next where is the line "e^2kπi = 1 for every k in Z coming from?

[pale epoch]

$e^{i x} = \cos(x)+i\sin(x)$

[vital dew]

Lochverstärker

[pale epoch]

you basically turn x radians on the unit circle in the complex plane

so if you turn 2pi (or any multiple of that) you land at 1

[cyan prawn]

Hmmm okay I'll look into that

[spring surge]

Describe all possible intervals in Z.
I suppose it asks for a set { a : a is interval of Z }

how can i make it more formal?

[cold topaz]

no one solved the question c here?

[austere cedar]

there are as many arrangements with the bride being on the left of the groom as there are arrangements with the bride being on the right of the groom

[cold topaz]

so it's simply half of the answer to a?

wait no

it's half of the total ways 6 people can be arranged

[austere cedar]

You can write something like $\lbrace [a,b]|a,b \in \mathbb{Z} \rbrace$, but i guess thats all

[vital dew]

Alexander42

[austere cedar]

yes

[vital dew]

waris

[austere cedar]

yes

[cold topaz]

awesome! thanks : }

[fickle turret]

How come i can use absorbtion law in this given
a v b v c v (!a ^ c ^ b) given
a v b v !c absorbtion

[floral field]

How can I argue that for a graph with 9 vertices, I can't have a bipartite graph, where the degree of the vertices are:
{3,3,3,3,3,5,6,6,6}? Because I've tried to get it done, but it's just impossible

[elder berry]

Maybe there is a better solution, but I think this argument works:
If we have two disjoint sets A and B, we can put one of the vertices with degree 6 in the set A.

Because of that, at least how many elements must be in B?

(and at most, how many elements can be in A)

[elder berry]

right

[sleek loom]

can I use the duality principle like this?

If $B^{c} \cap A \neq U$ then by the duality principle $B \cup A^{c} = \varnothing$

[vital dew]

Orian

[languid citrus]

can someone verify if my answer for this question is correct?

[stray reef]

there are some typos

also you keep saying A ∈ Z, B ∈ Z, C ∈ Z when you should be taking them as elements of P(Z) and not elements of Z

also "BSA is symmetric" doesnt make sense. relations can be symmetric, their particular values at particular points are just that - truth values

[languid citrus]

wait let me edit it

[languid citrus]

is this correct now?

[stray reef]

yes

[languid citrus]

how about the letter b?

determine all distinct element sof P(Z)/S

[frosty musk]

if the case of letters doesn't matter then why is the answer =>, and not 52^3 + ...?

[frosty musk]

why?

why is it 18 and not 21?
4* 3 * 2 * 1 - 3 (where a is followed immediately by b)

[bleak void]

Where to you get -3 from? If a is followed by b, then you have more than 3 situations where that can happen.

[frosty musk]

[a][b][][] [][a][b][] [][][a][b]

[frosty musk]

^

oh

[bleak void]

OK, so there are three "patterns", but e.g. for [a][b][][] you have two possibilities.

abcd, abdc

[frosty musk]

right

my bad

[frosty musk]

what about this one?

though here i wasn't careful, not sure about this one

[bleak void]

If you ignore case, there are only 26 letters to choose from.

[frosty musk]

it says, though, that the case does not matter

not that you should ignore it

so you still have 52 possibilities

oh wait

nvm

they'll be equal

so i'm double counting

[bleak void]

Well, you can do it with 52 possibilities, but then you have to divide out by the number of strings that are the "same" according to the casing.

You're going to get the same thing in the end.

[stray reef]

it is precisely because letter case for not matter that you have only 26 options for every letter and not 52 as you would if you considered a distinct from A

[cold topaz]

well just imagine in your head all the possible ways the bride, groom, and the four other people can be arranged. half the time the bride will be on the right side of the groom and the other half of the time she'll be on the left. so we want the total number of ways to arrange 6 people in 6 spots and find its half. does that make sense?

[frosty musk]

thanks

[zenith oyster]

Is turing machines discrete math?

[unreal stump]

Yea sure

[zenith oyster]

I have a problem to solve, and I'm struggling a bit on how to think about these Turing machines.

I'm supposed to determine if a problem is decidable. The problem is:

A Turing Machine is run on empty input and at some step if the position i of the memory tape is equal to a value x (part of the alphabet of M) then it returns true and if not false.

My question is what exactly the program is able to do? What if at position i+1 it enters a state where it tells the tape to go back one space and put a x in the cell instead. Then it surely would be able to enter accept state right? What if the program just puts x in every cell and when it hits position i it finishes. Can it do that?

Would this also mean it can theoretically keep going forever if the cell never is set to x? If the tape is infinite that is? Then I could use undecidable of Halting problem on empty input to prove that it's undecidable right?

It's very confusing to me

How does a turing machine know whether it's on position i of the tape anyway?

Because if I was to write this in Python then logically there would be some program that would never end.

[unreal stump]

Well,yea it can go back and put an x in that cell . I guess the assumption is the initial configuration is all blank except for position i which may not be blank

You can do a counter kind of thing in TM, so you can keep track of what position you are in

[zenith oyster]

Ok, so empty input means the memory tape is empty right?

[unreal stump]

That's what I would assume,but then isn't the problem obviously false?

[zenith oyster]

Maybe

[unreal stump]

Ok,nvm I get it

Your transition function might cause some changes

For example, convert blank to your x and move right while being in the same state

This would mean for any position i ,it will become x

Because your head sees a blank and makes it a x,and then move forward again seeing a blank

[zenith oyster]

Ok but if it stays in same state can it truly check for position matching as well?

[unreal stump]

No

You can accomodate for that in other ways

[zenith oyster]

But I can decide what my Turing Machine does?

[unreal stump]

Well yea

[zenith oyster]

this is the problem in its original formulation

[unreal stump]

This is decidable I think

If Your Turing machine doesn't ever reach i, the answer is No

If it does,It can make it into x or not

[zenith oyster]

Couldn't it reach i, go further than i and come back to i though?

[unreal stump]

If you come back to i,you are reaching i

Actually it could do that

[zenith oyster]

sure but for every pass couldn't it edit what x contains, in perpetuity without making it x?

[unreal stump]

The question is if i will be changed to x at some point of timd

[unreal stump]

You can predict that with transition functions

Well in that case it will be no

[zenith oyster]

but I feel it depends a lot on what instructions the machine runs on, should I think of it as I don't know what instructions are on it maybe?

[unreal stump]

Think of it as a program

No matter how big a program is,it will be finite

And you can do a dry run to check if a particular situation will ever occur or not

Think of the transition functions as a giant switch case

[zenith oyster]

sure

[floral field]

Why does any simple graph have at most nC2 edges?

[stray reef]

what's n? the number of vertices?

[floral field]

Yeah, n vertices

[stray reef]

if so then that's because nC2 is how many edges K_n has

[unreal stump]

Now finiteness of states mean your turing machine is either stuck between 2 integer points

Or it goes on in one direction forever

[stray reef]

K_n is the complete graph on n vertices. it is the graph containing every possible edge that exists

[zenith oyster]

yes I can see that

[unreal stump]

Well nC2 is the number of ways you can choose to make an edge with n verticrs

[zenith oyster]

so you're convinced its decidable?

[unreal stump]

Yea

If it oscillates between two points,The behaviour also oscillates

If it goes in one direction,That case could be yes or no but that is completely determined by the transition function

[zenith oyster]

ok I will think about this

[unreal stump]

This is just intuition, formalize this

[zenith oyster]

couldn't the position i be set to x without it the machine noticing

like it write x to i but it doesn't check if i is x if you know what I mean

[unreal stump]

Actually nvm,could happen ig

[zenith oyster]

so should my solution be that it applies for every possible program

[unreal stump]

Yea

[zenith oyster]

wack

thanks for your help I think I need to digest all

one last thing, it says in the problem,

"will ever be
assigned a certain value at some time during the execution of the program"

there will be some time step where position i of the memory tape contains the value x

does this mean it cannot go backwards? if i represents time?

[unreal stump]

i doesn't represent time

[zenith oyster]

oh its just some time as in at some point?

[unreal stump]

Think of an array a[100]
for x in a:
x=1

for x in a:
x=0

Here each element of a is 1 at some point of time

[zenith oyster]

ye

[unreal stump]

That's what they mean

[zenith oyster]

ok

[unreal stump]

Think of the space as an infinite array

And you are starting from 0

This problem corresponds to bring able to do a dry run and predict how variables will be,I believe

Because in a dry run ,you are acting like a "Turing Machine"

[zenith oyster]

ok

[weary tiger]

we have 3n+1 balls, and n are identical and 2n+1 are different, in how many ways can we choose n balls from them

I kinda need help, so if it is identical and it's all of thme

we have one way

and vice verse with all different

but between them

is it the sum from k=0 to n for 2n+1choosen-k?

[minor zephyr]

Let $A,B$ be languages with $A \leq_m B$. If $A$ is context-free, then is $B$ context-free?

[vital dew]

kxrider

[subtle juniper]

trying to solve congruence equation, which part am i doing it wrong?

[coral parcel]

What does \leq_m mean in that context?

[minor zephyr]

A is mapping reducible to B

[coral parcel]

Google finds me at least one definition of "mapping reduction" which looks like it means just many-one reducability with an arbitary computable map.

In that case, you could let A be a language that consists of just one string, and B be any language that is known not to be context-free...

For example A = { 1 } and B = { 1^n 0^n 1^n | n in N }.

[median mica]

Hey everyone, I wanted to hear your input on this one: (ping for response)

[minor zephyr]

ahh okay, thanks. the computable function concept wasn't really clicking to me at first, but this makes a lot of sense

[delicate river]

U={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} A={5,8,10,12,13,16,17,19,20} B={x∈U:x is a multiple of 2} C={x∈U:x>5}

[minor zephyr]

hmm the converse to this seems much less obvious though

wait no. If B is context free but say B \neq Sigma*, then given some non-context-free language A, there is a computable function mapping all strings in A to a single element of $B$, and mapping all strings not in A to a string not in B. At least that should be the idea

[coral parcel]

Yeah, as long as A is at least decidable.

[simple vale]

As you can see i've tried to solve this exercise and i think that i got it right, but i was wondering if it's possible to simplify the result even further because 47^22 is still a huge number.

[stray reef]

@balmy dome do you want somebody to do this for you?

[balmy dome]

yes

if u could explain it, that would be great

[stray reef]

we don't do other ppl's homework here

[balmy dome]

I just needed help understanding the topic, thanks anyway

[north pulsar]

The degree of a vertex A in an undirected graph is the number of vertices that do not share an edge with vertex A.

true or false

[wide vine]

For directied graphs, how do self loops work regarding indegree and outdegree of a vertex

[north pulsar]

well a self loop is an edge that connects itself to a vertex

outdegree of a vertex is how many edges are pointing from it, whereas indegree is pointing to it

[wide vine]

yeah so idk if you count it as both or none?

say you have this

A has a in degree of 1 because (b,a) and an out degree of 1 because (a,b)

but I am just not sure if you count (b,b) as both in and out

nvm I guess it counts as both

[north pulsar]

its false

[wide vine]

`in-degree(u) = |{ v | (v, u) ∈ E }|

out-degree(u) = |{ v | (u, v) ∈ E }|`

[coral parcel]

First, the line where you write about $21347^{182\bmod \phi(100)}\equiv 1\pmod{100}$ is misunderstood or misphrased. That simply connects two false statements with a $\implies$, because $21347^{22}$ is in fact not congruent to $1$ modulo $100$.

[vital dew]

Troposphere

[wide vine]

wdym its "false"

[north pulsar]

i asked above if it is true or false

and it is false

[coral parcel]

Second, you can get a better reduction by using the https://en.wikipedia.org/wiki/Carmichael_function instead of the totient function. The Carmicheal function of 100 is 20 rather than 40 -- namely, a^2 == 1 (mod 4), and a^20 == 1 (mod 25), so by the Chinese remainder theorem, a^20 == 1 (mod 100). So you can reduce all the way down to 47^2.

[wide vine]

oh Idk we never got to undirected graphs

[simple vale]

Thanks for the tip but my teacher didn't explain this way of doing this kind of exercise so i prefer to stick to what she taught to me (the Euler's theorem)

[coral parcel]

You did ask for ways to simplify it further. ¯_(ツ)_/¯

Another way you can simplify is to write 47^whatever as (50-3)^whatever; then if you expand by the binomial theorem all terms except the first two disappear modulo 100. (And the second term disappears too if the exponent is even).

[zenith oyster]

Anyone have any thoughts on this, JohnDS has helped me to think this is decidable. It would be decidable as the input is blank, if it doesn't reach i the answer is no and if it does it can either put x in position i or not.

However one thought I cannot shake from my head (as I don't fully understand the capabilities of a turing machine) is if it can tell if it's on a certain position, which I'm logically guessing it can how else would it know where i is?

[coral parcel]

One standard question to ask yourself each time you wonder whether such-and-such is decidable is: If I had a way to decide this, could I find a way to abuse it into solving halting problems for me?

(The other is of course: Can I come up with a way to actually decide this?)

There are problems that are neither decidable nor can be used to solve halting problems, but they arise surprisingly rarely in practice.

[zenith oyster]

Ok i will of abuse

[coral parcel]

This reasoning doesn't really sound convincing. What if the Turing machine reaches the designated square and doesn't immediately write an x to it? It's not immediately clear how you'd tell whether it eventually returns to that square to write x.

[zenith oyster]

Sure but same logic can be made from it just moving 2 squares in an infinite loop no?

[coral parcel]

Hmm, not sure how that becomes an argument that you can decide the problem.

[zenith oyster]

Well idk myself I’m not good at this

I will think more about it

[zenith oyster]

This was my first thought but somehow i can’t rly prove that such a thing is possible in a finite set of conditions

[coral parcel]

You can't prove that what is possible?

[zenith oyster]

A turing machine would be deterministic on empty memory tape right?

[coral parcel]

Turing, not "turning". But yes, Turing machines are deterministic.

[zenith oyster]

Ok, but what if it does an infinite loop looking for the x at i, does that count as decidable or undecidable? Like it's this part I don't rly get

[coral parcel]

"Decidable" means there is a way to decide the problem that will always complete with the correct answer. (Or in other words "(loops forever)" counts as a wrong answer no matter what the right answer was).

That's the difference between "decidable" and "recognizable". For "recognizable" you're allowed to loop indefinitely when the correct answer is "no".

[zenith oyster]

So in the case it is decidable, I need to think of a case where using it solves halting problem then it must be undecidable

Like should I assume it is decidable and if I don't find scenario of abusing halting then it is truly decidable

[coral parcel]

If you find neither a plan to solve halting problems nor a way to decide it, then you cannot conclude anything from that.

(I can tell you that one of these is in fact possible for the particular problem you're looking at, though).

[severe swan]

Question 8)
You roll a fair die once. Let A be the event that the number comes up a 5 or 6. Let B be the event that the number that comes up is greater than 2. What is p(A|B) ?
I don't understand why the answer is 3/6.
A) event that the number is 5 or 6

2/6 probability that 2 out of the 6 numbers are a 5 and a 6

B) event that the number is greater than 2
4/6 (3,4,5,6)

Because 5 and 6 appear for A where the number is 5 and 6 and also for B where the number is greater than 2 is it counted twice since it appears in event A and event B?
Trying to solve for p(A n B) I did 2/6 x 4/6 and got 2/9.

p(A|B)

p(A n B) = ? 2/9

p(A n B) / p(B) = (?) (2/9) (A n B) / (B) 4/6 = 2/9 and not 3/6 When I tried converting 2/9 to x/6 I got 4/3 as the answer.

How do you get to 3/6 as the answer?

[zenith oyster]

nice tease (maybe obviously idk), I'll think about it more

may I ask did you just know about this problem or did you think your way to the solution?

[zenith oyster]

Still my question about positioning remains, like how does the turing machine know which cell is at position i?

[severe swan]

Tickets numbered 1-100 are put into a hat. Four tickets are drawn randomly. Once a ticket is drawn then it is put back into the hat. The first ticket drawn wins $900, second wins $500, third wins $200, fourth wins $100.

What is the probability ticket #35 wins a prize?

Answer: 1 - (99/100)^4

Where does the 1 come from?
I get that one ticket is taken out and that is why it is 99 and there are 100 tickets total.

[clear ridge]

can anyone help with this proof by induction

[balmy jay]

Since there are 100 tickets total, there are 99 tickets that are not ticket #35. The probability all 4 tickets drawn are not ticket #35 is (99/100)^4. We subtract that from 1 to get the probability that ticket #35 is at least one of the four tickets drawn.

[coral parcel]

We number squares relative to the square the machine starts on. If the machine wants to know its absolute position later on, it needs to have kept track of how far it has moved since then, by a combination or low-level information encoded in its state, and writing appropriate navigation marks on the tape if if moves farther away than its finite state space can remember.

[coral parcel]

I don't recall seeing that exact problem before, but I know that questions about how programs behave in general requires knowing which parts of the program they can even reach, which means we effectively need to know if an early part terminates.

So if I'm asked does this program print out "hello world"?:

10 do something complicated (which doesn't contain any commands to print anything)
20 PRINT "hello world"
30 END

then effectively I'm being asked whether the "something complicated" terminates or not.

[weary tiger]

what have you tried so far

[south mesa]

How do we prove part a

[unreal stump]

Suppose G-{v} contains a cycle,Consider G

G will also contain a cycle

[south mesa]

Oh lmfao

Thanks

[south mesa]

How do you do 8b with proof contradiction also

I don't understand how you'd show it must be infinite

[severe swan]

How do I calculate this? Specifically if D is correct and how can I calculate E?

Two fair dice are rolled.

Let A be the event that at least one of the dice lands on 5 or 6.
Let B be the event that the sum of the values is 7.

A) If p(A) = v/36 what is v?
20/36

B) If p(B) = w/36 what is w?
6/36

C) If p(A n B) = x/36 what is x?
4/36

D) If p(A|B) = y/36 what is y?

p(A|B) = p(A n B) / p(B)
4/36 / 6/36 = 2/3
2/3 converted to 24/36

E) If p(B|A) = z/100 what is z?

p(B|A) = p(B n A) / p(B)

How can I calculate p(B|A) if I have p(A|B)?

Is p(A n B) the same as p(B n A)?

[proven silo]

Look up Bayes theorem (or just derive the relation yourself)

[delicate river]

how are sets and functions useful?
like whats the purpose

[coral parcel]

They are a common framework that we can use to speak about the things that are actually interesting. Without something like them we'd need to reinvent the same concepts a lot of times.

[delicate river]

is that the main reason they are useful?

[coral parcel]

Yes, it's a common vocabulary for essentially all of mathematics,

[delicate river]

thank you

[forest saddle]

So in this proof we assume that d is the minimum element in S, and using this assumption we find that d is a common divisor of a and b

We then show that any common divisor of a and b must divide d

But does this proof prove that the gcd of a and b is the minimum element in S

[coral parcel]

It proves that d is a common divisor, and that every other common divisor is smaller. What else do you want for being a greatest common divisor?

[forest saddle]

Isn't that all that needs to be proven to show that d is a gcd

[coral parcel]

I'd say so. It sounded like you were disagreeing.

[forest saddle]

But what I'm asking is does this also prove whether d is the smallest element in S, or that d is the smallest combination ax + by

[coral parcel]

It defines d to be the smallest element, which is (by definition of S) the smallest positive integer combination ax+by.

[forest saddle]

So it doesn't prove that it is the smallest element? My intuition says that because we use this definition in the proof that it must be the case that d is the smallest positive integer combination ax+by

[coral parcel]

It doesn't prove that d is the smallest element in S. It defines d to mean the smallest element.

With that definition there's nothing to prove.

[forest saddle]

So we initially define d to mean the smallest element, and then prove that it is the gcd

And this means the gcd(a,b) is equal to the smallest positive integer combination of ax+by?

[coral parcel]

Yes.

[forest saddle]

Great thanks

[dense glade]

What is an induced relatrion?

[coral parcel]

Needs context.

[dense glade]

never mind I figured it out

thanks

[severe swan]

Am I calculating this correctly?

You flip a fair coin 3 times. Let A be the event that all 3 flips come out Heads. Let B be the event that at least one flip is Heads.
What is p(A|B)?

A: H H H so 1/2 chance of Heads x 1/2 chance Heads x 1/2 chance Heads = 1/8

B: ---- ---- ---- 3 chances for heads since it says at least one flip is Heads

1/2 x 1/2 x 1/2 = 1/8 so B is 1/8

So to calculate p(A|B) = p(A n B) / p(B)

(1/8 x 1/8) / (1/8) = p(A|B) = 1/8

(1/8 x 1/8 would be p(A n B) ) I am not sure if I calculated p(A n B) correctly. If I was calculating p(B|A) then it would be the same correct? p(A n B) / p(A) = (1/8 x 1/8) / (1/8) = 1/8

[dense glade]

Let A be an 8 element subset of {2,3,4...,34}. Prove that there two disjoint non empty subset of A which have the same sum.

I know this screams pigeon hole principle but I can't really figure it out, any hint is appreciated

[bleak void]

How about starting with A = {} and building it up little by little?

[dense glade]

I did

so we want 2 subsets of A, 255 possibility for each

and they have to be disjoint but the sum s the same

I'm just not sure how to construct 2 subsets with the same sum but different elements

[bleak void]

Actually let's start with A = {2, 3} and keep adding elements carefully to prevent two disjoint subsets with the same sum.

A = {2, 3} is fine. Let's increase it to A = {2, 3, 4}. That's also fine. How about A = {2,3,4,5}. Here we are screwed because {2,3} and {5} have the same sum.

How about A = {2,3,4,6}. That also doesn't work. A = {2,3,4,7} has the same problem.

[dense glade]

yes

[bleak void]

A = {2,3,4,9} seems OK.

[bleak void]

How are you getting 3 for B? For example, all these have at least 1 head: HTT, HHT, HHH, HTH.

[severe swan]

You are totally correct, I messed up. Thanks for pointing that out.

[vital dew]

Rezende

[wide vine]

is there specific notation to denote directed vs undirected graphs?

Regarding when you write out the edge as a set

nvm

appears you would use (a,b) vs {a,b} to denote

[cunning locust]

Could somebody help me with this problem?

In 1.3 my answer is A_n = 1.12 \cdot A_n-1 but i'm not sure

[sour arrow]

Ye

[wide vine]

the notes only tell me what c6 and k6 are considered cycle and complete graph respectively. Is there a name for the Q3 and K3,4

Is it really just called "n-dimensional hypercube" graph?

and they didn't seem to give a name for the K3,4 other then denote the notation

like what do I looked up other then K_3,_4 if I want to learn more about that graph

just Kn,m graph?

[sour arrow]

Most graphs won't be named. Q3, at least from a graph theory perspective, has nothing to really differentiate it.

Maybe you're looking for "bipartite"?

[wide vine]

looks like it

https://en.wikipedia.org/wiki/Complete_bipartite_graph

[frosty musk]

How?

[coral parcel]

Take all the subsets, subtract the ones with two or fewer elements.

[frosty musk]

I don't know how to

Like

the ones with two or fewer elements would be C(100, 1) & C(100,2)

Would all the subsets be C(100, 100)? I don't think so

Like, that would be 1

[sour arrow]

C(100,100) would be all of the subsets that have size 100

[frosty musk]

I know

Take all the subsets
?

Summation notation, or what?

[sour arrow]

K

[frosty musk]

Mhm?

I mean, in case of the ^, it's simple

But here, I have no idea

[coral parcel]

How to choose a subset: First choose whether the first element is in your subset or not (2 ways to do this). Then choose whether the second element is in your subset or not (2 ways to do this). Then chose ... and so on, until you choose whether the 100th element is in your subset or not (2 ways to do this). How many ways are there in total to make all these choices?

[coral parcel]

Here you're forgetting the subset with zero elements, by the way.

[frosty musk]

2^100?

[coral parcel]

Yep.

[frosty musk]

Thanks

[wide vine]

with finding the isomorphism of 2 graphs it seems it requires lots of comparsions

and I am struggling a bit with finding the mapping between the vertexes even if the graphs I say are isomorphic

is there an easy way to do this or is it always time consuming and requires a bit of checking

for example this

[coral parcel]

There's no polynomial-time algorithm known for finding an isomorphism in the general case, so you'll need some ad-hoc cleverness.

[wide vine]

bummer :/

I guess easy to count vertex and edges and then start checking each vertex for its degree. Regarding checking if they are isomorphic.

the first 2 steps will I guess will help a lot :v

and at least with finding the function I guess I can start but looking at a vertex that has a unique degree within the graph

[dense glade]

@coral parcel are these isomorphic because I think so but the answer they are not

[cunning locust]

I tried to solve for \sqrt(a_n), but I don't know how to completely remove the square roots

[stray reef]

@dense glade why do you think they are isomorphic? have you constructed an isomorphism between them?

[dense glade]

I thought they were because I was under the impression

that I could connect the 2 edges and mak them cross

but I relaized that in isomorphism I'm not allowed

[stray reef]

so you did not in fact have a mapping from the vertices of one to the vertices of the other

[dense glade]

to disconnect

Yes

[stray reef]

yes, when constructing an isomorphism you cannot just sever an edge from one of its vertices.

[dense glade]

are you good with probability questions

by chance?

I have a question

but it's kind of weird

[stray reef]

...oh boy

i mean let's hear it anyway

[dense glade]

let me screenshot it

[stray reef]

very likely that i'll complain about it being phrased in a weird way or maybe even being underspecified

ok and what are you having trouble with

[dense glade]

it's an application of Bayes' theorem

[stray reef]

this isn't "kind of weird" this reads like a run of the mill bayes theorem question to me

yes

[dense glade]

but

what is the probability of (b)

in this scenario

[stray reef]

what's b?

[dense glade]

P(Observe someone at party | Introvert) =

[stray reef]

is that supposed to be an answer to what i just asked you or not

i hope not

[dense glade]

no

b is the probability they introvert

[stray reef]

in any case P(goes to party | introvert) is not what you're asked to find here

you're asked to find P(introvert | goes to party)

the probability of the person you're looking at being an introvert, given that they're at the party.

[dense glade]

ok

so that would

0.25(0.40)/0.40

or am I off?

I'm just unsure about p(b|a) here

[stray reef]

what are a and b?

are you trying to use some notation without defining it?

[dense glade]

ok so

we agreed on

P(introvert | goes to party)

[stray reef]

yes

[dense glade]

then the probability should be the p(introvert) *pr(party | introvert) / prob(goes to the party)

[stray reef]

what's &?

okay yes

you didn't need to use literally 3 different abbreviations for the word "probability"

[dense glade]

it increases

every term

1 letter

ok but what is the pr of the second 2nd term?

[stray reef]

"the second second term"?

[dense glade]

*pr(party | introvert)

[stray reef]

why did you write the word "second" twice tho

but anyway

[dense glade]

I'm very tired

I have been studying for 16 hours

3 finals

[stray reef]

jesus fuck!

go take a break this INSTANT!!!

[dense glade]

not until I figure this one out

LOL

i can't type

[stray reef]

ok fuck it

but after this you have to take a break

[dense glade]

I will go to bed

[stray reef]

unless you pride yourself on your own burnout which you should not do

[dense glade]

[stray reef]

but anyway

P(partygoer | introvert) = 0.4 as literally stated in the problem

[dense glade]

yep

[dense glade]

wairt sorry

hmm I see

well this simplifies to 0.40

because I used 0.25 as the prior probability

[stray reef]

what was your value for P(partygoer)?

what was that?

i saw you post a message that you then immediately deleted before i could read it

[dense glade]

yeah

this is the one I'm missing actually

the probability of being party goer

would that be

0.40+0.75

[stray reef]

no

you realize that's nonsense right

given that it's literally greater than 1

[dense glade]

yes

why am I struggling with this?

[stray reef]

because you've deliberately burned yourself out with 16 hours of continuous, no-breaks study.

i am sure your parents are so draconian that if they had their way you'd be studying for 25 hours every day.

anyway,

P(partygoer) = P(partygoer|intv)P(intv) + P(partygoer|extv)P(extv)

[dense glade]

ok let me crack the numbers

[dense glade]

does 15% make senses to you?

i think I did it

it's time to finally rest

[stray reef]

no that doesn't make sense either

15% is way too low

it should be between 40% and 75%

,calc (40 + 3*75)/4

[vital dew]

Result:

66.25

[stray reef]

66.25%

[dense glade]

yeah

[dense glade]

would you please

explain where did

the 3*75 come from

[stray reef]

$\frac14 \cdot 0.40 + \frac34 \cdot 0.75$ is what i did

[vital dew]

Ann

[cunning locust]

Any suggestions?

[stray reef]

well it literally says to make a substitution

have you done as you were told by the problem?

[cunning locust]

Honestly I don't know exactly how to make the substitution

$\sqrt(a_n)=b_n$

[vital dew]

Sisyphus

[cunning locust]

what then?

\sqrt(a_n-1) and \sqrt(a_n-2) are different numbers

[dense glade]

are you 100% sure about this? because I swear I'm plugging into the calc and giving me 15%

[stray reef]

@cunning locust first off, \sqrt**{a_n}**

[cunning locust]

yeah, sorry

[stray reef]

second, after the substitution you will in fact have $b_n = b_{n-1} + b_{n-2}$

[vital dew]

Ann

[stray reef]

you're supposed to do it for the whole sequence and not just one term

[stray reef]

take a picture of your calculator with the exact thing you're putting into it

[stray reef]

then why are you claiming that putting 0.40 * 0.25 + 0.75 * 0.75 into your calculator is giving you 0.15?

[cunning locust]

what about the '2' in '2\sqrt{a_n-2}'

[stray reef]

what 2?

$\sqrt{a_{n-2}}$ doesn't have a 2 coefficient attached to it as far as i can tell from your problem

[vital dew]

Ann

[dense glade]

I just followed what you told me and plugged in probabilties

P(partygoer) = P(partygoer|intv)P(intv) + P(partygoer|extv)P(extv)

[cunning locust]

Oh, sorry, wrong ss

[stray reef]

that 2 coefficient is missing here

but if it was meant to be there then sure

it will still be there after the substitution

[cunning locust]

Okay, thnx

[stray reef]

$b_n = b_{n-1} + 2b_{n-2}$

[vital dew]

Ann

[stray reef]

what i am taking issue with is that you made it sound like you were calculating JUST THE DENOMINATOR and not the whole thing, and that calculating JUST THE DENOMINATOR gave you 15%

[dense glade]

ahhh

wait

so

the whole thing is correct then

[stray reef]

,calc 0.25*0.40/0.6625

[vital dew]

Result:

0.15094339622642

[dense glade]

😭

thank god

[stray reef]

you will get about 15%, yes.

not exactly but close enough

[dense glade]

ok thanks a lot

when I graduate tomorrow

I will tell them without ann

it wouldn't have been possible

[cunning locust]

Should I use the same initial conditions after the substitution?

[stray reef]

no, you should recalculate them in terms of b_n

[cunning locust]

Okay

[zenith oyster]

@coral parcel What do you think of this related to the turing machine problem we discussed?

[coral parcel]

Um, if your tapes are finite, then it's definitely not standard Turing machines you're working with, and about everything I said should be ignored ...

[zenith oyster]

Nvm it's infinite

All I've done is wrong I guess

[coral parcel]

It looks like a good argument that essentially every question about finite-space machines is decidable.

[zenith oyster]

Well if the tape is infinite instead, that means I have infinite configurations so in finite time I can hardly conclude if x is on position i

Like I don't see another way this can be reasoned about

[coral parcel]

It is indeed not decidable.

[zenith oyster]

How do I prove it though+

[coral parcel]

Here's a hint for how to use it to decide halting problems. Say you want to decide whether M halts when started on the empty tape. Then modify M such that it moves two spaces each time it would originally have moved one, skipping over the odd-numbered squarea. When/if the original M would have reached a halting state, instead start a loop to write 1 into all the odd squares...

[spring surge]

Are there general properties of functions
which answers if (f ◦ g) ◦ f = f ◦ (g ◦ f )
without using substitution?

[coral parcel]

Function composition is always associative.

[spring surge]

There is no case when its not?

[coral parcel]

No, because f(g(h(x))) is always the same as f(g(h(x))).

[spring surge]

got it. thanks.

[stray reef]

but tropo what if you reject reflexivity of equality

[coral parcel]

Then your immortal soul is forfeit anyway.

[zenith oyster]

So I've been looking at my material and I'm allowed to use reductions from undecidable problems. I know halting on empty input is undecidable (or even just traditional halting problem but I'm guessing it's easier the more similar it is to my problem). So if I understand correctly, if I can reduce that problem to my problem then I'm good. Correct?

[coral parcel]

Yes.

[zenith oyster]

thanks

[zenith oyster]

I've been thinking about it a bit, is the idea that as the memory tape is infinite, the odd/even number of cells are infinite as well therefore writing 1 in every odd cell is an infinite operation?

[coral parcel]

The idea was just that you could ask your MemoryWatch decider whether cell 1 ever gets set to 1. Writing 1 to all the odd cells was just so the modified machine won't have to keep track of how to find cell 1 when it's ready to write something there.

[zenith oyster]

So do you mean that when M would have halted in accept state, I make M' write x to position i kind of? Thus, if M originally would go into a loop, M' would not write x to position i? Something like this?

[coral parcel]

Yes.

Remember that when reducing TO MemoryWatch, you get to choose what x and i will be.

[zenith oyster]

smart

[muted gate]

guys I'm trying to prove something regarding connectivity and just wanted to check if the following makes sense if I want to define a component of a graph $G = (V, E)$ recursively. \
Let $C_{n} \subseteq G$ denote a component of $G$, if $G$ has $n$ vertices. Then: \
$G = \bigcup_{k = 1}^{n} C_{k} = C_{1} \cup C_{2} \cup C_{3} \cup \dots \cup C_{n}$, then we define any component $C_{n}$ recursively such that: \

$C_{1} = G$ \
$C_{2} = G \setminus C_{1}$ \
$C_{3} = G \setminus C_{1} \cup C_{2}$ \
$\vdots$ \
$C_{n} = G \setminus C_{n-2} \cup C_{n - 1}$\

[vital dew]

texaspb

[muted gate]

does this make sense or is it not possible for me to make such assumptions?

[stray reef]

...no, none of this makes any sense

[muted gate]

ok

care to explain?

my guess is that it's not possible to define any component like this right

[stray reef]

well i mean like

you are defining the first component to be the entire graph

and the second to be... empty?

[muted gate]

hmmm

[stray reef]

and the third will also end up empty once you put in the missing pair of parentheses

the only thing that makes any sense here is the statement that G equals the union of its own connected components

[muted gate]

my thought process was that for a graph with n=1 vertices, C_{1} is obviously the entire graph, and then I tried to extend this by increasing the amount of vertices. but now that I'm rethinking of that, it doesn't make much sense

because when I increase the amount of vertices

it starts to get so tricky

😦

[coral parcel]

It sounds like you're using "component" in an unusual way. Why do you find it is obvious that one of the components is the entire graph? That sounds downright false to me.

[muted gate]

a component has to be a subgraph of the original graph?

can it not be the entire graph?

like

[coral parcel]

The entire graph is only a component if the graph is connected.

[stray reef]

if your graph is connected then it consists of one single connected component equal to the entire graph

^

[muted gate]

aaaaaah ok

[stray reef]

in fact tropo and i just said two halves of an iff statement

[coral parcel]

Heh.

[muted gate]

a graph has a single connected component iff it is connected?

[coral parcel]

Correct.

[stray reef]

yes

[muted gate]

okay guys, thanks!

I'll review these concepts they're still pretty obscure in my mind

is there any way to do what I was trying to do?

if you guys even get what I was trying to do...

[stray reef]

we don't

[muted gate]

alright I don't blame you two

[wide vine]

can someone explain to be what they are asking exactly "Prove that for any k, the property of having C_k as a subgraph is preserved under isomorphism."

C_k refers to a graph cycle?

and k would be just some integer value >=3?

[bleak void]

I suppose it's about: https://mathworld.wolfram.com/CycleGraph.html

[wide vine]

Sure but I am just confused what it is even asking

say k = 3

then you have C_3

I mean you could call C_3 a subgraph of itself but I don't get why they are asking about a "sub graph"

[stray reef]

you're asked to verify that if G contains a cycle of length k and G' is isomorphic to G then G' also contains a cycle of length k

which should be kind of obvious

[wide vine]

Ohhhh

I thought they were saying the graph was a cycle

[stray reef]

(G and G' are graphs)

[wide vine]

Okay I see.