discrete-math

[idle hazel]

yes my bad

[undone ibex]

Show that in any simple graph G there is a path from any vertex of odd degree to
another vertex of odd degree. I know the answer is yes, there is a path from any vertex of odd degree to another. Can anybody visually show me a graph of this?

[stray reef]

you have to be careful with quantifiers

it is NOT true that for any v, w ∈ G with deg(v) and deg(w) both odd there exists a path from v to w.

and it's pretty easy to construct a counterexample to that effect.

however if you mean that for every v ∈ G with deg(v) odd there EXISTS w ∈ G with deg(w) odd s.t. there exists a path from v to w, then the statement becomes true.

what exactly are you looking for here? an example of a graph with such paths highlighted for all odd-degree vertices? @undone ibex

[undone ibex]

yes please. I need a visual representation to explain this question.

[stray reef]

ok so here's a graph i drew without paying it much mind

and here are some paths between odd-degree vertices

the odd-degree vertices in this graph are A, C, D, F, G, J, M and Q

from A you can walk along the path AEBF to F

from C you can walk along the path CD to D

from D you can walk along the path DC to C

and so on

is this what you were looking for?

[undone ibex]

in a path, the vertices and edges cannot be repeated correct?

[stray reef]

the usage of the word "path" is not very consistent throughout the field

however for the purposes of the theorem you stated there is nothing wrong with allowing repeats, so long as we require that the other end of the path not be the same as its start.

[undone ibex]

it helped to see it visually. Thank you!

[undone ibex]

I have re-read this question a bunch of times, but nothing makes sense to me. Can someone explain how I can solve this?

Prove that a connected graph with n vertices has exactly one cycle if and only if it has

exactly n edges.

[serene marlin]

help, i have never been more lost in this class

[coral parcel]

Which of them?

[viral crown]

i think he means both

[true venture]

After drawing some graphs, it seems like for a connected graph with n vertices and n edges. You never have enough edges to make two cycles.
To have 2 cycles you need more edges

[true venture]

Think of the minimal number of edges you need for a graph of n vertices to be connected.
Will this connected graph of minimal edges have a cycle?

[serene marlin]

ya both, but 4 in paticular
4 I have 0 clue at all even wher to start
3 i have a 20%idea

[coral parcel]

Note that abcabc = 1001·abc

[serene marlin]

how do we get to that

cuz we have never learned that

so there must be some in between steps to arrive to that point

[coral parcel]

Uhm, that's just basic decimal arithmetic.

[serene marlin]

oh, ok then

[coral parcel]

For (4): Look for solutions modulo 3.

[serene marlin]

?

[coral parcel]

I mean, hopefully we agree that abc000=1000·abc, and abc000+abc = abcabc?

[true venture]

How is the second true?

123000 + 123 = 123?

[serene marlin]

yes

[serene marlin]

i think thatst what he means ya

that makes sense how u got to 1001

but im so confused how I would ever do this shit on an exam since I have no recolection and no info in the notes regarding 1001*abc = abcabc

now that I know I get it but if this question was on the exam and I never seen this in practice id be doomed

[primal moat]

You do not need notes for that. It is just basic arithmetic.

The second exercise is really nice.

[serene marlin]

how so

[true venture]

Oh and because 1001 is divisible by 3 primes every abcabc is?

[serene marlin]

ya 7,11,13

[primal moat]

As often, if you approach the problem in the right way, the solution comes to you.

[coral parcel]

Sorry, typo fixed.

[true venture]

Dang you knew those by heart?

[serene marlin]

I guessed and tested im ngl

but 1001 is supposed to be a known number

apparently

[serene marlin]

and that would be😭

is there any theorem that needs to be used here

or technique i can look up

dont really want the answer, just a step so I can atleast know what to practice

[true venture]

Pfffff

[primal moat]

Look at arithmetic modulo some number. In fact when you have such statements, it is likely that the answer is negative because it is much easier to prove that it is not possible than the opposite.

[viral crown]

who was the mf that pinged me

[serene marlin]

ok ill give it a shot

[primal moat]

All the numbers in the list satisfy a common property

[serene marlin]

all even?

[primal moat]

yes, but does that help?

you can also add 500 to the list and find a property that all the numbers in the list have besides 500

[weary tiger]

I have a kinda ambiguous question. If G is a particular graph with 8388608 vertices, each of which is adjacent to 50 vertices, and A is a particular vertex in G, can anyone tell me if it would be feasible for a normal computer to quickly find the shortest path from a randomly given vertex to A?

quickly being like, in under a second

I know I haven't given all the detail on what G is but I can do so if it matters (will be kinda complicated)

[coral parcel]

Under a second is probably pushing it a bit, unless there's additional regularity in the graph that you can exploit with an ad-hoc algorithm. Realistic CPU clock speeds lie in the low gigahertz, which means there's only time for a few dozen instructions per edge in the worst case where you need to look through all the edges before you find any path between your two vertices.

[weary tiger]

oh I have some more info that might help

[coral parcel]

It could be possible with a hand-optimized search in a close-to-the metal language, but probably not with off-the-shelf generic data structures to represent the graph.

[weary tiger]

the largest distance between A and any other vertex will be like 9 or something

according to someone else

but I know for sure it's 12 or less

I edited that a few times but it's correct now, I promise

[coral parcel]

Hmm, I still think you'll need to exploit whichever particular structure of the graph allows you to know those bounds, instead of using a generic shortest-path implementation, if you want it to be done in less than a second in the worst case.

If G and A are fixed, you could just precompute a table of distances to all the vertices. 8 MB isn't a lot these days, and looking up there would certainly be fast.

[weary tiger]

G and A are fixed yes

[coral parcel]

Yeah, then just tabulate the results.

[weary tiger]

hmm ok

now I just need to generate the graph...

thanks

[coral parcel]

There's a bit of a complexity/space tradeoff for what exactly to tabulate. Just distance to A from each vertex would be smallest (4 MB), but at each vertex you'd then need to enumerate all the neighbors to find a direction that decreases the distance. If you have 32 MB, you can instead store the exact neighbor that will take you closer to A.

[weary tiger]

I'd need to store one shortest path from each vertex to A, not just the distance

[undone ibex]

I need help figuring out what to do after using the induction hypothesis on this problem. Can someone explain how they got those steps.

[weary tiger]

to get to the ?? part, a -1/(k+1) was factored out of -1/(k+1) + 1/((k+1)(k+2))

you could multiply out what is in the ?? part to see it, if you don't

after that, 1 is rewritten as (k+2)/(k+2)

and after that, (k+1)/(k+1) is rewritten as 1

[undone ibex]

which 1? the 1- or the 1 / k+1

[weary tiger]

with more detail: $1-\frac{1}{k+2} = \frac{k+2}{k+2}-\frac{1}{k+2} = \frac{k+2-1}{k+2}=\frac{k+1}{k+2}$

[vital dew]

Botnuke

[coral parcel]

But if you just have the distances, and you start from one vertex, you can iterate through its neighbors to find one that has a shorter distance than the vertex you're at (which must then be shorter by exactly 1). Then you can make a shortest path from your starting vertex by going to that neighbor and continue by the same strategy until you reach A.

[weary tiger]

is that dynamic programming?

[coral parcel]

I suppose you might call it that. (But I wouldn't say the concept fits exactly, at least as far as I can immediately see).

[weary tiger]

ok I see what you mean now, interesting

[coral parcel]

In fact, if we really want to save on table space, we only need to store the distances to A modulo k for some fixed k >= 3. That will allow us, from any vertex, to distinguish between neighbors that are closer to A, and neighbors that are farther from A or the same distance (since the A-distances of two neighboring vertices cannot differ by more than 1).

[weary tiger]

lol, we don't need to go there

[true venture]

Howard, how many ways are there to express the number 20 as the sum of a string of positive integers, where each digit differs by at most 1? Example 5654 is one way for 20.

You better know this Howard

[undone ibex]

What is the difference between a "proof by contradiction" and "proving the contrapositive"?

[weary tiger]

Some examples you might want to consider:
All cows are dogs. Here is a cow which is not a dog. So, it is not the case all cows are dogs.

All toucans are birds. All things which are not birds are not toucans. I have proved that all things which are not birds are not toucans, so I have proved that all things which are toucans are birds.

[vital dew]

3080

[weary tiger]

Fuck

\begin{align}
(P \rightarrow ( Q \land \neg Q)) \implies \neg P \text{ Proof by Contradiction} \
P \rightarrow Q :: \neg Q \rightarrow \neg P \text{ Contrapositve}
\end{align}

[vital dew]

3080

[viral crown]

in simpler terms:
direct is: if A, then B
contradiction is: If not A, then B
contrapositive is: if not B, then not A

"If it is raining, the ground outside is wet." --> "If the ground outside is not wet, then it is not raining."

[weary tiger]

"contradiction is: If not A, then B"
Is this true? @viral crown

I guess ~A > B :: ~B -> A

[viral crown]

that's what i was thinking

since contradiction is $\neg\neg A \to A$, in logic

[vital dew]

valley

[viral crown]

and im not even gonna get into the differences between contradiction and negation >.>

bc it still confuses me

[weary tiger]

No sorry, I think that is incorrect. When you do proof by contradictions it is necessary to imply something causes a contradiction.

[weary tiger]

Double negation is the same as no negation

[viral crown]

http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/

uhhh

no

that was for 3080

[weary tiger]

I don't think the problem here is the nuance between proof by negation and contradiction. It's more that (A > B) > (~A > B) doesn't seem to show an immediate contradiction at least.

[viral crown]

hm

[undone ibex]

when do you use contradiction? how are most of the questions structured?

[viral crown]

prove __ is not ___

[weary tiger]

Ah alright

[keen geode]

Just need to make sure, this is a simple question on whether these two statements are true or not

[pale epoch]

well, are they?

[keen geode]

I mean, I'd assume so

but I don't know for a fact

[pale epoch]

you assume correctly but you should review the definitions until you dont have to assume

[sour onyx]

Strange question but I was doing exercise 1-12 of a walk through combinatorics and it mentions heaps of stones how many stones is in a heap more than one I assume but is there like a defined number?

[stray reef]

can you show the entire problem @sour onyx

[stray reef]

right

from this it can be seen that a heap must contain at least one stone, but i do not see any indication of all heaps containing more than one

[sour onyx]

Oh wait

I think I misread the question my bad

I was thinking they had to placed into the smallest heap not a smaller heap

[coral parcel]

Cute problem.

[weary tiger]

Does anybody know how I would go about solving this?

[stray reef]

are there any types of ppl besides knights and knaves here?

@weary tiger

[weary tiger]

nope

[stray reef]

right

there's at least one person whose type you can deduce immediately

[weary tiger]

U?

is a knave

[stray reef]

U is a knave, yes.

[weary tiger]

you know what

i might take another stab at it based on that

that might be the thread that unravels it all

[stray reef]

i can see a solution that requires a little bit more work

[weary tiger]

trying it again, all i can really deduce that X's statement is false 😦

Oh wait, mhm, maybe not.

[stray reef]

try thinking about like... what if there's exactly 1 knight? exactly 2 knights? exactly 3 knights? and so on

and who turns out to be right in each case

and find which cases are consistent

[weary tiger]

ill give it another shot based on that

[sour onyx]

I am stuck on this, I've tried recontextualizing this as sets A_1 through A_4 and sets B_1 through B_5 which are made up of elements of the A sets but I still don't see where it requires at least 2 be moved to smaller sets or the pigeon hole principle

[unique swift]

How many stones do you need to make a heap??

[sour onyx]

I would assume at least one like Ann said

[unique swift]

If you just need one stone then it is not necessary to take 2 stones

But I think that you should assume that at least two stones make a heap

[obtuse lance]

if someone in the real world pointed at a single grain of sand and told me "this is a heap of sand" I would shake my head

[pastel hollow]

what if it was a really big grain of sand

[coral parcel]

Here's a trick: ||assign to each stone the score 1/k where k is the number of stones in the heap it is in. How does the sum of all the scores behave when you rearrange them into 5 heaps?||

[coral parcel]

The claim is true even if we allow a single stone to make a heap. If a "heap" needs k stones, then a similar argument shows there must be at least k+1 stones that end up in a smaller heap than they were in before.

(Intuitively I'd think there must be a significantly larger lower bound, possibly even 2k -- but I don't have a proof of that ready).

[sour onyx]

I also had a question about writing the answers out, can I simply go there are n balls and m boxes therefore via the pigeon-hole principle this statement is true/not true, would you say that is formal enough?

[coral parcel]

Is that still the heap question? In that case, what you write leaves me with absolutely no idea what the argument you're trying to express is.

[sour onyx]

Oh no just in general proof writing

[coral parcel]

It's too general to answer in that shape.

[coral parcel]

You need to explain enough to make clear to the reader (a) what is is you count as balls and what you count as boxes, (b) why your counts of n and m are correct, (c) how you know that n>m, and (d) how the fact that there's a box with more than one ball implies "this statement is true/not true".

[tall oxide]

Given that a, b is real. The sum of a+b is 9. Is it a proposition?

[weary tiger]

can someone explain the reflection principle in set theory to me?

[north bay]

Does anyone know how to find a formula for this?
In class I learned to call a_n = c^n
and then find roots of equation and do
a_n = A*root(1)^n + B*n*root(2)^n

but now I have the independt term 3 so I guess I can't do that anymore

[cerulean wind]

do you know about generating functions? @north bay

[north bay]

yeah!

[cerulean wind]

try that

[north bay]

mhmm but how do I do that with generating functions ?

[cerulean wind]

set $A = \sum_{n=1}^{\infty}a_nx^n$. Now you have
$$A=\sum_{n=1}^{\infty}a_nx^n=\sum_{n=1}^{\infty}\left(4a_{n-1}-3)x^n$$

[vital dew]

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

[cerulean wind]

try getting the right hand side to look like 4A + (some other stuff)

then recall some general formulas for infinite series to finish it off

[north bay]

ooh alright!! I'll try that thank you very much

[cerulean wind]

if that doesn’t work, then you solve the recurrence without the -3 and then guess the rest

i would start by guessing a linear polynomial

[north bay]

mhmm I was struggling with the series method
I had 4a_0 + 4A -3/{1-x} = A
Guess I'll give that a try as well

if I ignore the -3 I get a_n = 2^{2n+1}
cause a_0 = 2 was given

[north bay]

I got with the second method you metnioned thank youu !!!

[cerulean wind]

nice

[wide vine]

@sacred dune did you ever get a solution for that problem (something about the solutions between -1 to 1 is fixed by an upper bound)?

[sacred dune]

I’ve had other things on my mind so haven’t thought about it

[wide vine]

Oh I thought they might have provided a solution

[north bay]

Given the set [n] = {1 , 2 , ... , n}
how many ways can we choose two subsets , S and T such that T C S ( S contains T)

the answer should be 3^n

I was trying to find a way to get the binomial expansion of (2+1)^n

but can't think of any way to do so

any hints ?

[obtuse lance]

there are n choose k ways to make a subset of [n] with k elements, now for each of these sets, how many subsets does it have?

[north bay]

uuh wait let me try to see if I can see it by drawingsome smaller examples for that

[obtuse lance]

sounds like a good plan 👍

[north bay]

uuh you have K choose Q
for Q = {1 , 2 , ... K}

I guess

I could do a summation for all Q's

but that could be also done for all K's

I think

or I am overcomplicating things

[obtuse lance]

this doesn't make sense, n choose k is a number computed with n and k also being numbers

[north bay]

oh

[obtuse lance]

3 choose 2 is the number of ways to pick 2 objects from a set of 3, like {a,b,c} has {a,b}, {a,c}, and {b,c} as subsets, so (3 choose 2) = 3

you can compute n choose k as n!/(k!*(n-k)!), you should probably familiarize yourself with that first

[north bay]

yeah

my brain is fried rn

k let me think a little more about this

@obtuse lance Suppose [n] is {1,2}
so there are the subsets { } , {1} {2} {1,2}
so like for k = 0 there is 1 subset which is {}
for k = 1 there are 3 subsets: { } {1} and {2}
for k = 2 there are 4 subsets { } {1} {2} {1,2}

that's what you meant earlier right ?

[obtuse lance]

almost, I broke it up in two ways that might have been a bit confusing

in terms of n choose k, there are:
for k = 0 there is 1 subset which is {}
for k = 1 there are 2 subsets: {1} and {2}
for k = 2 there is 1 subset {1,2}

then for each of these I can count the number of subsets of any of these, since they're the same up to relabelling the elements

well the only case to consider is {1} and {2} both look identical cause they're a relabeling of the other

{} has the 1 subset {}
{1} has the 2 subsets {} and {1}
{1,2} has the 4 subsets { } {1} {2} {1,2}

so altogether this combines as $$\binom{2}{0}*1 + \binom{2}{1}*2+\binom{2}{2}*4$$

[vital dew]

Merosity

[obtuse lance]

hopefully after looking at that for a bit it's clear what came from what and how that relates back to (1+2)^2 like you were asking earlier

maybe try doing the n=3 case worked all out to help see the pattern better

[north bay]

yeah! That definitely helps a lot !!

thank you so much !!

I'll try the n = 3

[analog tinsel]

Hello together !
I am trying to figure out right now whether or not a single vertex can be viewed as graph or not. Unfortunately I couldnt find a satisfying answer to this question on the internet. The general definition left me a bit unsure about it as I am really confused right now. Thanks for any help !

[wide vine]

I don't see why you can't call it a graph

I would think you would need to define an edge from itself to itself

To have an edge

Or maybe that is even okay

[analog tinsel]

I dont see a reason either. I am just trying to prove some statements and in case a single vertex could be considered a Graph they appear very bizarre to me

[wide vine]

You define the set with one vertex and then the set with edges can be empty I suppose

[analog tinsel]

yeah thats what I also thought

[wide vine]

https://proofwiki.org/wiki/Definition:Edgeless_Graph

[analog tinsel]

I mean can you tell me if I am right by saying that a 4-subdivision Graph H of a undirected simple Graph G can be not tripartite because if G is a single vertex you only have one vertex and therefore cant divide any edges and as a result of that you dont have a tripartite Graph?

[analog tinsel]

thank you

[wide vine]

Apparently you can have null graphs which I guess makes sense but doesn't seem useful

[elder sky]

I like geometric sequence

[analog tinsel]

same with 2 unconnected vertices

[analog tinsel]

well in reality if you are trying to model something I believe it can happen to you that none of your vertices are related to each other

[wide vine]

Sorry I mean a graph with no edges or vertex

https://mathworld.wolfram.com/NullGraph.html

[analog tinsel]

oh well ok a NULL graph is not what I meant

[wide vine]

Yeah I can see nodes with no relationship

[analog tinsel]

but yeah I agree with you, I dont see either why one would want to use that

[analog tinsel]

wdym exactly ?

[wide vine]

No connection

Like edges

[analog tinsel]

yeah

but I didnt quite get what you wnated to say

[wide vine]

Anyways your question you had, I am not sure.

Not sure what a 4-sudvision part means

Is that connected with the idea of cut vertices?

[analog tinsel]

sry I couldnt figure out what the exact english word is. So if you have an undirected Graph G (simple one, no double connections between vertices etc). Then you have to divide every edge at least once and at most 4 times. So dividing means you "insert" vertices into that edge. And that gives you a Graph H which is supposed to be a subdivision graph of G

[wide vine]

Oh

I see how that would be weird with the single vertex case

More so if it has no edges

[analog tinsel]

yes thats what I mean

like two vertices without any edge inbetween

now I thought that except for these two cases it should always have to be a tripartite graph because you have to have at least one edge from G that turns in to a tripartite subgraph which makes the entire Graph H a tripartite Graph. But I am unsure if I missed something in the defintion of graphs

[sour onyx]

There's a paper about that here if you wanted to read more https://link.springer.com/chapter/10.1007/BFb0066433

[wide vine]

paywalls

[sour onyx]

||scientifichub||

[wide vine]

The graph with no points and no lines is discussed critically. Arguments for and against its official admittance as a graph are presented. This is accompanied by an extensive survey of the literature. Paradoxical properties of the null-graph are noted. No conclusion is reached.

Some writers in graph theory, presumably by imitation, have introduced the concept of a (or the) "null-graph" -having no points and no lines; see Figure 1.

off to a good start

@sour onyx You can have vertices without edges but you cant have edges with vertices, right?

like you can't have G={{}, {{a,b}}

but you could have

[coral parcel]

An edge needs vertices to end at.

[wide vine]

yeah that is what I was assuming

[sour onyx]

Correct me if I'm wrong Troposphere but an edge must connect at least one vertex (in which case it connects to itself)

[coral parcel]

Yeah, if you allow loops in your graphs.

[analog tinsel]

Isnt an edge just representing the existence of a relation between two objects ?

so therefore an edge without vertices would make very little sense in that context imo

[wide vine]

not sure if any of this is related to what you said but The most convincing argument in favor of admitting the null-graph is that this assures that the intersection of any two subgraphs of a given graph is always a subgraph. In particular, the collection of all subgraphs of G then forms a boolean algebra, in which the null-graph is the zero element.

maybe this is unrelated to the problem you had though

[analog tinsel]

hmm well this thing with the proof or disproof I had to make, I think I have to discuss that again with my group. Maybe they all agree on what I thought

and this whole thing with a Null graph seems a bit funny to me lmao as I said you can have two object that arent related to each other like 1 and 2 dont divide each other so in this relation they wouldnt have any connection but you cant say that two nonexistent numbers divide each other. I hope what I say makes kind of sense. But in the end I am definitely not an expert on graphtheory, that was just my first thought on this nullgraph discussion

Oh well maybe my point is more about edges without vertices than about nullgraphs. Yeah well Im sorry

Edges without veritces dont make too much sense to me but a null graph could be yeah

[hollow flower]

Hi, I have a question about Graph Theory. To make a non transitive graph into transitive with least amount of connections. Is it like this we do it?

this tells that if xRz and zRy, xRy should exist

and to make the whole graph transitive, we must add connection across all nodes like this right?

why I am asking, because I am a bit lost on what transitive means.

I just relized, that I converted the graph to be Symmetric.

[vital dew]

AC18

Let $\sum_{i=1}^{100} c_i = 100$ and $\sum_{j=1}^{100} c_j = 10$
then  $\sum_{i=1}^{100} \sum_{j=1}^{100} c_i +  c_j = \sum_{i=1}^{100} c_i + 10 $
= $ 100 + 10*100 = 1100 $

[gentle sky]

^Is this conceptually correct

[golden thunder]

100 * 100 + 100 * 10 ?

[gentle sky]

How so? would we not just leave the c_i term untouched for the inner summation?

[golden thunder]

$\sum^{100}(100 + 10) = \sum^{100}100 + \sum^{100}10$

[vital dew]

pewdssssssss

[gentle sky]

But isn't the inner summation from j=1 to 100, how would that evaluate the c_i terms in the inner summation?

[golden thunder]

$\sum^{100}c_i + c_j = \sum^{100}c_i + \sum^{100}c_j$

[vital dew]

pewdssssssss

[stray reef]

uh

can you start from the beginning?

[golden thunder]

hmm?

[stray reef]

bc like, your premise seems to imply 100=10

$\sum_{i=1}^{100} c_i$ and $\sum_{j=1}^{100} c_j$ refer to \textbf{the same summation}. how can the same sum equal 100 and also 10 at the same time?

[vital dew]

Ann

[stray reef]

(it can't)

[golden thunder]

im guessing they are different

[gentle sky]

Oh sorry, if that seems to be the case I meant for c_i and c_j to represent two different sequences, let me rephrase and ask again

[stray reef]

???

oh

[golden thunder]

i mean the question wouldnt make sense if they were the same sequence lmao

[stray reef]

it's AC18 who asked

you default pfp gremlins are so easy to confuse with one another

[golden thunder]

gremlins?

https://tenor.com/view/spit-it-out-spit-disgusting-gif-16413711

[gentle sky]

Yes😅 Sorry if my account isn't too distinctive

But nonetheless, I hope the question is clear now?

[golden thunder]

yeah, just expand the sums

[gentle sky]

The part which is confusing me is the inner expansion, would the c_i sequence just be constant in the inner summation? since the summation is from j=1 to 100 ?

[golden thunder]

they will be constants in the outer sum

[golden thunder]

.

then apply the given sums for c_i and c_j

100 and 10

[golden thunder]

then this

[gentle sky]

Umm, sorry if this is dragging this too long if the sum is $$\sum_{i=1}^{100}\sum_{j=1}^{100} c_i + c_j $$ even though the inner summation is j = 1 to 100, we would still evaluate the $c_i$ sequence in the inner sum?

[vital dew]

AC18

[golden thunder]

🐸

oopsie

the c_i is treated as constant yes

in the inner sum

[gentle sky]

So is my initial answer correct?

[golden thunder]

hmmm

i dont think so

$\sum^{100}_{i=1}100c_i + 10$

[vital dew]

pewdssssssss

[golden thunder]

after evaluating the inner sum, do you aggree

[gentle sky]

Oh right Yes!, its clear now

[golden thunder]

👍

[gentle sky]

Thanks so much!

[pearl thicket]

Magician took out 5 rabbits from 5 distinct hats. Then he put them one by one back to each hat. On how many ways he could do it such that:

a) none of the rabbits ended up in the same hat as before

b) exactly 2 rabbits ended up in the same hat as before

how can the a) be done? From a its easy to derive b I guess, but I cannot come up with an algorithm that would take into account the none of the rabbits ended up in the same hat as before clause.

[obtuse lance]

maybe it's easier to think about how to end up with at least one in its original hat, and subtract that off from the total number of ways to place in hats

[pearl thicket]

_ _ _ a _ - one of the places is constant, so the total of these is 4!? Am I correct?

[obtuse lance]

try working it out for 3 rabbit case by hand and see if the logic works

[pearl thicket]

welp, not really

[pearl thicket]

I am not sure how to interpret the clause Then he put them one by one back to each hat Technically for n=2 (n - # of hats and rabbits). There's only one placement that satisfies the conditions, but there are the 2 ways to get into that placement. Assume that {a, b} is the initial sequence.

_ _ -> b _ -> b a
_ _ -> _ a -> b a

[tidal tulip]

why is the mapping below not a function

f: R -> RxR

defined by f(xy) = (x,y) for all xy in R

would this be a correct evaluation to show why it’s not well-defined

f(3) = f(1*3) = (1,3)
f(3) = f(3,1) = (3,1)

so it’s not well-defined?

[pale epoch]

sure

well, minus the typo

(i assume it is a typo)

[tidal tulip]

oh yeah 3*1

what’s confusing to me about the problem is it just says R

but x and y are two numbers in R and xy is in R, so if i pick x and y and multiply them together then i get an singular input but i have to start with 2 numbers to get that input (namely 1 and 3)

so is it fine i did it that way? picked 2 numbers to get a single input like that (namely 3)

otherwise i don’t know how to get xy if i can’t start with an x and a y

[pale epoch]

I don't really see where you are confused, sorry

[tidal tulip]

f takes an input xy

i have to have an x and a y to begin with to get xy

so is it fine to pick an x in R, y in R

and multiply them together to get xy

and then evaluate f under xy like f(xy)

[pale epoch]

well, the definition implies that a number can be factored, yes

this factorization is not unique

[tidal tulip]

ok that makes sense

[pale epoch]

so its not a function

maybe its worthwhile to note that its not even unique up to order

f(4) = f(4*1)) = (4, 1) != (2, 2) = f(2*2) = f(4)

[tidal tulip]

i am trying to work on the below problem, is my 1-1 proof correct? how do i work on the onto part?

f: R->R
f(x)=1+x^2

Prove if f(x) is 1-1 or onto

1-1:
f(x) is not one-to-one since
f(2)=f(-2)=1+(2)^2 =1 +(-2)^2 = 5
But 2 != -2

Onto:
Let y in R,
Then +/-sqrt(y-1) is in R.. oh wait is isn’t for all x (this is not closed if x<1 stuck here) — not sure how to proceed as usually you solve for x in the expression y = <expression with x> and then let that x be your x in f to show the function is onto and in this case the x i solved for isn’t closed under the reals when x<0 so not sure what to do from here

[pale epoch]

the 1-1 thing is correct

did you try graphing it?

[tidal tulip]

f(x)? not yet let me try

[pale epoch]

there is a pretty simple thing you can notice

[tidal tulip]

ok it doesn’t pass the hortizonal line test

so not 1-1

passes the vertical line test so is a function

not sure about the onto thing

[pale epoch]

look at the y axis

[tidal tulip]

ok so 0 in y isn’t mapped to anything from x

so it isn’t onto

[pale epoch]

ye you just have to figure out a reason why

[tidal tulip]

how do i write this up formally in a proof to show it isn’t into?

[pale epoch]

i dont know what else to say without giving you the reason

just uh

there is a reason why your attempted argument fails for negative numbers (or numbers < 1)

none of them are in the image

and for a simple reason

[tidal tulip]

hm

Onto:
Let y in R,
Then x=+/-sqrt(y-1) is in R if x>0.
it x<0 then x not closed under square root.

not sure how to go further to justify this

because i could theoretically pick a different x

[pale epoch]

pick some x

when is x^2 + 1 say negative

[tidal tulip]

which is only when x^2 is a negative number larger than 1

but that’s impossible since x^2 is always positive

[pale epoch]

indeed

it can be 0, too but yeah

[tidal tulip]

onto:
for f(x) to be onto then for any y in R there is an x in R such that f(x)=y.

this means if y in R is negative then there is an x in R, such that f(x)=-y

then pick an x where y=x^2 + 1 is negative , but notice that for y to be negative x^2 has to be negative and this is impossible since there is no real number x in R that makes x^2 negative. therefor f(x) is not onto.

how is that?

[tidal tulip]

seems fine to me but wanted to check

@pale epoch

[pale epoch]

if y is negative, then -y is positive

I'd just write x^2+1>=1

[tidal tulip]

ty

[hollow flower]

S = {x, y, z, w}, R = aRb if (a, b) ∈ {(x, x),(x, z),(z, x),(z, y)}: This should be the graph if we draw it. My question is following, How to convert this graph into transitive? I know that because of x -> z and z -> y, We must add a new directed connection that goes from x -> y and another connection z->z for it to be transitive. However, What about the vertex W that have no connections at all?

I am not sure if it will be transitive, if leaving out w

[hard citrus]

Nothing, you leave it as is. A relation is transitive if aRb and bRc then aRc. However, since w is in no relation with any element, then the implication is vacuously true.

However, you are missing one more directed edge in that graph.

[hollow flower]

okay so that means only x->y needs to be added for it to be transitive.

all singleton vertices is per automatically transitive if I understand it correctly? 🙂

[hard citrus]

A vertex itself cannot be transitive, but if a vertex is in no relation with any other vertex in a graph (including itself) , then a transitive closure (making the graph transitive) will also not include any paths from that vertex to another

[hollow flower]

thank you, so the next question on this one. if I want to convert it further so that it will become an equivalent relation. This means that All vertices must be reflective like x->x. And also we need to create symmetri.

Those that means W have to be included in this case?

[hard citrus]

That's correct

When you want to make some relation R an equivalence relation, you first make it reflexive, then symmetric, and at last transitive. So making it reflexive will include the edge (w, w) in your new R.

[hollow flower]

yea, that was what I thought 🙂

okay, that makes more sense now 🙂

thank you so much @hard citrus

[hard citrus]

Np

You can try to see why the order reflexive to symmetric to transitive matters by constructing some arbitrary relation yourself

[hollow flower]

that is a good exercise to do, thank you so much.

and have a nice upcoming week

[tidal tulip]

how would you formally prove this more condensed

[river imp]

how can i gain access to the advanced math> ? I just got into a phd program in pure math

[stray reef]

#get-advanced-access

[raw wedge]

is discrete math worth learning if i want to go into the medical field?

[sleek loom]

does this denote an open interval or a set of ordered pairs?

[ember obsidian]

here (a,b) denotes an open interval

[sleek loom]

thanks

[coarse lodge]

hello guys, i really need help with this induction proof exercise as it's way different than any other i've seen so far. Please help

[rich bronze]

I think it should be for m>=3

For less than three it would be nonsensical

[little prism]

induction isn't great to prove this because in the induction step you will have to know how many subsets with 2 elements there are. unless you already know that

[rich bronze]

True

Induction would be a bad way to do this

This is a simple combinatorial question

[little prism]

you could also prove the more general statement that there are $\binom{m}{k}$ subsets with k elements. then you could use that in the induction step for k and k-1

[vital dew]

Denascite

[little prism]

but yeah while induction works, it kind of misses the point

this is a statement about how many ways there are to choose something by going step by step and choosing stuff along the way

[coarse lodge]

i havent done cominatorics yet and the exercise requires it

[coarse lodge]

how did you come up with that ?

[little prism]

how do you want to choose 3 elements if you have only 2 elements to choose from

[coarse lodge]

?

[little prism]

although I guess technically the formula outputs 0 in that case so it works out

[coarse lodge]

i wanted to know the way he came up with that

if n = 3 it's 1

[little prism]

well you can't choose 3 elements if you have less than 3 elements to choose from

[coarse lodge]

if n = 4 it's 3

[little prism]

so for n=2 the problem doesn't really make sense

[coarse lodge]

yeah i got that part

shouldn't it be n > 3 and not n>= 3?

why 3 is included though

[little prism]

well for n=3 it makes sense

[little prism]

like you said here

there is 1 way to choose 3 elements from 3 elements

[coarse lodge]

ooooh now i get it

the plugging in of number is actually telling me how many ways i can get the subsets right?

[little prism]

well that's what you want to prove

[coarse lodge]

yeah now i get it

but is this enough?

can i just end it like this?

[little prism]

so far you haven't proved anything

why is that formula correct

why not something else

[coarse lodge]

yeah

how do i prove it now

i just know it works for n >= 3

like it's the base case

[little prism]

how many ways are there to choose the first of our three elements

we are going to do the combinatorial proof, not induction

[coarse lodge]

I didn't study it yet and the exercise asks for induction unfortunatly

[little prism]

do you know what $\binom{m}{k}$ is ?

[vital dew]

Denascite

[little prism]

"m choose k"

[coarse lodge]

no

only know induction

[little prism]

ok I don't have enough time to do the whole induction proof with you. I will give you a roadmap:

(1) Show that there are $\frac{n(n-1)}{2}$ ways to choose a subset with 2 elements from a set with $n$ elements, again per induction. to see this, note that any subset with two elements of ${a_1, \ldots, a_n}$ is either a subset of 2 elements of ${a_1, \ldots, a_{n-1}}$ or of the form ${a_i, a_n}$ with $1\leq i\leq n-1$. Use the induction hypothesis to show how many subsets there are of the first form and hopefully you know how many subsets there are of the form for the second one. add those two numbers and you get your induction step.

(2) Repeat the same but now for 3 elements. Each subset of with 3 elements of ${a_1, \ldots, a_n}$ is either a subset of ${a_1, \ldots, a_{n-1}}$ with 3 elements or has the form ${a_i, a_j, a_n}$ with ${a_i, a_j}\subseteq{a_1, \ldots, a_{n-1}}$ being a subset of ${a_1, \ldots, a_{n-1}}$ with 2 elements. from the induction hypothesis we know how many subsets there are of the first form and from step (1) we know how many subsets there are of the second form. again add those two numbers, simplify and that's your induction step

[vital dew]

Denascite

[little prism]

it's a lot of work but well that's what your course wants

the combinatorial proof is essentially a one-liner

[coarse lodge]

thank you vert much man you helped me a lot

[little prism]

for completeness I'll give you the combinatorial proof

there are n ways to choose the first element we want, n-1 ways to choose the second way we want and n-2 ways to choose the third element. but doing it that way we overcount the same set 6 times, because we can pick the subset {a,b,c} in 3!=6 different orders. so we have to divide by 6. in total n(n-1)(n-2)/6

[coarse lodge]

thanks

[tidal tulip]

can i get a proof check

f: R->R
f(x)=1+x^2

Prove if f(x) is 1-1 or onto

1-1:
f(x) is not one-to-one since
f(2)=f(-2)=1+(2)^2 =1 +(-2)^2 = 5
But 2 != -2

onto:
for f(x) to be onto then for any y in R there is an x in R such that f(x)=y.
this means if y in R is negative then there is an x in R, such that f(x)=y

then pick an x where y=x^2 + 1 is negative , but notice since x^2 +1<0 this implies x^2 < -1, which is a contradiction since x^2 is always positive.

Thus there does not exist an x in R such that for a negative y in R f(x)=y, hence f(x) is not onto.

namely onto case

[vale cairn]

Sure that works

Though for brevity it suffices to say there's no x with x^2 + 1 = 0, for example

[viral crown]

with a little adaptation, your argument works for x^2 + n

so there's that!

[wide vine]

Anyone know what results if you have a big Cup of a set that goes from 0 to inf but adds an addition 2 elements per union vs an addition of 1 element per union

for example
{1,2}, {1,2,3,4}, {1,2,3,4,5,6}

vs
{1}, {1,2}, {1,2,3}

If you take the unions of them up to infinity
will their difference be the empty set?

A= {1,2} U {3,4} U {5,6} ...., B= {1} U {2} U {3} ....

A-B = ??

<@&286206848099549185>

This questions is related to this stats question and I can't seem to understand their logic.

I don't understand how it would make sense for the solution to be empty ie 0 chips when it appears after every iteration you gain +9 chips

^ this is the solution in the back of the book and I don't see how it makes sense

[hot valley]

Hi, does anyone have notes about Hashing Functions and Cryptography?

[light heath]

Is this a good proof to show you can tile a rectangular checkerboard with an even number of squares using dominos?

[torn coral]

i don't think you're demonstrating that the tiles can be placed into the board

just that some number of dominoes contain a number of whole squares that is equivalent to the board

you can also explicitly state you're not considering 1x1 size boards, as these aren't guaranteed to have an even number of squares

[light heath]

alright thanks Ill redo it and change my approach

[torn coral]

if you want a tip || consider the base case of a 2x2, you can always fit dominoes either vertically or horizontally into that, what happens when you go from 2x2 to 3x3, how might you fill that remaining space ||

[light heath]

alright thanks

[weary tiger]

can someone tell me how the number of homomorphisms from (Q,+) to (Z,+) is just one

[naive saffron]

First assume f is a homomorphism. For the sake of contradiction say f is not 0, so you have f(r)≠0 for some rational r. Then conclude there must be another r with f(r)>0, then conclude there must be another r with f(r)=1, and lastly use this to get a contradiction

@weary tiger

[weary tiger]

thanks man, but does this mean its just identity homomorphism

also wanted to ask, can a lack of theory be substituted by ton of ques

[naive saffron]

What is the identity homomorphism

There is no identity here those are different sets

[weary tiger]

i dont understand modern algebra a bit, so i just practice a lot of ques to pass my exams, is it fine ??

[weary tiger]

f(x)=0 for all x in Q

[naive saffron]

Oh

Usually the word identity paired with the word function implicitly means that it's the function from a set to itself that maps any element to itself

But yes you're right there's only the zero homomorphism

[weary tiger]

ahh thanks

[naive saffron]

Well that depends on what you mean by "don't understand one bit"

You should be able to do some theory as in reason abstractly and understand all the definitions and theorems

But math is all about solving problems so doing a lot of those is definitely good

[weary tiger]

yeah but you need to memorize them, which becomes painful after a few chapters

every things order divides every other thing's order, like bruhh

[naive saffron]

Ah I see, I'd say yes doing problems is a great way to internalize the theorems

First they make you remember the theorems since you need to use them, second they give you motivation as to why these theorems are important or useful

[weary tiger]

yeah lmao such is maths

i aint studying math after my masters no shot

i'll do mba and become a banker

had eco as college minor anyways

[tidal tulip]

any insights?

[tidal tulip]

is the reason this is valid to go from

(g o f)(x) = z being surjective to g(y) = z surjective because it’s just unraveling the definition of what (g o f)(x) does under function evaluation

[lusty cave]

struggling to find the succession bn that satisfies this equation

got as far as to understanding the right part of the equation, but i get stuck at trying to make it a sum

[obtuse lance]

it might help to know the coefficient is the convolution $$\sum_{i=0}^n b_{n-i}a_i$$, so $b_{n-i}=n-i$, or rather $b_n=n$

[vital dew]

Merosity

[lusty cave]

i got that part, but trying to understand bn is what i cant comprehend

its supposedly the (1 + 2 + 3 + ... + n), but it depends of the value of n

is bn really n? seems to me like a sum itself

[plucky escarp]

can someone tell me what this means?

is it infinite?

[stray reef]

this is the union of S_i ranging over all natural i

there are an infinite number of sets involved in the union, however it is impossible to say whether the union itself will turn out to be an infinite set until it is known what S_i is

[plucky escarp]

thanks

[outer rune]

quick question. is 25!(mod23) equivalent to 0(mod23) ?

[opal crescent]

what's your thoughts on that ? you probably have some opinions about the question at hand

[outer rune]

well 25! is divisible by 23

so i think its 0

[opal crescent]

well 23 is a factor of 25! so yeah

[outer rune]

thank you

also why am i not getting the same thing on both sides

this is a mock midterm btw

not an actual exam

[little prism]

you missed the term 2k+1 on the left. the sum is 1+2+3+...+2k+(2k+1)+(2k+2)

[outer rune]

wait what

it is?

hold on

[little prism]

2(k+1)=2k+2

but you are adding every natural number. there is still the number 2k+1 between 2k and 2(k+1)

[outer rune]

Inductive step: IH: assume 1 + 2 + 3 + ... + 2k = 2(k)^2+k

then show that 1 + 2 + 3 + ... + 2(k+1) = 2(k+1)^2 + (k+1)

right

[little prism]

yes

but what is the sum on the left

[outer rune]

1 + 2 + 3 + ... + 2k + 2(k+1)

[little prism]

no

try k=3 or something

[outer rune]

oh wait

so i need to add 2k+1?

into the left hand side

[little prism]

yes

[outer rune]

but why do i need to add 2 numbers

to the left hand

[little prism]

write out what the sums are for some small examples of k

what is the sum 1+2+...+2*3 and what is the sum 1+2+..+2*4

the second sum is the first plus 7 and 8

not just plus 8

7=2k+1 if k=3 and 8=2(k+1)

[outer rune]

ohhh

thank you

i plugged this into a linear congruence calculator and i think i got this question wrong

can anyone check it over

,w 51x congruent to 15(mod72)

[vital dew]

Results provided by WolframAlpha

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

Requested by josh.#3881

[outer rune]

howd wolfram alpha get 13(mod24)

i got 15(mod 72)

i know that they divided 72 by the gcd which is 3

so the 24 makes sense

but why the 13

[austere cedar]

@outer rune from $17x=5$ we get $x=17^{-1)} 5$ and because $17^{-1}=17$ modulo 24, we get $x=17 * 5=13$ modulo 24

[vital dew]

Alexander42

[outer rune]

i dont understand

[austere cedar]

you fault was that you tried to invert 51 modulo 72, which doesn't work because the gcd is not 1. So there is no number c with $51*c=1$ modulo 72

[vital dew]

Alexander42

[outer rune]

oh

so wait

what do i need to do instead

so to invert a number the gcd has to be 1

[austere cedar]

yes

[outer rune]

but cant you write any gcd as a linear combination using bezouts theorem

[austere cedar]

suppose x is the inverse of 51. but clearly $51*x$ is divisible by 3 so it will never be equal to 1 modulo 72

[vital dew]

Alexander42

[outer rune]

my prof was able to solve linear congruences even when the gcd didnt equal 1

[outer rune]

ahh okay

so then what do i do once i see that the gcd isnt 1

[stray reef]

divide everything by the gcd

instead of 51x = 15 mod 72, solve 17x = 5 mod 24

[outer rune]

i got this

did i find the inverse correctly?

[stray reef]

do you mean "is my work up to standard" or "is my answer correct"?

[outer rune]

2nd option

[stray reef]

yes, your answer is correct.

[outer rune]

so

the inverse of 17

is 17??

[stray reef]

the inverse of 17 mod 24 is 17, yes.

that happens sometimes.

nothing wrong with it.

[outer rune]

cool beanz

@stray reefso this is the answeR?

[stray reef]

no

you want 17^-1 * 5, not 17^-1 * 1 as you wrote.

[outer rune]

wra got this

[outer rune]

what

ohhh

ok ok

[tribal pond]

Anyone suggest a good resource for discrete math

[glossy prawn]

how do I show all the subsets from this

[stray reef]

wym by "all subsets"?

@glossy prawn can you post the entire problem exactly as it is stated?

[boreal linden]

Hello! Anyone able to help me out with an assignment I am working on 1on1? 4 questions I am needing assistance on relating to logic and rules of inference

[wide vine]

If you are seeking help please post the actual questions (assuming it isn't something like a test/quiz/exam)

[weary tiger]

rosen's dm and its applications

[tribal pond]

Ok thanks

[ashen night]

@wooden swan

[wooden swan]

If 1+2+3=6
Then why is 1x2x3=6 as well?
Does that mean +=x

[ashen night]

@wooden swan

[wooden swan]

What

[ashen night]

nothing

1-0

[thick pasture]

What is $/lfloor{/pi}/rfloor$

[vital dew]

Noone

[thick pasture]

J

[opal crescent]

$\lfloor \pi \rfloor$

[vital dew]

aPlatypus

[opal crescent]

any thoughts?

[thick pasture]

Oh I haven't done latex in a while

[opal crescent]

it's ok ^^

[thick pasture]

\

[viral crown]

#latex-help

for next time

[opal crescent]

maybe they really wonder what floor(pi) is who knows

it's not that discrete-y, but it's not pure latex

[thick pasture]

I really don't know what floor pi is

I think it's 4

[opal crescent]

what does floor mean to you ?

[opal crescent]

unfortunately nope

[thick pasture]

4 is ceil

[opal crescent]

yeah

[thick pasture]

I think 🤔 2 is floor

Or maybe 2.9999

[opal crescent]

ceiling : integer just above, floor : integer just below

that's the ultra basics of those functions

(you have to consider what happens when you take floor(3) for example)

but to have a very quick idea that's pretty much it @thick pasture

[thick pasture]

🤣

[opal crescent]

if you find floor and ceiling funny I guess that's a good thing

[thick pasture]

I have a question floor(x)÷3=0. What is interval

Easiest question in the 🌎

Also what are mods

[opal crescent]

wdym by what is interval ? like you wanna find the x's such that floor(x)/3 = 0

well then we got floor(x) = 0

[thick pasture]

Ye

[opal crescent]

so what are the numbers such that the integer just below them is 0 ?

that's what the equation means

[thick pasture]

[cedar panther]

Hey! I'm currently stuck on this problem. I'm having a hard time simplifying ~ (p ^ q) ^ q = ~p ^ q. I'm not sure which law to use next. My approach could be entirely wrong. If anyone can provide some aid, I would really appreciate it! thanx

[hard citrus]

If you're still stuck on this, try applying the distributive law next

[cedar panther]

thank you! I was able to solve it by using the distribution law!

[weary tiger]

the division by 3 is negligible because it equates to 0, floor(x) = 0 is true for the set of real numbers such that $0 \leq x < 1$ (because $\floor{x} = x$ iff $x \in \mbb{Z}$

[vital dew]

Renegade

[livid mirage]

These kinds of questions always confuse me. I understand that in the latter condition passing has greater dependence on getting the good exam grade so 1 -> 0 would be false but in the first one im not sure how to understand the 1 -> 0 condition because then you get the good exam grade but dont pass which is also false and the false conditions are very similar — when i fall into this on a problem such as this it becomes a bit overwhelming so any clarification is appreciated

[narrow trench]

Yeah, this isn't a great example because there's good and good enough and a million other things that complicate the intuition

[livid mirage]

Yea I found a thing online that states with if you reverse the order and only if its the same as if p then q

I am just lost in the wording though

[narrow trench]

Do you have an exact quote?

[livid mirage]

https://youtu.be/goYEdhWCRiQ

1:40 in this video

Ty btw

[narrow trench]

Oh

All it's saying is that "P if Q" means "if Q then P"

But "P only if Q" means "if P then Q"

[livid mirage]

Oh hm i think that makes sense based on the other example

[narrow trench]

Let's take an example where the converse is clearly false to clarify

[livid mirage]

Ok

[narrow trench]

P = it's raining, Q = the ground is wet

[livid mirage]

So if p then q is logical

Like p-> q

[narrow trench]

If it's raining, then the ground is wet

i.e it's raining only if the ground is wet

You can't have rain without the ground being wet, it must necessarily be the case

That's why the ground being wet is called a necessary condition for it to rain

[livid mirage]

Ohhhhh

That makes so much sense

OH

[narrow trench]

But you can very well have the ground wet without it raining

[livid mirage]

This is such a good example

[narrow trench]

For instance if it just rained and it hasn't had time to dry

[livid mirage]

Ah ok!

[narrow trench]

So "It's raining if the ground is wet" is false

[livid mirage]

So it has rained if the ground is wet

Ohhhh

Ok

Hm one sec

Need to think for a moment

Ohhh thats the 0 -> 1 condition ?

Oops

[narrow trench]

It's unclear what 0 and 1 are

[livid mirage]

No 1 -> 0

Sorry 0 is the first statement and 1 is the seno d

Like false and true

I think this makes sense

Thanks so much

[tidal tulip]

for this proof

how is (f* o f)(b) = a

(f* o f)(b) = f*(f(b)) and f(b) is undefined since b in B i assume

[pale epoch]

b is in A

[tidal tulip]

oh i see now

how does f*f = id_A for each of those expressions mean that a = b, because id_A is a mapping and not a specific element

(ff)(a) = (ff)(b) = id_A i get that now

but that’s saying these function compositions equal the same identity map

[pale epoch]

there is only one identity map

do you agree that $c=d$ implies $g(c) = g(d)$ for any function $g$?

[vital dew]

Lochverstärker

[tidal tulip]

eg say 2,3 in A and f* (f(2)) = 2 and f* f(3)) = 3 but 2 != 3

[tidal tulip]

yes

[pale epoch]

ok

then now $f(a)$ and $f(b)$ are elements in $B$ and $f^{-1}$ is a function $B\to A$

[vital dew]

Lochverstärker

[pale epoch]

so if $f(a) = f(b)$ i can apply $f^{-1}$ on both sides and get $$f^{-1}(f(a)) = f^{-1}(f(b))$$

[vital dew]

Lochverstärker

[tidal tulip]

ah i see because this situation would not *** apply. we have f(a)=2 and f(b)=3 and in this case f(a) != f(b). what you’re saying is assume f(a) = f(b), so in this case it’d be like saying f(a) = f(b) = 2 and applying the inverse to f(a) and f(b) to get id_A and id_A(2)=2 — but i’m still a little confused as to how we know a = b from there

[pale epoch]

ok you figured why your counterexample doesnt work

i had more to say

if you agree up until now

[tidal tulip]

yeah agree

[pale epoch]

well, $f^{-1}$ is defined in such a way that $f^{-1}(f(x)) = x$ for all $x$

[vital dew]

Lochverstärker

[pale epoch]

so now just apply this fact on both sides and you get $a = b$

[vital dew]

Lochverstärker

[tidal tulip]

ok, that makes a lot sense now!

ty that was confusing

bc i was working with the wrong counter example

[pale epoch]

so there are two things happening here: first thing is that applying a function on both sides of an equality keeps that equality true and the second thing is how f^{-1} is defined

[tidal tulip]

ok that helps a ton, ty for explaining

one last question for now

for surjective

does this proof work because you picked an arbitrary b and shown how to get it from an a in A

it feels reversed to me

like pick a b and then reverse engineer the a

instead it seems like you picked an a and got a b

and i wanna know how does this show you can get all b in B

in this direction

[pale epoch]

it does start with an arbitrary b in B

[tidal tulip]

i would have wrote it like
let b in B be arb, b = id(A) = … = f(a)

[tidal tulip]

ok, so it says pick a b in B, and then they compute f(a) = … = b, but how do i know the b they chose is the b i computed

[pale epoch]

by the definition of a

and inverse of a function

[tidal tulip]

like i could saw 2,3 in B and then

pick 2 in B

f(a) = … = 3

i want to know how f(a) = 2

[pale epoch]

by definition of inverse

a is f^{-1}(b)

so f(a) = f(f^{-1}(b)) = b

[tidal tulip]

ah i see, so they say pick a b in B, then by f* we know f(a) = b

[pale epoch]

again f^{-1} is a function such that f(f^{-1}(x)) = f^{-1}(f(x)) = x

[tidal tulip]

so they pick a b in B and then compute its inverse

[pale epoch]

yes

[tidal tulip]

how do i know there is an inverse for every b i choose

[pale epoch]

there isnt much else you can do in this setting anyway

[tidal tulip]

instead of a subset

[pale epoch]

f^{-1} is a function B -> A

[tidal tulip]

ahh

it’s well defined

[pale epoch]

by definition of function you must be able to plug anything in and you get a unique output

ye

[tidal tulip]

so every element in B is mapped

ok

[pale epoch]

you have functions $f\colon A\to B$ and $f^{-1}\colon B \to A$ and an element $b\in B$

[vital dew]

Lochverstärker

[pale epoch]

the only thing you can really do is plug $b$ into $f^{-1}$ and see what happens

[vital dew]

Lochverstärker

[tidal tulip]

dumb question but this says all b’s have an inverse but how do i know all a’s will be hit by a b, oh wait this is onto and that isn’t a requiring

requirement

ok so argument is essentially pick a b in B

compute its inverse to get the corresponding a

[pale epoch]

all a's will be hit by the same proof

[tidal tulip]

and all b in B will be mapped because f* is a function

[pale epoch]

you just exchange mention of f with f^{-1}

(but that isnt technically used here)

ye thats the argument

[tidal tulip]

k cool

[pale epoch]

and then you confirm that this preimage works

[tidal tulip]

k

what’s the argument all the a’s will be hit by the b’s when you’re computing f* on b

[pale epoch]

the same one

if f^{-1} is the inverse of f, then f is the inverse of f^{-1}

so the same proofs show that f^{-1} is bijective as well

[tidal tulip]

ok i have to go but have questions around that but this will do for now ty — i’ll come back with those questions later

ty for this help

[alpine grove]

does anyone know a place, video or website or something where I can learn about big O notation?

I really am not understanding it

[wide vine]

I thought this video was good https://www.youtube.com/watch?v=0oDAlMwTrLo&t

[misty niche]

Prove that if a and b are integers and a divides b, then a is odd or b is even.

^ need help proving this

[livid minnow]

start with the definition of a divides b

[misty niche]

There exists an integer k such that b = ak

[livid minnow]

mhm

now just exhaust all your cases

there are only 4 cases to consider here

[misty niche]

ahh gotcha

[neat condor]

what is this statement trying to say

−ε < an − L < ε

[stray reef]

a_n - L is between -epsilon and epsilon.

that's what that inequality is saying.

[neat condor]

they say that the statement is trying to say this but i am confused on what an - L is trying to signify

[neat condor]

this part i understand

[stray reef]

a_n - L is a_n - L

it is the amount by which a_n differs from L

you might find it easier to intuit if the same inequality is written as |a_n - L| < ε so that it becomes a statement about distances

[neat condor]

ahh i see

also what is the role of integer N

[stray reef]

it is the point in the sequence starting from which its terms fall within ε of the limit

[neat condor]

ahh ok thanks

[weary tiger]

how do u guys answer this?

[coral parcel]

A bit sneaky that there's a 6^1 in the product but 6 is composite.

However, think about how you would find the GCD and LCM if you had full prime factorizations of both numbers.

What does that imply about the product of the original numbers?

Hmm, actually the givens in the problem are impossible. If 2¹3²5²7² is a common multiple at all, then neither of the numbers is divisible by 4. But then their product cannot be the stated number, which is divisible by 8.

Possibly 6¹ in the product is a typo and shouldn't have been there at all.

[obtuse lance]

I think it's possible but maybe I'm mistaken

well, I got an answer at least, I don't wanna say cause it sounds like you're trying to hint them towards how to get the answer with the formula I used at least

[coral parcel]

Does the answer you got divide the LCM like it should?

[obtuse lance]

that sounds backwards to me ||the lcm divides the product: gcd(a,b)=ab/lcm(a,b)||

well I just threw it in a calculator and got ||2100|| but maybe I made a mistake in plugging in lol

[coral parcel]

Every common divisor is necessarily a divisor of every common multiple, and your answer is not a divisor of 2¹3²5³7² = 22050.

Your spoilered formula is indeed what I was trying to hint at, but it only works when there exist a and b that give the stated product and LCM in the first place.

[obtuse lance]

I see, the solution naively works even though it's unobtainable in practice

well "works" in that it gives an integer out

I see exactly what you mean, the multiples of 2 are broken, I guess you weren't supposed to sanity check it like I blindly did

[coral parcel]

The numbers work out sanely if we ignore the 6¹, which is very out of place in what looks like it was intended to have been a prime factorization.

[burnt lynx]

I need help with the induction step

sort of stuck on trying to prove 6(2^k+1)-5

[flat trellis]

you can try to get a_{n} out of it maybe

like

ok nwm

[meager prairie]

use $a_{n+1} = 2a_n +5$

[vital dew]

jan Niku

[meager prairie]

so $a_{n+1} = 2\qty(6(2^n)-5)+5$

[vital dew]

jan Niku

[meager prairie]

then $a_{n+1} = 6(2^{n+1})-10+5 = 6(2^{n+1})-5$

[vital dew]

jan Niku

[meager prairie]

[burnt lynx]

ahhhh

[flat trellis]

wait

if it's induction

(idk if I understand that correctly)

if it's induction then while checking n+1 it's true for n

so while checking n+1 -> an = 6(2^n) - 5 is true

[burnt lynx]

omg i'm so dum I thought I needed to distribute the 2 to the 6 making me get 12

[flat trellis]

so at this point you can change the thingy inside () to an

but maybe I'm dumb

ok nwm

I was supposed to ask my own question

[meager prairie]

yes

i think dark is good, yea?

[burnt lynx]

yea

ty

[meager prairie]

[flat trellis]

So I have to calculate the formula for a_{n}

From what I understand

[meager prairie]

wolframs solution looks so screwy

[flat trellis]

first I do this
a^2 + 2a + 1 = 0
solve it
get a = -1

2 times, idk how to say it

not important here

[meager prairie]

multiplicity

[flat trellis]

ok, maybe it is

then

[meager prairie]

its important

to get here you assume that a_n = a_0 r^n or so

iirc

[flat trellis]

a*_{n} = C1(-1)^n + C2n(-1)^n

how do I

[meager prairie]

ye

[flat trellis]

use the math thingy bot

[meager prairie]

$a^* _n = C_1 (-1)^n + C_2 n (-1)^n$

[vital dew]

jan Niku

[flat trellis]

yes

So that's the first step, right?

[meager prairie]

yea

[flat trellis]

And to get the full solution

I have to do some magic stuff

with the things

[meager prairie]

assume $a_n = a^*_n + f(n)$

[vital dew]

jan Niku

[flat trellis]

yes

this thingy

now how do I calculate the f(n)

cause I've seen a lot of things and I'm confused

in different cases stuff like

f(n) = an^2 + bn^2 + c
or
f(n) = (b1 + b2n)n * 2^n
or
(An^2 + Bn + C)n^m * 2^n

So. I don't know which one to use when and why

like the last one was something connected to a method of guessing (idk if that's the correct name, I just translated it straight to english)

[flat trellis]

where the things in () was connected to the power of n on the right side

[flat trellis]

m was how many times 2 appeared here

[flat trellis]

and 2^n is just the rest of that

so I ended up with that

calculated A, B, C

and got my f(n)

which is the left side of this equation

[meager prairie]

this i never had a lot of familiarity with tbh

[flat trellis]

I was following a tutorial, don't judge me, I might have messed something up

[meager prairie]

nah no judgement

[flat trellis]

I don't really care about the method as long as I understand it and calculate that f(n)

[meager prairie]

https://www.cl.cam.ac.uk/teaching/2003/Probability/prob07.pdf

im examining this, 6th page

err, 7

i need to eat lol

[flat trellis]

All I see is dark magic

still, I don't think that's it

or maybe I'm wrong, who know

[meager prairie]

i wanna give it a real go

but i havent eaten yet today so i need to do that first

[flat trellis]

ok, ok

While we were doing a similar exercise with our professor

where there was

[vital dew]

cesarz

[flat trellis]

and the right side of the original equation being

[vital dew]

cesarz

[flat trellis]

he wrote f(n) as

[vital dew]

cesarz

[flat trellis]

wait, that might be actually the same thing as we are trying to get

since here it's just n and not n^2

so the thing in () is just (b1n + b2)

[flat trellis]

n^m = n because m=1 because 2 appears once here

so
(b1n + b2) n^1 2^n

🤔

soo in case of ..

[vital dew]

cesarz

[flat trellis]

there will be

[vital dew]

cesarz

[sharp cradle]

Dy guys know how to do this

[meager prairie]

hmm

[flat trellis]

and the right side of the original equation is

[vital dew]

cesarz

[flat trellis]

so f(n) will be (I'm not sure about that)

[vital dew]

cesarz

[meager prairie]

dont suppose you have matlab

well, any coding language will work to check

i would start checking these guesses

im plodding along on my own

[flat trellis]

Well, it's almost midnight for me and I have to get up early

I'll continue from this point later

[meager prairie]

[flat trellis]

also not A1 and A1

should be A1 and A2

and after that not A2 but A3

[meager prairie]

I'm not really sure exactly how youre supposed to get to the solution im getting from a calculator

it makes me think theres a typo somewhere

unless theres some super clever method

it looks like f(n) is an alternating cubic?

[sacred dune]

i must be having a brainfart but i dont see why this is true (why do we have (L-1)/2 >= N_c/n). Here n is the number of vertices and N_c the number of edges

the way i see it we have rL >=n and so we should be getting (L-1)/2 >= nN_c

i must be making a simple mistake i just need someone to verify this

[coral parcel]

Hmm, that does look odd.

[sacred dune]

And this can’t possibly be a mistake it’s a paper by erdos

[coral parcel]

Nc <= sum of (li choose 2) = sum of li(li-1)/2 <= sum of li(L-1)/2 = (L-1)/2 · sum of li = (L-1)/2 · n

[sacred dune]

Oh of course

Thanks I’m an idiot

[coral parcel]

Stumped me for several minutes too.

[sacred dune]

@wide vine @viral crown with regards to that exercise i sent

it was for a learning study and the TA provided exercises harder than for our course

in particular this particular exercise requires a theorem id never even heard of lol

Sperner's theorem

result follows directly from it