discrete-math

[narrow sorrel]

@grave totem So, the question is wrong?

[grave totem]

ig

[narrow sorrel]

Thank you

[dry raven]

So I’m confused. Why is it that when a div or mod is negative you go over. So -13 div 6 is -3 not -2, and -13 mod 6 is 5 and not -1?

Can you just round up when negative div

[haughty garden]

Well -1 is congruent to 5 in mod 6, we just like to assume that the remainder is an integer between 0 and 5

[dry raven]

Honestly I’m more confused now haha what do you mean

[haughty garden]

You can express -13 as -1 (mod 6) or 5 (mod 6) if you wanted

By convention, we always like the remainder to be positive

That’s why it’s preferred that we write -13 as 5 (mod 6) over -1 (mod 6)

[weary tiger]

Is there any course or lesson we should have studied earlier before we get started on discrete maths???

[gritty crescent]

No, but familiarity with basic algebraic manipulations and mathematical reasoning should be almost necessary.

Specific courses titled "discrete mathematics" might have a higher bar depending on the target audience.

[weary tiger]

ok, thanks 🙂

[dry raven]

When doin binary expansion do you base the number you div/mod on the number of digits. So 27 you would do 27 div 2 and 27 mod 2.

[coral parcel]

That's (the beginning of) one way to convert to binary, yes. But what does that have to do with the number of digits?

[dry raven]

Where does the 2 come from I guess is what I’m asking

Why is it 2?

[coral parcel]

Because that's what "binary" means. Binary is base 2.

That doesn't depend on how large or small the number you're expressing is.

[dry raven]

Gotcha that’s what I was wondering

Professor didn’t explain that haha thank you

[stray reef]

@dry raven it's been several hours, but there's something worth pointing out: the same algorithm can be used to convert into other bases - just swap out the 2 for the base you're converting into.

[balmy dome]

can someone explain how this answer comes about

[stray reef]

from -1 < x^2 - 2 < 2, add 2 to everything to get 1 < x^2 < 4

then square-root everything to get 1 < |x| < 2

[patent fulcrum]

Hey. Question. What's the formal definition of algorithm in computation theory?
And simply speaking how do you prove that you cannot determine if an algorithm halts?

[stray reef]

an algorithm is a sequence of steps that can be executed by a turing-complete system

also are you talking about undecidability when you're asking about being "unable to determine" if an algo halts?

[patent fulcrum]

What's a step?

[patent fulcrum]

Ummm..... I'm asking it's not true that you can always predict that an algo halts for a given input and algo

[stray reef]

what does "predict" mean

okay you know what

this is going precisely nowhere

[patent fulcrum]

Why?

Predict means say

determine

the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever.

[stray reef]

really instead of problems we should be talking about languages

the language corresponding to a problem is the set of instances for which the answer to the problem would be yes

and then you can speak of a language being decidable

[patent fulcrum]

Are you describing the input?

or the machine

[stray reef]

turing machines take strings as input yes

[patent fulcrum]

Makes sense

[stray reef]

the halting problem as a language consists of all strings of the form <M, w> where M is a turing machine (described in some way) and w is the input to M

and the statement "the halting problem is undecidable" means there does not exist a turing machine which decides the language of the halting problem

[patent fulcrum]

Since a language is equivalent to set of naturals, we can just consider a machine as subset of N -> N mapping, right?

[stray reef]

not really

maybe like, partial functions from N to {accept, reject}

a turing machine decides a language if it accepts all yes-instances (strings in the language) and rejects all no-instances (strings not in the language) and never loops

[patent fulcrum]

That sounds exactly like <=> a set is computable

[stray reef]

perhaps it does

[patent fulcrum]

Right so. Assume we have a description of a turing machine. Which is essentially a word of some language. Which corresponds to some finite natural number by some bijection.
Now... our machine returns yes, no, or never halts for each natural number.
Why cannot we predict the answer?

If I understand it correctly, this is equivalent to the halting problem

[stray reef]

for a particular machine we can predict its answer by running it

[patent fulcrum]

That won't always work

If it never halts, we will never know the answer

[stray reef]

then i guess i have no idea what you are talking about anymore

[patent fulcrum]

😢

What is the halting problem is about then?

I think I interpreted it correctly, but ...

Lmao

Okay I read the proof

he proof proceeds as follows: Suppose that there exists a total computable function halts(f) that returns true if the subroutine f halts (when run with no inputs) and returns false otherwise. Now consider the following subroutine:

def g():
    if halts(g):
        loop_forever()

halts(g) must either return true or false, because halts was assumed to be total. If halts(g) returns true, then g will call loop_forever and never halt, which is a contradiction. If halts(g) returns false, then g will halt, because it will not call loop_forever; this is also a contradiction.

Lmao

I'm laughing hard

that's just some ⭐ kind of proof

[coral parcel]

It's quite famous, and one of the two or three prototypical examples of a "diagonalization" proof.

[patent fulcrum]

I see

Question btw ; if an algorithm is a sequence of steps which yields something from a finite or countable set. What is a step of an algorithm?

[coral parcel]

Basically, "something you can program a machine to do". The description is deliberately vague and intuitive, such as not to get bogged down in technical details of exactly how programming or configuring a machine works. There are quite a lot of different-looking ways of setting up crisp definitions to back the intuition; they turn out all to lead to the essentially the same concept of what counts as an algorithm (this is the Church-Turing thesis). The reason we're keeping the word "algorithm" vague is such that we can still talk to each other even though we might prefer different ways of formalizing the details.

For a programmer "algorithm" means roughly "the intuitive idea behind how a piece of code does what it does, abstracting away from the details of writing it in a particular programming language".

[patent fulcrum]

Everything up to the computation models is well-formalized. I can track any statement down to the root of ZF theory.
Now... algorithm becomes some ... heuristically set word 😢

And so because I'm used to formal thinking, it's hard to grasp the exact meaning

[coral parcel]

Because the meaning deliberately isn't exact.

[patent fulcrum]

Yeah, I understand your point

[coral parcel]

If you want to speak in crisp terms, you won't go much wrong by mentally substituting "Turing machine" each time people say "algorithm", for example.

[patent fulcrum]

The reason we're keeping the word "algorithm" vague is such that we can still talk to each other even though we might prefer different ways of formalizing the details.
How can you be sure you talk about the same thing if it's not formalized?

[coral parcel]

There are formalizations, and each pair of them can be rigorously shown to be equvialent to each other in expressive power. The word "algorithm" is used to refer to "algorithms in any chosen formalism that can be proved equivalent to this canonical class of formalizations", such that one can talk about things without appearing to commit to one of them.

[patent fulcrum]

Okay, so algorithm is a generalization of instances of computational models, right?

And so, there's a formalized definition of Turing machine algorithm?

[coral parcel]

Let's say that the word "algorithm" means "computation realized in some computation model".

[patent fulcrum]

Right. So we can talk about an algorithm realized in Turing machine?

[coral parcel]

Correct.

If you're choosing Turing machines as your computational model, you wouldn't generally say "Turing machine algorithm", but just "Turing machine".

[patent fulcrum]

Aha

So a single machine implements some algo?

[coral parcel]

Yes.

[patent fulcrum]

Interesting. Well, as long as Turing machine has a formal definition, and all potential turing-complete machines have corresponding proofs about it, it's all good

[coral parcel]

It is definitely expected that if you claim your computational model is Turing complete, then you have actual proof of that fact.

[patent fulcrum]

What are examples of non-Turing-complete models?

[coral parcel]

One example is programs whose only looping construct is FOR loops where you need to specify the iteration count before the loop starts.

[patent fulcrum]

That one is strictly less powerful than a Turing machine, right?

So essentially if there's a set of mappings a machine can implement, a set of the ^ above one is a subset of that of Turing machine

That is, all algos implemented by that machine can be implemented by Turing

[coral parcel]

Indeed. Nobody has been able to propose a strictly more powerful model together with a halfway convincing argument that it ought to be thought of as physically realistic. Even quantum computers can be simulated by Turing-strong machines.

[patent fulcrum]

But who stops me from saying that my algorithm takes finite time to run any mapping from R to R?
Of course excluding this

physically realistic

[coral parcel]

Right. You can define stronger models mathematically without trouble.

[patent fulcrum]

Nice

[coral parcel]

There are such concepts as "infinite-time Turing machines", for example.

[final cliff]

Modus tollens or contrapositive look like they would be useful for this.

Idk the specific rules of ur proof system, so how exactly you might apply those rules will depend on that.

[quaint raft]

Hey if you have a matching of size n, do you also have a matching of size n-1?

[final cliff]

Double negation of E gives (E')' according to ur sheet not E'

But double negation shouldn't hurt anything and could help you in applying one of the prev rules I mentioned.

[dry raven]

so Im very lost on the bijection mapping power sets. I understand it up to where it says "to {0,1}^4 as defined above"

what is {0,1}^4

if someone could walk me through or write it out and show thought process I would be extremely greatful!

wait is {0,1}^4 the amount of digits I need in string?

then you take f({1,4}) and compare each of x={1,2,3,4} to it and use 0 or 1?

so first digit 1 == {1,4} so its 1, then 2 != {1,4} so its 0?

is that the right ideology haha idk just trying to think it out

[final cliff]

We can't see the function they are saying is defined above.

But {1,0}^4 is basically just bit strings of length 4 in this context.

[dry raven]

they dont give me a funciton...

unless they forgot to put it there lmao

[final cliff]

And from the looks of it you flip bits 1,2,3,4 to on or off based on whether 1,2,3,4 is an elt of the function you're evaluating f at.

This is kind of a variation of a well known map for representing finite sets when you have only finitely many possible elts.

[dry raven]

above it just says " the bijection mapping power sets to strings"

[final cliff]

It maps elts of the power set of {1,2,3,4} to bit strings of length 4.

[dry raven]

gotcha so was my ideology pretty much correct?

[final cliff]

I didn't really understand your reasoning very well the way you explained it.

[dry raven]

ahh so that {0,1}^4 just means length of 4 made up of either 0 or 1

[final cliff]

Lemme reread it.

Well A^B means the set of functions from B to A.

[dry raven]

when I say == or != I just mean that is or is not a element of the set

[final cliff]

In the case where B is a natural number we interpret A^B as the set of sequences of length B of elts from A basically.

[dry raven]

gotcha that makes sense

[final cliff]

"So it's 1"

[dry raven]

this is like the most confused Ive been in this class for some reason. the wording just throws me off

[final cliff]

You mean the digit at whatever position in the string is 1 when you said this right?

Oh I see yes.

You basically said that

[dry raven]

ya ya

exactly

im not great at wording

[final cliff]

Okay, it seems right to me, maybe just work on clarity and being specific?

Otherwise seems fine.

[dry raven]

alright cool sounds good thank you! im sure Ill be back lmao. cant wait til this class is over

time for the K-to-1 rule

[weary tiger]

I was wondering, howcome the primes that make up 'a' and the primes that makeup 'b' are the same?

howcome 'b' isn't written as $b=q_1^bq_2^{b_2}\cdots$

so it is sequence of different primes

than 'a's

[mystic elbow]

So far I got this

a is 100/10^7

b is P( V |D ) = ( 100/10^7)/( ( 1000/10^7)

Are these 2 answers correct??

Ping me too please

[stray reef]

you can make a and b have the same sequence of primes by including primes with 0 exponents

[weary tiger]

makes sense, thank you!

[mystic elbow]

Anyone? <@&286206848099549185>

[stray reef]

what you have so far is correct but you overcomplicated it for part b

could've just done 100/1000

[mystic elbow]

Why

[stray reef]

the number of people who died and were vaxed is 100
the number of people who died is 1000

therefore the fraction of vaxed people among those who died is 100/1000

[mystic elbow]

Ahhh

Ok got it

Can u tell how to do c and d

[stray reef]

c follows the same principle as b

you definitely know how to calculate conditional probabilities so it should not pose any issues for you

[mystic elbow]

Ok thankss

Also can u check this

For part b

@stray reef

[stray reef]

you were only asked to write the path

and you did write the path

and i have just verified that it works

there's no need to write anything else here

all you need to do for part b is "Yes, here is one possible route: c-e-h-k-g-d-b-e-g-h-f-c-b-a-d-e-f"

[mystic elbow]

Ohhh ok

But the path is correct right?

[stray reef]

and you did write the path
and i have just verified that it works

do i need to repeat what i said ten more times?

[mystic elbow]

Can you give an idea on how to do part a

[stray reef]

do you know what a complete graph is

[mystic elbow]

Just wanted to confirm since it says ‘on each path once’

[stray reef]

????

are you asking me about part a or part b

[mystic elbow]

Part b

That’s why I ping u

[stray reef]

okay fine

yes your path works yes your path works yes your path works

yes your path works

[mystic elbow]

Okayy

[stray reef]

how many times should i repeat it

[mystic elbow]

Now I’m asking about part a

[stray reef]

and i'm telling you in response to part a: do you know what a complete graph is?

[mystic elbow]

Yes

[stray reef]

can you tell me what a complete graph is?

[mystic elbow]

A completed graph is one that has an edge between every vertexs

[stray reef]

a complete graph is one that has an edge between every pair of vertices

okay, great

you're asked to draw the graph K_6, the complete graph on six vertices.

do i understand correctly that you find yourself unable to do this?

[mystic elbow]

Oh wait

Is it correct?

[stray reef]

no

there should be an edge between EVERY pair of vertices

you're missing a lot of edges

for example, this one. why didn't you join these two vertices with an edge?

what did they do to deserve such horrible treatment?

(and no this is not the only edge you're missing)

[stray reef]

okay yes now you've fixed it congratulations

[mystic elbow]

That’s all to do for part a right?

[stray reef]

yes

[mystic elbow]

Alright thanks a lot

[olive pendant]

name the following relation means

i have to name it "one to many" or like "reflexive/symmetry"?

[unique pebble]

Can anyone help me with this question?

[coral parcel]

The world may never know unless you ask it.

[grim citrus]

I have been stuck on this, my final is in a few days

can someone please help

[coral parcel]

Can you plug your f into the definition of "f(n)=O(n²)"?

[cerulean wind]

f(n) = n^2 (n^2 + 2)/(2n^2 + 1). show that for n large enough, n^2 + 2 < 2n^2 + 1

[willow fog]

a couple questions

1. if the size of the preimage of a function is equal to the size of the image, does that mean the function is injective?

2. what is the domain and codomain of
   a) x²
   b) √x

I just wanna make sure I understand

I had another question but I forget now

[cerulean wind]

by size, do you mean cardinality?

[willow fog]

yes

my argument is through contradiction

to me it makes sense but I want to verify

[proven silo]

If finite yes

[willow fog]

oh and my third one is, if the codomain is equal to the range, the function must be surjective, right?

[willow fog]

ok ty

epic

[willow fog]

so how about this one, bc I get confused sometimes

[proven silo]

You can define domain to be many things

[willow fog]

what do people typically define it to be

[cerulean wind]

ehh

[willow fog]

wrt functions

[proven silo]

f(x)=x^2 f: {2} \to {4} for example is valid

[cerulean wind]

i feel like with this question, it’s just like what are all the valid inputs. that’s typically how these questions are expected to be answered, though worded poorly

[proven silo]

They are a part of the definition of a function

[willow fog]

yeah ig

[willow fog]

alright just wanted to be clear

so here are my thoughts

[proven silo]

But if want natural domain then its R

[willow fog]

the domain and preimage of x² is R, while its codomain is the reals and image are the positive reals?

[cerulean wind]

…preimage of what tho

[willow fog]

for √x
domain: reals
preimage on (-∞, ∞): positive reals
codomain: reals
image on (-∞, ∞): positive reals
?

[cerulean wind]

u just saying preimage is a bit imprecise

[willow fog]

f(x)=x²

do I need a specified interval?

[cerulean wind]

if u just mean preimage of R under these maps, then that’s the same as the domain

[willow fog]

what else could I say

[cerulean wind]

yes, you need to take the preimage of a set

[willow fog]

oh

[cerulean wind]

otherwise i have no idea what ur taking the preimage of

[willow fog]

so I would need to say "the preimage of f(x)=x² on [a, b]"

right?

[cerulean wind]

yea, like f^-1([a,b])

[willow fog]

oh okay

[cerulean wind]

or f^-1([0,infty)) or f^-1({0})

[willow fog]

so how about these

probably not entirely correct lol

[cerulean wind]

like i said before, the preimage of R is the domain for all of these functions. the domain and preimage of (-infty,infty) = R should agree

[willow fog]

but √x is undefined for negative numbers

does that not matter?

[cerulean wind]

so why did u say the domain is all real numbers lol

[willow fog]

idk

should it just be positive reals then

[cerulean wind]

non-negative

[willow fog]

oh right

when would the domain and preimage be different

other then the preimage of a subset

is the domain the maximum possible preimage?

[cerulean wind]

they aren’t if you’re taking the preimage of any set which contains the image

[willow fog]

oh okay

[willow fog]

is this true?

[cerulean wind]

largest possible preimage is ambiguous. again preimage of what? how are we defining largeness? by cardinality? by containment?

[willow fog]

hmm idk

alright thanks for your help

[coral parcel]

It is valid syntax, but it's a claim that will never be true no matter what W is.

In that case just say L = {0,1}* or L = Sigma* or whatever the appropriate notation in your context is.

There's noting wrong with constructing a Turing machine that accepts w whenever w in emptyset. That just means "a Turing machine which never accepts", which is perfectly meaningful.

in your example L1 cup L2 is the language of all strings, which is easily recognizable.

You just need to make sure neither L1 nor L2 is itself recognizable.

Then it wouldn't be the kind of example you're supposed to show exists.

Yes, but L1 and L2 would not be "two unrecognizable languages".

[oak notch]

What does T^c mean?

Is it referring to some adjacency matrix?

[signal shard]

probably complement

[oak notch]

Wont it be a bar instead?

[stray reef]

there are different notations in use for the complement

^c is one of them

[full narwhal]

can someone explain ?

[long pike]

Oh ok so basically the person did casework

first, we consider the "5 characters"

36 represents how many possible (digits + lowercase letters)
raised to the fifth because yk, combinatorics

then they did complimentary counting (counting what you don't want)

so 26 represents only lowercase letters (since if its only lowercase letters, its not valid)

They did the same procedure (just 6 characters instead) for the "6 characters" possibility

summed those possibilities up, and voila

your awesome beeg number

[coral parcel]

(which is not really all that awesomely beeg).

[fresh venture]

What does a|b mean?

[obtuse lance]

it means a divides b

[main cargo]

I was wondering if anyone is familiar with the RSA encryption method that could help me

[sharp basin]

Could some explain what this notation means $$f: {0,1}^{} \rightarrow { 0, 1 }^{}$$

[vital dew]

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

[sharp basin]

f: { 0, 1 }→ { 0, 1 }

[vital dew]

Lochverstärker

[sharp basin]

yes

[pale epoch]

f is a function from the set of all finite strings built from 0, 1 into the same set

probably at least

[sharp basin]

is the symbol * commonly used

[pale epoch]

yes

it's called the Kleene star

[sharp basin]

ok this makes sence i have seen it but i was not sure what it meant

thank you

[pale epoch]

it's also used in regex

[lean bramble]

∀x(Ax ∧ Bx) ⊢ ∀xAx ∧ ∀xBx
Can anyone help me with natural deduction proof?

[fresh venture]

I doubt it

[final cliff]

Is the context basic number theory?

[fresh venture]

Modulo

[final cliff]

So modular arithmetic?

[fresh venture]

Yes

[final cliff]

That's basic number theory then.

In that context a|b meaning a divides b is super common.

Is there a reason why you doubt this is the case?

[fresh venture]

You mean here it is a don't divide p?

[final cliff]

Yeah p|a with the slash through it right there means p does not divide a.

[fresh venture]

Ohh ok
Thanks

[final cliff]

Bah, idk how to get the slash to go the same way as in ur pic.

But you see what I mean.

[fresh venture]

Yeah nvm

[past burrow]

is a.) Modus Tollens and b.) Modus Ponens

[coral parcel]

Before you jump to putting fancy names on the arguments, you ought to figure out intuitively whether or not they hold water.

[past burrow]

i mean ik a) inuitevely hold water

but for b.) its iffy

[coral parcel]

Indeed.

The premises don't say that the only ones who take CSE120 are people who major in computer science.

[past burrow]

i c

now

im dumb it doesnt even match modus ponens

[coral parcel]

"It doesn't even match modus ponens" is correct.

(a) is indeed an instance of modus tollens.

[past burrow]

i get it now thanks

also im confused as to what this is even asking for and what the point of the 4th option (d) is

[fresh venture]

Did they actually calculated it and got 142 remainder?

[coral parcel]

Possibly. It's not quick and easy with pencil and paper, but could probably fit on one or two pieces of paper if you use exponentiation-by-squaring and reduce modulo 1763 after each multiplication (and write fairly neatly).

[fresh venture]

How?

[coral parcel]

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

(Test division by primes up to the square root (about 42) would be quicker, though, but the Fermat test starts being quicker than test division when the numbers are larger than this).

[fresh venture]

I didn't understood from that

[fresh venture]

I mean still how did we got 142 here?

[coral parcel]

By computing 2^1762 modulo 1763, using exponentiation by squaring.

1762=2+32+64+128+512+1024, so first compute 2^2, 2^4, 2^8, 2^16, ... 2^1024 by successive squaring (nine multiplications modulo 1763). Then multiply 2^2×2^32×···×2^1024 to get 2^1762 (five multiplications modulo 1763).

[fresh venture]

Ahh I see

So most of the questions will be where power is in that form?

[coral parcel]

I don't know about "most of the questions", which questions?

[fresh venture]

Nvm

Also there are some questions like given 2 super big numbers and it asks what will be the remainder when one divides other

How do we do that?

[coral parcel]

Long division?

[fresh venture]

No

Like divide 7^6485397 by 43 and tell the remainder

[coral parcel]

You could just do exponentiation-by-squaring again -- but it's faster to start by making the exponent smaller by Fermat's little theorem.

[fresh venture]

Ok

But here it is to the power 7 not 2

Would that still work?

[coral parcel]

Yes, but you still work out the exponent in binary, not base 7.

Fermat's theorem first, though. Since 6485397=42×154414+9 we have 7^6485397 = 7^(42×154414) × 7^9 = (7^42)^154414 × 7^9, and now something should start looking familiar ...

[fresh venture]

Ok

[fresh venture]

Anyway so basically the only way to do this is by exponentiation by squaring

[coral parcel]

I'm not saying it's the only way, but it's a pretty good way, once you've reduced the exponent.

[fresh venture]

Like there is this example

Can we still write 1386 in 2^16+2^64....

[coral parcel]

Yes. Except I don't know where you get 16 and 32 from there; even 2^16 is much larger than 1386.

[fresh venture]

Yeah sorry I got confused

[fresh venture]

It's 2^10 + something ig

[coral parcel]

Correct.

[fresh venture]

I meant like what you did here

[coral parcel]

Yes.

[fresh venture]

And it will give remainder 1 ig

Then we need to do it again

[coral parcel]

If it's just about verifying the computations in the slides you're reading, I would use a computer :-)

[fresh venture]

Ohh ok

[coral parcel]

$ calc 2**1762 % 1763
    742
$ calc 2**1386 % 1387
    1
$ 

Much quicker than working it out on paper. :-)

[fresh venture]

I have a subjective exam though

[coral parcel]

Hmm, looks like the author even made a mistake in the first example :-D

[fresh venture]

What?

[coral parcel]

It's really 742, not 142.

[fresh venture]

Ohh

Nvm

Also how can we get x, y here?

[stray reef]

x is the message

y is computed from x as shown

[fresh venture]

Yeah

I mean how to compute?

Like if we have integer values of all T p q d e etc.

Can we get x, y?

Ig we need to know either x or y to get the other

Nvm leave it

Is there any particular formula for the multiplicative inverse or here we just think like what is the least number we can put so that 4x-1 is divisible by 5?

[grim citrus]

How many different 9-bit strings begin with 101 or end with 100, but not
both (i.e. no strings of the form 101xxx100 should be counted)?

can someone help with this

please @ me 🙂

[stray reef]

@grim citrus have you ever done counting problems with a "this or that but not both" constraint before?

[grim citrus]

I got the answer as this : 2^6+ 2^6 -2^3

[stray reef]

this is not correct

[grim citrus]

how?

[stray reef]

and you really should have shared your attempt at the beginning...

[grim citrus]

oh sorry

[stray reef]

but anyway, what you did counts all strings that begin with 101 or end with 100

however you included strings which satisfy both

which you shouldn't have done

[grim citrus]

but it says no strings of the form 101xxx100 should be counted

[stray reef]

the count 2^6 + 2^6 counts such strings twice

but you need to not count them at all

so you should subtract 2 * 2^3

[grim citrus]

oh okay but one of my books had an example where they did it the way I did, could u explain why if I send the book exmaple?

like the difference btw the 2 questions

[stray reef]

okay, sure. send the problem and the book's solution.

[stray reef]

ah, see

[grim citrus]

this is technically the same question as this: How many different 9-bit strings begin with 101 or end with 100, but not
both (i.e. no strings of the form 101xxx100 should be counted)?

I think>

[stray reef]

that problem doesn't have the "but not both" part!

so of course they subtract the intersection once only

[grim citrus]

but we're still subtracting the intersection in the book

whihc is "both"

[stray reef]

yes, and i'm saying that for your "but not both" problem you need to subtract it TWICE!

[grim citrus]

yeah why tho? i dont get that part

[stray reef]

well ok i can try to give a simpler example if you want

[grim citrus]

sure

also I really appreciate the effort lol been stuck for a while

[stray reef]

there is a group of people in a room. 20 of them have red hair and 50 of them have red shirts. 4 people have both red hair and a red shirt. how many people have a red shirt or red hair but not both?

[grim citrus]

20+50-4?

[stray reef]

no

imagine giving a coin to every redhead (20 coins in total) and then giving another coin to every red shirt (50 coins in total)

then every person in the set we want to count receives one coin

but the redheads in red shirts receive two coins each

[grim citrus]

ohhh

[stray reef]

so to exclude them from the count we subtract double their amount

[grim citrus]

now it makes total sense

thank you so much

[main cargo]

This might be the dumbest question ever, I'm rather confused about modular arithmetic and have a massive lack of understanding, but why do we introduce the set of congruence classes of the congruence modulo relation if we can just work with the congruence relation?

[gleaming notch]

For this question, when we try to prove A ⊆ B, can we also prove it in this manner?
Let x be arbitrary element of A so x = 4p-1
but then x = 4(p - 1)- 1 which is in B. So A ⊆ B.

[stray reef]

x = 4p-1
but then x = 4(p-1) - 1

@gleaming notch this is incorrect as stated...

[pale epoch]

it's just language, two numbers are congruent modulo n if and only if they are in the same congruence class modulo n

[main cargo]

Oooooh so we introduce it to make it more formal then? So that we can then extend the idea to make it a ring or a group or is that false?

[pale epoch]

well, the language of congruence classes is probably more modern

it's more general in the sense that you can turns any group/ring into a quotient group/ring by a similar construction

the language of of the relation is older

and i guess it is better to think of addition and multiplication as operations on congruence classes

instead of adding/multiplying numbers and then applying some equivalence relation

[main cargo]

Oooh yes I see, thank you very much for your help!!

[gleaming notch]

oh right, i see it now

thanks

[stray reef]

aaaaaaaaaaab is not equivalent to aaaaab

they are not in the same equivalence class

not every two strings with more a's than b's are equivalent to each other

@iron crescent

oh but wait

hold on

they havent actually defined the equivalence relation in question

what they meant is that two strings are considered equivalent iff the difference between the counts of a's and b's is the same in both strings

i think.

now that i'm giving it a second read they do not actually specify any equivalence relation so in fact they have no business talking about equivalence classes

eh?

uh

can you write that out for me again

or show the slide where it says that

okay

and the dot represents concatenation?

okay

well then yeah what i said before is true

no

just because it works when appending "b" does not mean it works when appending every string

take aaaaaaaaaab[bbbb] and aaaaab[bbbb]

[] highlight the appended string

the first string isn't in EQUAL while the second one is

[coarse cave]

Can someone explain this?

Can't really wrap my head around it

[last timber]

@coarse cave still stuck?

[past burrow]

is this right

[last timber]

@past burrow why you suddenly change from k to n

and you haven't stated usage of induction explicityly

but the logic is ok

[past burrow]

change from k to n where?

thats cuz im substituting k = n-1

also for d is this the correct way @last timber

[coarse cave]

no i figured it out, thank you :)

[last timber]

no this is not correct

you haven't applied division algorithm here

and on line 4 you just use what you are required to find

[last timber]

there is no need in this substitution

you want to show that P(k+1) follows from P(k)

[past burrow]

but can i substitute?

this is what i have rn

[past burrow]

how do i apply the division algorithm

[last timber]

read its definition

[last timber]

well yes you can

but it like extra step

[fallen vigil]

can an euler path or circuit repeat vertices as long as it doesn't repeat edges?

[stray reef]

yes, and in fact it will have to repeat vertices of degree greater than 2.

[balmy dome]

can someone please explain how the first expression simplified to the second one?

[pale epoch]

by factoring out (k+1)

[raven kite]

Hello everyone. Is anyone familiar with formal methods?

[worthy mist]

With a few specific ones although not the field in general.

That being said you should just ask your question, someone will know the answer^^

[coral parcel]

Doesn't what reject every string by definition?

But that is not a particular machine, just the first element of every pair where you're asking "is this pair in my language?"

Yes, but that can a priori be any Turing machine.

No, T is just a dummy variable.

You could also write the same language as { W in {0,1}* | W is the encoding of a pair, where if you interpret the first element of W as a Turing machine, the machine will halt when ran with the second element of W as input, it rejects }.

Whether "rejects" means "prints no and halts" or it means "does not print yes" unfortunately differs a bit between books and contexts.

In your case, it seems to mean the first thing.

So if T is a machine that loops on X, then <T,X> is not in your language.

No -- since there are inputs that U doesn't halt for it doesn't decide any language.

We can, however, say that U recognizes RejectTM.

Correct, so set of instructions that blithely say, "simulate such-and-such machine on such-and-such input" does not necessarily define a total function (and therefore by the most common definition in this area is not an algorithm).

That particular language cannot be decided by any algorithm, no.

There are other languages that can be decided by algorithm -- for example the language that consist of all strings whose length is a prime number.

When you write "u" do you mean "you" or something you have named with the letter U?

The language consisting of those pairs is not decidable.

Sure -- you could take the language that consists of all pair whatsoever.

You mean { W in {0,1}* | W = <X,Y> for some X and Y }?

That ought to be decidable if the way you represent Turing machines as bit strings is halfway sane.

(Which we generally always assume it is).

(Just ignore the qualification: Yes, that is decidable).

Well, there are several possible ways out. First, you might be able to prove that you only reach that step in your recipe in cases where X (for whichever reason) is guaranteed to be a machine that halts on Y. Second, the subsequent text might contain instructions for aborting the simulation before the simulated machine ends, such as "if the simulation performs one billion steps and still hasn't reached a terminal state, go to step 7".

For example, yes.

There's nothing really relevant to dovetail the simulation together with.

I'm also assuming that you're looking at a question that continues something like "does the U we've just described decide the language?".

In principle, just because that particular U doesn't decide the language, there could still be something else that does decide your langague.

I just happen to know for other reasons that there isn't.

You might enjoy trying to prove that if an angel descended from the heavens with an instrument that reliably decides RejectTM, then we could build that instrument into a larger machine that decides HALT. Since we know that no Turing machine can decide HALT, we conclude that the angel's instrument, however it works, cannot possibly be a Turing machine.

[main cargo]

Suppose we have the integers modulo m, why do we suddenly stop considering its elements as congruence classes and start treating them as if they were actually integers instead of sets?

[coral parcel]

Yes, that's a reduction proof.

[coral parcel]

What we actually do with the elements shouldn't change, but at some point one usually stops writing the brackets (or overbars or whatever your notation for congruence classes is) once one is reasonably sure the reader is familiar enough with them not to need to have the classification pointed out explicitly all the time.

[main cargo]

Hmm, so the numbers still represent the sets then, so it's a form of notation, but I don't get then how, for example, in the chinese remainder theorem, we just use the inverse of a congruence class to solve the particular problem with integers. (I'm sorry if these questions are weird, modular arithmetic is messing with my head)

[coral parcel]

Hmm, I think part of appreciating these matters is just in becoming intuitively familiar with when and how it makes sense to move back and forth between the two views. That does take some practice and examples.

[main cargo]

Hmmm alright, thank you for helping me understand it better 🙂

[queen river]

Hi all, I've been playing a video game with the ubiquitous feature of dispatching your forces on Tasks to get passive rewards, and I've run into (what I've recognised as) a scheduling problem.
I can't for the life of me remember how to go about solving this without brute force, which is a shame because there's an opportunity for me to learn some great mathematics.
Any hints or help would be appreciated on how I can approach it, especially any guidance on which heuristics I can check to see if there even is a solution to the problem.

In this problem there are 7 agents, who can work on a corpus of 8 tasks in groups of up to 3.
Three tasks can be worked on concurrently, so a start would be Task 5 being worked on by Simon & Maria, while Alucard & Shanoa work on Task 6, leaving Charlotte & Jonathan & Richter to work on some other Task.
In a trio, they are able to solve Tasks 4, 5, 6, or 8. Since Tasks 5 and 6 are already being worked on, I can only schedule them for Task 4 or Task 8.

Each agent has a unique tuple of three scores A, B and C.
Each task has three thresholds for those same scores A, B and C, and to get the maximum reward for a task, all thresholds should be reached (or exceeded). This is what I mean by "solving" the task.

By traversing all the unique sets of 1-2 agents, summing their scores, and comparing against the threshold of each task 1 through 8, I have surprisingly discovered that most tasks can be solved perfectly in unique pairs, shown in the matrix below.
This then leaves 3 agents to solve some other task like in the example above, and also get the maximum reward.

All of the Tasks have multiple solutions for 3 agents, but only one solution for 2 agents (with the exception of Task 8)
Task 8 is inconsistently labelled since there are multiple overlapping solutions, which I have tried to show using multiple columns.

My goal is to systematically allocate the agents to the three concurrent tasks and get the maximum rewards for doing so.

             1     2     3     4     5     6     7     8     8     8     8
Alucard                                   <>    <>    <>
Simon                               <>                <>
Maria       <>                <>    <>                      <>    <>
Charlotte   <>    <>    <>                      <>
Shanoa            <>    <>    <>          <>                            <>
Jonathan                                                    <>    
Richter                                                           <>    <>```

[queen river]

Ah I forgot to mention one of the most important constraints!
Each Task can only be attempted 3 times daily, and each Task attempt takes 3 hours, so in total that's 3 * (24 / 3) Task attempts which need to be solved for;
I can't exhaust all the Tasks, so in theory I could at most exhaust the rewards for 3 Tasks in 9 hours, by scheduling each team three times in a row.
Then for another 3 Tasks is another 9 hours.
Then I would be left with 2 Tasks and 6 hours, which I could throw teams of three agents at without even managing to exhaust them before the reset.

The next day would follow an identical strategy.

I do wonder though, if there could be some benefit to not fully exhausting Tasks immediately, so that I could still run 3 concurrent tasks in the last 6 hours...

[crystal ginkgo]

I think this is a discrete math situation: I'm running a small experiment among friends where they match a pool of 10 specific adjectives to 10 shaped tokens, making for 10P10 or 3,628,800 potential results. I have a template response where each adjective is assigned to its corresponding token, effectively {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} and I'm trying to figure out that, from the pool of 3,628,800, what the average number of adjectives assigned to their template-matching tokens is.

Since there's one "correct" answer, the other 3,628,799 answers have between 0 and 8 matching adjective/token pairs. I'm stuck on the bit where I figure out the proportions each template-matching amount has of the potential result pool, because if I have that I can just average it out. I feel like I'm missing something super obvious but I haven't used combinatorics at this level in like six years

example: {0, 1, 3, 2, 4, 5, 6, 7, 8, 9} is an eight match and {1, 0, 3, 4, 2, 5, 6, 7, 8, 9} is a five match

[neon latch]

Hey guys! Thought I'd share my competition entry for 3Blue1Brown's Summer of Math Exposition.
It outlines a weird and exciting find I had when extending the logic of the Collatz Conjecture, and having Python do a bunch of math for me.

Billions of calculations later, there's a new sequence I want to submit to the Online Encyclopedia of Integer Sequences from this work, and it suggests there's a fascinating convergence property of the Collatz conjecture yet unrecognized. Check it out!
https://deandrereichelle33.wixsite.com/website/drunken-inspiration-and-the-collatz-conjecture

[coarse cave]

Anyone able to help me understand this using a matrix?

[neon latch]

Sounds like a #linear-algebra problem

[coarse cave]

nah its from my discrete math graphs test

[neon latch]

Well let's break the problem down. Since all vertices are symmetric in linear algebra, you can treat the origin like any other vertex...

[coarse cave]

Ya

well this is the graph specifically from the problem

and this is the matrix i made

only for b,d, f**

bc theyre strongly connected

[neon latch]

a e c should be connected differently, perhaps a minus sign is necessary

[coarse cave]

well i didnt make the graph its just in the problem

[neon latch]

Is this like a preamble to Markov chains in matrices? Is that the next chapter?

[coarse cave]

no this course doesn't cover that

this if for the final

[neon latch]

Alright, so how are the matrix dimensions labeled? (I may be of only limited help, since I'm learning this kinda stuff too)

Which letters are which dimensions in the example?

[coarse cave]

so its like this

[neon latch]

Should it not be a 6x6 matrix? You should be able to fit every transformation on the graph in that, (but don't take me too seriously...)

It would be an array of ±1s and 0s still then...

[coarse cave]

well it would but we are only concerned with the strongly connected components of the graph

so b d f

[neon latch]

right since aec isn't reversible

[coarse cave]

exactly

here wait

a friend just helped me but im a bit confused

could u decipher this lol

[neon latch]

Let's see🤷‍♂️

[neon latch]

This might be helpful https://youtu.be/s8NoAehcmIE

Holy crap that's wild! I'll have to try this out!

[patent rover]

this is obvious but uh how do u actually prove this formally?
m = qd, mn = kd
then i got to m = (k+q)/ (n+1) * d but idk how to show that is an integer or if this is the right way of approaching it
<@&286206848099549185>

[gritty crescent]

@patent rover The forward direction is obvious, d|m is the hypothesis. For the converse, you get one part for free again (d|m implies d|m), to show that d|nm as well, use the definition.

[patent rover]

ik the forward direction is obvious but like how do u actually layout the proof?

when u say d|m is the hypothesis wdym

[gritty crescent]

"Since d|m and d|nm, in particular it follows that d|m..."

This is actually an unreasonably trivial proposition to prove lmao

[patent rover]

yea

i just dk how to actually prove it like formally lol

[gritty crescent]

If you have to show that statements A and B imply a statement C, you assume A and B hold, and they form your hypothesis

Over here A and C coincide, and every reasonable statement implies itself

So there's nothing to show

So I think one way to write this could be: Suppose d|m and d|nm. It follows in particular that d|m, proving one direction. Conversely if d|m, then m=qd for some integer q by definition, and hence for any integer n, mn=qnd; our definition then implies d|mn as well.

[patent rover]

yeah that makes sense

so doing the whole from definition thing isnt really the way to go about it?

like what i did originally

[gritty crescent]

I'm not really sure I understand what you did

[patent rover]

so for d|m ^ d|nm => m = kd and mn = qd

[gritty crescent]

Right

In particular m=kd, and the definition packs it up as d|m

[patent rover]

yeah i kinda tried to combine the statements/solve simultaneously ig

ty!

[gritty crescent]

No worries, goodluck!

[weary tiger]

Can anyone help me with this question ?

[obtuse lance]

,rotate

[obtuse lance]

what have you tried

[weary tiger]

I am new to the topic and i dont know how to start.

I only kinda know the concept but i am not good at solving it.

[remote cosmos]

drizzy, do you have an idea of what the function definition is defining, and what you're trying to find out about it?

[weary tiger]

No actually, I dont understand why the question writes f:R{-1} -> R

[remote cosmos]

so the notation

[weary tiger]

especially the /{-1}

[weary tiger]

{-1} sorry, trypo

typo*

[remote cosmos]

lol cant latex

but that means

subtract that set

so subtract the elements of the set {-1} from the reals

[weary tiger]

so no -1 in the set of real values ?

[remote cosmos]

also note it's a backslash, not a forward slash (which implies division)

yea

so it's a function that takes any real number as input except -1

and outputs a real number

[weary tiger]

the output can be -1 ?

[remote cosmos]

the right arrow signifies where it's outputting to

correct

do you see why they want to restrict -1?

in input?

[weary tiger]

They want to bound it ?

[remote cosmos]

no, think about the function it's talking about

$f(x)=\frac{x}{1+x}$

[vital dew]

pitabread

[remote cosmos]

what happens at f(-1)

[weary tiger]

it becomes undefined

[remote cosmos]

right

so no matter what

it wouldn't be bounded if we talk about it like that

and it wouldn't be an interesting question

so they're saying: removing that possibility of undefined, is this bounded, and is it monotonous

[weary tiger]

Ouh

Ok

[remote cosmos]

two different questions even though they phrase it as one

bounded does not imply monotonicity

and certainly monotonicity does not imply bounded

[weary tiger]

I am ust starting to understand the question , damn, hahaha

[remote cosmos]

so you have to confirm each one

[weary tiger]

Ok, so how to start normally given a function ?

Like what is the first step thing i should do ?

[remote cosmos]

i guess at first you can look at it informally

if you know how to graph it by sight

graph it

if you don't, maybe try some input values to sus out the behaviour a little

[weary tiger]

Ok, i will try it

[remote cosmos]

don't jump to a graphing calculator because you won't be able to use in an exam

[weary tiger]

Yeah ok

I dont have that kind of calculator , LOL

[remote cosmos]

you're in a class for this?

[weary tiger]

I am not in class right now. This is just like homework.

[remote cosmos]

right

[weary tiger]

I have problems understanding my professor

[remote cosmos]

but i mean they give methods, and you have a book right?

[weary tiger]

My prof dont use a book and he uses his own notes

Yeah, very difficult to understand him, ngl

[remote cosmos]

in terms of content, or accent?

[weary tiger]

Content

[remote cosmos]

so just copy down, and maybe with your phone audio record

as you understand more go back to the old lectures

and see if they start making sense

https://www.people.vcu.edu/~rhammack/BookOfProof/Main.pdf

here's a book

i actually don't find it's calculus section thatttt great but it's something to start with

[weary tiger]

Yeah , i have his working but i dont really get his idea. He doesnt explain the way he does it , he just keeps speaking and it is very difficult for me to relare

[remote cosmos]

yea sometimes for these things the student has to do a lot of work beforehand just to keep up with the prof

[weary tiger]

Yeah true

[remote cosmos]

but as long as you take notes and record, you have something to come back to

a lot of the times they say great things, but they can't aim it at everyone

[weary tiger]

He is a good, but i guess the problem with me understanding things quick

[weary tiger]

Yeah, that was what i am trying to say. Sometimes he just skips certain explanation because he assumes we done it in highschool.

[remote cosmos]

here's another resource

and if you don't know how to read the symbols, refer to book of proof that i linked earlier

[weary tiger]

Ok sure, i have exams in like 7 weeks and i am already worried with maths

[remote cosmos]

yes, that's normal lol

[weary tiger]

Are u a bachelor student ?

[remote cosmos]

it's my 3rd degree

but my first degrees were in music lol

[weary tiger]

So what is ur 3rd degree about ?

[remote cosmos]

now comp sci w/ minor in math

[weary tiger]

Ah ok

nice

Thank you for the help @remote cosmos .

[quiet echo]

How many triangles can be created from the diagonals of a tesseract such that all the vertices and exactly one edge of each triangle is the same as those of the tesseract?

‎
I came up with this problem for fun while doing combinatorics in class and I just want to see if my solution is correct or if there are some mistakes.

‎
‎
||Anyway, here it goes:

The first thing to realise is that the vertices adjacent (A.V.) to the vertices of one edge can't be chosen to create the diagonals because that would result in triangles sharing two edges with the shape.

So, the total number of vertices the required diagonals can be made from, for one side = (total vertices - n(A.V.) - 2) [-2 because the edge chosen uses up 2 vertices as well] = number of possible required triangles (n(T_1side))

All the other edges will be a part of the same number of triangles as well, thus the total number of required triangles = number of total edges × n(T_1side).

For this to be of any use, we will have to determine the total number of edges, the total number of vertices and the number of adjacent vertices to the chosen side:-

Determination of the total number of adjacent vertices to the chosen edge:-

Now, n(A.V.) to the chosen two points in 1D, i.e. a line = 0

The n(A.V.) to the chosen two points in 2D, i.e. a square = 2

The n(A.V.) to the chosen two points in 3D, i.e. a square = 4

Seeing the pattern, the n(A.V.) to the chosen two points in a cube of Nth dimension = 2(N -1)

Thus, the n(A.V.) to the chosen to two points, i.e. an edge in a tesseract = 2(4 - 1) = 2(3) = 6.||

‎

||Determination of the total number of vertices:-

To create a cube of (N+1)th dimension, the total vertices (T.V.) of the Nth dimensional cube are doubled, or, the T.V. in a cube of Nth dimension = 2^(N)

For example, T.V. in a line (1D) = 2
T.V. in a square (2D) = 4
T.V. in a cube (3D) = 8
Thus, T.V. in a tesseract (4D) = 16.

Determination of the total number of edges:-

As before, I will try to come up with a formula (for a cube of Nth dimensions) using examples.

The total sides in a line (1D) = 1
Total sides in a square (2D) = 4
Total edges in a cube (3D) = 12

The common pattern, for the total number of edges for an Nth dimensional cube that can be seen is = N × (A.V.)

Thus, the total edges in a tesseract = 4 × 6 = 24

Plugging in all the values in our main equation, we get,

Total number of triangles that can be created from the diagonals of a tesseract such that they share exactly one side and all their vertices with it = 24 × (16 - 6 - 2) = 24 × 8 = 192 triangles.||

If you have a better and a quicker solution, do tell!

11th grade rn

[quiet echo]

Edit: added spoilers to my solution

[coral raven]

||there are 12 edges in a cube and 8 vertices, so, as a tesseract is a prism with a cube at each end, with a cubic cross-section, there'll be 2 * 12 edges from the ends and another 8 edges in the middle, there will be 32 edges in total.

pick one of these edges. this gives us two points. if the third point is adjacent to either of the first two points, the condition is not satisfied. how many points are connected to each point in a tesseract? 4, as 2 edges meet per vertex in a square, 3 in a cube, so 4 in a tesseract. so of the 16 vertices in a tesseract, 16 - 2*4 = 8 are not adjacent to either of the points in our chosen edge.

then we have 32 possible edges to start from and 8 viable third points per edge, so this gives us 256 possible triangles in total.||

[crystal dove]

Is it wrong to define Combinations as subsets of some size?

For example, all the combinations of (A, B, C, D) choose 2 are just all the subsets of size 2

[weary tiger]

No, given a set A s.t. |A|=n, a k-element combination can be also defined as strictly increasing function f: {1,...,k} -> A (those functions are in bijection with image of f, which is a subset of A of size k)

@crystal dove

[quiet echo]

Dang it, I don't know why I forgot counting the "vertical" edges that time

Thanks for the reply!

[coral raven]

i think it's just that you saw a pattern that wasn't really there

[quiet echo]

I actually pictured the tesseract first before coming up with the pattern

but somehow didn't count 8 edges

Actually I don't even know why I tried to come up with a formula for the total edges, now that I see it, the total vertices will always be the double of the total number of edges, something I had already come up with a formula for

[coral raven]

what no

V: E
1: 0
2: 1
4: 4
8: 12
16: 32

[sharp ledge]

Can someone explains how to solve this ?

[stray reef]

F_n grows exponentially

more specifically $F_n \in \Theta(\varphi^n)$, where $\phi = \frac{1+\sqrt{5}}{2}$

[vital dew]

Kanga Gang Annihilator Ann

[sharp ledge]

how do i know to relate the ratio to this question ?

[stray reef]

do you mean "how was i meant to know that i needed to do this?" or "how do i use F_n ∈ Θ(φ^n) to solve the question?"

[sharp ledge]

The first one

[remote cosmos]

Very informally you can try some values and see that it behaves exponentially, at least to assure yourself that you're in the right direction

Then if you need to, you can prove it more formally

[quiet echo]

yeah it definitely messed up my brain lmao

I even edited that specific message like 4-5 times

[sharp ledge]

Question 2 - how do i solve this ? by drawing each of them ?

[coral parcel]

With so small numbers, listing the solutions concretely would definitely be an option. (There are only 24 possible arrangements; I think 11 of them are valid).

Alternatively, do you know derangements? If the leftover drink is cranberry, you have a derangement of the 3 other drinks; if it is not cranberry, you have a derangement of all 4 drinks.

Alternatively first ignore the cranberry and distribute the other three drinks among the three persons. One of the 3!=6 arrangements is useless because everyone is unhappy about their drink. It's not possible for exactly two of them to be unhappy. If there is one unhappy person, let them switch with cranberry. If everyone is happy, you can either use he arrangement as-is, or let one of the three switch with cranberry.

[sharp ledge]

How you know there is 24 ?

[weary tiger]

A connected multigraph with at least two vertices has an Euler circuit if and only if each of its
vertices has even degree. Prove. 

Hey I know this rule where if one vertex of the graph is odd then its impossible for it to have an euler circuit. But how can i actually write a proof for it?

like what am i supposed to do...

[coral parcel]

4!=24

[coral parcel]

Can you understand why that rule holds? If so, writing down that understanding would probably make a good first draft of a proof of it.

[weary tiger]

Could someone explain P(x) to me ?

[prime parcel]

Troposphere

[cerulean wind]

well, ya see

[weary tiger]

the set of all x in S such that P of X. A = {x ∈ S | P(x)}

[prime parcel]

[cerulean wind]

[onyx pagoda]

petition to draw graphs with 😩 emojis as nodes, instead of boring dots

[visual lily]

Y’all can someone just explain this to me, Ik what NAND does but I’m trying to understand this, don’t give me the answer but just lmk what to do 🥺

[obtuse lance]

I'd suggest writing out a truth table

[visual lily]

Like this?

[obtuse lance]

yeah now make another column for the whichever of the two options you think will be easier to work out

the way I learned was to write the statement out, then work out under each symbol what the result is

[visual lily]

So I feel like I’m using NAND wrong

But this is kinda where I’m lost

Like I read it as (X not and Y) so x and Y but the opposite

😅

[visual lily]

):

[weary tiger]

could someone explain this formula in simple terms

[amber prism]

$\sum (k+x)=\sum k+\sum x$

[vital dew]

Mosh

[weary tiger]

So just the sum of both summations ?

[weary tiger]

@amber prism

[amber prism]

yes, sum distributes

and clearly $\sum_{i=1}^n k=nk$ if k is independent of i

[vital dew]

Mosh

[distant bobcat]

In the field Z_p do we usually select p to a part of the natural numbers?

I dont think I have ever seen a modulo group with negative p for instance

[pale epoch]

Z_p is only a field iff p is prime

you can select negative numbers, if you want (and define the equivalence relation correctly) but you will just get Z_p = Z_{-p}

thus we do not use this notation

(in fact even the notation Z_p is uncommon)

[distant bobcat]

@pale epoch Do we need p to be a prime to guarantee the existence of multiplicative inverses for the elements?

[pale epoch]

yes

[distant bobcat]

right, that makes sense

[pale epoch]

if p = ab, you get that a and b are zerodivisors

(for a, b < p)

[distant bobcat]

zerodivisors as in equivalent to p in the group right? (p equiv 0)

[pale epoch]

yes

like

neither a nor b can have inverses

assume a had an inverse c, then ac = 1 (mod p)

but then b = acb = abc = pc = 0 (mod p)

[distant bobcat]

and why is it that 1 and p-1 are always cyclic in Z_n? if u dont mind

[pale epoch]

both kinda by definition

you can "reach" any element by adding 1 to itself often enough

and p-1 is just -1

eh, you need to replace either your n with a p or your p with a n

[distant bobcat]

yes, sorry meant p )

thanks, I understood.

[distant bobcat]

Im using this to show that 1, p-1 are the only elements of Z_p which equal to their own multiplicative inverse.

The hint considers x^2 -1 = 0

which I get I can factor to (x+1)(x-1) = 0 giving us +1 , p-1 as solutions

although im not sure why we consider this equation exactly for the proof

[pale epoch]

it's the same as x^2 = 1

which is what you want

[distant bobcat]

oh, ofcourse thanks

[visual lily]

Are these equal? I’m doing permutations but I’m not sure if I’m reading P(20,7) correctly or not since I wrote what’s on the right

[haughty garden]

Yes

[visual lily]

I know the bit length is 8 and the weight is 4, how do I find the amount of bit strings there are with a weight of 4 without just writing every single combination

[coral parcel]

Are you asking for the number of bit strings with length 8 and Hamming weight 4? How does that relate to the B_6^8 notation in your image?

[visual lily]

Well that’s how I was shown to write it

Is this wrong??

But yeah basically I want to figure out how many bit strings of length 8 have weight 6

[coral parcel]

Ah, but you said 4 in your previous post which confused me.

Do you know binomial coefficients?

[visual lily]

Oh shit 6 lmaooo

Lemme look it up, tbh I remember most of this by seeing it rather than name and I might’ve missed some stuff

Ohh

You mean the ! ??

Like 5!

[coral parcel]

! is a factorial.

Binomial coefficients are notated $\binom{8}{6}$ or sometimes ${}_8C_6$ (or variants of this with different staggerings of the numbers).

[vital dew]

Troposphere

[visual lily]

Yeah I wrote that somewhere but I kinda didn’t understand it too much lemme find it

[coral parcel]

Well, here's an application :-)

[visual lily]

So I wrote it down but I’m not sure I even know what it means

[coral parcel]

That explains the TeX notation but not the meaning -- the text underneath is for the nPk notation.

Perhaps there's a section in your textbook you could go back to and review.

[visual lily]

Yeah my notes are bit over the place

I’m not really using a textbook I’ve been pretty much googling everything but I’ll re check everything

[coral parcel]

(There's not supposed to be a horizontal bar in the binomial coefficient notation, by the way).

[visual lily]

My school website wrote that 😭

Fml ok thank you

[coral parcel]

Google it is, then.

The Wikipedia article is decent, actually gives the information you need here without being buried in too much impenetrably abstract cruft. But searching a bit longer might yield a more pedagogical explanation.

[visual lily]

Wait

So binomial coefficients is this right?

Cause I know how to do that

I just don’t understand how that would apply to my previous question, or at least maybe im missing how it’s supposed to be correlated

Cause it isn’t just actually doing n=8 and r=6 right?…

[coral parcel]

Yes, that's it. There are 8 possible bits that you could flip from 0 to 1, and you need to select 6 of them to flip.

[visual lily]

Here’s my confusion

876… wouldn’t that mean there’s 8 options in the first possibility, then 7, and 6 and so on

Which is more than 2 which is true or false

That’s kinda where I feel like it doesn’t make sense but it’s probably me

Like there’s 8 people and 6 chairs would make more sense

Just tell me if I’m off 😭

[visual lily]

I meant 876

8x7x6

[coral parcel]

That's only before you divide by the (n-k)!k! in the formula.

[visual lily]

So dividing it by 6! Makes it so there’s only two possibilities available essentially in each slot? Sorry for the vocabulary I’m using words that make sense to me

[coral parcel]

You have that 8!/(8-6)! is the number of ways to select an ordered sequence of 6 different positions. Then divide by 6! to correct for the overcounting because each unordered set is generated 6! times.

[visual lily]

I think I get it then, I guess I knew how to do it but I didn’t understand the explanation

Well until now I mean

[timber stirrup]

Hey! Any idea how this can be done? <3

[coral parcel]

This operation is sometimes known as https://en.wikipedia.org/wiki/Monus

There's a solution in the Wikipedia article.

[timber stirrup]

oh thankss!

[mossy wasp]

Since the factorial is multiplying, dividing by a different factorial chops it off. So $(n-r)!r! = (8-6)!6! = 2!6!$. Thus, $\dfrac{8\times 7\times 6\times 5\times 4\times 3\times 2\times 1}{6\times 5\times 4\times 3\times 2\times 1\times 2\times 1}$. Cross off everything that is on top and bottom, leaving $\dfrac{8\times 7}{2\times 1} = \dfrac{56}2 = 28$.

[vital dew]

tamara

[proper bronze]

Assuming I have 2 sets

$A = {red, blue}$ and $B = {0,1}$

[vital dew]

allucinator

[proper bronze]

How do I express this in set builder notation?
That a set must have either of the following
${(red, 1), (blue,0)}$ or ${(red, 0), (blue,1)}$

[vital dew]

allucinator

[proper bronze]

I can't search it in Google. What do you call this kind of thing where no two pairs have the same x or y assuming a pair is (x,y).

Now I know ${((a,b),(x,y)) : (a,b) \in AxB, (x,y) \in AxB, a \in A, b \in B, x \in A, y \in B, a \ne x, b \ne y}$

[vital dew]

allucinator

[tidal ibex]

Let $R$ is a reflexive and transitive relation on a set A. Prove that relation $R \cap R^{-1}$ is a relation of equivalence on $A$. Denote $\mathcal{S}$ partition of set $A$ induced by relation $R \cap R^{-1}$ and we define on a partition S following relation:
$$
\preceq={(X, Y) \in \mathcal{S} \times \mathcal{S} ;(\exists x \in X)(\exists y \in Y) x R y}
$$
Prove that $\preceq$ is a partial order on a set $\mathcal{S}$.

[vital dew]

Michal

[tidal ibex]

any ideas how to prove partial order ?

[coral parcel]

It sounds like you're looking for a set that is a bijective correspondence (or "one-to-one correspondence" or "bijective function") between A and B.

[wintry temple]

stuck on a generating function problem

Let [G_k(x)=\sum_{n \geq 0} S(n,k) \frac{x^n}{n!}.]
Find a closed form of (G_k(x).) \
We know that (\frac{d}{dx}G_k=kG_k+G_{k-1}). So, we inducted on (k) to find the general form.
\
To prove: (G_k(x)=\frac{(e^x-1)^k}{k!}) \
Base step: (G_0 = 1, G_1=e^x-1), so the base step holds. \
Induction step: Assume (G_k=\frac{(e^x-1)^k}{k!}) for all (k) with (0 \leq k \leq n.) Show (G_n+1=\frac{(e^x-1)^{(n+1)}}{(n+1)!}) follows. \
\
[\frac{d}{dx}G_{k+1}=(k+1)G_{k+1}+G_{k}]
[\frac{d}{dx}G_{k+1} = \frac{d}{dx} \sum_{n \geq 0} S(n, k+1) \frac{x^n}{n!} = \sum_{n \geq 0} S(k+1,n+1) \frac{x^n}{n!}]
[\sum_{n \geq 0} S(n+1, k+1) \frac{x^n}{n!} = (k+1)\left(\sum_{k \geq 0} S(n,k+1) \frac{x^n}{n!}\right) + \frac{(e^x-1)}{k!}]

[vital dew]

richarde

[wintry temple]

not sure where to go from here

[proper bronze]

Thank you!

[stray reef]

yes

[split ginkgo]

Can someone ELI5 me the best graph isomorphism test?
https://arxiv.org/pdf/1512.03547.pdf

[split ginkgo]

I think I already understand the 1-WL test. But from videos and examples. And I cannot relate my current understanding to the math equation. And I also want to improve my equation reading skills in general
(please reply ping me)

[undone spindle]

how to find number of spanning tree with tutte algorithm?

is there any source?

[stray reef]

at the end of the sequence should be the thing you set out to prove

[split ginkgo]

efficient graph isomorphism is an open and very hard problem. Generally speaking, people are inventing a new graph invariants to solve isomorphism. A quick test with zero false negative (so you can rule out non-isomorphic graph quickly), but a non-zero false positive (so you can't be sure if they are indeed isomorphic), would be WL test and the k-WL family

[coral parcel]

If I recall correctly, it is even hard to construct non-isomorphic graphs that are reliably difficult to distinguish.

[mossy flint]

How does one solve this with dynamic programming?

[stray reef]

what's "evdeg"?

do you maybe have a screenshot of the problem instead of this questionable-quality plaintext reproduction?

okay

so have you made any progress on this or not?

do you understand what the notation $\max_{v \in V} \deg(v) = 6$ means?

[vital dew]

Kanga Gang Annihilator Ann

[stray reef]

okay, can you tell me in your own words what it means?

@feral pasture ?

no, that is not what $\max_{v \in V} \deg(v) = 6$ means.

[vital dew]

Kanga Gang Annihilator Ann

[stray reef]

also there was no reason to take so long to reply tbh

$\max_{v \in V} \deg(v)$ means ``the largest of all the vertices' degrees''

[vital dew]

Kanga Gang Annihilator Ann

[stray reef]

if you ``see'', then you should immediately be able to say whether or not it is possible to have $\max_{v \in V} \deg(v) = 6$ be true.

[vital dew]

Kanga Gang Annihilator Ann

[stray reef]

who said anything about a?

[torpid wolf]

What are some important consequences of the reconstruction conjecture? I always see it celebrated as one of the most important conjectures in graph theory, but I never heard why it is so.

I understand that it reveals more about the structure of graphs, and that by itself is interesting, but I am looking for statements of the form "This is implied by the reconstruct conjecture", "If the reconstruction conjecture is true, then we could prove X", etc. excluding trivial statements that are well-known reformulations of the conjecture.

[dry sandal]

what exactly is a graph? I don't like the wikipedia definition

what is the requirement for two graphs to be equal [i.e. the same graph]?

[coral parcel]

A graph is a collection of things that for the purpose of graph-ness we call vertices, where some or all (unordered) pairs of vertices are singled out as "having an edge between them".

Equality between graphs is rarely mentioned in graph theory, because pedantically "equality" ought to mean that the vertices and edges of the graph are the same mathematical objects. More usually the precise nature of the vertices as mathematical object is something we deliberately want to ignore, so it's much more common to consider isomorphism between graphs than equality. It's also very common to say "equal" where one means "isomorphic", pedants be damned.

[young crest]

a graph is a tuple of two sets (V, E)

if the sets of vertices and the sets of edges are equal, the graphs are equal :)

[stray reef]

a graph is a collection of things you call vertices together with a collection of pairs of vertices you call edges

as mentioned earlier, "equality" is rarely talked about for graphs

[dry sandal]

so a graph is a set together with a single relation called "adjacent" [or "is adjacent to"] ?

wikipedia says graph isomorphism is between verticies, which leads me to believe that a single relation governs all graphs

[austere swan]

Not exactly a relation, unless you are considering directed graphs

In undirected graphs pairs are unordered, unlike in a relation

You can model certain types of undirected graphs (bipartite graphs) as relations tho

[coral parcel]

For a simple graph you can just specify that the relation is symmetric and irreflexive.

[austere swan]

Oh sure

That works too

I think at that point you're missing the point a bit tho

[full narwhal]

There are 20 identical sticks lined up in a row occupying 20 distinct places as follows: 11111111111111111111· Six of them are to be chosen.

How many choices are there if no two of the chosen sticks can be consecutive?

can someone explain me this part of the question?

[coral parcel]

Add a 21st stick to the right of the 20, and choose six non-overlapping pairs of neighboring sticks. Then take the left stick in each chosen pair. The 21st stick will never be a left neighbor and can be removed afterwards.

However, the reformulation allows you to further reformulate the problem to counting the ways to chose some sequence of 6 times "chosen pair of sticks" interleaved with 9 times "non-chosen single stick", which is just a binomial coefficient.

[light raven]

Not sure where to ask this, does anyone know if there is a name for a dual notion to monotonicity between partially ordered sets?

f monotone meaning a \le b implies f(a) \le f(b), but what about the reverse implication when the domain and codomain are not totally ordered?

I wanted to say comonotone perhaps but a quick google search tells me comonotone is already used in probability to mean something different

[stray reef]

holy fuck that's such an elegant reformulation tho

[dense whale]

Is this the right place to ask about numerical methods?

[balmy dome]

anybody know how to prove question 1

[stray reef]

@balmy dome have you made any progress so far or are you completely stuck not knowing how to begin?

for a start, you might want to:

• think about base-ten positional notation (since you're being asked something about "digits")
• prove that 10^n - 1 is divisible by 9 for all n

[vital dew]

Gave you the Advanced selfrole.

[weary tiger]

count the paths between Vertices

I don't understand what is required?

[weary tiger]

this

does he want me to count edges?

or he want me to find every possible path between every 2 node?

[finite rose]

@weary tigerWhat's the definition of a path?

List the objects in this graph that satisfy the definition

Then count them

[weary tiger]

edges that connect nodes

[weary tiger]

A, B, C?

[finite rose]

What's the definition of a path?

[weary tiger]

the edges that connect nodes

[finite rose]

That's not the definition

[weary tiger]

?

what is the definition?

[finite rose]

It should be in your notes

Usually it's a sequence of distinct vertices of the graph such that each consecutive pair is connected by an edge

[weary tiger]

ok

then paths in the graph are a-b-c

?

[finite rose]

a-b-c is a path, correct

There are more

[weary tiger]

so I have to list every path between two node

a-b

a-c-b

etc

right?

[finite rose]

You have to count them. Listing is optional

[weary tiger]

thanks I understand the required now

[scenic birch]

should I just show that if k divides m, then a = b (mod k). Then we have 3 distinct numbers which are m, k, and 1 ?

[finite rose]

yes

[scenic birch]

thanks

[weary tiger]

balls?

[fading abyss]

That's a cool reformulation but I just don't understand this part

I don't understand the "interleaving" part

[scenic birch]

Is proof by strong induction valid if u want to proof something for all integers k such that k mod 4 \neq 0 ?

[coral parcel]

I just meant you need to have nine of one and six of the other, in some order, possibly mixed in between each other in some way.

[scenic birch]

can someone check if this is correct ?

[coral parcel]

Even if it happens to evaluate to the right number, I'd say it is not a correct answer without some actual words to explain why it would evaluate to the right number.

[scenic birch]

Oh, the first term is how many permutation we have without the restriction. The second term the how many permutation can happen with bishops on the same color. 12 is how many ways we can have bishops on the same color and it's multiplied by the number of permutations for the other 6 pieces

[coral parcel]

That sounds reasonable. The reasoning could have been more apparent if you had written 12 as 2·(4 choose 2).

For an alternative count you could also say: 4 ways to place the white bishop, 4 ways to place the black bishop, then (6 choose 2) ways to place the rooks, (4 choose 2) ways to place the knights, and 2! ways to place the king and queen. If multiplying all that together gives the same result as your computation, chances are good that both are correct.

[scenic birch]

Oh this makes more sense, I actually thought about it as the permutations of (0, 0, Bishop, Bishop )

[scenic birch]

Thanks !

[weary tiger]

how do i solve b?

[coral parcel]

By complete, do you mean should distinguish every pair of non-isomorphic graphs? I'd say there cannot be one, for counting reasons -- there are exponentially many isomorphism classes of graphs with any given number of vertices, but any finite set of such vertex-counting invariants will only distinguish polynomially many.

[haughty garden]

Start by selecting one of the physicians to be president. Then you need to fill in the remaining three positions with two physicians and one other person from the board of directors

[weary tiger]

I gotit

thanks though

[haughty garden]

👍

[weary tiger]

If there are 15 books, ans 2 shelves, how many ways can we arrange them so that there are at least 1 books on each shelf?

[gritty pumice]

Do we have to place all the books?

[weary tiger]

Yes

[gritty pumice]

Consider all combination cases I guess?

1 book on shelf 1, 14 on shelf 2

Then 2 on shelf 1, 13 on shelf 2

…

Then 14 on shelf 1 and 1 on shelf 2

So 15! x 15?

Do the order of the books matter within the shelf?

[weary tiger]

The

[weary tiger]

Answer is 15!(14)

I don't how they got it

If there is 1 book on S1 then 14 on s2 the. There are 14! Ways go arrange them

[haughty garden]

Lsfhv has the right idea, except there are 14 different combinations and not 15. Denote $k$ books to sit on shelf 1. Then there are $15 - k$ books to sit on shelf 2. We run $k$ from 1 to 14 to ensure that {\em both} shelves have at least one book. Each of these arrangements are done with $15!$ permutations. Hence, we have $\displaystyle \sum_{k = 1}^{14} 15! = 15! \times 14$ arrangements

[vital dew]

opengangs

[weary tiger]

Shouldn't that be a permutation

And not a combination

[haughty garden]

I should say arrangements instead of combinations

[weary tiger]

@haughty garden I just don't get where the 14 came from?

15! Because there are 15 books that can go on the slef in 15! Ways

But there is a restriction

We have to have 1 on either