discrete-math

[prime grotto]

wouldn't it be
lowest: g
highest: a, d, b

(not that sure though)

[gritty garnet]

Deg (a) is 8

Deg(D) is 6

[agile magnet]

I don't think there is a standard notion of an adjacency matrix for a multigraph

and yea, this is correct. So have more confidence in your answers instead of asking for confirmation even if you think you are right

[prime grotto]

yeah this, you should never trust anything i say (this is not a joke)

[regal kernel]

Hello guys i need help

I need help to carry out this exercise of logical inference, and solve it, by direct method, by cases, by contrareciprocal, by any of those

[twilit sundial]

i assume this hinges on the assumption that a tree must have a leaf?

(ik how to prove that but just want to make sure that that is the assumption we need here)

"... There must be a node with degree 1: start at any vertex, and start following edges marking each vertex as we pass it. If we ever come to a marked vertex, there is a loop in the edges (contradiction). Therefore, we will eventually reach a node with degree 1 or else the path will continue forever."

[quiet eagle]

You already have a solution there. So you want to prove it differently?

[twilit sundial]

nah

just want to verify the assumption being made there

[quiet eagle]

You mean the I.H. ?

[twilit sundial]

"let's remove one leaf node" presupposes that the k+1 tree has a leaf

the inductive hypothesis only covers k-vertex trees

[quiet eagle]

If every node had degree > 1 there would be a circuit, contradicting that it's a tree

[twilit sundial]

that seems like a much saner explanation lmao

[quiet eagle]

Yea haha

[twilit sundial]

rather than what they give here

"or else the path will continue forever" LMAO we're dealing with finite trees why would the path continue forever

😭

[quiet eagle]

Whattt I thought that was your idea

[twilit sundial]

LOL these were probably typed up by some random TA

[quiet eagle]

Loll

[twilit sundial]

(this is a math course being taught by CS people sooo)

stuff like this happens

[quiet eagle]

Cant expect much🥱

jk

[twilit sundial]

lmao

cs majors when they actually have to do the math rather than having their computer do it 😱

[quiet eagle]

fr

[fossil mural]

exactly, so that's a contradiction

if every node has degree > 1, there's a path that either eventually loops back on itself (so it's not a tree), or continues forever (so it's not finite)

[ionic lodge]

RSA algorithm
please tell me some tricks to evaulate those big mods
i want some modular magic in my life to find
805^13 mod 2537

[fossil mural]

repeated squaring
compute 805^2, (805^2)^2 = 805^4, (805^4)^2 = 805^8
then multiply together 805^8 * 805^4 * 805 = 805^13

also reduce mod 2537 at each step to avoid the intermediate numbers getting too large

[ionic lodge]

but even squaring this number is too taxing on time
how'll i do it in exam?

[ionic lodge]

yea ur basically saying that multiply thing
a x b mod m = (a mod m x b mod m) mod m

how do i encypt text in rsa easily though

[twilit sundial]

simply compute faster

[stray reef]

* not x.

[ionic lodge]

same

[weary tiger]

Is this an Euler circuit??

[stray reef]

did you mean "Is this graph, in its entirety, an Euler circuit (of itself)?"
or did you really mean "Does this graph HAVE an Euler circuit?"

[stray reef]

also your drawing is a bit unclear with some of the edges' orientations -- i've reproduced your graph here, can you tell me whether i got all the edges right? @weary tiger

[weary tiger]

Pretty much

[stray reef]

wdym "pretty much"? did i or did i not reproduce this thing correctly?

[weary tiger]

e9 arrowhead goes to v4

e8 arrowhead goes to v2

Rest everything's fine

[vivid osprey]

I have a basic doubt. Consider a double union $$\bigcup_{i,j}(A_i\times B_i)\cap(C_j\times D_j),$$ where we first take the union over the index $j$ and then the index $i$. Can I then simply "pull out" the $(A_i\times B_i)\cap$ bit from the first union and compute $\bigcup_j (C_j\times D_j)$ and then intersect that with the union of $(A_i\times B_i)$?

[vital dew]

Philip

[stray reef]

@weary tiger so this is correct now, yes?

[weary tiger]

Yes

[stray reef]

ok

do you think that this graph does have an euler circuit or that it doesn't?

[weary tiger]

That's what I'm asking here

[stray reef]

yes, obviously. but i want to hear your own thoughts

i could just reveal the answer to you but that would be pointless.

[weary tiger]

Ig yeah, all Vs seem to have even degree

[stray reef]

evenness of degree is not sufficient for a directed graph

but ok, try to look for an euler circuit anyway.

[coral parcel]

Evenness of degrees (and connectedness ofc) would be enough for an undirected graph, though.

[oak creek]

Does this look good? When I checked on my calculator it was congruent to 10 with a tiiiiiiiiny remainder. I kinda feel comfy leaving the remainder to calculator rounding shenanigans but I wanted to check anyway

Offending tiny remainder

[fossil mural]

i haven't checked all of your working but it is true that 21^7 = 10 mod 23

[sterile flame]

Could anyone please explain me this definition? My book lists modus ponens as an example but I still can't wrap my mind around it

[prime pond]

what channel would people know about recurrence relations?

[stray reef]

i suppose that for modus ponens the j that they talk about would be 2

it's how many "input" formulas the relation has

[sterile flame]

Wati, so if the MP relation is $R={\langle B, B\to C, C\rangle : B,C \text{ wfs}}$, then, for every (two?) formula B, one can decide whether A, A->B or B?

[vital dew]

lazur__

[sterile flame]

It would actually make more sense to be two formulas, but then how do I express two formulas being in relation with a third one?

[rugged briar]

Hey guys is the following sequence graphical 8,3,2,2,1 ?

[coral parcel]

The modus ponens relation is indeed { <B, B->C, C> | B,C wfss }.
The additional condition is that for wffs X, Y, and Z it must be possible to decide whether <X,Y,Z> is in the set -- that is, whether there are wffs B and C such that X=B and Y=B->C and Z=C.

[sterile flame]

that makes sense, thanks a lot

yes

[coral parcel]

The sense of "relation" here is just a subset of a cartesian product -- so the relation "holds" for some combinations (those combinations that are elements of the set) and doesn't hold for others (those that aren't).

[coral parcel]

Yes.

[thorny crystal]

would it be correct to say something is vacuously true if it cannot ever be true?

[fossil mural]

no

vacuously true things are true, and also truth values don't like, vary over time or anything, so i don't know what "can't ever be true" would mean

[thorny crystal]

as in they can never be false, ever?

[fossil mural]

well... ok that is true about things that are vacuously true, but it's also true about all true statements

although i suspect the actual answer is that that's also wrong, because what you're trying to refer to with "ever" is a concept that doesn't actually make sense in this context

[thorny crystal]

hmmm i see

if you were to defice vacuously true in the most simple terms, how would you define it

[fossil mural]

basically it's just a word for when you have a statement that's quantifying over an empty domain, or that has a hypothesis that's impossible

like "for all natural numbers n, if n = n + 1, then n is prime"

[thorny crystal]

oh so like just impossible statements?

[fossil mural]

there are no natural numbers satisfying n = n + 1, so this statement is true

[fossil mural]

...no, read what i said again

"for all natural numbers n, if n = n + 1, then n is prime" is not an impossible statement, in fact it's true

[fossil mural]

or "every element of the empty set is divisible by 7"

there are no elements of the empty set, so any statement of the form "for every element of the empty set, [...]" is true

where to be clear this isn't the kind of thing where it really makes sense to ask about an arbitrary statement whether it's vacuous or not, it's more along the lines of "trivial"

[weary tiger]

can i get some help

[stray reef]

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[stray reef]

post the problem(s) you need help with

[pearl ermine]

3 people are having a water balloon fight. At the same time, each of the 3 people throws a water balloon at one of the other 2 people. What are the number of possible outcomes? can this problem be solved using graph theory?

[pearl ermine]

can someone help

[pale monolith]

I guess it can be solved with graph theory but that's pretty overkill

[pearl ermine]

how so?

[pale monolith]

Each person can be considered a vertex and "X throws a water balloon at Y" is an outgoing edge from X to Y

For each vertex you have to choose one of two outgoing edges to create so there are 2^3 outcomes

[stray reef]

but that's only barely graph-theoretic

it's still combinatorial counting at its core

[pale monolith]

Yeah it's a useless transformation of the problem

[stray reef]

@pearl ermine no, this problem cannot be solved "with graph theory".

[weary tiger]

Is this graph bipartite

And is this graph planar

[stray reef]

@weary tiger do you know the definitions of "bipartite graph" and "planar graph"?

[weary tiger]

Yes

I color coated the graph I think it’s bipartite but I just want someone to verify

Now with planar I know you can do V - E + F = 2

But idk if I did that calculation correct

[coral parcel]

You can't actually apply V-E+F=2 before you have a planar drawing, because "faces" only exist with respect to a particular drawing.

At this level, the expected way to find out whether the graph is planar is simply to try to find a way to draw it without crossing edges.

[weary tiger]

Oh ok.

[vague harbor]

hey guys, could i have help in understanding the "optimal substructure" property that is often associated with "dynamic programming"?

Wikipedia formally puts the definition of optimal substructure as below:

A slightly more formal definition of optimal substructure can be given. Let a "problem" be a collection of "alternatives", and let each alternative have an associated cost, c(a). The task is to find a set of alternatives that minimizes c(a). Suppose that the alternatives can be partitioned into subsets, i.e. each alternative belongs to only one subset. Suppose each subset has its own cost function. The minima of each of these cost functions can be found, as can the minima of the global cost function, restricted to the same subsets. If these minima match for each subset, then it's almost obvious that a global minimum can be picked not out of the full set of alternatives, but out of only the set that consists of the minima of the smaller, local cost functions we have defined. If minimizing the local functions is a problem of "lower order", and (specifically) if, after a finite number of these reductions, the problem becomes trivial, then the problem has an optimal substructure.

I am trying to understand what it means for a problem to have optimal substructure, and understanding these definitions is not helping me get anywhere. The wikipedia definition also says "...and let each alternative have an associated cost, c(a). The task is to find a set of alternatives that minimizes c(a)", where I absolutely do not understand how c(a) which was previously said to be related to a single alternative; now is related to a "set" of alternatives?
What do we mean when we say the problem? What even is an alternative?

[ashen bane]

I need help with this question, stuck on it for over 2 hours
let A = {1,2,...8}
S subset of AxA( S is relation)
|S| = 17
prove that there exists different (x2,y2), (x1,y1) s.t
max(|x2-x1|, |y2-y1|) = 1

I know it's piegonhole, but i couldn't find the non injective function ;((

[icy raven]

i just started this class and wanna cry

[ashen bane]

Combi?

[icy raven]

HUh?

[ashen bane]

:?

[icy raven]

Lost I am

[stray reef]

do you have a question or do you just want to complain

@icy raven

[icy raven]

Questions but my issue is idk where to start.

[ashen bane]

please

[stray reef]

are you allowed to reframe this geometrically

cause there is a very nice rephrasing

[ashen bane]

I think

It's not question from my class, a friend sent it to me, so any method is acceptable

i just broke my head on it

[stray reef]

imagine that A x A is a chessboard

(a literal chessboard, since A = 1:8)

[ashen bane]

Ive never played chess actually but i can imagine ye

[stray reef]

S is then a set of 17 tiles on this chessboard

max(|x2 - x1|, |y2 - y1|) = 1 is equivalent to saying (x1, y1) and (x2, y2) are a king's move apart

[ashen bane]

You lost me here

Idk any of chess rules 😦

[stray reef]

not even piece movements?

[ashen bane]

i guess it's some nice proof, but none

😦

I wish i could understand it

so basically 6 options?

[stray reef]

8

[ashen bane]

oh ok

[stray reef]

the idea then is to divide the chessboard into sixteen 2x2 regions

by pigeonhole, there will be a region with at least 2 cells from S

[ashen bane]

ok

[stray reef]

and the key thing is that within a region, any two of its four cells are connected by a king move

i find it somewhat surprising that in this day and age there are people who do not even know how chess pieces move

[coral parcel]

I would recommend not worrying too much about a precise crisp definition of "dynamic programming". It is really not a technical term, but more of a vibe, a vague set of connected ideas that can be useful for coming up with algorithms for particular problems.
There are no theorems that go, "Let A be a dynamic programming algorithm. Then bla bla bla".
You will never be asked to look at an algorithm and answer whether that is a dynamic programming algorithm or not (at least never for a boundary case where the precise interpretation of the words in that description matters).
There are no general "libraries for implementing dynamic programming" -- or if there are, such a library will come with its own constraints on what it can do, certainly much more restricted than the Wikipedia author's best attempt to capture everything at the highest possible level of generatity.
You may be asked in an exam or homework to "come up with a dynamic-programming algorithm for such-and-such" -- but then the vibe will again be much more important to have down than the precise boundaries of the term.
I know this kind of vagueness can be hard to accept, but please try anyway.

[ashen bane]

omg it seems so legit now

i think

wait

we divide 17 troops to 16, so there is one cell with two

omfg

Ok i understood it, it makes much sense now, thanks @stray reef

Is there a name for this problem btw?

[stray reef]

idk

[vague harbor]

i undertand you tbh. I have tried to do this exact thing for a long time now, but i am so frustrated with the idea of just knowing what is a dynamic programming problem, and what is not. Like, it is just to be known, as a fact that oh yes, this problem is solvable using the dynamic programming paradigm. I am choosing to not do that, which is why im here asking for a precise definition of optimal substructure. as far as i understand, it's a property of a problem itself, inherent to the problem. Now, that definition of wikipedia was the most formal that i could find. CLRS's definition is much abstract for me to comprehend. I dont worry about it coming on exams, since those are predictable. I want to know: what exactly does it mean when we say that a problem has optimal substructure?

[ashen bane]

Thanks again, how would you solve it without geometrical ? im just curious i want to learn for future cases

[stray reef]

you're gonna need a lot of lubricant

[coral parcel]

It sounds like you're trying to invent a technical distinction that doesn't really exist yet. Good luck with that research project -- perhaps you'll come up with something useful.

[stray reef]

bc it's thorny AND painful

[ashen bane]

Yeah... combinatorics...

[stray reef]

whatever mental image i evoked in your mind, that's the one i was going for.

[fossil mural]

i really doubt it's "a property of a problem itself" for any useful sense of the word "problem"

[vague harbor]

wait, are you saying that there really isn't such a thing as optimal substructure? I don't understand im afraid

[coral parcel]

I'm saying I think you're mistaken when you assume people (such as the Wikipedia author) had a crisp technical concept in mind when they wrote that.

[vague harbor]

hmm, so it is quite right that i have been overthinking this then perhaps? how is it that we just have the whole industry thinking that some problems have this, due to which we can apply Dynamic programming on them, and some dont?

[vague harbor]

damn lol, you're making me even more confused. I absolutely am trying to keep my sanity because its been like over 40 hours (not continuously) that i've invested into coming up with understanding this.

[fossil mural]

as in, if this concept is well-defined at all, then i suspect there exist distinct "problems" such that one is a dynamic programming problem, one isn't, but in fact the functions they're asking you to compute are identical

[coral parcel]

I don't think we have a whole industry thinking that -- at least nobody seems to think it in the spheres I move in, and I do work in a very PhD-heavy corner of the software industry.

[vague harbor]

oh

guess i'm more in the problem solving world, and am transitioning to attain the real knowledge. In this problem solving world atleast, you are just supposed to know that this type of problems are solvable by DP, and these aren't solvable by DP

[vague harbor]

how do you mean, sorry? how do you relate the functions that they're asking to compute are identical thingy here? im failing to understand that

if i were to ask if what the CLRS defines the optimal substructure property as (below), is this just what they chose to define? like, it just so happened that this is what they noticed the problems could be solved using by, and defined it like this?
a problem exhibits optimal substructure if any optimal solution to the problem contains within it optimal solutions to subproblems

[fossil mural]

basically i'm saying that this idea of "a dynamic programming problem" depends on how the problem is presented/what angle you're thinking about it as

[coral parcel]

It's useful as a vibe to be able to think something like: Is this a family of problems where it's reasonably easy to solve one of them if you already know the solutions to all smaller ones? Or can I extend the problem to a larger family that has this property? If you can, then trying dynamic programming might lead you to a good algorithm, but that's not guaranteed. Depending on exactly how the subproblems relate to each other, it may be that what you really want is memoization, or perhaps just straight-up naive recursion.

[vague harbor]

if we do have memoization, does it not mean that we also have optimal substructure? i ask so, because if some problem is asked more than once, i think it is fair to assume that bigger chunks relate to smaller chunks?

[coral parcel]

Memoization also uses the same vibe-concept of that you might call "optimal substructure" if you want.
I think the most common way to distinguish them is: If you can know even before you start which smaller problems you'll need to solve, and you then iterate through them bottom-up, that's DP. But if you find out only as you go along which of them you'll need, and then pause what you're doing when you need a subproblem you haven't done before, that's memoization.

[vague harbor]

oh, gotcha. I started with this exactly. When i was solving the "rod-cutting problem", my first instinct was that, we just check all the possibilities. i mean, what else can you do? Only after i was presented that we can have this nice property of asking "hey, make the first cut and get the maximum of both of the chunks you get from that", and so on, i was like "wtf? how is this more helpful?" then, i could see we were nicely structuring it, which helped us avoid some recalculation. But dude, how the hell was i supposed to know that this thing of nice recursion exists? this is what i think is optimal substructure. A nice recursive relation that describes how big chunks can be formed by knowing smaller chunks, but i for some reason think that there is more to this.

(https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture12.pdf)
rod-cutting problem that i referred to in the above

[vague harbor]

oh, no. you're bringing up the DP vs memoization semantics here. I (due to my biasness) say that "memoization" is constructing the table. Top-down DP and bottom-up DP are 2 things that exist. I understand your semantics are absolutely correct, but i am biased to look at "memoization" as the process of storing the duplicate results (lookup table), rather than associating it with a new paradigm itself.

[coral parcel]

At the bottom of page 5 that says:

To solve a optimization problem using dynamic programming, we must first characterize the
structure of an optimal solution.
but note this is specifically about problems that you already have characterized as optimization problems. That means you at least already ought to have an idea of what "optimal" ought to mean in the context of your particular problem.
But at least in my mind, "dynamic programming" is not inherently restricted to optimization problems -- even though I'll admit that the examples I can immediately think of are optimization problems.

[vague harbor]

i hope that we can not allow the semantics to come up here, since i just want to know what optimal substructure means.

[coral parcel]

"Let's not talk about semantics, but I want to know what _____ _means" is an oxymoron.

[vague harbor]

i meant to say that let's not talk about the DP vs memoization as far as semantics are concerened with. I believe optimal substructure is just something we can discuss standalone

[coral parcel]

It sounds like you're the person in the conversation who insists the most that the term means something crisp and that you can judge whether a meaning is right. Should it really be you who ask us what your preferred meaning of the phrase is?

[fossil mural]

that... isn't really related to what i actually meant there

what i'm saying isn't just that dp is hard to recognise, i'm saying the definitions you've presented assume we know what a "subproblem" even is

[vague harbor]

my apologies for sounding ignorant. I take everything that i said about that, back

[vague harbor]

ah gotchu. If we restrict ourselves to optimisation problems, can we then concretely describe what optimal substructure means?

[coral parcel]

We're not going to convince you to let those two innocent words go, are we?

[fossil mural]

which... we don't really? if the problem is "here's a random set of natural numbers, check if a number is in this set or not", ...what's a subproblem of that. is 4 a subproblem of 5 because 4 < 5? is 3 a subproblem of 6 because 3 divides 6? it depends on, not just what the set is, but your perspective on what the set is, whether the problem is "fibonacci" or "prime factorisation" or "the number is actually an encoded graph" or whatever

[fossil mural]

well what's an optimisation problem

all problems are optimisation problems, because your goal is to find an object that maximises the property of being the answer

[vague harbor]

im afraid not. I understand your points, but i just ask you to hear me out. If these things are well documented (clearly visible from the internet), then how come are we saying that we cannot define it properly? If we do limit ourselves to the optimization problems (such as the shortest-path, rod-cutting, Longest-Common-Subsequence), can we atleast then not define it?
I agree that im looking for an answer because i just cannot get over the fact that i invested so much time finding an answer, but now i am destroyed to hear that it perhaps doesnt even exist.

[coral parcel]

Well, you're the one who insists they must have a technical meaning, so I'd say you're the one who has the burden of showing such a meaning.

I don't think I can help you here, sorry for wasting your time.

[fossil mural]

"optimisation problem" is also more of a vibes-based "depends how you present the problem" categorisation
its usefulness isn't because we can name any particular problem that is not an optimisation problem, it's just that there are some ideas that generally work well in the fuzzy category of optimisation problems

it's the same kind of thing as classifying problems as being in different areas of mathematics

it does not actually make formal sense to take an arbitrary mathematical statement and declare that either it is "a question about group theory" or it isn't

[vague harbor]

you're the one who insists they must have a technical meaning
yes, i insist that; but only after being told that there is supposed to be meaning to it. I am simply not asking it out of the blue, right? I did see most resources documented on this topic (the CLRS textbook comes first to my mind, because it's widespread). They mention some definition of it, and im asking is that so?
I dont understand why you're trying to see this in any different way?

[fossil mural]

but in practice, there are some questions where viewing it as a group theory question, and applying methods from group theory, works very well

[vague harbor]

i understand that notion of abstraction. But my point is, we can atleast track back to making it fit in terms of that abstraction right? In the sense, I can say that it makes sense to think of integration as area bounded by the curve, because i can clearly show that to be the case. Similarly, are we trying to just do that here?

[fossil mural]

and sometimes it doesn't really work at all, or sometimes it sort of works but then you look at what you wrote and actually one of the objects involved has an obvious ring structure and what you did is a special case of some theorem about rings, or sometimes it perfectly solves half of the problem and then you need to use some completely different approach to finish it

it's not a technical categorisation, what you actually do is just whatever works and sometimes there is no sensible way to fit that into boxes

[vague harbor]

hmm

[fossil mural]

we use terms like this because there just isn't really much useful formally-valid structure on stuff like the space of all problems or the space of all mathematical questions

so we use fuzzy categorisations because they're all we have

[vague harbor]

i think you people are actually trying to get me out of this ditch, but im just too stubborn right now. Maybe all i need is some sleep to relax myself, and then i can come back, look at these chats again and then hopefully come to a conclusion.
I appreciate your time, i truly do. I mean, i couldn't get anyone to talk about this, so yeah, i hope you understand. Thank you so much for your time again, truly appreciated! @fossil mural @coral parcel

[fossil mural]

and they are useful if you take them as just being what they are: heuristics for problem-solving and communication

[coral parcel]

(Props to Bee for that very nice explanation where I had to nope out).

[fossil mural]

it is useful to notice in general that if you're trying to answer a question about divisibility, using modular arithmetic might be a good idea and using category theory probably isn't
even though there isn't a sharp boundary there, it's clearly useful in practice, at least sometimes, to categorise problems this way

[odd pumice]

Is it necessarily informal or not recommended to approach a proof in graph theory through the use of graphs of nth order whose vertices are, for the sake of convenience, ordered from 1 to n, assuming that this is essential to the proof?

[verbal zephyr]

Why would it be informal? As long as all your graphs are finite and you make sure that the same graph with two different vertex orderings is still considered the same I don't see a problem.

[gilded sun]

Can anyone help me understand why this is asyclic?

[blissful path]

my sir what is the shortest length cycle

[prime pond]

What is a cycle?

Usually also I think a property of trees is that if you subtract one edge that will guarantee that there wont be a cycle formed

[gilded sun]

I thought asyclic means that there's no cycles, implying that there are no loops in the graph so there's only one way to get from one vertice to another.

Am I incorrect?

[gilded sun]

^?

[blissful path]

yes what is the shortest possible length cycle in any graph

[gilded sun]

are you asking me

[blissful path]

yes

I know the answer

but I'm asking you to tell me

[gilded sun]

3

[gilded sun]

do you agree Edwards?

[blissful path]

I agree

[amber kite]

How can I figure out $\gcd(3^{2000}-1, 3^{12}-1)$ without a calculator?

[vital dew]

Sawbez

[amber kite]

So far I've tried using the extended Euclidean algorithm which means I need to find

3^2000 - 1 (mod 3^12 - 1)

there's a difference of squares but repeatedly expanding it out didn't appear to help

[gilded sun]

Do you also understand the difference between general trees and spanning trees?

[blissful path]

I understand many things

[gilded sun]

I'm kind of confused between the 2. a spanning tree allegedly connects every vertex of the graph, has no cycles, and uses the minimal number of edges. A general tree only connects a subset of vertices, also no cycles, but does not need to use the minimal number of edges as it does not aim to include every vertex?

If so, shouldn't a spanning tree be much easier to think through/process then a general tree? For instance, this is a spanning tree: A
|
B
/
C E
/ /
D F G

This is general tree

A
|
B
/
C D

spanning tree has more edges all throughout

(6)

vs the 3 edges of the general tree

[weary tiger]

Hey fellow Discrete Math learners >.>

[cerulean radish]

Trees have the minimal number of edges a connected graph can have

[obsidian cradle]

@amber kite this is a question for #elementary-number-theory
there is this property that you can try to prove using Euclidean algorithm: gcd(a^m - 1, a^n - 1) = a^gcd(m,n) - 1

[twilit sundial]

i am not satisfied with their explanation of 3c, particularly the "work is doubling at each level" part

the $n^2\left(1+\dfrac{1}{2}+\dfrac{1}{4}+\cdots\right)$ part i accept

[vital dew]

elrichardo1337

[twilit sundial]

but not the other part

oh wait

ok that exp sum is looking at a big O bound

and then we combine it with the big omega ?

aight

[amber kite]

thank you

[fast nacelle]

anyone know how to do these

[twilit sundial]

first one, set up a proof by contradiction

third one is a straightforward induction

second one im not as sure on how to state formally but

try casing on whether S and T are disjoint

[atomic lynx]

I'm currently doing some practice questions and struggling on this weird question

basically it wants a "round robin" tournament

• where all players play the same amount of games
• where all players play each other or if player A doesn't play Player B, they both play 2 of the same players (C and D)

example of a valid tournament

Set given is {(A,C), (D, B), (B, C), (A, D)}

A plays C
A plays D
B plays C
B plays D

Game amount: 
A = 2
B = 2
C = 2
D = 2

A doesn't play B, but both play C and D
C doesn't play D, but both play A and B

how would you approach this using discrete math?

[pearl quail]

is it possible that a series converges but its alternating form diverges?

as in the original series converges but when we include -1^n it diverges

[viral crown]

nope!

[gusty swallow]

No, you're basically asking if a series converges absolutely can it not itself be convergent, and that's impossible.

[viral crown]

look up "absolutely convergent"

[elder berry]

what exactly is the question? how many valid tournaments are there?

[flat loom]

can somebody please try and help me come up with an explanation to this

[agile magnet]

what does "pen traceable" mean

since that's not a standard term

[coral parcel]

Eulerian, I think.

[agile magnet]

see that's what I thought but also the classical question of a Knight Tour is if it's Hamiltonian or not

(and in that case idk what the explanation would be )

[coral parcel]

I think eulerian makes more sense for the term "pen-traceable", but also see #math-discussion message

[agile magnet]

oh I missed that

[empty vale]

how could i prove this without induction? with induction it would be easy knowing that (n,k) = (n,n-k) and (n,k) = (n-1,k-1) + (n-1,k) so we just use strong induction and expand (n,k) = (n-1,k-1) + (n-1,k) so we get (n-1,k-1) + (n-1,k) inside our sum, split the expanded expression into two sums and since with strong induction it is true for any number smaller than n and we got n-1 for the two sums, them both sums are 0

i don't think proving this without induction is as easy as saying "(n,k) is symmetric so when we subtract any (n,k) with its successor we get 0"

[agile magnet]

use the binomial theorem. This is equal to (a + b)^n for the right choice of a and b

I'm trying to think as well if there's a nice combinatorial proof

like "this counts XYZ object of which there are 0" but idk any off the top of my head (may be worth Googling)

[viral crown]

there is kind of

[agile magnet]

I'm sure there is one but idk it off the top of my head

[viral crown]

||consider the number of even sized subsets and the number of odd sized subsets of a set with n elements||

[empty vale]

yeah the previous exercise was this which i proved with a combinatorial proof and didn't need to use induction but with this current sum i don't really know how to think of a problem whose sum is 0

[agile magnet]

try this @empty vale

good proof technique to be familiar with anyways

[empty vale]

alright

[empty vale]

so, i started by considering the binomial coefficients of (a+b)^n which are n+1 coefficients, i let n be odd then i separated the coefficients into two groups, even and odd coefficients, then i did an gauss sum analog and ended up with 0, is that proof sufficient for the case n odd?

Something like this

[viral crown]

i don't think this is the intended proof by way of the binomial theorem

[fossil mural]

yeah that's, uh, i have no idea what you're talking about (probably because i'm sleep deprived) but it definitely doesn't look like the proof i'm assuming spamakin was referring to

[empty vale]

oh, i wasn't supposed to do it that way? it's the one i could think of

[agile magnet]

write out the expression for (a + b)^n

[viral crown]

generally proofs of identities using the binomial theorem involve picking a certain value of a,b

[agile magnet]

put it next to this expression

pattern match

you'll get your a and b

[empty vale]

ugh, i think my issue is that i haven't seen a proof like this, the ones we've been doing so far are inductive ones, combinatorial proofs (for problem X find 2 ways to solve it differently, solution A and solution B, since they both solve the same problem, A=B) and proofs involving sets and the like

[viral crown]

hint: ||you know it's an alternating sequence...||

oops

[agile magnet]

ok let me write out what I want you to do

\sun is a thing? lmfao

ok look at this

and decide what a and b should be

[viral crown]

put equals zero on the side

[agile magnet]

texit plz

$(a + b)^n = \sum_{k = 0}^n a^k \cdot b^{n - k} \cdot \binom{n}{k} = \sum_{k = 0}^n (-1)^k \binom{n}{k}$

[vital dew]

Spamakin🎷

[agile magnet]

technically we don't know it's 0 yet, that's what we want to prove

[viral crown]

true but it's a massive enough hint given we might as well use

[agile magnet]

I'm being pedantic

nah nah we don't need this hint, I believe in them!

[empty vale]

right so i just let b = 0 and a= -1 and prove it's 0?

[agile magnet]

close!

does b = 0 work here? then you get (-1)^n = 0 which is nonsense

errr not exactly 0, I guess you get 0^0 which is whatever

but point is you're right that a = -1

but what should b equal?

hint, you can multiply by 1 wherever you want

[empty vale]

well if i let a = b = -1 then a^(k)*(b^n-k) = a^k+n-k = a^k = -1^k then i get the sum of (-1)^k(n,k) from 0 to n right?

[agile magnet]

a^(k + n - k) = a^n not a^k

I'll just tell you

a = -1
b = 1

[empty vale]

ah my bad

[agile magnet]

all g all g you're trying many things which is good

but see how I came up with that?

as an exercise, do a similar proof to show that $\sum_{k = 0}^n \binom{n}{k} = 2^n$

[vital dew]

Spamakin🎷

[empty vale]

i just let a = b = 1 then i get (1+1)^n = 2^n but also 1^k * 1^(n-k) nCk which is just the sum of nCk

[agile magnet]

yup!

nice little proof technique

no induction needed

[empty vale]

yeah, first time i've seen it, thanks for the patience

[agile magnet]

all g

this is good procrastination from studying for this final I have tomorrow

that I don't want to study for

[empty vale]

nice, my first exam is in a week for algebra, i'm still studying the basics of combinatorics and i get like 4-5 days to study divisibility

[obsidian cradle]

@karmic pilot for 11 you can prove the hint using some factorization

try to make pairs in 1 + x^(2n+1) - x^(r+1) - x^(2n-r)

yes

and now you can check the sign

yes, they have the same sign

sum those inequalities from r = 0 to (n-1)

no, what I meant is to sum these inequalities:

x+x^(2n) <= 1+x^(2n+1)
x^2+x^(2n-1) <= 1+x^(2n+1)
...
x^(n-1)+x^n <= 1+x^(2n+1)

sometimes it's a good idea to group the first term in a sum with the last one, the second one with the penultimate one, and so on

and given that there are n pairings this way and we want to prove their sum is <= n*something, an idea is to prove that every group is less or equal to that something

I don't quite understand your question, but the idea here is that to prove something like a_1 + a_2 + ... + a_n <= nA, it is enough to prove a_i <= A for i=1,n

[obsidian cradle]

@karmic pilot the inequality is symmetric, so you may assume an ordering, say a<=b<=c
multiply the inequality in 34 by abc and use that inequality in 35

I did the calculations and it would remain to prove 3(ab^2+bc^2+ca^2) >= (a+b+c)(ab+bc+ac), which you can prove by expanding and factoring some stuff

just a remark: notice that the initial inequality is symmetric, while this last inequality is not; so the ordering that I chose is not quite random; I chose it such that the last inequality holds (this can be seen if you get the right factorization)

[plush bobcat]

In combinatorics, the questions seem to be more like riddles and I can't decipher whether I should use permutation, combination, multiplication rule etc.

finding it difficult to answer questions

[weary tiger]

Starting from this expression:
ab * (c|ab)+(ab) *

Construct a Finite Automaton using this two methods:

• thomson ( 3 steps )
• binary tree

can someone solve

[vapid cove]

How would I go abouts doing 2^{1/18} in Z_19?

[stray reef]

doesnt the mult group of Z_19 have order 18?

anything raised to the 18th power will be equal to 1, so 2^(1/18) is undefined.

[fickle steppe]

would anyone be willing to help me go through pset 1 of discrete maths (its about proofs and logic) from ArsDigita Uni with me? this seems crazy hard to me

[stray reef]

as in to assist you in doing it?

or to check existing work

[fickle steppe]

as in look at the solutions together cuz i got no clue how most of them work even after looking at the explanation

i only managed to solve problem 1

[stray reef]

...do you have PDFs of the set and solutions on hand

or like, what form do you have it in

[fickle steppe]

check dm

[fickle steppe]

not solved yet so if anyone is up to help a bit ... x)

[empty vale]

I've been using this along the material from my uni for combinatorics https://discrete.openmathbooks.org/dmoi2/dmoi.html

I recommend velleman's how to prove it as well if you don't know how to prove stuff

Some people recommend bona's combinatorics book but i read the beginning and was struggling too much

[sinful niche]

hey can anyone help me with a proof for this:

pattern shows this is equal to (-1)^n * (n+1) but i cant get a combinatorics proof down

[viral crown]

do u need a combinatorical proof here?

if not im sure induction will do fine

[runic sinew]

help

Relation set and edge set are same? '

[sinful niche]

i tried induction sorry but it does not seem to have been working

i wrote for quite some time but did not end up reaching anywhere

[viral crown]

write it out in factorial terms and just bash

im fairly convinced it will work

maybe break it up into cases for n even, n odd

so you know the right sign to use

[sinful niche]

oh thats actually fair

i will try again

ty for suggestion

[vivid osprey]

Hello there. I have a basic question. I would like to show that the cartesian product of two countable sets is countable. So I have a bijection from the naturals to A and a bijection from the naturals to B. So there exists a bijection from A to B by transitivity. Now, how do I use these facts to say there exists a bijection from N x N into A x B? I can use the Schröder-Bernstein theorem, though I'm not sure how.

I can use the fact N x N is countable, so by the theorem, it seems to me all I need to find is an injection from N to A x B.

[coral parcel]

Do you already have a bijection between N×N and N?

[vivid osprey]

yes

[coral parcel]

Okay, suppose:
f: N -> A is a bijection
g: N -> B is a bijection
then you can define a bijection h: N×N -> A×B by
h(n,m) = (f(n), g(m))

No need for Bernstein here.

[vivid osprey]

ah, nice 🙂

[vapid cove]

Hi how to do 11^37 mod 23?

I’ve used Fermat little theorem (x^p = x in Z_p) so far:
11^23 = 11 in Z_23
I now need to find 11^15

So to approach this, I used the squaring method, to get 11^8
11^2 mod 23 = 6
((11^2)^2) mod 23 = 11^4 => 6^2 mod 23 = 13
(((11^2)^2)^2) = 11^8 => 13^2 mod 23 = 8

[coral parcel]

Then you just need to multiply together 11^1 · 11^2 · 11^4 · 11^8.

[vapid cove]

Is my above calculations seem right?

[coral parcel]

The general approach looks right; I haven't checked the detailed numbers.

[vapid cove]

6 * 20 * 13 * 8

In mod 23?

[coral parcel]

Yeah.

[vapid cove]

That gives me 14

Then do I use the answer from flt and multiply that by 14 and mod 23?

[coral parcel]

You can also square once more to get 11^16 and then divide by 11 (whose inverse is clearly -2).

[fossil mural]

...where did you get 20 from

[coral parcel]

14 would then be the final answer. What Fermat told you was that 11^37 == 11^15 (mod 23).

[vapid cove]

Oh shoot I mistaken it for 11^3 instead of 11^1, so it should be a 11 instead. So 6*11*13*8=6864 mod 23 = 10

[coral parcel]

My computer agrees:

$ calc 11**37 % 23
    10
$ 

[vapid cove]

What I don’t understand is why we don’t do anything with the value from fermats

[fossil mural]

11^23 = 11
11^37 = 11^23 * 11^14 = 11 * 11^14 = 11^15

so then we compute 11^15 and that's the final answer

[vapid cove]

Because that lets us find 11^23

[vapid cove]

Yeah so we found 11^14 mod 23 to be 10. So surely we multiply that by 11 and then mod 23?

[vapid cove]

Does ur computer agree 162^111 in Z_23 is 10

[coral parcel]

No.

[vapid cove]

Oh no I’ve done something wrong then 😭

[coral parcel]

It says that 162 == 1 (mod 23), though.

[stray reef]

,calc 161/23

[vital dew]

Result:

7

[vapid cove]

Can you check my methodology in calculating 162^111

[coral parcel]

Also, 111 = 22*5+1

[vapid cove]

I did (162 mod 23)^111 mod 23
Brackets give 10.
So (10^111 mod 23) => 111= 3*37 so
(10^3 mod 23)^37 mod 23
Brackets give 11
So 11^37 mod 23

[coral parcel]

162 mod 23 is not 10.

[vapid cove]

162/23 = 7.04347….

0.4347*23 = roughly 10

[coral parcel]

0.04347·23 is 1, though.

It's safer to do 162 - 7·23 instead of trying to multiply up the fractional part.

[vapid cove]

Oh shoot I missed a 0!

I did (162 mod 23)^111 mod 23
Brackets give 1.
So (1^111 mod 23) = 1 mod 23

So 1 is the answer to 162^111 in Z_23?

[coral parcel]

Yes.

[vapid cove]

Oh my goodness

Silly me

Thanks 🤦‍♂️

[vapid cove]

Another quick question, how would I do 1251^5 mod 313

[hidden tide]

GG I got cooked on my discrete math final

[wicked bolt]

i would reduce 1251 first

[vapid cove]

Yeah 1251 mod 313 is 312

[wicked bolt]

and mod 313, 312 is also…?

[vapid cove]

-1 mod 313?

[wicked bolt]

yep

[vapid cove]

So what’s next

[wicked bolt]

so 1251^5 = (-1)^5 mod 313

[vapid cove]

Since its odd power, it will be negative?

So -1 mod 313

Aka 312 mod 313 (312 is the answer)

?

[wicked bolt]

yep ^^

[vapid cove]

Ty x

[ashen bane]

let A = {1,2,3,4,5,6}
How many Equivalence relations over A s.t [5] = [6] and [1] not = [2]?
my approach is to count the partitions on A, considering 5,6 the same element so it changes the problem to A={1,2,3,4,5} how much it has? where 1 and 2 not in same partition, {1} {2} {} {} {}
can someone help me continue from here

[stray reef]

ok so this is just the number of ERs on {1,2,3,4,5} with 1 and 2 not equivalent

[ashen bane]

yes

[stray reef]

which in turn is equal to the total number of ERs on {1,2,3,4,5}, minus the number of ERs with 1 ~ 2

[ashen bane]

total number of ERs on {1,2,3,4,5} is $Bell_5=52$

[vital dew]

homer

[ashen bane]

the number of ERs with 1 ~ 2 is basically again A={1,2,3,4} number of relations which is $B_5-B_4 = 52-15 = 37$

[vital dew]

homer

[ashen bane]

is it correct @stray reef ?

[stray reef]

seems so

[ashen bane]

Well you made it so simple

Thanks for clarifying

[gilded sun]

Is anyone familiar with spanning trees and the proofs behind enumerating them?

[cerulean wind]

what’s ur question

[blazing swan]

Any one can help me please

[stray reef]

you're gonna have to post the question(s) you need help with

!da2a

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[blazing swan]

how can solve this group theory question?

[stray reef]

by knowing what a group is

i.e. the definition

to do this question you just check whether each set and operation satisfy the group axioms

[blazing swan]

but how

[stray reef]

do you know the group axioms? yes or no

@blazing swan

[blazing swan]

I don't know anything

About group theory

My college university declared new topic in exam and there is a five days left

So what can i do know??

[stray reef]

well holy shit you're cooked now aren't you

but uh

i guess the least you could do is google "group theory basics" or even "group mathematics definition" or something like this

even wikipedia has it

[mental pecan]

This looks more like GRE group theory where you kind of just have to know big ideas / definitions

[stray reef]

my advice still stands

[mental pecan]

Oh yeah agreed but he’s not entirely cooked yet

Emphasis on yet of course

[stray reef]

she.

[vapid cove]

In Z_7, the quadratic residues are 0, 1, 2, 4. How do i find their square roots?

[coral parcel]

If you want to find all of them just square 0, 1, 2, 3, 4, 5, 6 and note down the results in a table.

(you can speed the calculations up slightly by noting that a² = (7-a)².

[vapid cove]

Thats finding the quadratic residue tho

thats how i got 1, 2, 4

Im interested in their square roots

which is apparently ±1, ±3 and ±2 which i dont get respectively

[coral parcel]

The square root of each of them is the number you squared to get it.

Note that each quadratic residue (other than 0) has two equally good square roots. There's no "the" square root).

[vapid cove]

I dont understand. Heres my table:
0 -> 0
1 -> 1
2 -> 4
3 -> 2
4 -> 2
5 -> 4
6 -> 1
sO z_7 q.r is {0, 1, 2, 4}

[vapid cove]

how do they get to ±1, ±3 and ±2

[coral parcel]

So your table shows you that
0 is a square root of 0
1 is a square root of 1
2 is a square root of 4
3 is a square root of 2
4 is a square root of 2
5 is a square root of 4
6 is a square root of 1

[vapid cove]

Right

i dont see how they get to those numbers tho

so taking square root 1, this would be 1, 6?

[coral parcel]

I got them directly from your table. I did't even verify your arithmtic myself, so I hope you calculated it right.

[coral parcel]

Yes.

Note that 6 == -1 (mod 7), which is why ±1 means the same two elements.

[vapid cove]

ohhh right

so for square root 2, this would be 3 and 4

[vapid cove]

how do u know which one to convert?

[coral parcel]

Yes.

[vapid cove]

like for example, sqrt 2, its 3 and 4, which one should i convert

[coral parcel]

You could equally well choose to write them as ±6.

But 1 is easier to calculate with than 6, so it's generally more convenient to write ±1 rather than ±6 even though the meaning is the same.

[vapid cove]

so for sqrt 2, i can write +-3 or +-4?

[coral parcel]

Yes.

[vapid cove]

Ahhh okay that makes so much sense now thank you

[vapid cove]

How did they get y=1,4 here?

[stray reef]

y^2 = 1 => y = ±1

4 = -1 bc you are in Z_5

[vapid cove]

Ah yes makes sense

[ashen bane]

I have this question:
How much ways to choose A and B subsets of {1,2,...,n}
such that 𝐴 ∩ 𝐵 = ∅.
is it the stars problem?

x1 + x2 + x3 <= n?

[coral parcel]

Each of the n elements can either be in A or in B or in neither, and all combinations of those choices are possible.

[ashen bane]

why in that case it's not the stars problem

[coral parcel]

Because that would count A={1}, B={7,5} as the same solution as A={2}, B={1,3}.

[stray reef]

because cardinalities don't suffice to describe the choice of A and B

[coral parcel]

Both of these have (x1,x2,x3)=(1,2,n-3)

[ashen bane]

so basically what im doing here is counting the different number of cardinalities, correct?

[coral parcel]

Yes.

[ashen bane]

Oh understood

[stray reef]

^

[ashen bane]

Im askign this dumb question only to understand this deeper

[ashen bane]

so it's 3^n

[coral parcel]

Yes.

[ashen bane]

Thanks

[vapid cove]

How do you go abouts determining whether an elliptic curve is cyclic or not?

for example, y^2=x^3 - x has order of 8 in Z_5:
(0,0), (1,0), (2,1), (2,4), (3,2), (3,3), (4,0), O.

[ashen bane]

hey

if i have x1 + x2 + x3 = 10
for example and i know x1 < 5
and i want calculate all the options.
is it better using the completement?
calculating when x1 >=5?

i have this question, i was able to solve a-c, now im wondering on d

is it basically helpful to work with the completement ?

so calculating where there more than 15 quarters chosen and more than 20 dimes chosen, and then using completment?

[ashen bane]

if it was for A,B,C
my approach is the next: x arbitary value, can go eiter to AB, AC, BC, A , B,C or none
this is 7 options that he can go into, therefore 7^n is the solution?

[latent flume]

can anyone confirm my answer idk if its correct or no

[ashen bane]

Arranging 8 blue chairs and 2 green chairs in circle? how many arrangements possible?

[uneven violet]

The two green chairs can have either 0, 1, 2, 3, or 4 blue chairs between them (the case of 5 blue chairs between them corresponds to the case of 3 blue chairs between them).

[ashen bane]

Can you elaborate?

[uneven violet]

Yeah

When the 10 chairs are arranged in a circle, use the positions of the two green chairs to distinguish between configurations. I expect the problem to assume that one configuration where the two green chairs are right next to each other is the same as another configuration, where they are right next to each other, because you can rotate the circle to get one from the other.

[vapid cove]

I’ve been given P (2,7) and I found 2P (5,2) for elliptic curve using double point addition. How do I find 3P?

[uneven violet]

And if you have a configuration, where there's 5 blue chairs between the two green chairs, then you can go around the circle the other way around to notice that the other way has only 3 blue chairs between the two green chairs (because there are 8 blue chairs in total).

[ashen bane]

ok ill try that tanks

[uneven violet]

np

[runic sinew]

how i can find all cycle of a graph

[sour flume]

hi I have always sucked at counting questions and had a really hard time learning the counting aspect of discrete math

does any one else here share the same pain?

if so how did you overcome it

and are there any good textbooks that holds the readers hand and shows you how to do it?

[analog mortar]

hi i need help

[ashen bane]

Let's say i have a circle. with 12 slots, now suppose i have 5 kids
I want them to sit around the table but no two kids adjacence to each other.
If i choose place for first kid its 1 option.

now i have 4 kids to spread without sitting to each other, how to do it? im trying to convert it to stars problem

[vestal bronze]

so there's 9 spots

for them

5 empty

.X.X.X.X.X.

6 choose 4?

no

maybe

yeah, so you place 5 empty spots around 4 kids, so 5 stars and 4 bars

but 3 stars are necessarily inside

so 2 stars and 4 bars

6 choose 4 again

[ashen bane]

can you explain

[ashen bane]

you draw here 11

not 9

[vestal bronze]

there will be 5 empty spots

and there will be 6 places where a non empty spot can go

like two spaces will be neither empty or have a kid

K X K X X X K X K

2 spaces disappeared so it's 9

[ashen bane]

ok this is example of arrangement

[vestal bronze]

i gave 2 different solutions by the way

this is not entirely like stars and bars

[ashen bane]

oh

[vestal bronze]

the second solution is entirely like stars and bars

[ashen bane]

this one

[vestal bronze]

yes this one

[ashen bane]

where is the second lol

"yeah, so you place 5 empty spots around 4 kids, so 5 stars and 4 bars
but 3 stars are necessarily inside
so 2 stars and 4 bars
6 choose 4 again"

[vestal bronze]

sorry yes

[ashen bane]

ok so i have 4 kids, and i want 5 bars around em, but i dont want kids in the same zone

[vestal bronze]

the kids are bars

[ashen bane]

oh

[vestal bronze]

you can have multiple empty spaces in the same zone

[ashen bane]

that's bugging me

[vestal bronze]

but you need to put 3 empty spaces in between the kids immediately

so 5−3 leaves 2 spaces to freely put anywhere

[ashen bane]

so the kids are the bars, and i dont want bars near to each other

[vestal bronze]

and you achieve it by doing minus 3 stars

these stars are used to separate

[mental mirage]

i suddenly open this and read "kids are the bars"

[ashen bane]

K B K B K B K this is necassary, now i have more 2 bars to spread correct?

[vestal bronze]

stars

yes

[ashen bane]

stars

[vestal bronze]

empty spaces

2 into 5

[ashen bane]

so there are actually 2 balls into 5 options

[vestal bronze]

yes

[ashen bane]

but then it's 5*5

doesnt make sense

each ball has 5 options

[vestal bronze]

it's (2+4)C2

[ashen bane]

But we said 5 options

[vestal bronze]

5 options means 4 bars

4 kids

K S K S K S K

left, right and 3 middle

5

[ashen bane]

hm

i think i lost this 😢

I have 4 kids, and 5 big people
K B K B K B K B B
ye ireally lost it

[vapid cove]

Hi,

Enigma machines:
How can the number of plugboard settings be calculated, assuming 10 sockets and 4 cables.

[verbal zephyr]

(British spy alert! 🕴️)

[vital dew]

quickdoom

[lusty loom]

Any help is greatly appreciated

[lusty loom]

I just realised k+1>N cannot happen for k=1,2,3,...,N-1

So i just need an answer for question (1)

[elder berry]

hi, I don't think your subgraph accounts for wins against players outside that subgraph. I don't think it is necessarily true that the number of wins of the teams with indices k, k+1, ..., N is \binom{N-k+1}{2} because you might not be accounting for edges that point to vertices Xj for j < k, like x1 for example

[weary tiger]

anyone know how to do (i)

show me how to solve (i) so then i can solve (ii)-(iv) myself

[silk kernel]

for (i), if we want to place r items into two boxes, for each item we have two choices. this gives us 2^r. we have to subtract two from this, because we don't want the options where we put all of the items into to the first box, or all of the items into the second box, since no box should be empty. this gives us 2^r - 2. finally, because both boxes are identical, we need to remove any options that are just the same but with the boxes swapped. this means we have to divide by 2, and we get: S(r,2) = (2^r - 2) / 2 = 2^(r-1) - 1.

[hallow apex]

I'm slowly reading through Grimaldi's Discrete and Combinatorial Mathematics, is anyone kind enough to tell me what {A} means if A = {1, 2, 3, 4}?

i must have rushed a bit and skipped it

[stray reef]

it just means a set whose only element is A (which is itself a set)

can you share the question(s) where you saw that tho

[hallow apex]

example 3.5 in the book

[stray reef]

yeah what i said stands

[lusty loom]

Yeah the subgraph H induced by the edges Xk,X(k+1),...,XN only includes the edges between XK,X(k+1),..,XN.H is a complete graph (because G is complete) so there will be binom{N-k+1}{2} edges in H. So the total number of wins over all vertices in the H should be binom{N-k+1}{2}

The whole point of considering the subgraph was to get rid of edges between teams that are not in the subgraph, like X1, so we have only edges between Xk, X(k+1),...,XN which there are binom{N-k+1}{2} of

[elder berry]

right, but does that not change the values of xi, since initially xi meant wins of team i against all other teams, and now it is wins against all other teams with index greater than some k?

[lusty loom]

Ah yes

[lusty loom]

Thank you, i felt like there was a fault but i wasnt able to pin point it

[weary tiger]

wtf is discrete maths

ITS THE SIMGA

best greek letter

[vital dew]

quickdoom

[lusty loom]

@elder berry this fixes the problem you pointed out

[weary tiger]

what is this 💀

[elder berry]

looks good

i have one other concern with the contradiction part

currently the problem is of the form:
if given stuff, show all xi are bounded

for a contradiction, maybe assuming that all xi are not bounded is incorrect(?), as in the negation of all xi are bounded is there exists at least one xi for which those inequalities do not hold

wait ur argument doesnt use that

[lusty loom]

I have assumed that xk<(N-k)/2 only for k

[elder berry]

yeah im being dumb, then it looks sound

[lusty loom]

Yeah, the other N-k inequalities follow from the ordering

Thank you for helping 😊

[elder berry]

no worries

[weary tiger]

Status 1

[hard citrus]

trying to prove that when moving from number base $a$ to number base $a^n$ you can take $n$ digits and convert them to a single digit in base $a^n$ is there a way to represent this in a simple expression? $$d_{m-1}\cdot a^{m-1}+d_{m-2}\cdot a^{m-2}+\cdots+d_{0}\cdot a^{0}$$ or to represent as a single digit the following for some $k$ $$\sum_{i=(k-1)\cdot n}^{k\cdot n-1} d_i \cdot a^{i-k\cdot n}$$

[stray reef]

missing some _ in a lot of places

[vital dew]

horizon2.0

[hard citrus]

yeah they disappear when copying and pasting

[stray reef]

@weary tiger i rewrote your summation with somewhat clearer notation that doesn't end up as a mess of superscripts and subscripts all running into each other

[weary tiger]

👍

[stray reef]

$\binom{20}{k}\binom{20-k}{9-k}$ can be rewritten in a cleaner way if you expand it all with factorials

[vital dew]

|Ann⟩

[weary tiger]

1 min

[stray reef]

and then it all ends up very nice

[weary tiger]

I didn't think of that

[stray reef]

i am using $\binom{n}{k}$ to mean ${}^nC_k$, to be clear on that

[vital dew]

|Ann⟩

[weary tiger]

I thought it 2ould be the coefficient of some term when 2 different binomial are expanded

[weary tiger]

👍

[hard citrus]

does this question belong here or is there a more suited channel for that?

[weary tiger]

Very nice.....

I thought this was a hard one

Got it

Thank you

[stray reef]

the difficulty was in the notation imo

[weary tiger]

"Notation imo "?

[stray reef]

imo = in my opinion

[weary tiger]

Oh

[weary tiger]

thanks

[plain shoal]

if we want to disprove something, can we do it only using an example that disprove it?

[cerulean wind]

if you think some statement saying for all x : p(x) is false, then yes, you can disprove that statement by providing a counter-example

really what you're doing is proving that there is an x such that ~p(x) is true

[weary tiger]

where do the 3 and 7 come from (and 6 for the matter)

[cerulean wind]

cancellation of lower order terms

[weary tiger]

?

what do you mean by cancellation of lower order terms

[cerulean wind]

you are trying to write x^3 as a linear combination of (x)_n's

[weary tiger]

ah yes

[cerulean wind]

so the constant, linear, and quadratic terms must vanish

[weary tiger]

thats true

[cerulean wind]

and that number, 3, makes that happen

[weary tiger]

ok

so for x^5 what would i need to do?

as an example

(this isnt the question to the problem but it helps me see)

let me try x^5

[cerulean wind]

there is a pattern in the picture.
for a natural n, you have x^n = sum_k S(n,k) (x)_k for k = 1 to n

[weary tiger]

yes

you guessed the question

🤣

[cerulean wind]

one of the best methods

[weary tiger]

Show that $x^r = \sum_{n=0}^r S(r,n) (x)_n$

[vital dew]

Derivative

[weary tiger]

thats the question

and you need to use induction (at least thats what i think you need to do)

this is what i have done

so the case r = 1 is trivial

[cerulean wind]

what is (x)_0

just 1?

[weary tiger]

yes

[cerulean wind]

coo

[weary tiger]

so i assume it holds for r =k

$x^k = \sum_{n=0}^k S(k,n) (x)_n$

[cerulean wind]

x^k

[vital dew]

Derivative

[weary tiger]

so now i check it holds for x=k+1

[cerulean wind]

is S(n,0) = 0?

[weary tiger]

yes

because we are putting n objects in 0 boxes such that no box is empty

thats stirling numbers of the second kind

so here i where i am at right now

$x^{k+1} = xx^k = x\sum_{n=0}^k S(k,n) (x)_n$

[vital dew]

Derivative

[weary tiger]

seems like its done

[cerulean wind]

no

[weary tiger]

ah so what am i missing

unless i took the wrong path

[cerulean wind]

there may be a way to do it this way, but i was thinking of starting with the sum and applying a recursive formula for the stirling numbers

[weary tiger]

so S(k+1,n) = k+1S(k,n)?

that actually works for stirling numbers of the first kind

i think it applies to the second kind as well

because it makes sense

[cerulean wind]

it should be S(n + 1, k) = kS(n, k) + S(n, k - 1) for the second kind

[weary tiger]

ah

i never proved such a formula

i think i would need to prove it

[cerulean wind]

induction again

[weary tiger]

because in my textbook they dont show that formula

yes but how do i find a formula like that in the first place

and why doesn't S(k+1,n) = k+1S(k,n)?

i think it does

because we select one object to put in 1 box

k+1 choices. then we just need to arrange the k objects in n boxes such that no box is empty

[cerulean wind]

do you mean S(k+1,n) = (k+1)S(k,n)?

[weary tiger]

yes

because if we start with the sum

[cerulean wind]

thats not correct for the stirling numbers of the second kind

[weary tiger]

ah why is that?

because we choose 1 object for 1 box. k+1 choices

then we arrange the remaining k objects in the n boxes such that no box is empty (boxes are identical)

(k+1)S(k,n)

[cerulean wind]

not quite.
so lets say that there are n + 1 objects. we want to place them into k non-empty boxes

so, consider the last element, e. e is either in its own box or it shares a box with another element.

if it is in its own box, then the rest of the elements can be matched in S(n, k - 1) ways since there are now effectively k - 1 boxes (one whole box was used for e)

if it shares a box, then we can first place n objects into k non-empty boxes in S(n,k) ways. then, for each of these ways, we can place e into one of k boxes, leading to kS(n,k) total ways to match n + 1 objects into k non-empty boxes where e shares a box
@weary tiger

adding the two possibilities together gives you the recurrence

[weary tiger]

ah i see

[cerulean wind]

once you have that, then
$$\sum_{k = 0}^{n+1}S(n+1,k)(x)k = \sum{k = 0}^{n+1}(kS(n,k) + S(n,k-1))(x)_k = \cdots$$

[vital dew]

c squared

[weary tiger]

ahh i see

[cerulean wind]

should work out nicely. remember, S(n, k) = 0 = S(n, 0) for n < k

[weary tiger]

ok i will try

[hard citrus]

question in Boolean algebra and specifically addition/subtraction in two's complement notation:
how am i supposed to do these problems?
0111+0001=? i got 1000 but that means negative 0 and an overflow
0101-0110=? i converted the negative with the complement giving me 0101+1010=1111 but it doesn't make sense since in decimal its 5-6=-1 which when converting it becomes 5+(-2) =3 and the result i get at the end is actually -7
or for example coverting 9 + (-19) => 001001 + 110011 = 111100 which in two's complement is actually -28
the rules I've learned dont help
(addition of different signed numbers is always correct but need to leave out the carry bit, in addition of same signed numbers if the 2 MSB are different there's overflow and we'll use the carry bit, and if the 2 MSB are the same then there's no overflow and we'll leave out the carry bit)

[cerulean wind]

sign extend to five bits wide

also, in four-bit two's complement, 1000 is -2^3 = -8

there is no negative 0 in two's complement

negative 0 occurs in signed magnitude a.k.a. one's complement

[weary tiger]

are you sure the sum goes to n+1?

or does it go to n

for the right hand side

[cerulean wind]

yea

[weary tiger]

it goes to n+1?

[cerulean wind]

but you can shift the indices on the sum to make it work

[weary tiger]

how?

[cerulean wind]

so like, the first term is $$\sum_{k = 0}^{n+1}kS(n+1,k) = \sum_{k = 1}^{n+1}kS(n+1,k) = \sum_{k = 0}^{n}(k+1)S(n+1,k+1)$$

[vital dew]

c squared

[weary tiger]

ah i see

you went from 0 to n+1

and then 1 to n+1

so you subtratced 1

right now i am at this

maybe if i show my work a bit more it will be more helpful

[cerulean wind]

i see how you got there, nice work

[weary tiger]

thanks

but we are not done

[hard citrus]

Which still isn't the answer tho.
And I didn't understand your first reply

[cerulean wind]

0111 + 0001 is the same as 00111 + 00001

[sharp ibex]

need help with those 2 please

[cerulean wind]

in the first sum, you can write it as $$\sum_{n = 1}^{k}S(k,n)(x)_{n+1}$$

[vital dew]

c squared

[cerulean wind]

hmm. this is a bit tricky. i can't quite work it out in my head atm. let me writ it out and get back to you

[cerulean wind]

use the binomial theorem and pascal's identity. 1.70 is a special case of 1.69

[weary tiger]

ok here is where i am at now

oh wait mistake

[hard citrus]

Oh I know that but was specifically asked to stay with 4 bits, so that means overflow and the answer has no meaning,
The second problem there is the real problem for me

[weary tiger]

this is where i am at

[cerulean wind]

1111 is negative 1. -8 + 7 = -1

an $n$-bit two's complement digit is represented as a string of binary digits $(b_{n-1},\dots,b_0)$ and we convert to decimal by $$\sum_{k=0}^{n-2}b_k2^k - b_{n-1}2^{n-1}$$
where $b_k \in{0,1}$ for each $k = 0,1,\dots, n-1$.

[vital dew]

c squared

[sharp ibex]

got it thanks

struggle with proofs and couldn't find pattern

[cerulean wind]

it looks like you are conflating this with one's complement (or signed magnitude), where an $n$-bit one's complement is represented as a string of binary digits $(b_{n-1},\dots,b_0)$ and convert to decimal by
$$(-1)^{b_{n-1}}\sum_{k = 0}^{n - 2}b_k2^k$$ with $b_k \in{0,1}$ for each $k = 0,1,\dots,n-1$. we allow negative zero to be distinct from zero

an $n$-bit two's complement digit is represented as a string of binary digits $(b_{n-1},\dots,b_0)$ and we convert to decimal by $$\sum_{k=0}^{n-2}b_k2^k - b_{n-1}2^{n-1}$$
where $b_k \in{0,1}$ for each $k = 0,1,\dots, n-1$.

[vital dew]

c squared

[weary tiger]

now what do i do after this

it seems complicated

my final answer is supposed to be

$x^{k+1}$

[vital dew]

Derivative

[weary tiger]

and that n in from of the S(k,n) is annoying me hahah

what do i do with it

i have to use my assumption

this is difficult haha

but at least we got the recurrence formula

@cerulean wind have you tried to solve it?

well this is where i am at rn:

its more that I don't know what to do with the second sum. and the (x)_{n+1}

[hard citrus]

yeah i think you're right im confusing the two, for example how for example i calculate -19 two's complement?
how i understood we do it is start with a 1 to represent negative at the MSB and then just write the string of number in binary that represent the magnitude, in this case 10011 so the two's complement must be 110011 but i belive i'm wrong

[cerulean wind]

in order to write a negative number in two's complement:

1. write the number in binary (normal binary)
2. invert each bit
3. add one

[hard citrus]

and add the MSB of 1, right?

so for -19 it'll be $(10011)'+1=01101$ which gives us the final result 101101

[vital dew]

horizon2.0

[weary tiger]

ah i see

thats good

but what's x

ill be at this expression

[vital dew]

c squared

alright, so i'm going to advise that you just start the sum from 1 instead of 0; starting from zero is redundant. although it was tough for me to see initially, it is easier to start with your original approach

$$\begin{align*}
x^{k+1}
&= x^kx\\
&=\sum_{n=1}^kS(k,n)(x)_nx\\
&=\sum_{n=1}^kS(k,n)(x_{n+1})+\sum_{n=1}^knS(k,n)(x)_n\tag{$(x)_{n}x = (x)_{n+1}+n(x)_n$}\\
&=(x)_{k+1}+\sum_{n=1}^{k-1}S(k,n)(x)_{n+1}+\sum_{n=2}^{k}nS(k,n)(x)_{n} + x\\
&=(x)_{k+1}+\sum_{n=2}^kS(k,n-1)(x)_n+\sum_{n=2}^knS(k,n)(x)_{n}+x\\
&=(x)_{k+1}+\sum_{n=2}^k(S(k,n-1) + nS(k,n))(x)_n + x\\
\end{align*}$$
```Compilation error:```! Package amsmath Error: Erroneous nesting of equation structures;
(amsmath)                trying to recover with `aligned'.

See the amsmath package documentation for explanation.
Type  H <return>  for immediate help.
 ...                                              
                                                  
l.66 \end{align*}
                 $$
Try typing  <return>  to proceed.
If that doesn't work, type  X <return>  to quit.```

[weary tiger]

hmm

i see a bit

but not much

let me write on my paper

[cerulean wind]

the last line wont load

lol

[weary tiger]

ok but how did you go from step 2 to 3?

why dont you start at 0?

[cerulean wind]

\begin{align*}
x^{k+1}
&= x^kx\
&=\sum_{n=1}^kS(k,n)(x)nx\
&=\sum{n=1}^kS(k,n)(x_{n+1})+\sum_{n=1}^knS(k,n)(x)n\
&=(x){k+1}+\sum_{n=1}^{k-1}S(k,n)(x){n+1}+\sum{n=2}^{k}nS(k,n)(x){n} + x\
&=(x){k+1}+\sum_{n=2}^kS(k,n-1)(x)n+\sum{n=2}^knS(k,n)(x){n}+x\
&=(x){k+1}+\sum_{n=2}^k(S(k,n-1) + nS(k,n))(x)n + x\
&=\sum{n=1}^{k+1}S(k+1,n)(x)_n
\end{align*}

[vital dew]

c squared

[cerulean wind]

because S(k,0) = 0

so we're just adding zero and we don't need to in the proof

[weary tiger]

okso you start at 1 true

ok how do u go from step 2 to 3

[cerulean wind]

i use the fact that $x(x)n = (x){n+1}+n(x)_n$

[vital dew]

c squared

[weary tiger]

how?

which property

i didnt know that haha

[cerulean wind]

yea, just some playing around

[weary tiger]

but is it trivial?

[cerulean wind]

$$x(x)_n = (x - n + n)(x)_n = (x - n)(x)n + n(x)n = (x){n+1} + n(x){n}$$

[weary tiger]

well $x \times x_1 = x^2$

[vital dew]

Derivative

[weary tiger]

$x \times x_2 = x^2 + x^2(x-1)$

[vital dew]

Derivative

[weary tiger]

so i see that $x(x)n = (x){n+1}$

[vital dew]

Derivative

c squared

[cerulean wind]

this is not true

[weary tiger]

ye i forgot about somethin

how does (x-n) (x)_n = (x)_n+1

[cerulean wind]

$$(x)n = \prod{j = 0}^{n-1}(x - j)$$

[vital dew]

c squared

[cerulean wind]

does that help

[weary tiger]

yes it does haha

yesssir

amazing

wow u r so good

but this problem is so complex

you need to prove so many things

its like a recursive proof

[cerulean wind]

yea, this was a tough one

[weary tiger]

proof within a proof within a proof

im self teaching myself combinatorics

and i dont recommend

its way too hard

you need a different mind

[cerulean wind]

counting is hard

[weary tiger]

yes it is very difficult

when do people typically learn stirling stuff?

undergrad?

like i havent even done discrete math yet

haha

ive only done prob and stats

[weary tiger]

@cerulean wind i have understood the problem

thank you very very much

it is greatly appreciated

truly

❤️

[cerulean wind]

yea

a pleasure working with you!

[weary tiger]

thanks!

[weary tiger]

i am so close to solving this here is what i did

so first this is the reccuring identify for stirling number of 1st kind: $s(k+1,n) = s(k,n-1) + ks(k,n-1)$

[vital dew]

Derivative

[weary tiger]

now here i where i am at

r=1 is trivial

assume it holds for r=k

ie: $x(x+1)(x+2) \dotsb (x+r-1) = \sum_{n=0}^k s(k,n)x^n$

[vital dew]

Derivative

[weary tiger]

now we check for r=k+1

as you can see on my last step I am so close to finding a solution

but i must have made a mistake somewhere

please let me know where

unless we dont worry about that x value and $xs(k,n-1) + ks(k,n-1) = xs(k+1,n)$

[vital dew]

Derivative

[weary tiger]

but i dont know if this is mathematically valid haha

like 5x+6 is now equal to 11x

thats why i must have made a mistake with the x^n's

[cerulean wind]

when you go from s(k,n) to s(k,n-1), you need to also decrement k

[cerulean wind]

i think you're recurrence is wrong though. i thought it was s(k + 1, n) = k s(k, n) + s(k, n - 1)

[weary tiger]

now its for stirling of the 1st kind sorry forgot to say

[cerulean wind]

right

[weary tiger]

the recurrence formula is different

[cerulean wind]

this is different from the recurrence for stirling numbers of the first second kind

[weary tiger]

for the first kind its this

[cerulean wind]

sorry

[weary tiger]

$s(k+1,n) = s(k,n-1) + ks(k,n)$

instead of n

[cerulean wind]

that is wrong

[weary tiger]

why is it wrong

𝑠(𝑘+1,𝑛)=𝑘𝑠(𝑘,𝑛)+𝑠(𝑘,𝑛−1)

its that

[vital dew]

Derivative

[weary tiger]

sorry i forgot

[cerulean wind]

that is correct

[weary tiger]

ok

[inner otter]

what book is those Stirling number problems from?

[weary tiger]

Principles and Techniques in combinatorics

by Chong

its from 1990

[inner otter]

cool. you've been doing a ton of them

[weary tiger]

too many

they are too hard

these problems are from chapter 1

intro to permutations and combinations

apprently this book is used for math competition

[weary tiger]

ye so lemme redo it since the formula was wrong

[weary tiger]

alright i fixed it

i have one more pretty tough problem i cant solve

its discrete math combinatorics again

from that same book

@cerulean wind here is the final proof

thanks again btw!

[cerulean wind]

that looks great

[weary tiger]

thanks!

can i post another question?

this one is tough but i am sure we can solve it

i started it already a bit

i came up with a few observations

im finally done with the stirling part of this problem set

but now i am on to geometrical combinatorics

those are probbaly the worst

here it is

now here are the observations:

when one chord is drawn, there are 2 regions

so we always need to add 2

if a chord has no intersection, then it adds one region

if a chord as an intersection it adds 2 regions. We can generalize that if a line as k intersetions it adds k+1 regions

also concurrent means that two chords can only intersect at the same point once

now, how do i put this all together

[mental mirage]

combi is more than just counting tho lol

whenever i am doing those counting probs i miss out on a case or smth

However it becomes really interesting when u hit things like game theory

[plain shoal]

what does it mean that a full relation is anti-symmetric and can we disprove that this is not a full relation {(2,3) ,(2,1) ,(1,2) ,(3,3) ,(2,2) ,(1,1)} = R by highlighting the pairs (1,2) and (2,1) they are symmetric?

[plush bobcat]

Thank you so much

[weary tiger]

anyone know how to do this?

[empty vale]

so, i gotta prove

which i already did like this

but i was told that i also could prove it using "remained tables" but i'm clueless about this

saw some solutions from people that did the same course but years later and this was one of the "solutions"