discrete-math

[weary tiger]

way out of context

forget what i said

[weary tiger]

i have a genuine hatred for proof

on another topic, I have to simplify an expression using tautologies to reach a conclusion of F, can't get past 3 steps and I'm just scuffed.

[digital gyro]

how is discrete math defined

[stray reef]

very loosely

set theory, logic, combinatorics, maybe even some shit with sequences and recurrence relations

all sometimes gets called discrete math

[stray reef]

you have a genuine hatred for formalized bureaucratic proof

by the looks of it, anyway

[weary tiger]

I got no clue what that means

[sand hamlet]

How does math relate to bureaucracy

Enlighten me pls

[weary tiger]

ekks dee

[junior rivet]

p and (p or q) = p (p or q) and p = p

is that correct?

[simple nimbus]

Does anybody know the answer to these?

[weary tiger]

yeah

[simple nimbus]

Would you be able to help me answer them please?

[coral parcel]

If you present your answers we can help you figure out if they are correct, and if not then what is wrong with them.

But you shouldn't expect to just post a picture of your homework and then someone will do it for you.

[simple nimbus]

Okay makes sense

[severe swan]

I am learning converting decimals numbers to binary and binary to decimal numbers. I tried to do a problem where I had to convert 46 base 10 to binary. I got 10111 which is 23 and not 46. To get 46 it would be 101110. When I did the math I had 3 left over so would that make the last digit a 0? So then it would be 10111 with 3 left over being a 0 so the answer is 101110? Did I mess up somewhere?

[weary tiger]

32 16 8 2 1 ?

where's the 4

[severe swan]

I completely forgot the 4. That was the issue. Thanks

[hollow karma]

prove that we can separate the edges of a $K_{p^2}$ graph into $K_p$ subgraphs where p is a prime number

[vital dew]

AeroBennu

[coral parcel]

Label the nodes of K_{p_2} with elements of the group C_p×C_p. Consider all cosets of order-p subgroups.

[crude pelican]

Let $A$, $B$ and $C$ be sets such that $\emptyset \neq A \cap B \subseteq C$. Then which of the following is not true? \
(a) $B \cap C \neq \emptyset$ \
(b) $(C \cup A) \cap (C \cup B)=C$ \
(c) If $(A-C) \subseteq B$, then $A \subseteq B$ \
(d) If $(A-B) \subseteq C$, then $A \subseteq C$

[vital dew]

LazyKnight

[hard bone]

Can you help me idk the answer and how I solve

[digital phoenix]

I'll get onto the explanation why

[digital phoenix]

I should also state this solution was for part 2

[hearty elbow]

what grows faster

n or log(n)^2

I know that log(n) is slower than n

but what about the square of log(n)

[coral parcel]

Squaring doesn't help the logarithm.

[hearty elbow]

okay thats what i thought

but whats the reasoning behind it?

I havent done Big-O proofs in a while and i forgot about it

Do you have to use a squeeze theorem or something?

[coral parcel]

Let's look at $\lim_{n\to\infty} \frac{n}{\log(n)^2}$.

[vital dew]

Troposphere

[coral parcel]

First we switch vatiable to $x=\sqrt n$. That gives us $\lim_{x\to\infty} \frac{x^2}{4\log(x)^2}$.

[vital dew]

Troposphere

[coral parcel]

Then we can take the square root of the fraction but immediately square it back: $$\cdots = \lim_{x\to\infty} \left(\frac{x}{2\log(x)}\right)^2.$$
But we know that $\frac{x}{2\log x}$ goes to infinity, so its square does likewise.

[vital dew]

Troposphere

[hearty elbow]

shouldnt that be log(sqrt(x))?

[coral parcel]

No, since log(n) = log(x²) = 2log(x).

[hearty elbow]

log(x^2) = log(x) * log(x) ?

oh wait

im dumb

yeah okay

where does the 4 come from?

[coral parcel]

Since log(n) = 2log(x), the original log²(n) becomes 4log²(x).

[hearty elbow]

ahhh

ty

[coral parcel]

By similar reasoning we can show that n^a eventually grows faster than log(n)^b for any positive a and b, even n^0.01 versus log(n)^100.

(even though that particular pair doesn't break even until somewhere between n=2^100,000 and n=2^1,000,000).

[harsh forum]

Hey, we think this proof is impossible, they ask us to do a rigorous proof but it doesn't seem to work well backward

[cerulean wind]

what do you mean backward? this proof is not impossible. B intersect C is a subset of B and a subset of C…

your set is A = {1,2,3,4}. the equivalence relation is E = {(1,1), (2,2), (3,1), (3,2), (4,2)}. check that for x,y,z in A, if xEy and yEz, then xEz.

[pale epoch]

yes

but the explanation is "this is transitive because there is no counterexample"

you just have to try all possibilities

(though there arent much arrows you can "chain together" in the first place, its pretty much only loops you can "chain to" any arrow, and those dont break transitivity)

[zenith valley]

Sorry for the late reply. The book is The William Lowell Putnam Mathematical Competition 2001 - 2016.

[cosmic valve]

Guys is Game Theory part of discrete math

[coral parcel]

"Discrete math" is not really a crisply-defined area of mathematics. If you have a question of game theory you'd like to discuss, this channel or #combinatorial-structures would probably be the best channels to try in.

Perhaps think of the existence of a cycle a-b-c-d-a as "Vertices a and c have at least two neighbors in common".

Instead of what I said? Perhaps.

I don't particularly see how, though.

[spring surge]

There are N points on a circle. How many N-sided polygons (not necessarily convex) can be formed with these points as vertices? How to think about those kinda problems?

[coral parcel]

Your polygons don't have to be convex, but can they self-intersect?

[spring surge]

yes

[coral parcel]

Can the same vertex be used twice? E.g. for N=6, will 1-2-3-1-4-5-1 be a valid solution?

Sounds good.

[spring surge]

Yes

[coral parcel]

Would 1-2-3-4-3-5-1 also be a solution, despite the angle at 4 being degenerate?

[spring surge]

It's a yes. Because the polygon is formed still.

[coral parcel]

But 1-2-3-3-4-5-1 wouldn't, I suppose.

Huh, I thought you already had that.

There are 2r-2 vertices that are not your chosen ones. Each chosen vertex has r of them as neighbors ...

[spring surge]

the author gave the answer which is n!/(2n)

wanted to hear different angles how to approach these kind of problems

[coral parcel]

That's the answer if vertices cannot be used twice. Which is much easier.

[spring surge]

got it

[coral parcel]

It's a bit confusingly worded, especially with the "a or c". How about choosing one of them and say:

There are r-2 vertices that are neither a nor c nor adjacent to a. This implies that at least 2 of the r neighbors of c are also adjacent to a.

[coral parcel]

I would say: No two vertices of the K50 subgraph can be neighbors in the cycle, so the cycle is at least 100 vertices long. On the other hand, if the cycle does have 100 vertices, we can pick every other vertex, and subgraph they induce in the complement will then be a K50.

[coral parcel]

Um, could you stop pinging me with new problems, please?

[tidal tulip]

could someone check my proof

suppose f: X -> Y is a function and let A, B subset X. prove if A subset B then f[A] subset f[B] where f[A], f[B] denotes the image of A, B respectively

proof: pick y in f[A] then y in Y such that y=f(a) for some a in A

since f[B] is a set that contains all elements in Y that are mapped from every element in B we know that f(a) is in f[B] due to A subset B, since every element a in A, a in B.

thus we see that f[A] subset f[B]

[pale epoch]

ye

[tidal tulip]

sweet, thanks!

[spring surge]

What is the math word to define relashion between two permutation when they make the same cycle? like 1 2 3 4 and 2 3 4 1 ?

[pale epoch]

"equality"

[spring surge]

good. thanks.

[plucky canopy]

Im having trouble with this coefficient extraction. What do I do once I have a product of two sums?

[swift idol]

Hi, I'm not sure where to ask this question but. I am writing a small recursive function to generate permutations of the elements of an array with size n. But I've been reading about the random shuffles and I am wondering whether I can just run the shuffle function some number of times >= to n! o get the same result? After googling for a bit, it seems like a limitation is that pseudo-random number generator has a limited number of internal states. Can anyone elaborate more on this limitation? Or maybe point to be a good article on PRNG internal states? Is there an n too large that a PRNG would not allow me to compute permutations using something like fisher-yates shuffle?

[coral parcel]

You can always get permutations, but if n is large compared to the internal state size, you might not be able to get every possible permutation out. Even so, it is kinda hard to imagine a scenario where that would create a problem in practice.

[maiden drift]

If K is a compact convex set in the plane w nonempty interior , then there exists a line which bisects K into two parts of equal area and perimeter. This seems like clear visually, but how do I go about showing this

Like we can obviously get the area part to work if we take any line intersecting k and rotating that line

since the area changes continuously on each half space of the line as we rotate the line

[coral parcel]

Parameterize the perimeter of K by arc length as p:[0,L] -> R^2.
Consider how the line between p(0) and p(L/2) splits the area of K. If that line splits K into equal-area parts you're done.
Otherwise, sucessively consider the lines from p(t) to p(L/2 + t) as t grows from 0 to L/2. At the end the difference between the area to the left and the right of the line has changed sign. At some point it must have passed 0.

[maiden drift]

So visually what is happening in what you described -- it seems like the area part of your idea is similar to this rotation idea, but I don't see geometrically what the perimeter part is doing

[coral parcel]

Since I've specifying parameterizing by arc length, the perimeters of the two parts will be equal by construction no matter what t is.

[opaque mortar]

Good evening, would anyone be able to help me with a combinatorics question?

[shadow geyser]

Is anyone help to help me with linear orderings by any chance?

I'm a little bit confused on something

[wide vine]

∃x : ∀y ≥ x : P(y) In the context of limits, these terms refer to some (unspecified, even unknown) point at which a phenomenon prevails as the limit is approached. A statement such as that predicate P holds for sufficiently large values, can be expressed in more formal notation by ∃x : ∀y ≥ x : P(y). See also eventually.

how do I read the stuff in quotes

I understand it says There exist some x and for all y

but I am not sure how I parse it all together

Do the : have a specific meaning here

do the ":" denote "such that"

[last flicker]

yes

is the fact that they mean such that enough to answer your question or do you need more explanation

[wide vine]

I understand it but it really doesn't make sense just replacing it with "such that". There exist some x "such that" forall y >= x such that P(y). I would read it more like There exist some x such that for all y >= x p(y) is true

at least the part after the for all y >= x

but I get it

I think

[last flicker]

Your reading of it is correct. I get why having the second colon mean "such that" is confusing, reading it again the second colon is odd lol. usually you'd see a comma or something in its place. Given the surrounding text explaining what it means though, There exists some x such that for all y >= x p(y) is true is a good reading of it

the colon for such that is usually seen with an existential quantifier(∃) or in set builder notation, not with a universal quantifier(∀)

[drowsy marsh]

Have I formulated this correctly?

I'm not sure about the objective function.

<@&286206848099549185>

since I didn't include any x variables, I'm unsure if the objective function is correct or not, as it looks weird

but in the question it says it just want to maximise Time cycling and running

doesnt mention swimming

[crimson timber]

the objective doesn't have to mention all of the variables

obviously, if a variable doesn't participate in the problem at all you should just drop it as it'll be completely free

[drowsy marsh]

Ah ok wicked, so does it look like I formulated it properly? because next part is initial tableu of two-stage simplex and I don't want to start it with an incorrect part a

[crimson timber]

but in this problem, x (time spent swimming) is not completely free because it participates in at least some constraints

your constraints appears at first glance to me to be correct

[drowsy marsh]

I see, so are you saying I need to include it in my objective function?

[crimson timber]

no, it's sufficient that it appears in at least one constraint, which it does

[drowsy marsh]

ah ok cool, thanks.

and now for the tableau 🥱

[crimson timber]

if it didn't appear in any constraints, you'd get a singular constraint matrix, which would be problematic. bt you can fix that by deleting the variable from the problem. but that's not the caes here, just providing a practice note.

[drowsy marsh]

oh ok cool, cheers.

[crimson timber]

these constraints appear sufficient to at least guarantee a bounded solution

[drowsy marsh]

ok cool

thanks for your help

[crimson timber]

np

[drowsy marsh]

u can see on the bottom what I've done

I have 2 artificial variables but in the table provided there is only 1, so what have I done wrong?

[crimson timber]

oh, man i haven't done one of these by hand in decades

oh, slack variables, right

ok, three slack, that appears correct

[drowsy marsh]

yh its the artificials which are apparently wrong

[crimson timber]

it's been years and i don't want to give yuo bad advice, so i'm reading through the formal algorithym again, give me a moment

[drowsy marsh]

np, i appreciate it

[drowsy marsh]

I guess I could swap the 3x >= inequality?

and make it 2y + 2z - 3x <= 0

and then I wouldn't need the artificial variable?

[crimson timber]

i'm trying to find a clear definition of canonical form thta is actually written in words i understand

i use LPs all the time, but i usually just use software because the programs i'm dealing with have hundreds or thousands of variables and doing them by hand is...

[drowsy marsh]

haha yeah understandable

[drowsy marsh]

are u a data scientist?

[crimson timber]

not really, a lot of the time this shows up in gaming contexts actually

[drowsy marsh]

ah ok, what's your job?

[crimson timber]

parent

[drowsy marsh]

I see

where does it come up in gasmes?

games*

[crimson timber]

finding an optimal strategy, proving one exists, proving that the game is exploitable or not exploitable, stuff like that

game design more than game playing

also writing ais to play games

Bring the constraints into equality form. For each constraint in which the slack
variable and the right-hand side have opposite signs, or in which there is no slack
variable, add a new artificial variable that has the same sign as the right-hand
side.

i think the issue is that you didn't canonicalize x+z >= 28 correctly

no, sorry, that one is right, it's the other that's wrong

you don't need an artificial variable in the second equation because its RHS is already 0

so only the third equation requires an artificial variable to canonicalize it

[drowsy marsh]

Ah ok thanks

[weary tiger]

A gambler played the following game with a friend. The gambler bet half the money in his pocket on the toss of a coin; he won on heads and lost on tails. The coin was tossed and the money handed over. The game was repeated, each time for half the money held by the gambler. At the end, the number of times the gambler lost was equal to the number of times he won. Did he gain, lose, or break even?

I thought that $\mathbf{E} = \frac{1}{2} \cdot \frac{x}{2} - \frac{1}{2}\cdot \frac{x}{2} = 0$

Where x is the amount of money he starts with. Why is that wrong?

[vital dew]

n/c

[stray reef]

that's for only one round

starting with x and playing the game for one round the gambler ends up with either x/2 or 3x/2 in bank

so your issue is probably that you did not make it clear to yourself what your E really represents @weary tiger

||also you don't even need to do any expected value shit here||

[weary tiger]

I understand that but what if I wanted to?

[stray reef]

you want to shoehorn some probabilistic shit into this?

[weary tiger]

I don't know what you mean by shoehorn, I just want to apply the definition of expected value but it is proving to be difficult

[stray reef]

before you apply the definition of expected value you need to make it clear to yourself what you're taking the expected value of.

[weary tiger]

So I understand that's a single round, but it seems kind of impossible to go from there because we need casework depending on whether he loses or wins

[stray reef]

i mean let's be honest

the change in the gambler's bank is multiplicative, not additive.

it is multiplied by a random variable which takes values 1/2 or 3/2 with 50% probability each

though calculating the expected value of the product of n independent copies of this will give you 1 [since E(XY) = E(X)E(Y) when X and Y are independent], which isn't very informative.

[weary tiger]

So there's no easy way to use expected value here?

[stray reef]

yes, i would say there isn't.

i hope there is nobody (not even yourself) holding you at gunpoint to solve this problem "using expected value" or else.

[weary tiger]

I was just checking to make sure.

[stray reef]

anyway just to be clear the gambler's final bank is (3/4)^k times his starting bank, where 2k is the length of the game (k wins, k losses)

[weary tiger]

I know, thank you.

[coral parcel]

One subtle point here is that if we don't have the assumption of "exactly as many wins as losses" but instead take the expected value over all possible sequences of wins and losses, then the gambler's expected pocket at the end is exactly what he started with.

There are some (rather unlikely) sequences with a lots of wins where you end up very rich which pull the average upwards from the median. There are other sequences with a lot of losses which are exactly as unlikely, but they don't pull the average downwards to the same degree, because those unlikely additional losses don't have much of a dollar value.

So the scenario serves as an illustration of a case where the formal concept "expected value" is quite misleading and not even close to the most likely range of outcomes.

[main cargo]

New to equivalence relations and classes here, but I was wondering if it is a good practice for when two objects are in (equivelance) relation to each other, to consider them as "equal" but in a different context/world . For example, 1 = 6 mod 5 , so 1 and 5 are equal but in this context. Or is this generally bad

[pale epoch]

this is kind of the point

you forget information by treating two different objects as the same up to something

(in this case "up to" divisibility by 5)

[main cargo]

Oooh yes, sorry I'm quite new to this stuff and wasn't super sure

But thank you for your reply!

[pale epoch]

i mean you figured out decent intuition for it yourself, so thats good

[main cargo]

Thank you!

[crude mango]

I'd just be careful with calling it equality

Because it's not equality, it's some other equivalence relation

If 2 lines are parallel and non-intersecting, we don't say they're the same line. We just say they're parallel

So you don't say 1=6, you say 1=6 (mod 5). I'm pretty sure you'd generally use a different symbol in place of the equals (like an equals sign but with 3 lines) but idk the latex for it or even what it's called

In my head it's always been "threequals"

But you're right, under the equivalence relation of mod 5, 1 and 6 are identical

[coral parcel]

$\equiv$

[vital dew]

Troposphere

[crude mango]

Latex symbol names make so much sense but only after you learn what they are

Yeah it's that one

$1\equiv 6\equiv 11\equiv -4$ (mod 5)

[vital dew]

hiiistrex

[lyric osprey]

in the proof, where does the x^2 >= 0 abd y^2 >= 0 come from

and how do they get the y<= -2 or y>= 2

[lone raft]

x^2 >= 0 and y^2 >= 0 comes from squaring a number is always non negative. There are saying any integer y <= -2, it follows y^2 >= 4, hence y cannot satisfies that equation since 5y^2 >= 20, same for the other case. You can show If a <= b < 0 then a^2 >= b^2. It basically says if a solution exist, it must be -2 < y < 2.

[lyric osprey]

if you were to do that in terms of x would it be -2, -1, 0, 1, 2,?

since 2(3)^2 would be greater than 14

with 2 included since 2(2)^2 would be less than 14

oh yeah when they do 5y^2 >= 20, where does the x go

it seems to just disappear from the equation

[lone raft]

Do you understand if 5y^2 >= 20, then it not possible 2x^2 + 5y^2 = 20. For the equation to hold, it must be -2 < y < 2. If we were to do it with x, we notice if x <= -3(or 3), then x^2 >= 9 then 2x^2 >= 18 which would not satisfy that equation. So if a solution exist then it must be -3 < x < 3. Observe if we had said if x <= -2, then x^2 >= 4 hence 2x^2 >= 8. So it is possible the equation still holds.

We are eliminating cases for y.

After that we went through each remaining case for y, to check if the equation holds.

[lyric osprey]

so when we do problems like these then most of the time we want to solve for y?

[lone raft]

We are not solving for y, we are trying to find the bounds for x or y, which if a solution exist then it must be within those bounds. Doing that reduces the problem to checking if each integer in those bounds satisfies the equation(hence equation reduces to a single variable).

Does this make sense now?

[lyric osprey]

kind of

[lone raft]

Which part are you confused at?

[lyric osprey]

im still confused at why we can only find the bounds for y and not for x

[lone raft]

We can do it for both, it just it doesn’t matter then since doing it for one reduces the equation above to several cases which we are only dealing with one variable in the equation.

[lyric osprey]

ohh i see now

[lone raft]

In fact it they do this for both when doing the cases.

That is how they choose x = 0, 1, -1, 2, -2.

[lyric osprey]

kk ty

[silent cave]

is contrapositive of converse always inverse ?

[ember obsidian]

@silent cave yes

[sleek loom]

Is this identity correct? The book I’m studying for asks to prove it, but doesn’t this counter example disprove it?
b=5, a=b+5k =5, 10, 15, 20…, x=3
bx = 15, ax=bx+5kx = 15, 30, 45 which does not fit the definition so (ax, bx) is not in R

R is an equivalence relation over Z where K is any whole number, x is any whole number

[severe swan]

If I am doing binary addition and am adding 1111 + 110101 then would it matter if I put the answer as

0100100 instead of 100100 because they are the same number. Is there a big difference between having the 0 at the front or not having it?

[rigid oriole]

1 + 1 = 02

This isn't false.

It is up to you really.

[severe swan]

So 0100100 is the same as 100100 correct?

[sleek loom]

Yes

[severe swan]

Thank you

[coral parcel]

The result should be 1000100 (sixty-eight) rather than 100100 (thirty-six), though.

[undone ibex]

Hi, I need help with this. What should a and b be in p(a|b)?

[peak grail]

Does master theorem apply in such questions?

I saw a solution where It was applied where f(n) = Nlog(n)

[cold latch]

Does anyone have an idea on how to complete the last question (rd^-1)?

[native sable]

well, do you know what the inverse of a relation is?

[weary tiger]

I have to write a proof for that. But I'm confused as to what I'm supposed to prove. Isn't that just {...,-47, 0, 47, 94}. Can someone explain it to me

[lone raft]

The proof is showing those two sets are equal, I am assuming.

[weary tiger]

what two sets? isn't the whole thing just one set?

[lone raft]

The Z and the one with 33a + 14b.

Show does two sets are equal.

[pale epoch]

how did you get that the RHS is "just {...,-47, 0, 47, 94}"

[lone raft]

Do you know what it means two set A and B are equal?

[weary tiger]

integers(Z) = ..,-1,0,1,2 etc

I pluged them in

[pale epoch]

you plug what into what

[weary tiger]

I pluged in integer values into the 33a and 14b to get {...,-47,0,47,97}

[pale epoch]

do you think a and b have to be the same?

they do not

so i have no idea what the ... is supposed to signify

[lone raft]

Showing A <= B and B <= A, where <= denotes subset.

[rigid oriole]

(just use 'sub' in plaintext)

[heavy tinsel]

If 2 graphs have the same degree sequence, does it follow that they are isomorphic ?

[pale epoch]

no

[heavy tinsel]

yeah, I think I found a counter example nvm wasnt a counter example

[weary tiger]

What does it mean to prove something using definitions of even and odd numbers? I answered it by saying "A number is even if it is divisible by 2 without any remainder, and it is odd if it returns a remainder." and "n = 2k is even and n=2k + 1 is odd." Apparently, she marked both wrong.

[pale epoch]

post the whole question

[pale epoch]

there are a few ways to think of one

[pale epoch]

wikipedia has a nice example

[pale epoch]

you didnt do the exercise then?
you just wrote what odd and even means

[weary tiger]

what exercise?

[pale epoch]

the proposition 1 in your picture

[weary tiger]

I solved the proof. She just took off points for not using the "definition of odd and even"

[pale epoch]

then probably post your solution

or just ask your professor to clarify

[amber hill]

contradiction tho, assume a is even then a+1, a-1 are both odd

odd times odd = odd

so contradiction

:/

[cold latch]

How come, lets say, if two homogeneous relations being Ra and Rb are transitive then Ra ∩Rb is also transitive?

[native sable]

yes, though I'm not sure how that relates to R_d^-1

[weary tiger]

Does anyone know how I can use the pigeonhole principle here? like, how to start

[hoary cloak]

i could think of something

try to set the points as far as you can one from another

do it with 9 points, try to fit in the 10th one

[distant bobcat]

If a simple graph G has more than one spanning tree then G cannot be a tree right? If each spanning tree provides a unique path between all vertices then we have found more than one unique path for each pair of vertices of G, s.t it cannot be a tree. Thats what I am thinking anyways

[heavy tinsel]

I think pythagorean Theorem might also be helpful once you do what Adazak said

[hoary cloak]

that is correct. would be a nice exercise for you to try and prove that! shouldn't be that difficult

[distant bobcat]

@hoary cloak well we can assume by contradiction that G is a tree with two spanning trees which leads to a contradiction since we end up with more than one path between each pair of vertices which is not allowed in a tree.

[hoary cloak]

i mean yeah i would add that two distinct paths between two vertices form a cycle and by definition trees do not have cycles just for the sake of extra rigor

[weary tiger]

thanks for the help. I should be able to figure rest of it out

when writing proofs, Can I assume that unit square is 1/3 by 1/3? or is that not allowed?

[hoary cloak]

no because it is not necessarily 1/3

you can call a unit a

and half of it a/2

[hoary cloak]

this won't set you back in this particular question but in general assigning constant values randomly can get you into pitfalls

[distant bobcat]

btw is a 3-connected graph the same thing as a 3-regular graph? I take it 3-connected just means that each vertex is connected to three other vertices.

[hoary cloak]

no

what you described is 3-regular

3-connected means that you need to remove at least 3 arbitrary vertices to make it disconnected

[distant bobcat]

ahh, yes that makes sense. So in a way its a measure of how connected a graph is ?

[hoary cloak]

K_6 is not 3-regular but it is 3-connected

[hoary cloak]

think of it as how much the graph can endure getting its vertices removed by an attacker before getting disconnected, if that makes sense

important to notice that is it is k-connected, any k-1 vertices removed will not disconnect it

[distant bobcat]

right, thanks

[hoary cloak]

np!

[weary tiger]

For nested existential quantifiers can x and y be the same value?

Exp: ExEyP(x-y=1) - can x and y be the same value?

[native sable]

existentially bound variables can take on the same value, yes

[weary tiger]

Ok thank you!

[oak notch]

Hey guys, what does the (n 2) mean in the paragraph?

[sleek loom]

Google “n choose k”

[silent cave]

how can I find number of terms in expansion of
(w + x + y + z)^10

[cerulean wind]

refer to the multi nominal theorem and the number of weak compositions of an integer

[oak notch]

What allows him to equate (from < to =) an equation? Is there a rule for changing it?

[hoary cloak]

idk if i understood it correctly just from this image, but he's calculating big O notation which is an upper bound

[desert edge]

Can someone help me understand the difference in proper subset and subset?

if A is a subset of B, every element of A is in B.
But in a proper subset, the difference is every element of B is not in A

Does this mean in a subset, every element of B is also in A?

As in A is a subset of B and B is a subset of A?

[austere cedar]

A is a subset of B, if every element from A is in B, yes. But A is a proper subset of B, if A is a subset of B and there is at least one element in B, which is not in A. So A is a proper subset of B, if A is a subset of B and $A \neq B$

[vital dew]

Alexander42

[desert edge]

What does that say about a subset?
That if A is a subset of B, then B is a subset of A?

[cerulean wind]

no. if A is a subset of B, it allows for the possibility that A = B. if you want to emphasize that this is not the case, then one says that A is a proper subset of B.

for example, (-1,1) is a subset of R and a proper subset of R. every set is a subset of itself and no set is a proper subset of itself

[tidal tulip]

professor wrote ~ in R^2 is an equivalence relation

(x1,y1) ~ (x2,y2) if

y1-y2 = 2(x1-x2)

they said write the set of
equivalence classes

for C(0,0)

they said that set is

C(0,0) = {(k,2k) : k in R}

how did they calculate that?

[pale epoch]

plug x1 = 0 = y1 into the definition

you get -y2 = -2x2

which is just that

the second coordinate is twice the first

[tidal tulip]

how did they calculate x2 ? plug y=2x2 back into the original equation?

let’s say you wanted to calculate C(1,0) then is that

0-y2 = 2(1-x2)
-y2 = 2-2x2
y2 = 2x2 - 2

?

[pale epoch]

looks correct to me, yes

so all (x2, y2) that satisfy this are in C(1, 0)

[tidal tulip]

and to solve for x2:
0-(2x2 - 2) = 2(1-x2)
-2x2 + 2 = 2 - 2x2
-2x2 = -2x2
x2 = x2

so C(1,0) = { (x2, 2x2 - 2) : x2 in R }

is that how you’d calculate it

[pale epoch]

i dont get what your "solving" does

but C(1,0) = { (x2, 2x2 - 2) : x2 in R } already follows from what you did above

[tidal tulip]

to write out the equivalence class

[pale epoch]

i dont see how this calculates anything

or what you even did

[tidal tulip]

C(1,0) = { (x2, 2x2 - 2) : x2 in R }

is the set of all elements in C(1,0) no?

[pale epoch]

yes

[pale epoch]

this is what you did here

[tidal tulip]

the example in class was to write that set but they didn’t show their work

[pale epoch]

i dont get this

[tidal tulip]

so i was wondering if i did C(1,0) correctly to understand

that’s plugging y2=x2 into the equation

how did they calculate x2

[pale epoch]

calculate x2?

[tidal tulip]

yes you want to write tuples

[pale epoch]

you just need the relationship between x2 and y2 to write down the thing

which is what you did
C(1,0) = { (x2, 2x2 - 2) : x2 in R }

i dont see how you used the other thing at all

[tidal tulip]

then is my method for solving x2 wrong? i don’t understand how to find x2

[pale epoch]

i dont know what finding x2 entails

[pale epoch]

here you calculated what must be true for (x2, y2) to be in C(1, 0)

and you showed that y2 = 2x2-2

[tidal tulip]

then how can you just write x2 in the __ here (___, 2x2 - 2)

without solving for x2

[pale epoch]

so all tuples (x2, 2x2-2) are in C(1, 0)

again i dont know what solving for x2 means

[tidal tulip]

you have an equation

you solve for y2

[pale epoch]

your solution is x2 = x2, which is not helpful

[tidal tulip]

you should also solve for x2 i assume

i see how to solve for y2

i don’t see how to find x2

[pale epoch]

you can only find one

you have an equation in 2 unknowns

but you only have 1 equation

you can either write x2 in terms of y2 or y2 in terms of x2

it doesnt matter what you do

[tidal tulip]

oh i see

which of the two did i do then

[pale epoch]

you could also write C(1,0) = { (x2, 2x2 - 2) : x2 in R } = { (y2/2+1, y2) : y2 in R }

[tidal tulip]

so the general procedure is the solve for say y2 and then write (x2, blank) and then write y2 in the blank

[pale epoch]

yes

[tidal tulip]

ok i see

[pale epoch]

you can do it the other way around if that looks better

[tidal tulip]

i guess that’s solving for y2 in terms of x2

[pale epoch]

in this case i think it doesnt, because you have to divide the y2 by 2

[tidal tulip]

ok i see

ty

[empty sequoia]

Hello, can someone give me a hint on how I can write the formal proof for every n>=1, a_n+1 <= a_n?

I know that this sequence is bounded below by sqrt 2, and intuitively I know that it's decreasing because we are just continuously dividing as n approaches infinity (of the sequence)

I'm just stuck on how I can actually write this formally

[native sable]

how about a proof by induction?

[empty sequoia]

oh yes, sorry about that I forgot to mention that I needed help with the proof by induction, I started by writing down the base case already and I wrote let n>=1, assume a_k <= a_k-1 for every k = 1, ..., n

I'm just stuck now because I don't know how to show that for a_n+1, this would hold true

[proven silo]

Use the definition of a_{k+1}?

Together with induction hypothesis

[empty sequoia]

something like this?

[sleek loom]

Why is there an equality there if you're trying to prove an inequality?

[proven silo]

He has an inequality at the end?

[empty sequoia]

i was thinking that since it's smaller or equal, I can set it a_k+1 = a_k-1/2 + 1/a_k-1

[sleek loom]

Kinda confusing since a_(k-1) is not equal the RHS expression in the last line

[proven silo]

Oh whoops

[sleek loom]

I might be wrong but I think it's less confusing to use an inequality sign and then replace the terms

And then show that the inequality holds

[empty sequoia]

like on the last line?

a_k+1 <= (a_k-1)/2 + 1/(a_k-1) <= a_k?

[proven silo]

Your 3rd line equality is wrong, you should then plug in a_{k-1}/2 instead of a_k

[empty sequoia]

the equality where i wrote a_k = a_k-1/2 + ... ?

[proven silo]

No that is 2nd line

[sleek loom]

Yeah, what I'm saying is that the left side is not equal to the right side in the last line so there shouldnt be an equal sign

[empty sequoia]

okay yeah i see what you mean

it should look more like this

[sleek loom]

On what basis are you saying a_k+1 is smaller than a_k tho? That's not your assumption

[empty sequoia]

I think I just don't get that part, I know that a_k <= a_k-1

and i tried using that into the first equality where i wrote a_k+1 = a_k /2 + ...

[sleek loom]

You didn't really use it, the first 2 lines are basically just the given equality for a_n

What you want to do is make an assumption for some inequality, and then prove another inequality, such that if the assumption is true, the inequality you proved would be true as well

Try to prove that a_k+1 >= a_k after making your assumption

By writing that exact statement down

And then manipulating the inequality as if it were true

Until you reach something that is definitely true

[empty sequoia]

so writing down a_k+1 <= a_k
and manipulating this using the fact that a_k <= a_k-1
is that what you mean?

or the other way around

[sleek loom]

I do mean that

[empty sequoia]

okay ill try that out thank you

[sleek loom]

You just want to write down the statement I said and prove that it's true, and you'll probably be able to do that using the assumption

Sure

I did solve this if you want a solution but you should try it yourself

[empty sequoia]

so, I tried something like this:

I wrote down a_k+1 <= a_k along with their equalities, and I said that since the sequence is bounded below by sqrt2, we have that
-sqrt2 <= a_n <= +sqrt2

and then with the assumption, if a_k <= a_k-1, then a_k/2 <= a_k-1/2

1/a_k >= 1/a_k-1 but this will become irrelevant as n approaches infinity because these values will converge to 0, leaving us with just a_k/2 <= a_k-1/2 which implies that a_k+1 <= a_k

[sleek loom]

I don't think it's a good idea to just forget about the 1/a_k and 1/a_k-1, they are still relevant at least when using induction

I havent checked if they approach zero but even if they do they still matter when asking if one value is bigger than the other

Other than that the proof might be good but kinda hard to understand through text

[empty sequoia]

I wasn't sure how to show that despite 1/a_k >= 1/a_k-1, these usually retrieve a small value that won't change the original inequality by much since we're just adding a small number

the other part of the sum was more trivial because with the assumption it's easy to show that a_k/2 <= a_k-1/2

[sleek loom]

A much easier argument would be to write that the inequality that needs to be proven, and replace on of the terms with a value that is bigger or smaller than itself. For example
R.T.P: a < b
Assumption a < c
If we replace a with c in the first inequality, and prove that is true, (c<b) it definitely follows that a<b because a<c and c<b

[sleek loom]

I don't think that proves what you want to prove

There might be a way to prove it but you wouldn't need to think about it this way using induction

[empty sequoia]

okay so what I'm thinking now is that replacing a_k by a_k-1 in the equality for a_k+1

It shows that a_k+1 <= a_k is true

now when you say a smaller value than itself, I'm not sure what that means in this context

[sleek loom]

In the example c is bigger than a

So we're replacing a with a bigger value and proving the inequality still holds true

[empty sequoia]

oops sorry, i meant smaller value*

since i'm replacing a_k by a_k-1 knowing that a_k-1 >= a_k

[sleek loom]

Same thing with a smaller value, if you replace b with a smaller value and show that the inequality still holds true, then the original inequality must be true

[native sable]

you take the expression, make it smaller using what you assumed in your hypothesis and then show that it's still bigger than the other side

[sleek loom]

Yeah that's a much better explanation

[empty sequoia]

this is what I understand from your explanations

on LHS i replaced a_k by a_k-1, making the LHS bigger
and on the second line i replaced the RHS a_k-1 by a_k making it smaller ?

[native sable]

@empty sequoia try expressing $a_{n+2}$ in terms of $a_n$

[vital dew]

crossbeam

[empty sequoia]

it would be a_k+1/2 + 1/a_k+1

and that should be what i replace in the last inequality?

[native sable]

in terms of $a_n$, not $a_{n+1}$

[vital dew]

crossbeam

[empty sequoia]

would that take the whole expression of a_k+1 over 2 + the reciprocal of the whole expression of a_k+1?

[native sable]

sounds right, yes

[gilded marsh]

Do I create variables for this question?

[harsh thorn]

yeah, i think thats a good idea.

@gilded marsh what are you thinking of doing for it?

[muted patio]

i'd recommend creating a variable a and b for the first and second numbers. Then having some m and n respectively [figure out how these come into play]. Not sure if they're wanting an algebraic proof but thats what I would do

"Let a be an odd integer and b be an even integer. Then a can be expressed as ___ ..." is ur start

[silent cave]

I have a word "TALLAHASSEE"
L repeated 2 times
S repeated 2 times
E repeated 2 times
A repeated 3 times

how to find the number of ways in which 2A's are adjascent?

[silent cave]

hmm i got it by using inclusion-exclusion principle

[gilded marsh]

yeah ive got it now, thanks

[languid citrus]

<@&286206848099549185>

[pale epoch]

please read #❓how-to-get-help

what have you tried?

[languid citrus]

yes but no one answered?

[pale epoch]

fair, but you still didnt tell what you tried

[tidal tulip]

Define $\sim$ on $\mathbb{R}^3$ as follows: $(x_1,y_1, z_1) \sim (x_2,y_2, z_2)$ if $x_2 - x_1 = 0$. How can I calculate the equivalence class of $(0,0,1)$ and what is a geometric description of this, so that I have some intuition about the problem?

[vital dew]

strings

[tidal tulip]

writing that out I get: (0,0,1) ~ (x2, y2, z2) if x2-0=0

so x2=0

but not sure how to proceed from there in calculating it

[pale epoch]

you are done

x2=0 is the only requirement for (0,0,1) ~ (x2, y2, z2) to be true

[tidal tulip]

so C(0,0,1) = { (0,y2,z2): y2, z2 in R} ?

[pale epoch]

yes

[tidal tulip]

oh cool

how can i think about this geometrically?

of the equivlance class (0,0,1)

[pale epoch]

think of R^3 as euclidean space

with x, y, z coordinates

if the first coordinate is always 0 that means ...

[tidal tulip]

it's always centered at the origin

[pale epoch]

what is?

[tidal tulip]

x-axis

so it's 3-d shapes centered at the origin

er doesnt havr to be 3d

[pale epoch]

i dont know what this is supposed to mean

but its probably wrong

y and z are arbitrary

i think of the coordinates as "walking in the cardinal directions"

so you can walk into y, z directions arbitrarily far

but in x directions you are not allowed to walk at all

[tidal tulip]

that makes sense

My next question is just understanding a statement of these claims: Given a partition {Si}i in I of U we can define relation ~ on U as a ~ b if there exist i in I such that a in Si, b in Si, claim 1: ~ is an eq. relation. Claim 2: Let ~ be an eq relation on U, then {Ci: a in U} forms a partition of U. I want to see if this thinking is correct: Claim 1 seems to say you have a family of sets and if you define a relation on each set so that every element in a particular set is related to each other and any two elements in distinct sets aren't related. Claim 2 seems to say you can define an equivalence. class for each of the sets so all the elements in S1 form an eq. class C1 where all the elements in C1 are just the elements in set S1. Is that a correct understanding of these 2 claims?

[stray reef]

kind of but it feels overcomplicated

[tidal tulip]

what's an easier way to describe it

[stray reef]

these claims basically say that equivalence relations and partitions are, in a certain strict sense, the same thing

and how to go back and forth between them

[tidal tulip]

related to this specific a~b is my description correct

[stray reef]

your description of the equivalence class of (0,0,1) under that relation you gave?

[tidal tulip]

ah no

the one Given a partition {Si}i in I of U we can define relation ~ on U as a ~ b if there exist i in I such that a in Si, b in Si, claim 1: ~ is an eq. relation.

[stray reef]

sure

[tidal tulip]

k

[stray reef]

like

the equivalence relation is "a~b iff a and b lie in the same part of the partition"

[tidal tulip]

so like U={S1,S2}, S1={a,b,c}, S2={d,e,g} then we have a~b, b~c for example but a not related to d, and C1 = { a,b,c } ?

[stray reef]

sure

[tidal tulip]

cool

[tidal tulip]

just did a proof of this type for the first time want to see if this is good

define ~ on R^3 as: (x1,y1,z1) ~ (x2,y2,z2) if x2-x1=0:

Show ~ is an equivalence relation

proof :

~ is reflexive iff for all x1,y1,z1 in R^3 we have (x1,y1,z1) ~ (x1,y1,z1)

(x1,y1,z1) ~ (x1,y1,z1) means x1-x1=0, thus ~ is reflexive

~ is symmetric iff for all x1,y1,z1,x2,y2,z2 in R^3 if we have (x1,y1,z1) ~ (x2,y2,z2) then we also have (x2,y2,z3) ~ (x1,y1,z1)

since (x1,y1,z1) ~ (x2,z2,y2)

then: x2-x1 = 0

adding x1-x2 to both sides of that equation we obtain

x1-x2+x2-x1 = 0 + x1-x2

=>

0 = 0 + x1 - x2

=>

x1 - x2 = 0
thus we see
(x2,y2,z2) ~ (x1,y1,z1)
hence ~ is symmetric

~ is transitive iff for all x1,y1,z1, x2,y2,z2, x3, y3,z3
if (x1,y1,z1) ~ (x2,y2,z2) & (x2,y2,z2) ~ (x3,y3,z3), then (x1,y1,z1) ~ (x3,y3,z3).

we have equations:
(1)x2-x1 = 0
(2)x3-x2 = 0

adding (1),(2) we obtain

x3-x1 = 0

hence ~ is transitive

therefore ~ is an equivalence relation

reflexive seems so obvious i wasn’t sure how to word it

[tidal tulip]

could i get a check for that ^

[old delta]

i need help with one or the other of the above, whatever's easier

[weary tiger]

bruh is this even a legit question

A graffiti artist used red spray on a flat green wall. Prove that one can find two points of the wall so that they are both of the same color and the midpoint of the segment connecting them is also of that same color.

how does my teacher expect me to prove this

i mean, if what is the artist just painted one dot

[stray reef]

if the artist painted one red dot you can take two points far away from it with the segment joining them completely in the green

[weary tiger]

but there are no more red dots

i dont understand what you mean tbh

[stray reef]

it doesn't say "prove that there exist two red points whose midpoint is also red"

it says "prove that there exist two points of the same color s.t. their midpoint is that same color"

i.e. 3 points of the same color, one of them being the midpoint of the other two

that said, this problem feels vaguely topological in nature and im not sure what the intended line of attack is for it...

[weary tiger]

oh

[stray reef]

so what if there are no more red dots? did i say the points we pick had to be red? no, of course i didn't. in fact i said we were going for GREEN points.

[weary tiger]

well, i can imagine this is always true

but i have no idea how to prove it

any ideas?

[stray reef]

do you want me to repeat my no

[weary tiger]

i was speaking to everyone else in a way

[tidal tulip]

can i get a proof check on this

[weary tiger]

anyone know?

[silent cave]

Is this system Idempotent??

< P(s), union, intersection >
where P(s) is powerset of S

[pale epoch]

what does idempotent mean in this context

[surreal stream]

The hell is discrete maths supposed to be

[pale epoch]

some topics are mentioned in the topic

[junior lily]

i would guess that union and intersection would be idemptotent

[twilit sierra]

is the e statement true or false?
i was thinking that
a^n b^n c^n is NOT a CFL
and this example is close to that case

[weary tiger]

How do you go about checking

nvm got it

[olive wren]

It’s not a CFL. Since CFLs are closed under concatenation, if the language were a CFL, so would
{a}•L = {a^nb^nc^n}
Which is a contradiction

[hushed fiber]

Can I get help on this?

Suppose that a pyramid is on a regular hexagonal base. The triangular faces are isosceles of the same dimension and are labelled 1,2,3,4,5,6 in a cyclic order. What will be the group of geometric transformations that leaves the pyramid invariant (symmetries), if the transformations were expressed as permutations of the faces?

[twilit sierra]

can somebody help me with those? maybe privately?

[haughty garden]

For a), it might be helpful to remember that the empty language is regular. So you should be able to show that it is false

For b), try showing that the complement of the language {ww : w \in {0, 1}*} is context-free

For c), it might be helpful to look at subsets of L’. Clearly, if L is a subset of L’, then the union is L’ which is regular. Can you construct a nonregular language L which is a subset of L’?

[manic gazelle]

Hallo!
I have an encoding function for natural numbers
its f(x,y) = ((x+y)(x+y+1))/2 + y
this should give a new unique natural number for every pair of N x N
im trying to reverse this and create a function, rev1 : N -> N: rev1(f(x,y)) = x
its harder than i thought and im struggling.
Does anyone have some leads for me?

[twilit sierra]

why is {ww : w \in {0, 1}*} not context free?

[haughty garden]

Consider the word (0^p1^p)(0^p1^p) and show that it breaks at least one of the axioms of the Pumping Lemma for CFL

[weary tiger]

how you go about this

[old oasis]

Anyone

[echo lagoon]

Can someone help me?

A function is given by f (x) = - 4x + 23.

Calculate f (21).

[stray reef]

@echo lagoon is this your first time working with functions?

[echo lagoon]

yea

but i got help

[stray reef]

mkay

[desert edge]

What happens in ~(p and q) ?

do we distribute the negation?

im having some trouble differentiating it with ~p and ~q

[mental pecan]

De Morgan’s laws says that we pretty much “distribute the negative” on p and q AND flip the sign in the middle (so and -> or)

So that would be ~p OR ~q

[desert edge]

My issue comes from the notation

so when I see negation outside a parantheses, i should think dem?

does this also apply for ~p and ~q, ~p or ~q

[sleek loom]

~p and/or ~q = ~(p or/and q)

in matching order

[desert edge]

this might sound stupid but what exactly is the difference in~(p and q) and ~p and ~q

i did draw the truth tables and they are not equivalent

[mental pecan]

I just told you

The first is not p or not q

Obviously or is not equal to and

[desert edge]

yeah ~(p and q) equivalent to ~p or ~q

i get demorgan

the notation is just messing with me

couldnt this also be de morgan? ~p and ~q equivalent to ~(p or q) ?

[mental pecan]

Yes

Those would be the same (by demorgans)

[desert edge]

Alright ty

[young knot]

Does an automorphism over a graph help by making a seemingly complicated problem more approachable by remapping stuff to a more familiar arrangement? Also, I am not sure if this is the correct channel, direct me somewhere else if it isn't

[hoary cloak]

seems like you are in the correct channel (we also talk about graph theory here), also i can't think of an instance of what you're saying right now, mind giving an example?

[young knot]

From what I understand about isomorphisms and automorphisms (not a lot), if you have a very complex graph with say 20 vertices and 20 edges, you could remap it onto a 20-gon to be able to solve the problem of "what is the most efficient way to go through all the points"

[hoary cloak]

i don't see how that would help

especially because not every graph of that form is a 20-gon

[subtle juniper]

Anybody have a moment to explain diophantine equation? I'm having hard time to understand the concept from this video.

[young knot]

Well, that was an example. If you have n vertices and m edges, you could remap the graph into something more familiar

[young knot]

The question is, is that helpful at all?

[hoary cloak]

afaik graph isomorphism (particularly subgraph isomorphism) is helpful in solving an infinitude of problems in math and CS, but not as a mean so "remap" a graph into something. it's not something i studied in depth, but i never really did this

i might be wrong

[young knot]

I'm in fact learning this for a cs thing, tho I was just wondering about the uses of automorphisms since the pdf I'm reading is brief, too brief. Sometimes I get confused about why I'm learning what I am

[hoary cloak]

i mean, if you can prove that a graph has a non-trivial automorphism, it is symmetric, which means it has some interesting properties you could use

every graph has trivial automorphism ofc (just map each vertex into itself)

[young knot]

Hm, what would a non-trivial automorphism be? Stuff like turning the graph 90 degrees and remapping that?

Actually

[hoary cloak]

you shouldn't worry about the geometry of this stuff

[young knot]

I said it wrongly, should've asked about trivial automorphisms

[hoary cloak]

think of a cycle graph and you send a vertex to one that is right next to it

that is a non-trivial automorphism

trivial automorphism means each vertex maps into itself, which is ofc always possible in every graph

[young knot]

Ok, then I have another question

How do you know if a graph has an isomorphism with another?

Wait

Nvm

[hoary cloak]

it is np complete

[young knot]

The pdf covers that, iirc it is about checking every single possibility

Which honestly sucks computationally

n! ew

[hoary cloak]

actually

no

i was wrong

subgraph isomorphism is np complete

graph isomorphism class isn't known apparently?

[hoary cloak]

that's right but no poly algorithm is known to solve that

[young knot]

Is it part of the whole P vs NP thing or is it just randomly really hard to get a good algorithm?

[hoary cloak]

it is part of the P vs NP thing for a somewhat complicated reason. it's one of the problems thought to be in the np intermediate class (problems in NP that are not in P or NP complete). proving that this problem doesn't belong in any of these classes means that p != np

it's a "special" problem

[young knot]

what if you prove there is a faster method?

p = np?

[hoary cloak]

i assume that by faster you mean poly, then the answer is (i think) not necessarily

if it was already proven to be np hard and you found this algorithm then by all means that would be the case

[young knot]

gotcha. Thanks

[hoary cloak]

👍

[livid minnow]

I am trying to find the number of unique ways to multiply 2 2 167 3 together
so I know i need to find the number of unique subsets of this multiset since multiplication is commutative and we have 2 2's
so [2,2,167,3]
one method I tried
was
doing (4 choose 2) + (4 choose 3) + (4 choose 4)
but this gets me one short

[crude mango]

As in how many ways to write it down?

Should be 12 right

I forget if it has a name but there's an extension of the choose function that does exactly this

$\choose{4}{2,1,1}$

[vital dew]

hiiistrex

[crude mango]

Ignore my terrible latex skills

The 4 should be on top and the 2,1,1 should be on the bottom

The 2,1,1 refers to how many of each type of object there are, so there's two 2s, one 167, one 3

Computation is (n choose a,b,c,...) = n!/(a!b!c!...)

With the caveat that a,b,c,... have to add up to n

$_4\choose{2,1,1}$

[vital dew]

hiiistrex

[rigid sonnet]

can somebody help me with a and b

[livid minnow]

huh that works

ive never known that was such a method

gonna have to figure out how that works now ;p

[crude mango]

Hint: normal choose is a special case of this

[tidal tulip]

could someone check my proof

Suppose:

f: X->Y

g: Y->Z

are functions

Prove if f,g are surjective then g o f is surjective

g o f: X->Z means for each x in X

(g o f)(x) = g(f(x))

f is surjective means for all y in Y, there exist an x in X such that y=f(x)

thus g(f(x))= g(y)

g is surjective means for z in Z, there exist y in Y such that z=g(y).

thus g(y)=z

hence for all z in Z, there exist an x in X such that: (g o f)(x) = g(f(x)) = g(y) = z therefore g o f is surjective.

[cerulean wind]

you should start with "g is surjective means..." instead of "f is surjective means..."

it just reads better that way

[tidal tulip]

i dont know what you mean. can you explain

is the proof as i wrote it correct?

[cerulean wind]

the proof is fine.

g surjective means that for all z in Z there is a y in Y such that g(y) = z.
f surjective means that for all y in Y, there is an x in X such that f(x) = y.

i just think the way this reads is easier to understand. you get the existence of some y, then you use a property pertaining to all y in Y to finish the proof. i just think this is better in terms of the order in which your variables appear

[tidal tulip]

ah

ok, ty for looking over it

the book defines composition of functions as:

g o f: X->Z means for each x in X

(g o f)(x) = g(f(x))

why doesn't it mention anything about elements in the range

[cerulean wind]

it doesnt need to. g(anything in the domain) is in Z

[tidal tulip]

ok

ty

wanted to check if this is correct as well: show (x1,y1,z1) ~ (x2, y2, z2) if x2-x1=1 is not an equivalence relation. i have it failing reflexivity: (x1,y,1,z1) ~ (x1,y1,z1) if x1-x1 = 1 => 0 = 1, contradiction

[tidal tulip]

im still kind of confused by this @cerulean wind - can you show me the proof written out as you see it

[cerulean wind]

dont worry about it. its my writing style coming through. i shouldnt have mentioned it

[cerulean wind]

for this one, there is no need for contradiction. it just isnt reflexive because no element is related to itself, that is, what you have shown is fine, my point being, x1 - x1 = 1 != 0 is enough to show that its not reflexive

[tidal tulip]

thanks for checking both

[cerulean wind]

5n = 2m + 1 tells you that 5 times n is odd.

an odd times an odd is odd.
an odd times an even is even.

what can you say about n if an odd number (namely 5) times n is odd?

ye

proof by cases (so contradiction). n is either even or odd. can’t be even, so it’s odd

a possibly shorter way, an odd divided by an odd is an odd when divisible. n = (2m+1)/5 so n is odd

[wide vine]

can someone help define what a loop invariant is or exactly what I am trying to do.

the definition says "A loop invariant is an assertion that is true before each iteration of a loop. "

and then they go on to show this example

So is my understanding that this loop invariant thing is basically if your pre conditions valid that the loop will always execute as expected?

because I am really lost as to what they mean when the bring up the term in these examples and which part it is actually referring to

[pale epoch]

this kind of misses the point of what a loop invariant is supposed to do

this is true, but a loop invariant has to give you correctness at the end of the loop as well

its very similar to induction

except you have a step where the loop condition is false and at that point the loop invariant is supposed to give you correctness

[wide vine]

so is a loop invariant just basically a proof that a loop executes correctly given you have a satisfactory pre condition?

[pale epoch]

yes, thats what its supposed to do

[wide vine]

and I guess also execute the way you want it to within that loop

not just "complete the loop"

[pale epoch]

the loop invariant doesnt talk about what is happening inside the loop

[wide vine]

oh.

[pale epoch]

this example is kind of simple but a more complex loop invariant would be on certain sorting algorithms

the loop invariant would be something like "the list 1..j is sorted and the list j+1..n contains the other elements in whatever order"

[wide vine]

well they have this example but idk if it is the same

but again this really doesn't bring up a loop

only the pre condition (before the algorithm) and then post (after algorithm)

[pale epoch]

there is no loop invariant here

[wide vine]

yeah :/

[pale epoch]

that part is missing

it would also depend on the sorting algorithm used

[pale epoch]

this works for insertion sort for example

and the point i wanted to make is that it doesnt talk about what the algorithm does in an iteration

just what the result is

and the result gives you correctness once the loop is left

[wide vine]

I have some examples I have to work through

I am just not sure I guess what the "loop invariant" means

you are saying it is just a condition that is true during each iteration?

[pale epoch]

it is true before each iteration

hence invariant

but there are many things that are true before each iteration

[wide vine]

and I would prove that based on my algorithm implementation and the pre conditions?

[pale epoch]

the loop invariant also has to give you correctness once the loop is left

[pale epoch]

yes

[wide vine]

okay I see

[pale epoch]

like, in the first example the loop invariant is true before ever entering the loop

and then you have to argue what happens in the loop

it changes prod in some way and then adds 1 to j

so after those things happened the invariant is still true

but the argument didnt depend on what j or prod was at that point

so it is true before each iteration of the loop

so it is still true once the loop condition is not satisfied anymore

in this case this happens when j=n

but then prod=m*n, which is what you wanted to show

[wide vine]

okay I think I get it. I was just confused of the context on its own

I think it is clear now that is is a statement that is used in conjunction with pre condtion and the loop to show that a loop will execute properly, I believe

[pale epoch]

yes

the end goal will always be proving correctness

i.e. the algorithm does what you claim

which is the post condition

[wide vine]

okay

Got it

[pale epoch]

so the loop invariant has to be true (obviously) but also "strong enough" that you can prove correctness with it

they are chosen here with that in mind

[wide vine]

okay I see. It is isn't much of a loop invariant to just say j <= n throughout the loop (and before and after)

[pale epoch]

yes

that would be true but not helpful

but its usually part of the invariant

since you need this info to show that the loop operates correctly in an arbitrary iteration

[wide vine]

well thanks for the help

[pale epoch]

ye, i hope it helps

my explanations arent great but i think you get it after spending some time with it

[rigid sonnet]

is this true or false?

[final cliff]

You see how the complement of a regular language is regular?

[rigid sonnet]

yes

[umbral tendon]

Does anyone know what this proof is called or where I can find some information about it?

[final cliff]

How are regular languages related to context free languages?

[rigid sonnet]

in CFL, the closure property are closed under union and concatenation

not under complement and intersection

[final cliff]

Think simpler lol.

[rigid sonnet]

but what is tricky is they are asking NON cfl

closure properties dont apply to them

[final cliff]

Oh shit I'm just misreading my bad.

Maybe there's some contrapositive trickery going on?

Like this: $\forall x(x \not\in CFL \implies x^c \not\in CFL) \iff \forall x(x^c \in CFL \implies x\in CFL)$.

[vital dew]

DootDooter

[final cliff]

Where "in cfl" is just shorthand for "is a cfl"

[final cliff]

The rhs of that equivalence seems like it ought to be false.

Just a rough guess.

[tranquil vector]

if 4 different people flip 1 coin each (independent events), what are the odds that at least 2 of them guess the outcome of their own flips correctly

[maiden drift]

If I have a finite set X in the plane where X has an even amount of points, does there exists a line such that each half space (each half space will include the line itself) determined by the line contain exactly half the points of X?

It can easily be shown that in any direction, there exists a line of that direction such that the closed half spaces contain AT LEAST half the points, but can equality always be reached? The method to do this is just to take any direction, and a line of that direction which contains ALL of X in one of its open half spaces. Then we can translate this line in its orthogonal direction and use the IVT to get that there exists a translated copy of this line which contains at least half the points. But I don't think this is strong enough to show equality

[native sable]

assuming the points are distinct, yes

[maiden drift]

Yes, it is easy to come up with counterexamples if not distinct. But does it use this rotation argument? If so, I don't see how this rotation gives the needed equality

[native sable]

do you mean fixing a point on the plane and rotating the dividing line about that point?

[maiden drift]

yes

or is there another way to see that fact... I'm am having trouble convincing myself of it. I certainly see it is possible to get at least half the points in each half plane using that argument, but not equality which we need

[north girder]

Can someone check this please?

Please check

[sturdy walrus]

I'm learning sets right now and I am trying to prove: Let A, B be sets. Then B − (B −A) = A ∩ B .
This is what I have so far... not really sure if I am on the right path, could some one please take a glance and give some pointers on this?

[livid minnow]

for your first part

think about it like

(a in B) and ~(a in (B - A))

where ~ is the negation

[sturdy walrus]

From that, I did this:

[livid minnow]

maybe it will help you if I expand this

(a in B) and ~(a in (B - A))
=> (a in b) and ~( (a in B) and (a not in A) )

and then negate the second part, knowing that the and will turn into an or

[celest lagoon]

Could someone pls help?

[timid flame]

$a\in B-(B-A)$\
$a\in B \land a\not\in (B-A)$\
$a\in B \land \neg (a\in (B-A))$

[hard citrus]

$\land$?

[timid flame]

thank you

[hard citrus]

np

[timid flame]

hmm

nope

$a\in B-(B-A)$\
$a\in B \land a\not\in (B-A)$\
$a\in B \land \neg (a\in (B-A) )$\
$a\in B \land \neg (a\in B \land a\not\in A) )$

[vital dew]

Joe Mama

[timid flame]

yup

form here

use de morgan

$a\in B \land (a\not\in B \lor a\in A)$\
($a\in B \lor a\not\in B) \land ($a \in B \lor a\in A) $

[hard citrus]

Alternatively, there's a less tedious method as well

It's the $ signs

[timid flame]

oh, directly changing the set only?

[hard citrus]

Yep

[timid flame]

yes, it could work

[vital dew]

.itsjustnai

[hard citrus]

With this

[vital dew]

Joe Mama
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[timid flame]

yep, make sense

$a\in B-(B-A)$\
$a\in B-(B \cap A^C)$\
$a\in B \cap (B \cap A^C)^C$\

[hard citrus]

Wait

B-A= BcapA'

[timid flame]

then use de morgan as well

@sturdy walrus this is easier

^

[hard citrus]

You have it the other way around

[timid flame]

Aw shut

yes2

[hard citrus]

$a\in B-A \Leftrightarrow a \in B \land a \notin A \Leftrightarrow a \in B \land a \in A^c \Leftrightarrow a \in B \cap A^c$

[vital dew]

Joe Mama

.itsjustnai

[timid flame]

thank for the correction

[wide vine]

How would I go about showing this by "induction"

I see this the example "( () () ) )" isn't properly nested

and it just makes sense just based on the principle that it isnt an even string length.

but I would also need to show ")(" is not properly nest

which I would assume is based on lack of following either the basis or the recursive rules. Im just not sure how I would prove it for cases that have a correct strength count but have incorrect structure

[north girder]

???

[timid flame]

a is good

b is incorrect i think (?)

c also good

[timid flame]

Like this?

Suppose

$P_n$

[vital dew]

Joe Mama

[timid flame]

Denote all the set that possible properly nested paranthesis

with n open bracket and n close bracket

Then

Wait, the notation will be tedious

$P_n=\union^{n}{k=0} (x_k||x{n-k})$

where

$x_k \in P_k$\
$x_{n-k} \in P_{n-k}$

[vital dew]

Joe Mama

[timid flame]

|| is concatenation

[vital dew]

Joe Mama

[timid flame]

maybe word wont help much

Suppose

for n=3

$P_3 = { [][][], [[]][], [][[]], [[][]], [[[]]]}$

[vital dew]

Joe Mama

[timid flame]

Then

$P_4 = {([][][]), ([[]][]), ([][[]]), ([[][]]), ([[[]]]),$\
$[][], [[]], [][], [][], [[]], ...}$

[vital dew]

Joe Mama

[timid flame]

Just like stated at a) and b)

[unique epoch]

Hi! Anyone know how to do part (a)? I can workout that there are (n - 5) Choose 3 ways, but how do I describe that using Stirling Numbers? I got that solution by $(x_1 + 2) + (x_2+ 2) + (x_3 + 2) + (x_4 + 2) = n$ where x is the lab number. Since every lab must at least have 2 students. Then there are (n + x - 1) Choose ( x - 1), and therefore there are (n - 5) choose 3

[vital dew]

Rasperro

[unique epoch]

But idk how to write it using stirling numbers

I dont really see the connection

[austere cedar]

@unique epoch I think that the students are different. you calculate the number of possibilities of the sizes of the labs. For n=8 you get one possibility (two students each day), but i think that it matters which student is in the Monday lab, which in the Tuesday lab etc. So its not n-5 choose 3

[restive finch]

Hello, Ive been trying to learn resolution but I am getting stumped. Can anyone help me?

[north girder]

What would be b then?

[native sable]

if you have a finite set of n distinct points on a plane then it is always possible to draw a straight line through them such that there are k points above/below it for an arbitrary integer k <= n.
(if you need convincing of this think about how there are infinitely many real numbers between any two real numbers and how n is finite)

(1) if n is even, you chose your line to have n/2 points above/below it, done.

(2) if n is odd you can ignore one of the points so that n-1 even, solve the problem as in (1), then add the ignored point back and move/rotate the line so it intersects the closest point in the direction of the ignored point. then there is 1 point on the line n/2 points above and n/2 below.

[timid flame]

10:50am to 08:00pm right?

,w 10:50am to 08:00pm

[vital dew]

Results provided by WolframAlpha

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

Requested by Joe Mama#8435

[native sable]

#proofs-and-logic, but that isn't unsatisfiable

[distant bobcat]

Could we call this a directed cycle as it includes a directed path?

[native sable]

the clockwise cycle is a directed cycle, yes

[distant bobcat]

@native sable But is the graph called a directed cycle? like we have DAG directed acyclic graphs, so Im wondering if we have directed cycle graphs as well?

[native sable]

well, names are just conventions so ultimately you can call it whatever you want, but i've never heard a graph itself being called a directed cycle.

[distant bobcat]

aha, thanks

[distant bobcat]

@native sable does it also hold that if a graph contains directed cycles then it is strongly connected?

[native sable]

doesn't even have to be connected

[native sable]

however the cycle will be part of a strongly connected component.

[distant bobcat]

that makes sense, thanks

[desert edge]

im to prove if m is even then 3m+5 is odd
I let m = 2k+1 and substitute and multiply to 6k+5
what do I do from here?

i feel like factorizing but dont know what to do about the 5

2(3k) + 5

oh think i see it

[jolly rivet]

Hey I have this pretty basic proof. I think my proof makes sense just not sure if I showed it properly. Would anyone be able to look at it, thank you!

Do i even need to talk about x

Since like I'm just talking about one element of the set and not all

[olive wren]

I wouldn’t say “arbitrarily chosen” I’d say “suppose x is an element of A”.
And then at the end maybe say “since every element of A is an element of BnC, A is a subset of BnC”

[jolly rivet]

Ya that makes more sense

but is talking about x too specific

[olive wren]

No because you’re doing it by definition

It’s not specific at all

[stray reef]

you should not say proper subset

just say subset

[olive wren]

The definition of a subset is
[ A\subseteq B\iff (x\in A\implies x\in B) ]

[stray reef]

you are using $\subseteq$ which explicitly includes the possibility of the sets it connects being equal

[vital dew]

Ann

[olive wren]

Which is what you showed

[jolly rivet]

ok thanks I will change that and keep the x part

also do I need to re state the original statement inside the proof

like the original question

[olive wren]

Why? That’s up to you. But I don’t see why you’d need to do that

That’s like dependent on how your teacher grades assignments, if they require that (I don’t see why they would), then yeah do it

[jolly rivet]

ok I will check past assignments

[olive wren]

It doesn’t really matter as long as your proof is coherent

[jolly rivet]

Ok thank you!! I will fix it up

Oh and do I need to talk about x in the conclusion

Just changed it to this

[olive wren]

That looks good!
(Now I’m just being a little nitpicky, but maybe add a comma between “… is a subset of B” and “x belongs to B”, and the same for C)

But that doesn’t really matter

It looks good!

[jolly rivet]

Thank you!!

And the commas makes it look better

[olive wren]

[jolly rivet]

😄

[jolly rivet]

I also have this proof and it seems pretty simple since the proposal is just the contrapositive so I had trouble putting it into a proof

Would anyone be able to critique it?

Thank you!

[olive wren]

This is a bit confusing? I’m not entirely sure what you’re doing here. But the proof that you’re giving seems a bit convoluted and more complicated than it needs to be.

What you can say is that:

Since $A\subseteq B$, this means:
[ x\in A\implies x\in B ]
Which is equivalent to its contrapositive, so:
[ x\in B^\complement\implies x\in A^\complement ]
Which by definition means $B^\complement\subseteq A^\complement$

[jolly rivet]

Ya I feel like the proof seemed too good to be true so I tried to make it more complicated

[olive wren]

Which seems to be what you were getting at?

[jolly rivet]

Is it really just showing it’s the contrapositive

[olive wren]

Ah okay. Just keep in mind that these are all basic set theory identities, so there proofs will sometimes be quite simple actually

[olive wren]

Yep

[jolly rivet]

Ya I’m just starting set theory today after doing some complicated proofs for other sections so I may be thinking too hard lol

[olive wren]

Ah okay!

What were you doing before?

[jolly rivet]

Well it’s still fairly basic

Like proof by induction

And then direct proof

[olive wren]

Ahh I see

[jolly rivet]

But I guess our teachers was giving questions that take much more work than these ones

[olive wren]

Well it’s the natural order of teaching an introductory discrete math course

[jolly rivet]

So I’m over complicating them a bit

[olive wren]

You’ll need induction later on

[jolly rivet]

Thank you!

[olive wren]

[wide vine]

im a bit confused how to set this up with the 2 different terms

k and n

I assume I need to show that something like b_(n+1) = b_(k+1)?

[willow fog]

this seems like some induction shenanigans

technically you have to use 2 different variables

[willow fog]

but you dont need to show anything like this

just proceed with the proof using n

[wide vine]

hmm?

well if it is induction I assume I need to show if $b_n = 2^{n+1} -1$ then $b_{n+1} = 2^{n+2} - 1$ ?

[vital dew]

Brandon7716

[wide vine]

ill go ask proofs/logic maybe

[willow fog]

yeah

[wide vine]

but I would need to really show that all that holds for b_k?

seeing I need to prove that b_n is holding to that of the recursive defintion of b_n

[willow fog]

yeah exactly

[wide vine]

wait noo

i am going the wrong direction though...

am I not?

[willow fog]

?

I don't think so

[wide vine]

don't I need to go towards b_(n-1)?

[willow fog]

I don't think so?

[wide vine]

seeing the previous definition is recursive and then I would hit a base case eventually?

[willow fog]

first you need a base case then induction step

[wide vine]

yeah but idk what my base case should be

[willow fog]

b_1 since you're given b_0

[wide vine]

yeah

see now this is where the whole 2 terms I think is needed?

because one is subbing in the b_k values from the recursive defintion and the other is subbing in b_n where we using n values :/

and i guess k = n in the test case

[willow fog]

no

b_1=2*1+1 is your base case

and that is in fact 2^2-1

[final cliff]

I'd start from 0

And just point out trivially they've given you b_0 holds.

[wide vine]

sure I mean I think I need to prove 0

yeah

but then start the induction step from b_1?

[final cliff]

The induction step involves k.

[wide vine]

well like using the information in case b_1

well yeah I mean that

[final cliff]

Specifically you wanna show b_k=blah blah formula for k implies b_(k+1)=blah blah formula for k+1

Discord messed up my ghetto subscripts :/

[willow fog]

discord formatting pog

[wide vine]

well are these not 2 differnent formulas?

I assume I need to show b_K = b_n

[spark aurora]

\* escapes the markdown

*

**

[final cliff]

I don't see why you need to show that?