discrete-math

[dusky island]

you can collapse the for j and for i loops into one by changing the parameters a bit. Or you should be, a moment

[fresh venture]

Is it possible given n?

It says the answer is like the form - "a Choose b"

[sharp ledge]

Anyone could help with this ?

[fresh venture]

Total is 3^6

Minus 3^4 ig

[sharp ledge]

Why is it 3^ 4?

[fresh venture]

4^4*

Just through a logic

Maybe wrong

[cerulean wind]

mind elaborating?

[fresh venture]

The total is 3^6 for sure

Now what we don't need

Is 3 c together

Then just consider 3 C together as another unit

And check how many are possible

Then subtract it

[cerulean wind]

yea we understand that. but how are u checking lol

[fresh venture]

I am just a bit confused that wheather taking single C is wrong or right along with triple c

Total places are 4

And total inputs are 4 as well ig

So 4^4

[worldly cypress]

are discrete fourier series exact? can we state that x = DFS(x)?

periodic ones*

[fresh venture]

Check if the answer is 473

[cerulean wind]

for CCC _ _ _, there are 3^3 different strings

for _ CCC _ _ to not over count, there are 2 choices for the first slot (A or B) and 3 for the last two slots.

for _ _ CCC _ there are 2 choices for the second slot (A or B) and 3 for the other two.

finally for _ _ _ CCC there are 2 choices for the third slot (A or B) and 3 for the first two.

in each case, the slot before CCC is always different than the case preceding it so you don’t over count. for emphasis, no string in case one can ever get counted in case two, three, or four

getting 3^6 - 3^4

[fresh venture]

I doubt that 3^4 is counting some outcomes like
CABCCC

[cerulean wind]

that falls into the last case. it gets counted exactly once

[fresh venture]

Lemme check

Yeah makes sense

But CCCCCC is also an outcome

Would last case support it?

[cerulean wind]

first case

[sharp ledge]

How do you get 3^ 4 ?

[cerulean wind]

3^3 for the first case
2 * 3^2 for the last three cases
3^3 + 3*2(3^2)= 3^3 + 2(3^3) = (3^3)(1 + 2) = 3^4

[sharp ledge]

= 3^3(1 + 2) = 3^9 not ?

[cerulean wind]

how do you get that 3(3^3) = 3^9?

[sharp ledge]

Ah , i think there should be a () in 3^3(1 + 2), so (3^3)* 3

[cerulean wind]

ah

[sharp ledge]

Or it is just me misunderstood it

[dusky island]

@fresh venture the numbers in your poblem follow the tetrahedral numbers with a slight delay. 4 = 1, 5 = 4, 6 = 10, 7 = 20 and so on. I got this answer by running drawing some graphs in my notebook and running the loop with python. This isn't the most mathematical way of doing things, but it works

[sharp ledge]

So it is the same case if lets say i now have string of length 5 ?

[cerulean wind]

there’s going to be a total of 5

i can even list them out:
CCCCC A
CCCCC B
CCCCC C
A CCCCC
B CCCCC

[sharp ledge]

i mean like 5 length string without CCC

[cerulean wind]

three choices for the last spot, and so you don’t over count, 2 for the first slot in the next case

oh

[mystic elbow]

Hi can anyone please check three questions

[cerulean wind]

i think now it’s 3^5 - 3^3
should be the same process tho.
C C C 3 3
2 C C C 3
3 2 C C C

[mystic elbow]

Hi @cerulean wind could u please check my answers above?

[cerulean wind]

what you sent is incomprehensible

[weary tiger]

for this problem

Let N>5 be a positive integer. Can N2-9 ever be a prime?

is this solution good:

Factoring $N^2-9$, we get $(n+3)(n-3)$. Since $N-3\neq1$ (because N>5) we have 4 distinct factor of $N^2-9.$

[vital dew]

static

[weary tiger]

anyone?

come on

this is important

[gritty crescent]

It cannot be a prime precisely for the reason you stated

[weary tiger]

so my solution is good?

[coral raven]

yes

[weary tiger]

ok

how about for this problem:

(n+1) integers are chosen from the set {1,2,..., 3n}. Show that the difference between two of them is at most 2.

my solution:

Let’s say that it isn’t possible. So, since we are choosing from 3n numbers, we can split into n groups of 3. We know that it isn't possible to have a difference of at most 2 from two numbers, therefore we would have to choose one number from each of those groups, but because we are choosing n+1 numbers, based on pigeonhole, we will have to choose 2 numbers from the same group.
Thus, the difference between the two of them is at most 2. Q.E.D

[floral field]

Is there a family of polytopes, where (# faces - #vertices) is arbitrarily large?

Bc I can think of some examples, but idk if there's like a bigger group of them that satisfy that

[coral raven]

consider antiprisms

[floral field]

Oooo, very interesting. It looks like it already, but it wouldn't be the case for (# vertices - # faces) huh?

[tidal mica]

Hey! I have a question regarding Boolean algebra, because I can't find a proper definition, sorryy

That's the question

So based on one of the textbooks I read zero element in lattices (which power set belongs in) is an element that is less than all others, in this case I'd think it's an empty set
And the unit element is biggest one, here, the whole S set

Is this correct? Because in the slides I was given from uni zero element is defined as 0+x=x (which honestly makes no sense to me.. isn't in Boolean algebra + representing "or"? ;-;;)
Unit element as : 1*x=x

[snow sleet]

@sharp ledge , @cerulean wind , @fresh venture I saw the question about the number of 6 letter strings made using the alphabet {A,B,C} such that CCC does not appear and it looks like y'all could use some confirmation on what the answer is. The answer is 648; as ya'll figured out, there is no getting around the tedious casework. I've attached an excel file I used to list out all 3^6 sequences and then used some code to sift through those sequences to find what the total number of desirable sequences are. In it the spreadsheet, you'll notice that I used 0,1, and 2 rather than a,b, and c (respectively)...just a personal preference of mine...some more coding is required when using a,b,c in excel instead of good old numbers. Hope this helps!

[cerulean wind]

thats pretty neat lol, glad my analysis was correct

[wheat leaf]

Does anyone know if this is correct. I said yes no yes for a) b) and c)

[hidden crystal]

can anyone explain why this is right

<@&286206848099549185>

like in a way i can understand

[meager prairie]

this question is a nightmare 🤔

i cant think of a good way to do it without altering 2 into a more intuitive form

but it takes the shape of a literal puzzle

depends on how you draw the pictures to yourself, heres how i did-

but that wont make sense im guessing to someone else

[split drum]

I'm trying to prove 5.25 by contradiction. So assume there is an $a$ such that the statements are true then I'm thinking that I can form the equations $a-5=14k$ and $a-3=21l$ for some integers $k$ and $l$. Then I can form a system of equations and subtract the first one from the second and get $2=7(3l-2k)$ as 7 does not divide 2, there is a contradiction.

[vital dew]

Umiguess4000

[split drum]

Does this seem valid?

[north dust]

Okay, I've given up on this Combinatorics problem and will just maybe ask some people tomorrow

[snow sleet]

what problem?

[snow sleet]

yes

[north dust]

Just an explanation or showing how at least two people at a party (min 2 people) know the same number of people (where either two people are mutually friends or mutually strangers)

[snow sleet]

ah this is a pigeonhole principle problem

[north dust]

Yes, sir. Been trying to figure a way to show it for a while. Will probably sleep over it and begin again tomorrow.

[snow sleet]

I can save you some trouble lol. Think of the worst possible case.

This is when you have all n-1 people knowing different numbers of people.

but then the nth person

knows some number of people that was used before

draw a circle of n people

and above those people, write down 0,1,2,3,..,n-1

[north dust]

You mean like a counterexample

Okay, sure yes

[snow sleet]

no I literally mean the worst case scenario. If we prove it holds in the worse case scenario, it holds in every scenario because any other scenario would be better

[snow sleet]

so 0,1,2,3,...,n-1 represent the various number of people that those people know

[north dust]

Oh, okay, yes of course

[snow sleet]

so now tell me is this really possible to have no one having the same number?

consider when n=2

then we have 0,1

which isn't possible in reality because we assume "knowing" is symmetric

[north dust]

Yes

[snow sleet]

(i.e., if I know you, then you know me)

so really, we have 0,1,2,...,n-2

and then the nth person must have one of those numbers in the set {0,1,2,...,n-2}

because if not, then that would contradict the fact that "knowing" is symmetric

[north dust]

Oh, makes sense

[snow sleet]

so using the pigeonhole principle, we have n pigeons flying into n-1 pigeonholes

so at least one pigeonhole contains at least two pigeons

@north dust to make it more concrete why {0,1,2,...,n-1} is really a possible set for this problem is because here we have one person who knew nobody, while n-1 represents someone knowing everyone else. These things contradict each other and so {0,1,2,...,n-2} is the worst possible case scenario

now if everyone knows at least one person, then we're dealing with the set {1,2,3,...,n-1}, which again is a set of n-1 elements. So the nth person must have one of the numbers in this set.

does that all make sense?

[north dust]

Intuitively and mostly, I'll have to think about it more in the morning

Thanks

👍

[sacred dune]

There’s a bonus « for fun » question in my cs class about Hamiltonian cycles, namely finding a simple condition as for Eulerian cycles to decide whether or not one exists. The only piece of insight I’ve had so far is that if you have two graphs admitting Hamiltonian cycles and you glue them along an edge of the cycles (a single one) you get another graph with a possible Hamiltonian cycle, but if you glue along two edges in a row you don’t.

I don’t think that’s really putting me on the right track though I’d really appreciate a hint

I’ve also thought of the simple fact that we’re removing E-V edges in creating a Hamiltonian cycle but it might be too trivial to get us anywhere even by thinking in terms of it

[pale epoch]

i think this question is setting you up for failure

this is a classical NP-complete problem

[sacred dune]

Sure

But it should be doable I know my teacher’s style

They warn you afterwards when it’s a setup for failure

[pale epoch]

well, there is no known "simple" condition

i.e. can be checked in polynomial time

[sacred dune]

Here I’m not meant to generate a Hamiltonian cycle just check that it exists

[sacred dune]

Really 🤔

We saw that it wasn’t known whether or not the problem of finding a Hamiltonian cycle was P but not the problem of asking whether or not it exists

But it wouldn’t surprise me ig the only new piece of insight I got in the past 30m was that removing a vertex preserves the property that the graph admits a Hamiltonian cycle. Not very useful though cause it doesn’t preserve the property of not admitting one

[pale epoch]

it shouldnt be too hard to reduce 3SAT to this problem

so yeah, this is NP

ther are some graph classes where its easier

and some known theorems that guarantee a hamiltonian circuit (intuitively if you have many edges / high minimum degrees, there will be one)

[sacred dune]

Wait but if this is NP isn’t it P

Since the same algorithm would be used to verify it?

[pale epoch]

you can verify a given path in polynomial time

[sacred dune]

Yeah but we aren’t giving a path

[pale epoch]

you cannot show that one one exists (unless P=NP)

[sacred dune]

Only saying that it exists

[pale epoch]

wait

i misread maybe

you gave a graph and know it has a hamiltonian circuit and just want to find it?

[sacred dune]

No, I have a graph and want to say if it has a Hamiltonian path or not

[pale epoch]

ok, that is NP-complete

[sacred dune]

What’s the difference between np complete and np?

[pale epoch]

NP-complete problems can be used to "simulate" other NP problems

[sacred dune]

In what way does this « simulate » NP problems?

[pale epoch]

you can reduce other NP problems in polynomial time to finding a hamiltonian circuit in a suitably constructed graph

[sacred dune]

Hmm I see

[pale epoch]

this is also how you prove this iirc

you construct a graph that has a hamiltonian circuit iff some logic formula is satisfiable

[sacred dune]

So I guess it really was a setup for failure

The question had the same format as for eulerian cycles though 😭

And earlier when asking about 3-colorings we were told to only give it a think but that we would not find a solution (or be eternally famous)

[pale epoch]

thats kind of the goal i guess

why is finding eulerian cycles so easy and hamiltonian cycles not

there is this theorem by dirac (not that one) about graphs with minimal degree >= n/2 having hamiltonian cycles

and some special graph classes can be solved more quickly

but in general its tough

[sacred dune]

I see

Well at least I’m glad I gave it an honest think it was fun

Too inexperienced in graph theory to have tried much stuff though

[pale epoch]

not like graph theory provides many tools to tackle problems

most arguments seem very ad hoc

[sacred dune]

Oop

I thought there were matrix and group methods?

[pale epoch]

yeah, there are

the adjacency matrix is very powerful

but lots of argument still feel very ad hoc

[sacred dune]

Tried to look at the adjacency matrix but got nowhere

[pale epoch]

if you study specific graph classes that are e.g. defined by some group theoretic notion, you get more powerful tools

[sacred dune]

Lie Cayley graphs?

[pale epoch]

yeah

[sacred dune]

Aren’t they used in proving that subgroups of free groups are free?

That’s a proof I really wanna learn at some point it seems great

[pale epoch]

you can i guess

[sacred dune]

Yeah covering spaces are more standard right

[pale epoch]

its more topological

but you can define graphs topologically as simplicial complexes and study them that way

but the "standard" graph theory is very combinatorics-y and feels (to me at least) very ad hoc

[teal rune]

Need some help w this

[cerulean wind]

what r u confused on

[teal rune]

I got it figured out, it made no sense at first lol

[wheat leaf]

Does anyone know how to finish this

[stone moss]

@wheat leaf

[wheat leaf]

Ily

[wheat leaf]

Last one I need help on this

Tyty

Mb sorry I got another one sorry for all the questions guys I’ve been struggling with prop logic

I tried using de morgans but couldn’t simplify further

Ty it makes sense when someone explains but I’m stuck otherwise

[frigid steppe]

Hi all, can someone help me with the proof of this identity?

It was covered in a class involving generating functions

[granite shoal]

Yea one example is technically enough to disprove

[weary tiger]

Hi guys small question

why is discrete math related to computer science ? Thanks

[pale epoch]

well, computers are discrete in nature

and many problems (in e.g. graph theory) are algorithmic in nature

[autumn horizon]

how does this = 31?

[stone moss]

It doesn't. It's 33.

[torn tendon]

it doesn't

[chilly pumice]

its 33

[weary tiger]

Hey guys

Hey guys can someone explain this to me?

I know its simple but i dont know what it is asking by prove it.

Like what should i write?

should i write in english words or somehow show with formula

[cloud cargo]

i'd just write english

[rough crater]

would a venn diagram work?

[weary tiger]

Yeah thats what I thought I would do like give an example

also disjoint union means they dont have anything in common right?

[cloud cargo]

idk what you are expected to do from your class

yeah each component is disjoint

[weary tiger]

Okay

[cloud cargo]

so (A\B) \cap (A\capB) = {}

and their union is equal to A

just suppose x in A, show that it is in $(A\setminus B) \cup (A\cap B)$

and then the reverse direction

[weary tiger]

oh okay

i will try thanks

[vital dew]

jabra

[weary tiger]

wait if its disjoint doesnt that mean i should show that it isnt in the union?

[cloud cargo]

hm i think it refers to A \ B being disjoint to A ∩ B

[weary tiger]

so would this be decent proof?

i mean is it even correct?

[cloud cargo]

yeah (it's an example)

[weary tiger]

Thanks a lot.

[cloud cargo]

i don't know if your teacher expects you to formalise it in english

[weary tiger]

I dont know either xd

well i guess i will learn the hard way

[weary tiger]

What should I have done tho

English words?

[tranquil vector]

Prove by strong induction that for any n≥4, there exists j,l ∈Z≥0 such that n= 5j+ 2l,

can someone explain to me the corelation between k and k+1 for my proof

[desert edge]

What exactly is the difference between euler and hamiltonian circuit

they sound so similiar

Both circuits use every vertices once and end at start?

[pale epoch]

eulerian circuits visit every edge exactly once, hamiltonian every vertex

[desert edge]

oh

[tranquil vector]

Prove by strong induction that for any n≥4, there exists j,l ∈Z≥0 such that n= 5j+ 2l,
can someone explain to me the corelation between k and k+1 for my proof

[desert edge]

can I use the same vertex in a euler circuit?

[pale epoch]

multiple times? sure

[desert edge]

I have to compute the value, showing the process for each computation

The thing is, when i mod57 i get 21

but when doing it in hand, i get to remainder 22

shouldnt the bottom line and top line be both equal to 21?

also ignore stick arm shadow

Is it wrong to say (9.987.421*(32.413+43.256))mod57 is equivalent 22?

the end result is throwing me off

[pale epoch]

,w 9987421*(32413+43256) mod 57

[vital dew]

Results provided by WolframAlpha

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

Requested by Lochverstärker#5585

[pale epoch]

yes

tbh i have no idea what exactly you are calculating

[desert edge]

Im just trying to show the steps to getting 21 as remainder but I guess I did it wrong

[pale epoch]

is this supposed to be the euclidean algorithm?

[desert edge]

Im not sure. I just did the same process as with expansions

[pale epoch]

the easier way would be to reduce the numbers mod 57 before doing any arithmetic

[desert edge]

Like this

they are both under the same exercise, so I assumed its solved this way

[pale epoch]

ok but what is your starting number

[desert edge]

This

[pale epoch]

,w 9987421*(32413+43256)

[vital dew]

Results provided by WolframAlpha

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

Requested by Lochverstärker#5585

[pale epoch]

i still don't see what you are trying to do

compute the 57-ary digit representation of that number?

[cloud cargo]

i'm confused aswell

if you want to compute the value that is congruent to that expression, you're done after the first step

[desert edge]

This is the exercise

[pale epoch]

i mean that works, but then you are done after the first step as you only need the "least valued" digit

[desert edge]

its 2b

[pale epoch]

besides, i think that exercise wants you to compute the numbers by hand

[desert edge]

Isnt that what I did

[pale epoch]

you calculated 9987421*(32413+43256) by hand?

and divided that by 57?

[desert edge]

Yeah i think so

thats what this was

[cloud cargo]

by hand as in without calculator

?

[desert edge]

no i used calculator to see the result after divide

[pale epoch]

so i think that this is not what this exercise wants

[desert edge]

after that I used mod57

[pale epoch]

and also dividing shouldn't happen

[cloud cargo]

i wonder how you'd simplify that anyway, except from reducing the sum

[pale epoch]

it's weird because those numbers are still very big and i would not want to do this by hand

but i guess its possible

you reduce the individual numbers first

and then it should be manageable (kinda)

[coral raven]

i think they just want basic long division to find the remainders before doing the multiplication and addition? and then combine those remainders, rather than the other way round?

not certain

the sheet seems fairly basic

so i could buy it being like that, rather than the full extended euclidean algorithm

[desert edge]

I can show the solution to my other exercises

im just confused about that one

[pale epoch]

its kinda weird exercise

by "theorems shown in class" however they probably want you to reduce the individual numbers first

[desert edge]

yeah I had sinus infection that lecture

so I kinda missed what they did

asked classmates but they arent kind to share unfortunally

But i used youtube quite abit. trevtutor especially when it comes to discrete math

[pale epoch]

well, if you do it like you did, you are done after the first step as that is the remainder

the 22 (and in fact all other calculations) are unrelated

what you could do instead is reduce the individual numbers first, so

,w 43256 mod 57

,w 32413 mod 57

,w 9987421 mod 57

so you get 52*(37+50)

canc calculate that and reduce again

not even sure it is much easier

weird exercise

[coral raven]

it's definitely much easier

[desert edge]

Ohh

[coral raven]

the other way round, you'd have to do a 7-by-5 digit multiplication and then do the long division of that probably 13-digit number to find the remainder by hand

obviously trivial with a calculator but

[pale epoch]

numbers still so big that i wouldn't do it

[desert edge]

these are the remainders, right 52*(37+50)

of each number

but what does it really tell us?

is it just the number to begin with thats simplified?

[pale epoch]

those are the remainders of the original numbers

there is a theorem that when dealing with sums/products of numbers modulo n, you can reduce each summand/factor modulo n first

[desert edge]

i am so gonna fail my discrete math exam lmao

[pale epoch]

unfortunate

[desert edge]

Well Ill try again next semester but jesus christ its hard

im not the best at math but Id like to think I had it easy back in highschool.
discrete math is a pure monster compared to anything ive tried

[cloud cargo]

I dont think that works

for multiplication

only for addition

actually

i might be stupid

[pale epoch]

it does work

you can prove it by considering a = b mod n and c = d mod n and showing that a*c = b*d mod n

[cloud cargo]

yeah i brain lagged

[pale epoch]

(or argue via the ring homomorphism Z -> Z/(n))

👍

[desert edge]

o__o

the real ziltoid

[pale epoch]

this reminds me of something

[frank wing]

could someone help me with relations and fuctions

[weary tiger]

https://cdn.discordapp.com/attachments/423244559682764800/899096959133048842/unknown.png

can any1 help me with this

[cerulean wind]

what specifically do u need help with

[weary tiger]

yo can you help me with this while u wait for him to answer please? https://cdn.discordapp.com/attachments/423244559682764800/899096959133048842/unknown.png

[cerulean wind]

do you know what P(E) means?

[weary tiger]

Hey can someone explain this to me? I did a and b but I dont get c,d,e.

please tag me if you can help

[mystic elbow]

Can anyone help with 5

Tag me too

Please

[cerulean wind]

i’m assuming it’s asking if you can get all but one square colored white

[elder berry]

The answer should be ||it's impossible.||
Consider what happens when you switch the colors in a row/column.
What must always happen to the white/black squares?

Hint: ||Is the sum of all black/white squares even?||
Answer: ||The grid is 8x8. In a row either we have even black and white tiles, or odd black and white tiles. Switching the colors preserves the parity. Since the chessboard starts with even number of each, it must remain after each transformation as such.||

[ornate cliff]

For Question 7d,
Cardinality of Powerset is 2^n.
n being the # of elements in a set.

I thought the # of elements in set C = 3 so 2^3 = 8. Why is the answer False?

[coral raven]

C only has 2 elements

[ornate cliff]

so the empty set is 1 element and {a, {a}} is also 1 element?

sorry this is such a basic question

[dawn imp]

Yes. That's right

[ornate cliff]

okay, thank you both!

[knotty pulsar]

Can someone help pls

[ornate cliff]

I’m still new at discrete math so my answer may be incorrect. I think

1. ¬ S —> R
2. If there is cloudy weather and sunny weather, then there will be sunny weather

[knotty pulsar]

Thanks

[kind hollow]

what does this symbol mean? ~

[amber prism]

depends on if order matters

[slate burrow]

not

[amber prism]

need way more context

[kind hollow]

okay, in my text its a sideways L

[slate burrow]

oh right, smart thx

[amber prism]

asking "what's this symbol mean" and just putting the symbol means jackshit

[slate burrow]

ignore what i just said

[kind hollow]

in this case what does it mean

not q or r?

okay thanks

[vital dew]

Steppaz

[ornate cliff]

Use combination when order does not matter & no repetition is allowed.
Ex: Picking a committee of 5 people from a group of 10 people.

Use permutation in situations where order matters & no repetition is allowed.
Ex: What are the number of different words that can be formed with the word APPLE? The words do not need to have meaning.

I think you are on the right track but I'm not sure what " $\binom{8}{3}+\binom{5}{2}$" means.

Following what you said about counting the number of repeated letters, ANACONDA = 8
A = 3
N = 2
C, D, O = 1

8!/(3! * 2! * 1! * 1! * 1!)

The 1! = 1 so some people don't bother including it in the calculation but I added it to be consistent.

[slate burrow]

oh wow

yeah ignore what i said about (83) lol

so here we basically look at the strings which is 8! and then we divide with the amount of letters right=?

[ornate cliff]

yes

[slate burrow]

this is the formula right? Just want to check, so i can watch the lecture again

[ornate cliff]

yes that is the formula for permutation

[slate burrow]

but we are not working for permutation no?

[vital dew]

PolePuma 🇺🇸 🇭🇰 🇻🇳

[slate burrow]

this is combinations right?

[ornate cliff]

I fairly sure this is permutation since the order of the letters should be taken into account.

[slate burrow]

alright, thank you

[ornate cliff]

I'm basing it off of these examples. But anyone else with more discrete math mastery please feel free to chime in!
https://www.mbacrystalball.com/blog/2015/09/25/permutations-and-combinations/

[slate burrow]

it makes sense if we compare my question to those

I can check if it's correct, but I need write a code for it first

[kind hollow]

what does the weird x mean in this statement?

[elder berry]

You say that 2|n if 2 is a divisor of n. If it's not, then you draw a line through the |, aka the vertical bar.

[elder berry]

Similar to $\neq$

How we draw a line through to say it is not equal. In your context it would be doesn't divide

[kind hollow]

so it can be said not equal too as well. just want to make sure

[elder berry]

No we can't, I was just mentioning the crossing out the vertical bar is similar to crossing out equality

[elder berry]

So the direct translation to the above is: Let n be an integer that is odd. Then 2 doesn't divide n. Therefore 2 doesn't divide n^2. Hence n^2 is odd.

[oak bobcat]

Hi, I'm new here and I have difficulty in proving this, can someone help me out 🙂

[storm brook]

$x \in A \cap \overline{B} \iff x \in A \wedge x \in \overline{B} \iff x \in A \wedge x \notin B$.

Now, assume that $A \subseteq B \cup C$. Then, $x \in A \implies x \in B \vee x \in C$
Therefore, $x \in A \wedge x \notin B \implies (x \in B \vee x \in C) \wedge x \notin B \iff x \in C$. Thus, $A \subseteq B \cup C \implies A \cap \overline{B} \subseteq C$

[vital dew]

Campanha

[storm brook]

It is an iff statement, so you must also prove the converse.

i.e., $A \cap \overline{B} \subseteq C \implies A \subseteq B \cup C$

[vital dew]

Campanha

[unreal yew]

can anyone help me with b and c?

[proven silo]

What are you stuck with on b?

[unreal yew]

Im not sure how to prove P(k+1)

[proven silo]

What have you tried

[unreal yew]

a3=5 and a2=3 were from part a

[proven silo]

So haven’t tried anything for P(k+1)? Its a straightforward application of induction hypothesis

[tranquil vector]

how do I prove that a function is well defined?

like ik it is but how do I prove it properly

in this case prove that g(s) = sqrt(s) is well defined

[pale epoch]

how is sqrt defined though

[hidden crystal]

Can anyone tell me how this makes any sense. Last time I checked, you can't take a 4 out of a 2. You can't divide 2a by 4a because 4a is too big to fit into 2a. So how is this the right answer? <@&286206848099549185>

[hallow horizon]

#❓how-to-get-help

[hidden crystal]

thanks for not helping me with the question and only teaching me how to ask for help in this specific server @hallow horizon I figured it out.

[desert edge]

@pale epoch This was the solution to my task ,incase you wanna see

[hallow horizon]

Glad you figured it out remember to wait 15 minutes before tagging helpers next time.

[tranquil vector]

$g(s) = \sqrt{(s)}$

How do I prove that this function is well defined

[vital dew]

arcuzie

[tranquil vector]

like ik for every s there's a unique g(s) but how do i prove it mathematicly

[carmine vine]

if you want to show there's a unique g(s) you can suppose for a contradiction that there exists a and b such that g(a) = g(b). Then by our assumption it must be that a != b. If you can show that a=b, then that renders your assumption to be contradictory so you can conclude that the function gives you unique outputs

In other words try proving that your function is one to one

the process is quite quick, takes about 1 line

[split drum]

<@&286206848099549185>

Could someone give me a hint on where to start with this proof? I'm feeling a little iffy on even how the base case should look. I know it's for n=2.

[tranquil vector]

@carmine vine I have to do a direct proof

$\forall s \in S$, $\exists! b \in \mathbb{Z}^{\geq 0}$ such that $g(s) = b$

[vital dew]

arcuzie

[tranquil vector]

(because for my case we describe S as a set containing only positive integer)

is this right

or am i just lost lol

[carmine vine]

what does the ! mean

there exists a non-negative integer !b is how im reading it but i dont know what ! means

[tranquil vector]

i was looking at the latex wiki and it was like there exists ONLY 1 b

something like that

[carmine vine]

can you send a picture

[carmine vine]

there is no one way to prove something, i believe what i sent suffices

it tells you that there is only one way to get a distinct output

[tranquil vector]

but how do I do that with a direct proof

like ik you can prove something is wrong with just one counter example

but to prove its right you need every example

or did i misunderstand

[carmine vine]

is that statement verbatim to the way the problem is asked

[tranquil vector]

Let S:={x2:xis a multiple of 3}
.a. Consider the functiong:S→Z≥0such thatg(s) :=√s. Isga well-defined function? If so,prove it via a short direct proof. If not, disprove by providing a counter-example.

[carmine vine]

yes, i showed that the function is injective and thats a direct proof

its another way to phrase your proposition and it gets the same idea across

in order to show uniqueness you need to quantify two outputs

so there is not much i can do with the proposition that you had provided

[tranquil vector]

but how would I go about doing a diredt proof?

[carmine vine]

if f(a) = f(b) then a = b

[tranquil vector]

is that enough for a proof?

[carmine vine]

assume f(a) = f(b). then show a = b

[tranquil vector]

I had that at one point but I deleted it

do I have to show a=b?

[carmine vine]

yes

[tidal tulip]

I would like proofs checks on two theorems

(1) Prove for any set A is isomorphic to itself

For there to be an isomorphism between sets X and Y we need functions

f: X -> Y and g: Y -> X

that satisfy the following compositions:

(g o f) = id_X

and

(f o g) = id_Y

we will check these compositions are satisfied.

let g=id_A: A -> A

we see that by substitution

(id_A o id_A) = id_A

let f=id_A: A -> A

and we see that by substitution

(id_A o id_A) = id_A

thus the compositions for a isomorphism between f:A->A are satisified and hence A is isomorphic to itself

(2) Prove for any sets A, B id A is isomorphic to B, then B is isomorphic to A

Proof:

Assume A is isomorphic to B then there are functions

f: A->B

g: B->A

Such that

(g o f) = id_A

(f o g) = id_B

B is isomorphic to A if we have the compositions:

(f o g) = id_B

(g o f) = id_A

But due to A being isomorphic to B, we already have such compositions satisfied

Therefore B is isomorphic to A

[tranquil vector]

but how do i show a=b

like do i make my own examples

[carmine vine]

are you familiar with what constitutes a direct proof?

the process of showing if P then Q

how would you go about proving this statement

[tranquil vector]

honestly I forgot how to show a direct proof

like do i make my own examples for s

[carmine vine]

okay, so when you have something in the form of if P then Q the process is that you assume P holds

then use that assumption in showing Q holds

so in the case if f(a) = f(b) then a = b you start by assuming f(a) = f(b)

now from this assumption can you arrive to a = b?

hint: rewrite f(a) = f(b) in terms of the function results

[tranquil vector]

so like in my case its g(s) = sqrt(s)

[carmine vine]

yeah,

[tranquil vector]

do i do like g(4) = sqrt(4)

[carmine vine]

so g(a) = g(b) implies sqrt(a) = sqrt(b)

No, you need to keep a and b arbitrary

[tranquil vector]

oh

[carmine vine]

so from sqrt(a) = sqrt(b), can you get a = b?

[tranquil vector]

I would assume yes

oh do i square it

[carmine vine]

yep

[tidal tulip]

<@&286206848099549185> could someone verify my proofs?

[tranquil vector]

so like (f(a))^2 = a?

[carmine vine]

sure, but the point of the proof is to show how you got that its equal to a

so what you really are showing is g(a)^2 = sqrt(a)^2 = a

so after you square both sides you get that a = b

so your function is one-to-one

[tranquil vector]

ohh

wait so like g(a)^2 = sqrt(a)^2 = g(b)^2 = sqrt(b)^2

[carmine vine]

yeah

[tranquil vector]

do i just write that

[carmine vine]

you may do that but it looks messy

i would advise splitting it into implications

$g(a)^2 = g(b)^2 \implies (\sqrt(a))^2 = (\sqrt(b))^2 \implies a = b $

thats odd

[tidal tulip]

@rigid tartan could you check to see if these proofs are correct? i’m using the categorical definition of isomorphisms but dealing with sets and functions so posted it in here

[tranquil vector]

its ok i can run it in my own latex software

ok thanks vaizex

[carmine vine]

np

[tidal tulip]

or can someone here check them

[carmine vine]

unfortunately i'm not quite familiar with isomorphisms

[tidal tulip]

i appreciate the willingness to help regardless!

[rigid tartan]

yes both are correct.

honestly might even be too much detail

[viscid moat]

$\sqrt{x}$, not $\sqrt(x)$

[vital dew]

Delta

[viscid moat]

use {these} not (these)

[carmine vine]

yes i know i forgot to change it

but my point still gets across

[waxen sequoia]

what is the correct answer in number 7 and 8

[stone moss]

@waxen sequoia
For 7, $d=-2x$. Use $a_n=a_1+(n-1)d$ to obtain a10.

For 8, $d=2c+1$. Use $a_n=a_1+(n-1)d$ to obtain a10.

[vital dew]

Saurus

[waxen sequoia]

thank you!

[stone moss]

That's not a problem. Can you see how to determine $d$ for each case, though? That's hugely important.

[vital dew]

Saurus

[waxen sequoia]

yes by adding

[stone moss]

OK, rather do $a_2-a_1$, but it will do the job.

[vital dew]

Saurus

[split drum]

Can someone check these two proofs I have:

[stray reef]

looks like you miscalculated b_3 in 5a

[split drum]

-3* bn-1? B2= 9, right?

[stray reef]

oh, my bad, must be me who's misread it

[split drum]

• 4bn-2, b1=6

Oh, phew lol

[stray reef]

...+4b_n-3, no?

[split drum]

Ah frick

Ah, OK. I just mislabeled. I get it

Does the rest look good to you?

[stray reef]

no this looks kinda sus to me

where are you getting $b_{k+2} = 5 - 2(b_k-5)$ from?

[vital dew]

Ann

[stray reef]

also your 1 looks too much like a 2

it keeps messing me up

but the question still stands

[split drum]

$b_k= 5+(-2)^k$, so I just subtracted the 5 to the other side to get $b_k - 5= (-2)^k$

[vital dew]

Umiguess4000

[split drum]

I'm trying to get $(-2)^{k+1}$, so I multiplied (-2) by $(-2)^k$ or $b_k-5$ in other words.

[vital dew]

Umiguess4000

[split drum]

Then I just worked out the algebra from there to show that the recursive function is actually equivalent to $5+(-2)^{k+1}$

[vital dew]

Umiguess4000

[split drum]

I'm not entirely sure if these steps were valid, however.

[stray reef]

they are valid but irrelevant.

[split drum]

Oof, OK

Could you provide a hint as to what the correct starting point would be?

[split drum]

@ann nevermind, I figured it out. Thanks.

[pale epoch]

what does that notation of f and g mean

[rich siren]

I guess I meant like
f(1) = 1
f(2) = 2
f(3) = 3

g(1) = 3
g(2) = 2
g(3) = 1

f ◦ g = g ◦ f means
f(g) = g(f)

[pale epoch]

ok, then this is not a counterexample

f is the identity and it commutes with every other function

[amber hill]

f: multiplies the number by 2
g: squares the number

[pale epoch]

...

[amber hill]

oh that can be used as counterexample

[rich siren]

Damn that's pretty good

Thanks

[amber hill]

but I guess it works with real number only, if we are talking about integers only then domain and co-domain get a lil bit commplicated.

[rich siren]

Why's that?

[amber hill]

uhh you see like if I 2x then number and square it the co-domain will contain only the multiple of 4, but if I do opposite it will contain a different co-domain

[pale epoch]

you will also find an f that works for your chosen g above

(even another bijection)

[rich siren]

Well as long as 1 example doesnt work, it proves it wrong, no?

Even if it's super niche

[pale epoch]

well, sure

i was just hoping you would find one yourself

[amber hill]

yea

proof by counterexample

[amber hill]

sorry

:/

[pale epoch]

the most immediate examples are probably just two different constant maps

[rich siren]

that's what I tried at first

just flipping the co-domain

but maybe just scrambling them randomly is better

[pale epoch]

i mean just f(x) = 0 and g(x) = 1 and consider them as function {0, 1, ..., n} into itself

but then you might ask if it works for bijective functions, the answer will also be no

[rich siren]

Thanks for the in-depth help :)

[rich siren]

Is there a quick way to check your answers for these type of questions?

[naive saffron]

Fermat's little theorem

Or you can just use a computer to check if your answer is correct

[stray reef]

@sharp ledge do you still need help with this?

[sharp ledge]

Yup

[stray reef]

what's giving you trouble here?

[sharp ledge]

Any fastest way to count it ? I found a way but took time, where i count the prob for each possible scenarios from 0 heads to 10 heads and times their the number of heads from that scenarios

[proven silo]

variance of sum of independent variables is the sum of variances

since they are also iid, just compute var for the number of heads for the 1st throw

[coral raven]

given 2 N's and 6 X's, how many strings can you make with those 8 letters? and how many of those will have the N's next to each other?

[slate burrow]

so

so like 2?

oh 2*6?

[sullen thorn]

tl;dr need help with graph theory terminology

I'm doing a programming challenge involving finding the maximum number of mutually-exclusive pairs of integers from a list, and the only answers I could find on StackOverflow are these:

Your question is equivalent to finding a maximum matching on a graph. The nodes of your graph are integers, and your pairs (a, b) are edges of the graph. A matching is a set of pairwise non-adjacent edges, which is equivalent to saying the same integer doesn't appear in two edges.
A polynomial time solution to this problem is the Blossom algorithm also known as Edmond's algorithm. It's rather too complicated to include the details in the answer here.

If we view each number in a pair as node in a graph, we can build a bipartite graph, with edges between each node if there is a pair containing these two nodes.
So, this problem is reduced to find the maximum bipartite matching, which can be solved using classic Ford-fulkerson algorithm.

Problem is, I've never studied graph theory, so I have no idea what this means. Could someone please explain and help me understand?

The big thing I'm confused about is what "edges on a graph" means.

[tidal tulip]

someone could correct me if wrong, but they may mean edges where a is the source vertex and b is the target vertex, for each pair of vertices a, b in your edge pair

[sullen thorn]

I think you're right. I'm still trying to wrap my head around it, but that definitely helps.

Alright so I found a really helpful explanation of the second answer, but I don't at all understand the first.

[pale epoch]

"mutually-exclusive pairs of integers from a list"?

[sacred spindle]

(a,b), (c,d) s.t. a,b,c,d are unique

[rich siren]

True/False Let A = {2, 3} and B = {2, 3, 4}. Then B×A = {(2, 2),(2, 3),(3, 2),(3, 3),(4, 2),(4, 3)}

Hm I think this is true but chegg is saying it's false

[simple nova]

https://i.imgur.com/gYYS9kz.png

Anyone know how to do this question?

[rose cipher]

Hey I made a little mistake on my homework and I was wondering if I could get some help? Question was fairly simple, it gave us a bunch of relations and told us to find with are equivalent relations. I said that the following were equivalent relations but one of them is in fact not (going by how many points I lost). What did I do wrong? The set was S = {1, 2, 3, 4}. These all look equivalent to me unless I am missing something

[pale epoch]

you mean equivalence relations?

anyways, the second is not transitive

[rose cipher]

ah wow you're right. how did I miss that. thanks.

[long elk]

yo I'm in y1 discrete structures and need help with if-then statements, the question wants me to write "This integer is even if, and only if, it equals twice some integer" as a conjunction of two if-then statements

please send help

[sacred spindle]

The phrase “if and only if” is often represented by a bidirectional arrow $\Leftrightarrow$. That could be a good hint for you

[vital dew]

noah

[tidal tulip]

i am confused by the highlighted part of the proof, how is -m=1, is it because m=-1 so -m = -(-1) ?

[wooden spear]

No, what you said is backwards logic

They concluded -m = 1 because -m is a positive integer divisor of 1

And then they used that to conclude m = -1

[tidal tulip]

how is -m a positive integer divisor of 1 when 1 = (-1)(-1) and (1)/(-1) = (-1)

[wooden spear]

They were handling the case that m is negative. In this case, -m has to be positive

[tidal tulip]

then isn't -m what i said -(-1)?

im confused

[wooden spear]

Show me your logic for why

that is the case

[tidal tulip]

because m=(-1), n=(-1) and (-1)(-1) = 1

-m = -(-1)

with variable sub

[wooden spear]

The case they're handling only says m and n are negative

and that mn = 1

If you feel like that automatically implies m = n = -1, then hats off to you

but they are doing more explicit logic to arrive there

[tidal tulip]

i dont feel anything, i dont understand the proof

[wooden spear]

Then strictly speaking

[tidal tulip]

can you explain the proof

[wooden spear]

going from "m and n are negative" to " m=(-1), n=(-1)" is not a valid step

[tidal tulip]

because my interpretation of it is not valid

[wooden spear]

I think you have to see why your reasoning isn't valid

You gave an example of two negative numbers which multiply to -1, and then said m and n have to be those examples

[tidal tulip]

i dont understand the proof, so was assuming -m = --1

which is a wrong assumption

so i dont have a proof

[wooden spear]

ok so

[tidal tulip]

as i dont understand their proof

[wooden spear]

Goal: prove that mn = 1 implies that m and n are plus or minus 1

that's more or less the theorem statement, yea?

[tidal tulip]

yes

[wooden spear]

you understand up to the purple part I presume

[tidal tulip]

yes

[wooden spear]

That covered the case m and n are positive

Now the case remaining is m and n are negative

Those are the only assumptions so far

that m and n are negative

how to get from there to the fact that m=n=-1?

that's what the purple part answers

[tidal tulip]

yeah i dont understand the purple part, was hoping you could explain their logic

[wooden spear]

I lied when I said those are the only assumptions

The other assumption is that mn = 1

[tidal tulip]

right

i am following...

[wooden spear]

Therefore, (-m)(-n) = 1

[tidal tulip]

i dont get your jump

[wooden spear]

Just now?

[tidal tulip]

yeah

m and n are negative, so (m)(n) is a post number

where is -m and -n coming from

[wooden spear]

Do you agree that if mn = 1 then (-m)(-n) = 1 is also true?

[tidal tulip]

yes

[wooden spear]

That's all it is

one implies the other

[tidal tulip]

but they claim -m = 1

when -m = -1

[wooden spear]

Ya

No

m is negative, so -m is positive

[tidal tulip]

-m = 1 only if -m = --1

since m=-1

[wooden spear]

They got -m = 1 because -m is a positive integer divisor of 1

and they appealed to the case they already proved

to prove that -m = 1

[tidal tulip]

what does postivie integer divisor of 1 mean? because i take it to be k in a=bk where b|a

and 1/-1 = -1

and -1 isnt post

[wooden spear]

Slow down

-m is positive

Because m is negative

It totally makes sense to say -m is a positive integer divisor of 1

[tidal tulip]

ok

isnt m=1

[wooden spear]

No

[tidal tulip]

i meant -1

[wooden spear]

Yes

[tidal tulip]

you told me -m doesnt equal --1 when m=-1

so i am confused

[wooden spear]

-m does equal --1 but --1 is just 1

--1 is positive

[tidal tulip]

so how is this wrong

[wooden spear]

The logic was backwards

I said that first thing

[tidal tulip]

ok i will go back to look at it ty

[weary solstice]

Hey, I'm not sure about Blossom algorithm/Edmond's algorithm, but this picture shows what a matching is (the matching in the picture is not a maximum matching though). It's a selection of edges in the graph such that none of the selected edges share an endpoint. A maximum matching is the biggest set of edges satisfying that property in a graph.

[sharp turtle]

can i have a hint on this question?

Let G be a graph. A clique in G is a subgraph in which every two nodes are connected by an edge. An anti-clique, also called an independent set, is a subgraph in which every two nodes are not connected by an edge. Show that every graph with n nodes either contains a clique or anti-clique with at least $\frac{\log_2{n}}{2}$ nodes.

[vital dew]

TheToadSage

[sharp turtle]

i did try some testcases to observe the rule

but idk how to prove it

[void lake]

Can someone point me in the right direction on how to start this proof? I am having issues figuring out where to start on these. Maybe which type of proof and why?

[weary tiger]

looks like you want to use induction

basically you assume that the kth case is true and try to produce a series of statements that gets you to the k+1th case

then so long as some base case is true, all the following cases will be as well

[last timber]

@weary tiger no

@void lake if k is even
k = 2p

so n = 2^(2p)-1=(2^p)^2-1

[weary tiger]

u right

[last timber]

now use that

[void lake]

ohh I see, ok awesome that should help me figure it out, I got the k=2p so that makes sense

[weary tiger]

same thing i said but replace k with some number p ( k is even so k = 2*p for some integer p)

[last timber]

a^2-b^2=?

[void lake]

sorry I have been trying to figure it out, I am not sure what you meant here, but I need to get 2 factors from "((2^p)^2)-1" to prove it is composite right? That is my next step?

[last timber]

yes

[void lake]

Oh I just got what the a and b statement was haha, got it, thanks a lot!

[elder atlas]

how do i find the formula for this, i cant think of anything that would work

[lofty cloud]

From

#❓how-to-get-help

Rule 4

If your question has not been answered for a minimum of 15 minutes, you may use the Helpers tag once. Please do not try to bump your question using this ping unnecessarily. Do not abuse this ping. Do not individually ping users with the Helpers tag without their express permission.

[last timber]

anyway looks like it is something like a_n = 3a_{n-1} for n > 2

[elder atlas]

so should i make a_0 and a_1 as givens

[last timber]

why not this is legal rule

[elder atlas]

ahh ok i thought i had to come up with a formula where it calculates a_0, and a_1 using the formula

[sharp ledge]

Can someone helps with these two questions

[quaint star]

-2 is not a solution, plug it in and and check

[sharp ledge]

Yeah, the answer is the third one

Just that dont know how to get that

[quaint star]

Since you are given options, you can actually just plug in numbers to see which works

But to solve it from scratch:

4x + 5 = 0 becomes 4x = -5 = 8 (mod 13)

Because-5 and 8 are congruent mod 13

Does that make sense?

Now here, you can either use inspection to see that 4(2) = 8 so 2 must work. Or you can find the multiplicative inverse of 4 and multiply by it on both sides.

4(10) = 40 = 1 (mod 13) so 10 is the inverse of 4

Multiply both sides by 10 and get

40x = 80 which becomes x = 2 (mod 13)

And for the other question, you just want to reduce all the numbers mod 5. So 6 is congruent to 1, and -4 is also congruent to 1.

[sharp ledge]

How do you get this ?

[quaint star]

I subtracted -5 from both sides

Then replaced -5 with 8 since they are congruent mod 13

[sharp ledge]

So you are saying first we convert it to 0 = 4x + 5 = 13 mod(13) ?
Then minus 5 becomes -5 = 4x = 8 mod(13) ?

[quaint star]

Yes

[sharp ledge]

Ok

[queen flax]

how would i justify
p->q
q->p

---

∴ p V q

[queen flax]

∀x ∈ R+, ∃y ∈ R+
s.t. xy = 1
Is this valid?

[stray reef]

do you mean "is this valid" or "is this true"

@queen flax

[queen flax]

true, and i figured it out

it is, cause let y = 1/x, then xy = 1

i hope i did that right

Heres an easy one thats stumping me rn, 2am brain aint it

[sharp ledge]

Suppose that p and q are prime numbers and that n = pq.
Use the principle of inclusion–exclusion to find the number of positive integers not exceeding n that are relatively
prime to n

[sharp turtle]

<@&286206848099549185>

[plucky patio]

I hope this is the right channel for this. I'm supposed to show that if I have a graph with one vertex of odd degree then there's always a path from that vertex to another vertex of odd degree. I know that there always exists at least two verticies of odd degree so in the connected component of that odd degree vertex there's always another odd degree vertex. Since everything is connected I'm done. I must be missing something. Like am I supposed to show that connected implies that the path exists or what am I supposed to do?

like am I supposed to say anything else or am I just done?

[pale epoch]

if you know that the component has another odd degree vertex, you are done

[plucky patio]

wow

wtf this problem is supposed to give you 4 points. In the problem before this one you are supposed to show that in a graph, there are at least two verticies with the same degree and that problem gives you 2 points. How tf is this possible?

[pale epoch]

i mean you still need to argue that there is another odd degree vertex in the component, i guess...

[plucky patio]

ye but it like literally follows from the earlier problem

[pale epoch]

how?

[plucky patio]

I mean there must be another odd degree vertex in the component

[pale epoch]

yes, but it does not follow from "show that in a graph, there are at least two verticies with the same degree"

[plucky patio]

but if there is one odd degree vertex then there must be another one with odd vertex

am I missing something?

and they must lie in the same component

[pale epoch]

but why is there another vertex of odd degree?

[plucky patio]

because of the handshaking lemma which you already used in the earlier problem, right?

[pale epoch]

ok yeah, that works

[plucky patio]

oh okay lmao

[pale epoch]

handshaking on the component

[plucky patio]

ye right

okay great, thanks for telling me. I thought that something very fishy was going on here

[weary tiger]

Hello I have the following question in graph (network) theory. Given a cycle on n (n odd) nodes so that there is an edge between every consecutive node, and an edge between 1 and n. How can I find the "betweenness" of each edge? The betweenness is defined to be the number of shortest paths between all pairs of nodes that use that edge in the given context

Any hints would be highly appreciate as I have been stuck for quite a while on this problem

[carmine veldt]

Hi, how do you do this?

[cerulean wind]

do you have any thoughts?

[carmine veldt]

Yeah to try to write into cartesian products but I don't know how to do

[cerulean wind]

you tried drawing a picture?

[carmine veldt]

no, I'll draw one

[storm brook]

You should use the definiton of cartesian product: $A \times B = {(x,y) \mid x \in A \wedge y \in B}$.

[vital dew]

Campanha

[storm brook]

Then, proceed as you would proceed in other proofs of set theory.

If I may give you a hint, take an element $(x,y) \in (A \times B) \cap (B \times A)$.

[vital dew]

Campanha

[carmine veldt]

Thanks, I'm trying in this way

[carmine veldt]

Is ithe solution (A ∩ B) × (A ∩ B) ?

[storm brook]

Yes

[carmine veldt]

Thanks!

[storm brook]

yw

[exotic fog]

does this simplification make sense? is it correct?

https://cdn.discordapp.com/attachments/816668609191346256/900409375573807194/IMG_4659.jpg

[carmine veldt]

you would need to argue over semantics maybe

[carmine veldt]

btw, I know this is true, but do you know how prove it step-by-step formally? Thanks in advance

[exotic fog]

I need to translate it to english, but wanted to make sure if the logic simplification looks right

[carmine veldt]

I meant on latex

[ember obsidian]

claims of the form P if and only if Q are usually proven by showing P implies Q and Q implies P

[storm brook]

Exactly. First, assume that P is true and prove Q is also true. Then, assume Q is true and prove that P is true.

Suppose $A \times B \subseteq C \times D$. We can then say that $\forall (x,y), x \in A \wedge y \in B \implies x \in C \wedge \in D$. Therefore, $\forall (x,y), x \in A \implies x \in C \wedge y \in B \implies y \in D$, which means that $A \subseteq C \wedge B \subseteq D$.
Now, you should prove that Q implies P, which is pretty easy.

[vital dew]

Campanha

[carmine veldt]

Thanks a lot!

[storm brook]

I think that the expression "$\forall (x,y), ...$" is redundant. You can omit it.

[vital dew]

Campanha

[carmine veldt]

Ok 👍

[tidal tulip]

is this a correct interpretation of the proof high lighted in purple here

consider the m,n=1 case where both m, n are negative integers

by theorem T12 in appendix A we know (-m)(-n)= mn = 1

in this case -m is a positive divisor of 1,

so by theorem 4.41 we know -m <= 1

and since -m is a positive integer, we know -m = 1, hence m=-1

[marble pivot]

yep that's right

[tidal tulip]

ty

[marble pivot]

Let's say I have a choice function $$f: X \to \bigcup X,\ \text{where}\ \ \forall A \in X,\ f(A) \in A.$$ How can I prove that any such function $f$ is an element of $$\prod_{i \in I} X_i?$$ Is the set of all choice functions on $X$ precisely the above set?

[vital dew]

abs_0

[ember obsidian]

if your definition of the product is what i think it is then both questions are answered instantly

[marble pivot]

Oh lol

For some reason I thought the Cartesian product of an indexed family was some like… infinite tuple thing lol

Makes sense

[sullen thorn]

Subject: graph theory, maximal matching
How do I modify the Blossom algorithm to use one set of items as both the "jobs" and the "applicants" (in the job application metaphor)? Basically, to pair items from the same list together instead of matching the items of one list to the items of another.

[sullen thorn]

Or do I even have to modify it? I've only been working with the Ford-Fulkerson algorithm so far, which matches between two sets, but I don't fully understand the blossom algorithm

[onyx zephyr]

Do I need to remember the stirling numbers of the second kind or is there any easier way to do for example S(5,3)?

[north dust]

grrr, I'm not doing so well in my combinatorics class

[gritty crescent]

I think you could use some recurrence in terms of S(n,k) itself?

[vital dew]

Manan.

[gritty crescent]

Keeping in mind that S(n,n)=1

And S(n,k)=0 when k>n

[gritty crescent]

Correction, the second term on right is k×S(n-1,k)

[balmy dome]

does anyone know how to do part 2

[pale epoch]

use the extended euclidean algorithm

basically back substitute

[scenic vault]

can anyone help me find something. I think I might just be searching for the wrong thing

Im looking for some papers on descrete fourier transforms, specifically with how they change with time

as in, x[n] becomes something like x[n+t]

so really, im looking for how the frequency bins change over time and what it could mean

eg.. if you have a 4 point FFT, at t=0 it would use samples x0 x1 x2 x3, then at t=1 it would use samples x1 x2 x3 x4 .. and so on...

[scenic vault]

Is there an equation that says how the FFT output would change with time, given that all but one of the samples are the same and they have just been shifted left by 1 sample.

[mystic elbow]

Can anyone please help

[stray reef]

have you made any progress so far?

@mystic elbow

if you are stuck and don't know where to begin, then please say so explicitly

i promise i won't bite

[mystic elbow]

No I’m not getting how to do

[stray reef]

...okay

would you like a hint or an explicit instruction?

[mystic elbow]

Instructions

[stray reef]

consider the parities of the numbers before and after each move in the game.
if you pick two odd numbers, what is the result? if you pick two even numbers, what is the result? if you pick one odd and one even number, what is the result?

(i know it's hard, but i want you to answer these in complete sentences.)

[mystic elbow]

Ok wait

Wdym by results

Like odd/even?

[stray reef]

i mean the parity of the result, yes.

@mystic elbow is your internet malfunctioning or are you really spending this long thinking

[mystic elbow]

I didn’t check my phone sorry

I think when I pick 2 odds I get even

2 evens- 2 is even

1 odd 1 even would give even( coz 1+1=2 which is even)

?

[stray reef]

no

if a is odd and b is even then |a-b| is even, is that what you just asserted? (y/n)

[mystic elbow]

No

[stray reef]

1 odd 1 even would give even( coz 1+1=2 which is even)

[mystic elbow]

I did + not -

[stray reef]

did you even read the problem

[mystic elbow]

Yes I know it’s -

That’s what I’m abit confused now

[stray reef]

even, even -> even
odd, odd -> even
even, odd -> odd

[mystic elbow]

Yes

[stray reef]

now

in each scenario

how much does the amount of odd numbers change?

[mystic elbow]

I didn’t get u

[stray reef]

if you pick two odd numbers and replace them with an even number

you have 2 less odd numbers than what you had before

do you understand this or not

[mystic elbow]

Yes

[stray reef]

okay

can you tell me the change in the amount of odd numbers for the other two scenarios?

[mystic elbow]

now wewill have 4 even and 1 odd?

[stray reef]

no

that doesn't answer my question and also nobody said we had to begin with picking two odd numbers

in fact the problem says we need to prove something no matter how you pick the numbers

[mystic elbow]

ya this is one case when we pick two odd first, then take when we pick two even, and third one picking odd and even

[stray reef]

you do not need any case work you just need to answer my questions instead of ignoring them

cause what you're doing rn is ignoring my questions

if you want to do that then you must at least tell me "i will ignore your questions"

[mystic elbow]

Sorryyy I’m tryna do abit faster coz it’s urgent

[stray reef]

oh so now it's urgent.

and this only comes up now.

i'm out

[mystic elbow]

Sorry pls helpp

[marble pivot]

Let’s say $I, X$ are sets and there is a function $f: I \to X$. What does the indexed family ${X_i}_{i \in I}$ refer to exactly? The set $X$, or the function $f$, or what?

[vital dew]

abs_0

[marble pivot]

I imagine it’s the function since if I={1,2,3} and X={1,2} and
f(1) = 1
f(2) = 1
f(3) = 2
Then you want the indexed family to refer to (1,1,2) rather than just X lol

[quaint star]

You haven't really given much context, but I will asssume everything means what I think it means. X is a family of sets and f: I -> X is a function that maps to each i in I one of the sets in the family X. Then X_i refers to f(i).

[marble pivot]

Yes

Ok ok that makes sense thank you

[floral field]

For a cube in d dimensions, an exercise asked to give a formula for the number of ridges, and I came up with:

ridges = d(2^(d-1))

This should work for all d, right?

[cerulean wind]

what’s a ridge ?

[floral field]

So in d=2, it would be the same thing as one of the 4 sides

[cerulean wind]

so an edge

[floral field]

An edge yes

[cerulean wind]

there are 2^d vertices

at each vertex there are d edges that connect to it

but this over counts by a factor of 2

so there are d(2^(d-1)) edges

[crystal scarab]

I was wondering if someone could help me with this problem. I understand the equivalence relation but im not sure what [4] means?

[cerulean wind]

all the elements that are related to 4, that is, all x in A such that (x,4) or (4,x) is in R (by symmetry)

that is called the equivalence class of 4

[crystal scarab]

ahhh i see thank you very much so the only one would be (4,4) right? Since thats the only one that is being related to 4

[cerulean wind]

no

[4] = {4} since 4 is the only thing in A that is related to 4

[crystal scarab]

hmm got it seems i need to study equivalence class by x more ty

[languid moss]

Is anyone good with discrete math that I could dm about a proposal

Someone good with discrete math pls dm me

[floral field]

Ahh I see. What would be the formal way to prove this? The only thing I can think of is induction, but I'm not even sure how to start it that way

[cerulean wind]

i just gave you a formal combinatorial argument

[floral field]

Maybe a counting argument?

Ahh yes

Ohh

[cerulean wind]

more precise arguments need an explicit construction of the d-dimensional cube

[floral field]

Maybe something about the coordinates of the different vertices?

[cerulean wind]

well what is your definition of the standard d-dimensional cube

[floral field]

[0,1]^d

[cerulean wind]

because the coordinates (in Cartesian coords) could be arbitary

okay

that works

so look at one vertex right. going to be some binary string of length d

for now just look at the origin

how many other vertices are connected to it by exactly one edge?

[floral field]

In d dimensions, a vertex is connected to d other points

[cerulean wind]

okay great

well you already know that

[floral field]

Wait I didnt answer this question

[cerulean wind]

you just did

[floral field]

Oh okay

[cerulean wind]

like, you just told me that given any vertex in d dimensions in [0,1]^d, that there are d other vertices connected to it

do you need to prove that result?

[floral field]

No

[cerulean wind]

okay. first step done

since we could have done this for each of the 2^d vertices, then there are going to be a total of d(2^d) edges counted in this way

but by symmetry, we counted every edge twice

so we have to divide our answer by 2

[floral field]

Ahh

◾

[cerulean wind]

the top two vertices of that square count the top edge twice in this argument

[floral field]

Right

[cerulean wind]

same for every other pair of vertices that are connected by one edge

hence the division by 2

[floral field]

I see. Okay, I understand how we argued that. Thank you.

Are you familiar with Discrete Geometry by any chance?

[cerulean wind]

nope

[languid moss]

can someone good with discrete structures math dm me

[nova zenith]

Hey there is there anyone here who would be willing to help me in understanding how to find a recursive step from a function to then prove induction?

[surreal flower]

Oh man have i never thought i will be doing this

Using discord to find a math solution

[wild merlin]

i did the first part since it's the same as showing p(n-1) is the number pf partitions with the two largest parts distinct, and i did it showing a bijection

but for (b)

it doesn't work since it's now that the three largest parts are equal

does considering cases where the three largest parts are all equal or not all equal still work

it's really hard finding a bijection

[sullen thorn]

With the blossom algorithm in graph theory, can the starting edges be considered potential matches between items? Like in implementing it, would I check my condition to make starting edges?

I'm trying to make the max amount of valid pairs from a single set of integers

and I never did graph theory

[nova zenith]

Hey was wondering if anyone is good with induction here? I could use some help. Have no idea how to find a recursive step.

When you have a recursive step it should be used for Base Case through k and k + 1 correct?

[iron night]

[ \phi \colon n \mapsto n! \iff \phi \colon n_{i+1} = (n_i + 1) (n_i), \quad n_1 = 1, \quad i, n \in \N ]

is this what you want?

[\psi \colon n \mapsto 2^n \iff \psi \colon n_{i+1} = 2 \times n_i, \quad n_1 = 2, \quad i,n \in \N ]

[vital dew]

ricey

ricey

[nova zenith]

I'm not sure if this is what I meant or more specifically if that is what my teacher meant.

My teacher uses := to mean "is defined as"

[iron night]

oh sorry you can treat the colon as :=

[nova zenith]

Thank you

[viral vigil]

Does this membership table look right?

[weary tiger]

Seems good

[red drum]

Hey!, i really liked this, for b let's call r(n) the number of partitions of n in which the three largest parts are equal, q(n) the number of partitions in which the two largest parts are equal and s(n) the number of partitions in which the two largest parts are equal but the third largest part is different from them, then clearly r(n)=q(n)-s(n) so we just need an expression for s(n). Consider a function that takes the partition a+a+(a-k)+.... (k greater than or equal to 1 since (a-k) has to be different from a) to the partition (a-1)+(a-1)+(a-k)+.... the second partition is a partition of n-2 with the two largest parts equal and with no restriction to the third largest part, and it's easy to see this is a bijection, so s(n)=q(n-2)=p(n-2)-p(n-3) and finally r(n)=q(n)-q(n-2)=p(n)-p(n-1)-p(n-2)+p(n+3) i think there might some details to check for example when a=1 or stuff like that, but that's the idea 🙂

[viral vigil]

ok thx so much