discrete-math

[hasty terrace]

[haughty garden]

I am drunk

Sorry

Let x = 1, a = 2, b = -2

[fossil mural]

-2 is not a positive real number

[haughty garden]

oh right yep

[vague laurel]

Try contradiction to prove it here

[zealous oracle]

@hidden totem So could you give an example like take 3 stars and 3 bars and try to solve the confusion through that i think it would make sense to try to solve like this

or if there is something other that you think might help

i might try. to myself come up with example i will ping you again if i complete it or arrive at some conclusion or question

[hasty elm]

Is warshall's algorithm even useful???

why the fuck do I have to use it to compute the transitive closure of

and number of steps is n^3

[hidden totem]

Sure, let's tackle the question of how many ways there are to place 3 identical balls into the labeled boxes A B C and D

I'm going to be a little bit verbose here, because I think some of the details here really help clarify good habits regarding counting problems

Before we begin even starting with solving the problem, we need to know what we are even counting

This seems like a silly question, but there are a bunch of assumptions you are likely making subconsciously and internally, and if we don't bring those up to active awareness, you would be unable to check them, and so when your answer is wrong, you might feel unable to tell why

Let's first begin by imagining that in the worst case scenario, we just draw the things we want to count in a list, and then just count the number of things in the list

For instance, one way is to place all 3 balls into box A

Another way would be to place 1 ball in A, 2 balls in B

I recommend drawing a picture of these on paper or visualize them in your head if you can

Now the question is, would placing 3 balls in A be the same as placing 3 balls in B?

In this case, we can distinguish between boxes A and B, because they are labeled differently, so no, this would not be the same, count these cases as 2, not 1

[hidden totem]

What if we swapped the ball in A with a ball in B? Are these the same?

In this case yes, because the balls are identical, we can't tell the difference, don't count this case twice

Ok so now I'm going to write out a notation for this assignment of balls into boxes

Let's say one of these assignments is:
3,0,0,0

This means we put all 3 balls into box A

0,1,1,1

This means we put a ball into every box except A

Notice that 0,3,0,0 is different because we put all balls in box B

Cool, all we have to do now is count the number of these 4digit sequences that represent our balls in boxes

The reason why we can do this is because of a thing called bijections

If I give you a seq like 0,2,0,1

You can draw how the balls are distributed

Similarly, if I tell you how the balls are distributed, you can give me the seq

And there is no way two distributions will give us the same seq, or two seqs will give us the same distributions

There is no way we listed a seq that doesn't have a matching distribution

Everything is paired up monogamously with nothing in the list being lonely

We are now going to apply this technique again to get it to stars and bars

3,0,0,0 <-> ooo | | |

1,1,0,1 <-> o | o | | o

Can you see what I'm doing? Do you see the pattern?

Rather than having boxes, I am now using bars to mark the walls between the boxes

We call these dividers

Same thing, for any balls and boxes distribution, i can give you the stars and bars arrangement

And likewise, if you give me the stars and bars arrangement, I can tell you how the balls need to be placed in the boxes

| oo | | o

This would be 0,2,0,1

All you need to do now is count the number of ways to arrange the stars and bars, and you'll have the number of ways to place 3 identical balls into 4 distinct boxes

Notice that no matter how we order the stars and bars we get a unique distribution

All that's left is to calculate the number of ways to order the 3 stars and 3 bars

Let me know if that helps and if you still need any clarifications

[hidden totem]

How else would you compute transitive closure?

There are, as far as I know, 2 algorithms in particular that compute transitive closure, but they have different running times such that one is faster when the graph is dense and another is better when the graph is sparse

Or are you asking why transitive closure is a useful notion?

[zealous oracle]

Thanks for the explanation i tried to learn from it, made some notes, I can see the similarity between arranging 4 balls and 3 bars and box and ball problem, what currently confuses me how to drive the formula that is n+r-1 C r-1 from it,
what i ususally interpret from the forumla is just make the dash for the subscipt value that is r -1

[zealous oracle]

so in this case you have 3 balls and 3 bars that could showcase the sequence of number of possible ways but how does one work around the formula for the calculation of number of possible ways in this case the answer should be 35 using n+r-1 C r-1, but i find it difficult to arrive at this and know the logic, given that i am confused about if we use the formula stars and bars will be treated as the same object which they are not

how i understand nCr formula is say you want to find number of ways to draw 3 alphabets from 10 such that order is not important it is 120, at the base level n+r-1 C r-1 is the same as the previous formula but there are two different elements whose arrangemnt needs to be done so how is this formula apt for that problem

[fossil mural]

to be fair, in that case you, a human, probably don't, it's not that hard to just work it out from the definition without really having any sort of plan
if you had 1000 vertices and wanted a computer to solve it, it would be important to have a systematic approach

[hasty elm]

Yeah just feels very strange to get an exercise where we're asked to compute the closure using the algorithm

When it's obviously cyclic

Meaning that the matrix is trivial

[hidden totem]

so once again, we can draw another bijection, but first let's clarify some things

for starters, notice that in any arrangement of stars and bars, the stars and bars are identical

this means that you can swap any stars, swap any bars, and it wouldn't give you something different
the dividers don't matter because the boxes are determined by a fixed order, not by the boundaries

for example, like our previous example, 3,0,0,0 <-> ooo | | |

no matter how i change the order of the dividers: |

it's still going to give me 3,0,0,0

now let's draw the bijection to (n+r-1) C (r-1)

what this expression means combinatorially is out of n+r-1 total objects, you are selecting r-1 of them

n is the number of objects, the stars

r-1 is the number of boxes, the dividers or bars

this is because if you have 4 boxes, you only need 3 walls to separate them

now let's use our example

we have 3 stars and 3 bars

a total of 6 objects, which we will for now create blanks to insert them

. . . . . .

choose r-1, the number of bars, out of these blanks

let's say I choose these:
. | | . | .

the remaining 3 are automatically determined to be stars

o | | o | o

this gives the distribution 1,0,1,1

so once again let's draw the bijections in each direction, the entire way through

suppose I have the distribution: 2,0,0,1

2,0,0,1 <-> oo | | | o <-> 3, 4, 5 (these are the positions of the bars)

the positions of the bars are 3 numbers selected from 1-6

now let's go the other way

pick any 3 numbers from 1-6: 1,4,6

1,4,6 <-> | oo | o | <-> 0,2,1,0

and we get our distribution back

that's why it's (n+r-1)C(r-1), which is also the same as (n+r-1)Cn if that's easier

[hidden totem]

in a simple case like this of course it's trivial, but one of the best ways to understand how an algorithm works is to go through it step by step by hand to see what it's doing

[dire stag]

Where did the -3 (5 x 4) come from?

[fossil mural]

that's the number of words with no repeats that contain the substring "bad"

3 possible places you could put it: xxbad, xbadx, badxx

then 5 possibilities for the first x, 4 possibilities for the second, given that they can't be the same as each other and also can't occur in "bad"

[dire stag]

This makes literally no sense

For part e, you do |U| - |A U B U C|.

So I did 30 (total # of elements) - 27, and it shows that I did 3.

But 27 is not the answer for part d???

I don't even know what the deal is with part f)

It's not 3, 33, or 30

[fossil mural]

...where did you get 27 or 30 from?

[dire stag]

A = 9
B = 11
C = 10
A + B + C = 30

30 - 2 -1 -3 + 3 = 27

[fossil mural]

well that's not the total number of elements, because some things are in multiple of A, B and C

[fossil mural]

i don't know where you got -2, -1, -3, +3 from here

[dire stag]

| A intersection B | 2

| C intersection A | 3

| C intersection B | 1

A intersecton B intersection C = 3

[fossil mural]

|A intersection B| isn't 2, it's 5

there's 2 that are in A and B and not C, and 3 that are in A and B and C, which is 5 in total

[dire stag]

ok

[fossil mural]

...also this seems like a kind of overcomplicated way to do this

[fossil mural]

you can just add up all of the numbers here and you get the total number of things

[dire stag]

I'm trying to do the principle of inclusion / exclusion

So is the total # of elements 18?

[fossil mural]

well the number of elements that are in A or B or C is 18

the number of elements of U is 21, because there's also the 3 outside

[dire stag]

ok thx

[zealous oracle]

So let me try to explain what i understood:
The problem we had initially was about how many different ways are there to distribute 10 runs to 11 different players, which we converted to a problem of 10 identical ball to 11 different boxes given they are identical problems.
An analogy was formed about representing balls with stars and bars for specifying which box get which number of balls
**|** |*||*|*|**||*|| which is representative of the sequence 2,2,1,0,1,1,2,0,1,0,0.
we needed 10 stars and 10 bars in order to determine the sequence

Now we need find the number of ways or arranging 10 stars and 10 bars for which we see we need to find the number of different ways the bars can be assigned positions that is 1st, 2nd, 3rd, 4th... 20th A total of 20 objects out of which only 10 needs to be selected thus 20 C 10 or n+r-1 C r-1, C has been used because the order of the bars is not important they are identical

[tepid pecan]

can someone explain what trivial conclusions are and how to do questions like this

[zealous oracle]

not confident but it says the only trivial conclusion is z as it appears in both the clauses, there are no non trivial conclusions because there are no clauses that contain its literal and negation

[zealous oracle]

can you tell anything about what is being done in the second image

[tepid pecan]

im not sure what exactly trivial conclusions are so im trying to figure what the solution means too

[zealous oracle]

Trivial conclusions, in propositional logic, are statements that can be immediately deduced from a given logical formula without any further analysis or reasoning.

[zealous oracle]

do you know about what domain of maths this is related too, i like the complexity tho

[tepid pecan]

the course is just discrete math

its in topic 1 propositional logic

[tepid pecan]

seems somewhat similar to what my professor said, he said non trivial conclusions must not be tautology (so trivial would be tautology) and it has to be related to the premise

the premise must be true so in this case it should be A(x,y,z)

[zealous oracle]

i would suggest doing simpler problems, if they are availiable, to be sure about fundamentals

[zealous oracle]

if you are up for a discussion for the same please let me know i will like to learn more about it

[tepid pecan]

would you mind if i ask another question on binary tree diagram?

its not exactly related to the original question but i believe its simpler

[zealous oracle]

sure if it helps you i am not from Maths background but will try

[tepid pecan]

okay!

oh sorry i meant binary decision tree

[zealous oracle]

[zealous oracle]

are you doing masters??

[tepid pecan]

no

[zealous oracle]

what grade are you studying

[tepid pecan]

its just introductory discrete math

im y1 undergrad

[zealous oracle]

from computer sciences??

[tepid pecan]

eee

[zealous oracle]

that is yees or no...

[tepid pecan]

electronics and electrical engineering

[zealous oracle]

cake broski, there are some fundamental knowledge that this needs

i am missing it

[tepid pecan]

hmm

maybe this might help

ill give an example

@zealous oracle

[zealous oracle]

i find so much beauty in what i don't understand or if it is complex

[random vine]

What is this

I don’t understand it but if it can be rephrased in terms of computer science then maybe I will

I know about binary trees

[zealous oracle]

binary trees lol

trees are binary

[random vine]

Wdym

Not all trees are binary

[tepid pecan]

its binary decision tree

[random vine]

Binary trees are the ones where each node has at most two children

[zealous oracle]

https://tenor.com/view/geometric-tree-dendrite-gif-5859486

[tepid pecan]

t and f?

[zealous oracle]

TF

[random vine]

Those are leaf nodes

[tepid pecan]

heres my main question btw, i dont get how the true and false assignments amount to 5 and 3

[random vine]

a has children b and f. b has children t and c. c has children t and f

[tepid pecan]

oh that idk

i only deal with true and false

[random vine]

I’m just listing the relationships between the nodes in that particular tree that was drawn

Each circle is a node

Each line represents a relationship between two nodes, where the node above is the parent node and the node below is the child node

Binary trees are trees such that every node has at most two children

A node with no children is called a leaf node

Here, leaf nodes represent true and false (labeled with t and f)

[zealous oracle]

all are leading to undecided whether it will be true of false

total t assignements are 4 and f assignments are 4

[random vine]

What does “t assignments” and “f assignments” mean

[tepid pecan]

true and false assignments?

[random vine]

Yeah but idk what “assignments” means in this context

[zealous oracle]

whether the logic follows true value or false value

maybe 0 or 1

[tepid pecan]

yea

the outcome is true or the outcome is false

[random vine]

I mean, here it looks like there are two true outcomes and two false ones

[tepid pecan]

and depending on the path

[random vine]

Does that mean there are two true assignments and false assignments?

[tepid pecan]

no

that number will depend on this part

hence the addition on the right

[random vine]

Ok so it’s the number of distinct ways that “a”, “b”, and “c” can be assigned true/false

[tepid pecan]

this seemed to me that the assignments will have to be at least as much as the number of t/f outcomes

but the answer for f assignments was only 3

[zealous oracle]

my brain is firiing iron sparks

[tepid pecan]

yes somewhat

[random vine]

Oh wait I think I get it

[zealous oracle]

please explain

[random vine]

For any given leaf node (outcome), how many distinct ways can the intermediate nodes (“a”, “b”, and “c”) be assigned true/false such that that outcome is achieved

So there are 8 possible assignments

[tepid pecan]

yes and 4 true/false assignments each

[random vine]

Five assignments lead to false:
right, right, right
right, right, left
right, left, right
right, left, left
left, right, right

[zealous oracle]

t assignment value is 5..

[tepid pecan]

isnt right righ left true

[zealous oracle]

f assignment value is 3

[random vine]

Three lead to true:
left, left, right
left, left, left
left, right, left

Wait which graph are we doing

[random vine]

I’m doing this graph

[random vine]

Ok I see I’ll do this one

[tepid pecan]

nono that one is done

okay

[random vine]

Ok things are interesting here

[tepid pecan]

im stumped at the variables

[random vine]

Since the x’s and y’s and z’s are all over the place

[zealous oracle]

i don

[tepid pecan]

yea

[random vine]

So here’s how I’m gonna do it

I’m gonna say stuff like “x goes left, y goes right, z goes left”

[tepid pecan]

okay

[random vine]

But I don’t wanna write all that

So I’ll say “left, right, left” to mean the same thing

[tepid pecan]

no problem

[random vine]

left left left -> true

right left left -> true

left right left -> true

right right left -> false

[zealous oracle]

right left left is false...

[random vine]

left left right -> true

[random vine]

I’m doing this by variables

i.e. “right left left” is shorthand for “x means go right, y means go left, z means go left”

[tepid pecan]

ohhh its a trick question?!?!

[random vine]

So you start at x, go right, find x again, go right again, find y, go left, find yourself at false

[random vine]

Idk, I’m just doing this my own way lol

No idea if this is how the question is supposed to work

[tepid pecan]

no but your answer kinda makes sense

ok ill try it and see if it matches

[random vine]

Anyway, continuing where I left off

[zealous oracle]

hehe

[random vine]

right left right -> true

left right right -> false

right right right -> false

So I see five true assignments and three false ones

Out of the total of eight

[tepid pecan]

how did you get the left left left

isnt it x true y true z true

i dont get how you figured the z one out

[zealous oracle]

ah!

there are three neccesssary value here

xy z

so you alot 2 differetent direction and find out possible ways

total 8 combinations are possible

Jason is aloting the different values and using them to see what they lead to arriving at the assignment value possible

[zealous oracle]

which one??

[random vine]

Ok I understand this rule now

[tepid pecan]

cause he said the 3 directions are x y z its not jus the direction right?

[random vine]

So, from the left, the first endpoint is true, with parents x, y, and x. That is one variable short of all the variables, so it gets two assignments.

[tepid pecan]

yes

[random vine]

The second endpoint (false) is impossible to reach because it implies that x is both true and false, so it gets zero assignments

[tepid pecan]

ah

[random vine]

The third endpoint (true) involves all three variables so it gets one assignment

Fourth (false), same logic, so also one assignment

Fifth (false) misses one variable, so would get two assignments, except it’s impossible to reach because it implies x is true and false, so it actually gets no assignments

[tepid pecan]

5 and 6 are impossible right

[random vine]

Sixth (true), same logic, no assignments

Seventh (true), same logic except without the impossibility, so two assignments

[tepid pecan]

then the last one is also 2

[random vine]

Eight (false), same logic, two assignments

[tepid pecan]

omg yes thats it!

[errant bear]

this might be one of the worst problems and ways to teach logic

[random vine]

first true 2
second false 0
third true 1
fourth false 1
fifth false 0
sixth true 0
seventh true 2
eight false 2

[tepid pecan]

yes total 5 t 3 f

[random vine]

Tallying that up, that gives 5 assignments for true and 3 for false

Total eight assignments, as expected

[tepid pecan]

best part is this question is only worth 2 marks

[random vine]

Total assignments is 2^x, where x is the number of variables

If total assignments adds up to a different number, you probably miscounted

[tepid pecan]

yea

ill keep that in mind while doing similar question

[hidden totem]

Brilliant

[true venture]

Say I have a function
b(n) = n^2 + n +2

Then I want to find the generating function
A(x) = sum_{n>=0} x^b(n)

How could I do this?

[lusty loom]

What do you mean by "find the generating function"?

I don't know why you're using generating functions here, since b(n) already has a nice closed form

Usually you use generating functions to find closed forms for recurrence relations ,like say, f(n)=f(n-1)+f(n-2), n≥3 and f(1)=1 and f(2)=1

Also I think your generating function is a bit odd, should be $A(x)=\sum_{n \geq 0} x^{n}b(n)$

[vital dew]

smidgin

[true venture]

I mean yea, what I wrote is a generating function. I got to this trying to find a generating function for the seq. [1 2 1 2 3 2 1 2 3 4 3 2 1 ...]

I know normally the coefficients are for all n, but what I wanted here was something that Expands to x^2 + x^4 + x^8 ...
Not 2x + 4x^2 + 8x^3 which is more common

[lusty loom]

I don't see how having that helps you find the general term for the sequence you sent

n^2+n+1, n≥0 gives you the index of each 1

In your sequence

[true venture]

Yea, then for the other numbers it is a similar quadratic for each occurrence in both the acents and decents, so then summing a bunch of x^b(n) would give the seq

But that way seems messy, 🤔

[lusty loom]

If you will be using a generating function to any effect, you need a relation between b(n) and b(n-1), b(n-2),b(n-3),...,b(1) (and it should be a linear one afaik) and right now we don't have that happening

[true venture]

Oh yes

The progression I want is not geometric, so there is no function for what I'm looking for

[lusty loom]

There is a function, there definitely is a function but we won't be able to find it via generating functions

[true venture]

For the nth term for the seq, there is a equation using floors.

Thanks

[upbeat pine]

does anyone understand this

wait nvm

i misread it

[hard hazel]

can someone help with this?

[lofty cloud]

What step are you on?
1. I don't know where to begin.
2. I have begun but got stuck midway.
3. I got an answer but I was told that it's wrong.
4. I got an answer and would like my work checked.
5. I have a question about someone else's work/solution.
6. I have completed the problem and don't need help anymore. Thank you.
7. None of the above

[hard hazel]

4

[brave rock]

Post your answer then!

Don't ask to ask, just ask.

[hard hazel]

f^-1(T) = 2n for all neZ ?

[brave rock]

Do you mean to say f^-1(T) = {2n | n in Z}?

Because no, that's not right.

[agile magnet]

well hold on we can work with this

[brave rock]

You may need to recall the definition of f^-1(T).

[agile magnet]

{2n | n in Z} = T, agreed right?

[hard hazel]

yea

[agile magnet]

if you think f^-1(T) = T

give me a proof of each subset inclusion

[agile magnet]

(hint: this process will tell you why it's not right)

and this is one good way to check your work

[hard hazel]

well my defn of f^-1 is f^-1(T) = {a in A | f(a) in T} ⊆ A

[agile magnet]

say in instead of e

[hard hazel]

ok

[agile magnet]

but ok that definition of f^-1(T) looks right to me

(but in particular, A = Z right?)

so its all integers a such that f(a) is even

[hard hazel]

right

[agile magnet]

so now give me the proof that T is a subset of f^-1(T), or that f^-1(T) is a subset of T (or both if you think you have valid proofs of both!)

[hard hazel]

hm

I dont really have one

that i can come up with on the spot

[agile magnet]

well you claim that f^-1(T) = T

you must have proved that somehow

[hard hazel]

I did?

[agile magnet]

since you claim to have an answer

[hard hazel]

Oh yeah

[agile magnet]

😵‍💫

[brave rock]

If you cannot justify your answer, then it's just a guess, and that's not good enough.

[hard hazel]

Unfortunately there didnt seem to be an option for that

but basically my thinking process was

[brave rock]

How about you try getting a different answer, and try proving it before you ask us to check it.

[agile magnet]

(would have been option 2 btw)

[agile magnet]

anyways yea do this

[hard hazel]

in this case i choose option 2

im not really sure how to go abouts this

problem

[agile magnet]

try to find a pattern

pick some test values

0, -1, 1, etc a few others

see if you can determine if they are in f^-1(T) or not

[hard hazel]

could you explain the defn of f^-1(T) in a easier to understand english way

[brave rock]

And make sure you can explain why those values are in f^-1(T)!

[brave rock]

What part of the symbolic definition are you struggling with

[hard hazel]

I can look at the formal defnition but I find it tricky to understand it

f(a) in T} ⊆ A

like this part

[brave rock]

Ignore the ⊆ A.

[hard hazel]

okay

[brave rock]

f^-1(T) = {a in A | f(a) in T}

Is that clear or not?

[hard hazel]

Yes

[brave rock]

Great.

[hard hazel]

for the most part

[brave rock]

If you have a specific problem with it, just say it.

[brave rock]

If not, do what spamakin suggests here now.

[hard hazel]

what particularly does f(a) in T means?

like

[brave rock]

It means that f(a) is in the set T.

[hard hazel]

how does it relate to f^-1

[brave rock]

f^-1 is just notation.

f^1(T) is defined to be {a in A | f(a) in T} — this is the definition of the notation f^-1(T).

[agile magnet]

(also don't say something is clear when its not clear)

(makes it harder to help you)

[hard hazel]

So theres a set A and set T and funciton f, f(a) is in T if a in A

[brave rock]

No.

f(a) is in T if a in f^-1(T).

Not everything in A gets sent to something in T.

In this specific circumstance, A = Z (the set of integers).

[hard hazel]

so if my function is x+1 if x is even, and my set T is all even integers

[brave rock]

Yes

Do not fall for the trap.

[hard hazel]

so if it was just asking what is f(t) then it would just be all the odd integers right?

[agile magnet]

you mean f(T)?

and if so why

[hard hazel]

yes

[brave rock]

Sure, f(T) = {2n + 1 | n in Z}, yes.

[agile magnet]

(but can you tell us why, and does this help you at all?)

[hard hazel]

because if you put in an even integers into f(x) from the set T, you will only get odd integers because even + 1 = odd

[agile magnet]

• that tells me that f(T) is a subset of the odd integers, still want the other direction
• does this help you at all answer what f^-1(T) is?

[hard hazel]

How do you go the other direction?

[agile magnet]

well say you have an odd integer 2n + 1

can you tell me why it's in f(T)?

(also there is a reason I am asking that second bullet point but this is still good practice ig)

[hard hazel]

2n+1 is in f(T) because f(x) takes in the set T which makes all even integers odd?

sorry im having a lot of trouble wording what im trying to think

like it makes sense in my head but I cant put it into words

[agile magnet]

why is 3 in f(T)?

[hard hazel]

because 3 = 2n+ 1 if n = 1?

[agile magnet]

all you've said is that 3 is odd

I am asking why is 3 in f(T)?

what is the x in Z such that f(x) = 3?

[hard hazel]

Because f(T) is the subset of all odd integers and 3 is odd?

[agile magnet]

I am trying to get you to prove the other subset inclusion

[agile magnet]

answer this

then tell me what is the x in Z such that f(x) = 5?

[hard hazel]

x = 2

x = 4

[agile magnet]

what is the x in Z such that f(x) = 2n + 1 for any n in Z?

[hard hazel]

the subset T ?

[agile magnet]

x is an element not a set

[hard hazel]

2x?

[agile magnet]

f(2x) = 2n + 1?

[hard hazel]

well how do I represent x as a collection of numbers

[agile magnet]

I am not asking for a collection of numbers

I give you a random odd number 2n + 1

I want the integer x such that f(x) = 2n + 1

[agile magnet]

similar to how you answered this

just now we are dealing with an arbitrary odd number instead of a concrete one

[hard hazel]

x = n ?

[agile magnet]

f(n) = 2n + 1?

are you sure?

does that line up with your previous answers?

[hard hazel]

if I want 3 my x = 1, if I want 5 my x = 2

[agile magnet]

so now you're saying f(1) = 3

when earlier you said f(2) = 3

[hard hazel]

oh

wait sorry

[agile magnet]

and now you're saying f(2) = 5 when earlier you said f(4) = 5

[hard hazel]

well werent we talking about different functions though?

[agile magnet]

no

[hard hazel]

one was x + 1 and the other was 2n+1

well I suppose they are the same

[agile magnet]

the only function we have been talking about this entire time is f here

they are not the same what

[hard hazel]

well if x is all even

[agile magnet]

when I was saying 2n + 1 I was talking about an arbitrary odd integer

I gtg but you really really have to be strict about the definitions you are using

and what variables mean what

[hard hazel]

its okay

I need to think on this

thanks tho

[hard hazel]

wait is it x -1 ?

or n - 1

[hard hazel]

If Im proving a piecewise function to be injective do I have to show it is injective for each case ?

[brave rock]

That's typically not sufficient, no.

[hard hazel]

2 and 5 produce the same value 1, meaning they wouldnt be injective

But if you did each case separately then they would be injective?

which method is correct?

[elder berry]

You look at all cases

it's wrong to just check if the specific cases are injective

[hard hazel]

I see

[elder berry]

so, f(x) is not injective, even though x/2 is injective and (x-3)/2 is injective

[hard hazel]

hmm

okay

Thank you

[fossil mural]

yeah if f(2) = f(5) and 2 is not equal to 5 then f is not injective, that's just, what "injective" means

[hard hazel]

Yeah I did know what the meaning of injective is I just wasnt sure how to go abouts it with a piecwise function

[vapid drift]

does anyone have a video going step by step with truth trees no textbooks

[stray reef]

injectivity is a property of the function as a whole, not any individual i/o pairs within it.

[robust bramble]

that looks like the 3n+1 problem

[odd prism]

The question is how many ways are there to walk from home (0,0) to the exciting location (5,14) by only moving east or south each block and avoiding crime zone

I’ve split into cases for the Manhattan distances

[dire stag]

Anyone knows what this is about? My book doesnt cover this

Is this just algebra? How do I expand it then?

(y2 - y1) / (x2 - x1)

[odd prism]

It is quite literally binomial coefficient

Algebra

[dire stag]

So this essentially?

Would (x + y) ^2 be the same as (x1 + y1) (x2 + y2)?

[silk lily]

Hi I have a question about euclidean algorithm.
Let's say we want to use it to find gcd(14,6):

First 14 % 6 = 2 , with q = 2, meaning 6 fits 2 times to get 12 and we are left with remainder 2.
Now we know 2 | 14 and 2 | 6, so it means 2 | 14 - 6.
My question is why does the algorithm jump to the conclusion/decision of considering 2(the remainder) and not any other number less than 6 ?

[gusty swallow]

only if x1 = x2 and y1 = y2, but you'll get something similar.

[gusty swallow]

because your remainder, 2, divides your dividend, 6. so the algorithm stops, and that remainder is the gcd.

[silk lily]

hmm okay
for example for (14, 8) I can see the same pattern, but for (14,9) how do we know that the remainder will not divide the dividend again and the algorithm will give the correct result? which should be 1.

how should I understand this in a general sense ?

[gusty swallow]

if your remainder divides the dividend, then the new remainder is 0. So the algorithm cannot continue.

we know it works because there is a proof that it works

[agile magnet]

Do you know the lemma behind the algorithm?

If $a, b \in \mathbb{Z}$, then there exist unique $q, r \in \mathbb{Z}$ such that $a = qb + r$ where $0 \leq r < b$. Then using this, we have that $\gcd(a, b) = \gcd(b, r)$.

[vital dew]

Spamakin🎷

[agile magnet]

that's how you know "the algorithm will give the correct result"

[odd prism]

Any tips on how to do this without having to brute force it

[agile magnet]

it's case work

So for example going from home to red and continuing right is one case

and going from home to blue and continuing right is another case

you can split into further casework as needed but that's the high level idea

@odd prism does that help

its annoying but better than bruteforce

[odd prism]

My professors hint was to split into two cases going up and down

[agile magnet]

and then there's another case of going all the way to the bottom

[odd prism]

The idea is manhattan distances

And how the nodes represent binomial coefficients

[agile magnet]

oh sure

[odd prism]

The total number of paths not considering the crime zone is

5+14 choose 5

[agile magnet]

do you know how to do this problem wihtout the crime zone being present?

ok yea

perfect

so now you have to do this same analysis but now you have to split into cases

so like going from home to red

then red to location

home to blue, then blue to location

home to bottom row, bottom row to location

etc etc those may or may not have sub cases

[odd prism]

Oof

[agile magnet]

but those cases are all disjoint if you do this properly

yeaaaaa it sucks

but better then brute force

which is all we can hope for I guess

[odd prism]

I was under the impression that there was a couple of points that a path must go through

Which would simplify things down

[agile magnet]

yes but the way you do that is by considering the cases

for example as soon as you hit the bottom row

you have to go right only

there's no other option

[odd prism]

Right

[agile magnet]

nvm red and blue should be here

[odd prism]

I hate this diagram stuff

[agile magnet]

if you go to blue, you have to go right for a bit

etc etc

case work 😔

[odd prism]

Is this what cs discrete math is

Graphs

And cases

Because this sucks

[agile magnet]

in the beginning yes

but later you can get to some beautiful stuff

or you may realize you just hate it all, happens

Like personally I took a graph theory course, hated it

but I love love love algebraic combinatorics

[odd prism]

I’m not a cs major, but a math/stats

[agile magnet]

same

[odd prism]

This is just my combinatorics class

[agile magnet]

combinatorics related to abstract algebra gets really pretty IMO

but some people just dislike combo overall

just depends on how your neurons are wired

[odd prism]

I like that you have creativity over your solutions

[agile magnet]

ye

[odd prism]

But I hate the fact that solutions are so hard to come by

[agile magnet]

https://igorpak.wordpress.com/2013/05/14/what-is-combinatorics/

this is a nice read

also some of these are fun: https://www.math.ucla.edu/~pak/hidden/papers/Quotes/Combinatorics-quotes.htm

or if you hate combo still: https://www.math.ucla.edu/~pak/hidden/papers/Quotes/Just-quotes.htm

[odd prism]

I really like probability so that’s why I’m taking combo

But again it only helps for discrete cases

Plus I keep telling myself that all the technical job interviews are likely to ask some sort of combinatorics question

[odd prism]

Still having trouble, it is a valid solution if I just did a form of pascals triangle putting 0s in the crime area

[obsidian dove]

[vital estuary]

Hello 👋 is this correct?

Number 4

This is what our prof taught us but when i used converter, it's different

[stray reef]

yeah cause you're supposed to repeat the procedure on the quotient, 43
it too should be converted into octal and not just written in decimal as is

@vital estuary

[vital estuary]

How do i do it?

[vital estuary]

This is what I've learned from google btw, is this correc

[stray reef]

,calc 8^3 + 2 * 8^2 + 8 + 3

[vital dew]

Result:

651

[stray reef]

idk how you got that 1213 and you haven't written anything

so i can't tell what you got wrong, but it is wrong

but #4 is correct

[vital estuary]

That is wrong hehe, i followed my professor's formula

[stray reef]

can you show your professor's "formula" exactly as they wrote it

[vital estuary]

His formula was only 971/8

[vital estuary]

The answer is 121 here without the remainder and he said that we put that remainder beside the answer

IDK he does not teach us the correct way xD

[stray reef]

...

ok so like, you're supposed to repeatedly divide your number by 8 until you get a quotient of 0

and then write down all the remainders you get in right to left order

[stray reef]

i think there is some miscommunication somewhere. either between your professor and you, or between you and me

[sacred basin]

i am trying to prove that

((10!)!)/(10!)^(9!)

is an integer by using a combinatoric type of proof by making a prolem that has said number as a result which kinda verifies that the number is an integer

[stray reef]

count the number of arrangements of 10! symbols in a row, in which the symbols come in 9! different types and each type appears exactly 10 times

or to demystify that a little:

count the arrangement of 3,628,800 symbols in a row, in which there are 362,280 types of symbols and each type appears exactly 10 times.

[sacred basin]

I see, it makes sense now ,thank you!

[sterile flame]

Hi there, In my real analysis book there's this definition $\sqrt[k]{x}:=\sup{t: t^k\le x}$ (which of course, assuming the completeness axiom, serves the purpose of proving that the k-th root of a number exists). The author then asserts, without justification, that $(\sqrt[k]{x})^k=x$. I get why that should be true, but I can't understand why it is formally valid. Can anyone help me out?

[vital dew]

lazur__

[stray reef]

by trichotomy exactly one of the following options is true: $(\sqrt[k]{x})^k < x$, $(\sqrt[k]{x})^k = x$, $(\sqrt[k]{x})^k > x$. try to rule some of them out.

[vital dew]

アンナ

[sterile flame]

Obviously it can't be $>$... What about $<$ though?

[vital dew]

lazur__

[stray reef]

if it were < then it would belong to the same set of which it's claimed to be the supremum

[sterile flame]

Oh, is that not allowed? The supremum can belong to the set itself, can't it?

[stray reef]

well, it can. i guess spelling it out formally would take a bunch more symbol-pushing.

[cobalt latch]

how do i do this problem

[sterile flame]

Oh okok, got it. Thanks a lot

[cobalt latch]

@stray reef

[stray reef]

!noping

[lofty cloud]

Please do not ping individual helpers unprompted.

[stray reef]

also might wanna be a bit more specific what you're having trouble with.

[cobalt latch]

what is the integer m

[stray reef]

it is part of the translation of "b mod 12 = 7" into elementary language

[cobalt latch]

oh so m is q

[stray reef]

m is the quotient of the division of b by 12, yes.

"m is q" is kind of bad since the letter q appears later on. but whatever.

[cobalt latch]

so i have 60m + 35 = 12q +r

[cobalt latch]

how would i find q and r?

[stray reef]

wrong replied-to message.

anyway, consider: 60m is itself a multiple of 12. namely, 60m is 12 times what?

and how many more twelves could you fit in by breaking them off of the 35?

[cobalt latch]

(5 x 12)m + (5 x 7) = 12q + r

[stray reef]

don't use the letter x as a multiplication symbol.

also you didn't really follow my instructions there.

[cobalt latch]

im kinda confused

wym by breaking them off of 35

[stray reef]

first,

60m is 12 times what?

[cobalt latch]

5

[stray reef]

no, 60m ≠ 12 * 5.

[cobalt latch]

5m

[stray reef]

60m is 12 times what?

yes, 60m = 12 * 5m.

and i am then asking you, essentially, to break down 35 itself into quotient and remainder.

[cobalt latch]

how do i break down 35 into quotient and remainder

[stray reef]

divide it by 12 ...

tell me the quotient and remainder that you get

[cobalt latch]

quotient 2 and 11 remainder

[stray reef]

35 = 2 * 12 + 11, right.

60m + 35 = 12 * 5m + 12 * 2 + 11 ...

[cobalt latch]

so 12 * 5m + 12 * 2 + 11 = 12q +r

[stray reef]

yes, now you need to connect the dots

[cobalt latch]

do i divide both sides by 12

[stray reef]

no you are overthinking it

[twilit sundial]

trying to prove with contraposition that if $a+b+c>0,$ $ab+bc+ca>0,$ and $abc>0,$ then $a,b,c>0$

[vital dew]

elrichardo1337

[twilit sundial]

the cases where exactly one or three of $a,b,c$ are negative are easy, i'm having a bit of trouble with the case where two of them are nonpositive

nvm, just turned out i needed to consider more subcases

[vital dew]

elrichardo1337

[twilit sundial]

actually for the case where two are negative im not quite sure how to proceed

[cobalt latch]

ok so i got 12 for quotient and 11 for reminder, the reminder is correct but idk why it says the quotient is incorrect

5b = 12(5m+2)+11

[twilit sundial]

can anyone help with this 😭

bc i don't see a way to bound $ab+bc+ca$ above

[vital dew]

elrichardo1337

[twilit sundial]

since i'm trying to prove that that inequality fails in that case

[haughty garden]

WLOG, we may assume that a <= b < 0 < c. Firstly, we have that ab + bc + ac > 0 implying that ab > c(-a - b). We also have that a + b + c > 0 implying that c > (-a - b). Therefore, we have that ab > (a + b)^2 = a^2 + 2ab + b^2, or equivalently that a^2 + ab + b^2 < 0. Show that this can’t happen

[twilit sundial]

ahh gotcha

and that fails bc all those pairwise products have to be positive?

a^2, ab, b^2

i think i got it now, thanks!

[cobalt latch]

nvm i got it its 5m+2 thanks

[calm sapphire]

does this truth table look right ?

[twilit sundial]

both of your disjunction columns are very incorrect

$p\vee q$ is disjunction NOT conjunction

[vital dew]

elrichardo1337

[twilit sundial]

it is true if at least one of $p$ and $q$ is true

[vital dew]

elrichardo1337

[twilit sundial]

so that column would read T,T,T,F

[weary tiger]

i have no idea how to even start this question

i know i need fundemental theorem of arithmatic

thats about it

this course is the end of me

[twilit sundial]

$2^3\cdot 3^2=72$ works

[vital dew]

elrichardo1337

[twilit sundial]

for $a$ to be minimal, its only prime factors should be 2 and 3

[vital dew]

elrichardo1337

[twilit sundial]

the exponent of the $2$ should be a multiple of $3$ and $1$ less than a multiple of $2,$ i.e. $3$ is the smallest such exponent

[vital dew]

elrichardo1337

[twilit sundial]

the exponent of the $3$ should be even and $1$ less than a multiple of $3,$ which forces it to be $2$

[vital dew]

elrichardo1337

[weary tiger]

i dont understand the last 2 parts

[weary tiger]

i get this is 6

[twilit sundial]

???

when did i say it was 6

it should be a power of 2, times a power of 3

when you multiply by 2 you get a perfect square, i.e. all the primes in 2a should be raised to even powers

when you multiply by 3 you get a perfect cube, so all the primes in 3a should be raised to powers that are multiples of 3

[weary tiger]

wait but why do the prime factors have to be 2 and 3

[twilit sundial]

if we had any larger prime factors

they wouldn't be contributing anything towards minimizing a

[weary tiger]

so since 2 and 3 r the two samllest prime we use them?

[twilit sundial]

reread the problem

bc we're multiplying by 2 to get a perfect square, and multiplying by 3 to get a perfect cube

[weary tiger]

mhm

[twilit sundial]

that means we only need to care about those

[weary tiger]

oh

[twilit sundial]

especially since we're looking for the minimal a

otherwise you'd have to tack on random $p^6$s which are clearly not helping us minimize

[vital dew]

elrichardo1337

[weary tiger]

but then how do the exponants work

why multiples of 2 and 3

[twilit sundial]

there is no reason to include any primes larger than 3

this should just follow from basic number sense

[weary tiger]

so i do 2^x * 3^y because 2a and 3a

[weary tiger]

why

how do i know the smallest a cant have 5 or 7 init

[twilit sundial]

try it yourself

any higher primes you include

would be forced to be raised to the 6th power

[weary tiger]

why

[twilit sundial]

and are extraneous for your square/cube condition

[twilit sundial]

for it to be both a square and cube when you multiply the rest of it by 2 or 3

[weary tiger]

oh

[twilit sundial]

and the idea is you don't need those extra primes

[weary tiger]

so 2 and 3 are the smallest primes so i use them

[twilit sundial]

because they're the ones directly relevant to the problem

if they said 5a is square and 7a is cube

i'd use 5 and 7 instead

[weary tiger]

oHH

how do the exponants work then

[weary tiger]

why does it need to be a multuple of 3

[weary tiger]

isnt 2 to the poer of any even exponant a perfect square

[twilit sundial]

remember your cube condition also exists

any prime to any even power is a perfect square, yes

[weary tiger]

so why is it not 2^2 8 3^3

[twilit sundial]

2a is a perfect square --> exponent of 2 must be odd, so that when you increase it by 1 it becomes even

3a is a perfect cube --> exponent of 3 must be 1 less than a multiple of 3, so that when you increase it by 1 it becomes a multiple of 3

now to combine these two conditions

[weary tiger]

why am i increasing them by 1

[twilit sundial]

😭

when you MULTIPLY by 3

you're INCREASING the exponent of 3 in the prime factorization by 1

[weary tiger]

OHHHHH

thanks

im HARD struggling in this class

[twilit sundial]

npnp

[odd prism]

Can anyone help me understand the process

[stray reef]

12 is not the quotient it is the divisor.

[tender zealot]

can the subset symbol be used for single elements? for example, is the statement 2 ⊆ {2, 3}

true, false, or does it have a syntax error and it's undefined?

[fossil mural]

depends on what the elements of 2 are

if you're treating 2 as not being a set then it's a syntax error

if 2 is a set, then it's true iff every element of 2 is either 2 or 3

what's definitely true is that $2 \in {2,3}$

[vital dew]

bee [it/its]

[tender zealot]

thanks

[cyan horizon]

hello everyone

can anyone recommend me a youtube channel for discrete math

i wanna prepare myself before going to my lectures

[cobalt latch]

i see thanks

[weary tiger]

Hi everyone

Hi everyone, please what do you think the solution of the inverse of a function is when we are dealing with a relation and the inverse of an injection is when we are dealing with a relation.
My intuition for this was that the inverse of a function will be a function and the inverse of an injection is an injection as well.

Here is what I mean(although I did get it wrng in a quiz but I have to understand why)

[hexed saffron]

Hello guys, how is it going?

I need a help for discrete mathematics.

[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/

[weary tiger]

he literally never said that

[weary tiger]

any help please?

[regal pelican]

is combo basically permutation but order diesn't matter

[haughty garden]

yes

that's why C(n, k) is just P(n, k) / k!

[regal pelican]

alright ty

[icy swift]

How many sets of three integers between 1 and 20 are possible if no two consecutive integers are to be in a set?

my way of doing it is using subtraction principle: finding 20 choose 3 as | U | = 1140
for |A ^ c |, I said that if you fix 2 consecutive elements of the set {x, x, _}, then there are 20 choices for the last element, and there are also 20 ways to fix the 2 consecutive elements, thus |A ^c| = 20 * 20 = 400

|A| = |U| - |A^c| = 1140 - 400 = 740 sets, but the answer is 816

I tried to figure what is wrong with my way but I'm a bit stuck

[distant bobcat]

I am not sure how to expand further for the linear combination of the gcd where for gcd(91,84) I have

91 = 84 *1 + 7
84 = 7 *12 + 0

writing 7 = 91 - 84 1 , but the answer gives the linear combination : 7 = 2591 -27*84. How do I proceed rewriting?

[stray reef]

hold up

,calc 25 * 91 - 27 * 84

[vital dew]

Result:

7

[stray reef]

but on the other hand your 91 * 1 + 84 * (-1) works too

@distant bobcat

can you show the answer key that you're looking at?

[distant bobcat]

Yes, I know both work , but Im wondering how the other coefficients are found

[stray reef]

beats me

[distant bobcat]

I was puzzled as well, but thanks anyway

[elder berry]

There aren't 20 choices to choose the last element

you want a set of numbers (distinct), so if you fix the first two, you can't use them again for the third number

so there are only 18 choices

continue from there

[icy swift]

how come you cant use them again for the 3rd number tho?

We would want to subtract subsets like {1,1,1} which count as a set of consecutive integers?

[elder berry]

{1, 1, 1} is simply {1} in set theory

[icy swift]

oh

[elder berry]

what you are thinking of are ordered tuples

[icy swift]

right

well then there'd be 19 choices for that last integer?

[elder berry]

18

[icy swift]

from 2 to 20?

[elder berry]

if you fix two consecutive integers, say 1 and 2, you can't use those integers again, meaning the last integer is from the other 18 integers, in our specific case from 3-20

[icy swift]

ohhhh wait

i think this whole time i was thinking consecutive was the same number

nvm i was being dumb

makes sense now thanks for the help

[somber spindle]

hi, im doing a sample paper in preparation for my exam next week and got confused on a question about equivalence classes. how exactly do you determine the equivalence class? because at first i thought there would be 2 equivalence classes,
{(x, y): x * y > 0} and
(0, 0)

but then thought about it a bit more after seeing the answer choices and thought that maybe there are 3 equivalence classes,
{x: x < 0}
{0}
{x: x > 0}

would love to know tips on how to determine equivalence classes and if my second answer is correct

[fossil mural]

well the equivalence classes are going to be subsets of the set, they're not pairs or sets of pairs, so {(x, y) : x * y > 0} definitely isn't an equivalence class of R

in terms of checking whether your answer is correct: are any two elements of the set related by R iff they're in the same equivalence class? if they are then your answer is correct

[somber spindle]

ohhhhh i see

[somber spindle]

trying to wrap my head around this cause its late at night for me already hold on

[somber spindle]

ohhhhhhhhhhh ok

that gives me a new perspective to look at it from

thank you so much bee 🙏

[outer flame]

Hello

I got a question

i need to show, that BA is symetrical. But I need to multiply them first which I know how to do, but not with a1, a2 etc

[errant bear]

wut

you mean you only know how to multiply them when they aren't variables?

its the same rules

[outer flame]

oh wait it might never happen that I gotta multiply a1 with a2 for example..

[stray reef]

you just leave $a_1a_2$ as $a_1a_2$ lol.

[vital dew]

アンナ

[outer flame]

ohh I see

[stray reef]

just leave them as-is

[outer flame]

sorry i am in uni but my math skills are from 5th grade 😄

[errant bear]

:o

have you taken an algebra class?

[outer flame]

yeahh ig in the normal math subject

I barely passed after over 100 hours of studying

[distant bobcat]

There exists some luxirious chocolate which comprises 103 packages. They were divided onto plates with 8 on each, and
there were 6 cheeses left to eat.
Formulate the problem "how many chocolates were in each package?" as a problem in
modular arithmetic, and solve it.

I thought here of solving the problem either by formulating
$103x = 6 (mod8)$ which gives $(8 \cdot 12 ) + 7 x = 6 (mod8)$ Hence $x=2$. Alternatively,
$103x - 8y = 6$ which when using Euclids algorithm gives $-6$ as an x-value, but is we want the principal remainder in mod8 we get $x=2$. I am assuming I am justified in doing so since $x=-6$ does not make sense as being an answer. Cannot have negative amount of chocolates in each package?

[vital dew]

FredrikPiano

[gilded dragon]

do u consider “this sentence has 12 words” to be a statement

[timber barn]

I need help with inverse image

[distant bobcat]

its a sentence that is either true or false, so yes @gilded dragon

[timber barn]

How do I use this

[stray reef]

f^-1({2}) is the set of all x such that |x|+2 = 2

[timber barn]

so what would be the answer?

0?

@inland gale

{ 0 }

[gilded dragon]

uhh what about "this sentence is true."

not a statement since truth value can't be determined? not verifiable?

[fossil mural]

i think i'd just say that in general, don't do self-reference

sometimes something that is informally written with self-reference (like "this statement is not provable") can be written in a way that doesn't directly refer to itself, but in that case i'd say the version without self-reference is what the statement really is and the self-referential version is just a shorter way to communicate it to another human

sometimes something that is informally written with self-reference (like "this statement is false") doesn't actually describe any fully-written-out sentence and is therefore just meaningless

[mental pecan]

Yes

[mint granite]

anyone got time for a quick q

[quiet adder]

can any1 please help with a game theory question

[static briar]

can anyone help me out with this?

[haughty garden]

Suppose you have a pool of n students competing for one of at most 3 positions (President, Vice President, Secretary) in a society. Only k students are eligible for selection because they need to be in the society first. The President and Vice President positions must be filled; however, the Secretary position may be filled if need be. Our goal is to count the number of ways to form this society of k students, which includes assigning all two or three positions.

We can either fill in the society first and then assign the positions, or assign the positions first and then fill in the remaining spots of the society

[static briar]

To prove something combinatorially do we always need a story like this?

[haughty garden]

you don't need a story per se, a combinatorial proof is a proof by double counting (i.e. counting the number of elements in some set in two different ways, giving you the two different expressions in your combinatorial identity)

[static briar]

Would it still be a valid proof is a story is used as a frame of reference

[gilded dragon]

Is “The Chiefs will win the superbowl.” a statement?

[gusty swallow]

yes

[gilded dragon]

Ik “She…” is not considered a statement but what about “I am 10 years old.” Is “We are five years old.” a statement ?

just wondering cus i feel like the TAs are telling me different things

[gusty swallow]

anything that has a truth value (true or false) is a statement

[gilded dragon]

i mean some things they consider too ambiguous

so idk

[gusty swallow]

sure. Things can be too vague sometimes "This play is good" is an opinion, it doesn't have a truth value because there's no objective truth.
"This sentence is false" has no truth value, it's self contradictory. so it isn't a statement.

"That person is tall" is also something I'd say is too vague to be a statement, where as "That person is taller than 6ft" is a statement

[gilded dragon]

Hm ok

interesting bc i think my prof considers “Bill is tall” a statement but not “He is tall” since he is too vague

[gusty swallow]

I'd say neither is really a statement. Shaq probably won't think Bill is tall, while your prof does.

[gilded dragon]

tbh yeah idk is this stuff even relevant

[gusty swallow]

However, something like "Compared to me, Bill is tall" could be a statement

[gilded dragon]

like is this english thing used in actual logic or whatever

ig am i gonna be translating stuff back and forth later on

[gusty swallow]

eh, i mean, being able to use natural language to communicate math is a very important skill.

[gilded dragon]

ok makw ssense

what abt for discrete math

[gusty swallow]

Sure, understanding statements is part of understanding theorems and proofs

[somber spindle]

hi, im a bit confused on how to tackle this weak induction problem:

here is what ive worked on so far and im not sure where to go from here, or if im even on the right track

would appreciate any hints or nudges in the right direction 🙏

[sick grail]

you can change the two terms in the middle to be 16*stuff + something useful

[somber spindle]

OHHHH

thank you so much

that never crossed my mind 😭

[misty storm]

hello, can someone explain how to solve linear congruences? for example: 7x = 5 (mod9)

so to find x

[cerulean radish]

Start by finding the inverse of 7 modulo 9

[stray reef]

^

you need to know how to find modular inverses (incl. how to determine whether one exists)

@misty storm

[misty storm]

so like checking if a solutino exists?

like finding gcd(7,9)?

[stray reef]

that's how you find whether "the inverse of 7 modulo 9" exists

(but if you find that it does, then you aren't done -- you still need to find the inverse itself, now knowing it exists)

[mighty saffron]

7×1=7 remainder
7×2=14/9=5 remainder...so x=2

[misty storm]

ahh okok

thanks for the help everyone!

[stray reef]

this is trial and error, and will take a million years on even slightly bigger numbers.

[icy swift]

Can someone explain to me the logic of this change of variables from x to y = x -1?
https://gyazo.com/a084d08aa590f4af145e7cf7482dc962

it's an interesting trick but i dont understand why it works

[agile magnet]

Because the formula for the number of solutions is for the number of nonnegative integral solutions

Not positive solutions

So the change of variables allows for this

x is positive implies that y = x - 1 is nonnegative

[calm chasm]

I have a theorem that shows to propositions are logically equivalent. Does that mean I can say rewrite on proposition with the other if I need to?

[brave rock]

Yeah

[calm chasm]

I need to write p -> q using conjunction disjunction and not. So I figured maybe this is the way I'd do it

[brave rock]

I imagine you mean disjunction lol

And yeah, sure

[calm chasm]

Yeah auto correct

[icy swift]

Right but why not subtract x by 2 or some other arbitrary number s.t y is still nonnegative

[agile magnet]

because if x = 1 then x - 2 < 0

Which is negative, not nonnegative

[icy swift]

i see so any other number would make y nonnegative

makes sense

[grizzled storm]

Hey I just started learning a bit about this subject, I'm following this course:
https://www.youtube.com/watch?v=UwYJUKVc-Hs&list=WL&index=5&t=1002s

Right at the end of the first lesson he mentions a problem with 4 coins arranged in a square that can change position by jumping over each other (kind of hard to describe with just words). The goal is to find out if it is possible to end up in a set up with the coins arranged in a square bigger than the original. Since I'm a beginner at this I have no clue on how to even start thinking about this lol. I also don't want to just look up the solution since it would be a missed learning opportunity

[tidal kindle]

Hello guys, if someone could explain me this...
As I have understood, a Hamiltonian cycle is a graph where you visit all the vertices but only once every edge.
So, in this example, the degree sequence when there are ones, you cant put it connected with the graph, right?
Thanks

[cyan horizon]

is this helpful? the video

[agile magnet]

A Hamilton cycle is a cycle where you visit every node exactly once

The degree sequence is saying that there are 6 nodes of degree 1 and 2 nodes of degree 3

[grizzled storm]

It gives a visual description of the problem around 15min. It does not give the answer

[agile magnet]

So in a graph with that degree sequence, can we have a Hamilton cycle?

Why or why not? What have you tried?

[tidal kindle]

If you have 6 nodes of degree 1, how can they be connected? If the graph is not connected, its not a Hamiltonian cycle, right?

[agile magnet]

They can be connected

Uh for example take a single central node and attach 6 nodes to it

In like a flower shape

Boom, 6 degree 1 nodes

You are on the right track though

Your intuition is right, just make the argument concrete

[tidal kindle]

Okay, let me think

[agile magnet]

Remember in cycles you can't use edges multiple times

Which you said earlier

[tidal kindle]

Like I dont know how to explain it with an argument, but as you see in the picture, they cant be connected because it would contain 2 nodes of degree 4, so there is no form of draw it

[brave rock]

There are no nodes of degree 4 in this image

Oh it would contain, ok

[tidal kindle]

Exactly, only if they would be connedted, but they are not, so it cant be a Hamiltonian cycle

[cerulean radish]

Btw that's not the only simple graph with the given degree sequence

[tidal kindle]

Thats why I think its not a good solution... 😕

[cerulean radish]

Hmmm

I think you can argue that there are not enough edges for the graph to ever be connected

Because it would require at least 7 edges

And by simple addition of the degrees we clearly have only 6

[tidal kindle]

How did you arrive to 6 ? Sum of the degrees/ 2 ?

[cerulean radish]

Yes

[tidal kindle]

Thanks @cerulean radish @agile magnet

[dire stag]

I do not understand this

Each one has 16 different combinations

But where do I go from there?

How do I know when someone chooses at least 6 of the same type?

[agile magnet]

Do you know what the pigeonhole principle is?

[dire stag]

Yes, I have the notes in front of me, but there is nothing in them

[agile magnet]

wdym nothing in them

[dire stag]

Worthless

I do what it tells me, and yet it's still incorrect.

64 x 5 + 1

Each type is filled up 5 times, the next one ( + 1) has to end up in one of the 4 groups

So the answer should be 321

[agile magnet]

how did you get 64 * 5 + 1?

[dire stag]

Each group has 16 combinations

2 ^4

[agile magnet]

this is correct

there aren't 64 types though

[dire stag]

16 + 16 + 16 + 16 = 64

[agile magnet]

what is the definition of type?

in this question

I agree that each type has 16 combinations but there aren't 16 types

[dire stag]

0XXXX0, 0XXXX1, 1XXXX0, 1XXXX1.The xs can be replaced by every combination, which would be 2^4

[agile magnet]

No, there are 4 types

each type has 16 strings in it

but there are only 4 types

In fact what you have computed here is how many strings do you have to select before you are guaranteed to get 6 of the same string

not 6 of the same type

[dire stag]

81?

[agile magnet]

how did you get 81

[dire stag]

(64 x 5) / 4 + 1

[agile magnet]

how did you get (64 x 5)/4?

what does that quantity represent?

[dire stag]

16 x 5 should also work

+1

[agile magnet]

that is equivalent to (64 x 5)/4 yes

but that doesn't answer my question

these values represent something in the problem

I want you to tell me what they represent

and how they give you the answer you want

[dire stag]

64 = total # of combinations

5 = it needs to be filled up 5 times

4 = divides by the # of types

1 = self explanatory

or in the case of 16 x 5 + 1

fill up one type 5 times, and the next time will be the 6th.

[agile magnet]

we want to find how many strings we need to select until we have 6 of the same type

how many types are there? it says in the question

[dire stag]

4

[agile magnet]

ok

so apply that to the pigeonhole principle

it's not 16 * 5 + 1

or 64 * 5 + 1

_ * 5 + 1 where _ is the number of types right?

because we just want to see how many we have of the same type right?

[dire stag]

is it 21

4 x 5 + 1 = 21

YES THANKS

[cloud zealot]

Hi I need help

Mgf1106
CRASH COURSE STYLE
module 2 please explain as much as possible
Section 3.1, Statements, Negations, & Quantified Statements-2
Section 3.2, Compound Statements & Connectives
Section 3.3, Truth Tables for Negations, Conjunctions, & Disjunctions
Section 3.4, Truth Tables for Conditional and Bi-Conditional-2
Section 3.5, Equivalent Statements, and Variations of Conditional Statements 2
Section 3.6, Negations of Conditional Statements and De Morgan's Laws
Section 3.7, Arguments and Truth Tables
Section 3.8, Arguments and Euler Diagrams

[brave rock]

You haven't asked a question.

[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/

[silent tree]

Ive opened a help channel so im not sure if i can post this here but ive re-arranged until the 5th option

and wanted some input on how to proceed

if i did the steps correctly

this is what i now have after thinking long and hard about it

[dire stag]

I have an idea of what needs to be done here, but where do I even begin?

[haughty garden]

Since two balls have the sum (5 + 125k) + (5 + 125m) = 10 + 125(k + m), then this is equivalent to finding the least number of selections from the set {0, ..., 16} such that you pick a pair of elements whose sum is equal to (2010 - 10)/125 = 16. Note that there are eight pairs (0, 16), (1, 15), ..., (7, 9). Picking one number in each pair and the 8 is the maximum number of selections that can't guarantee the existence of a pair of elements whose sum is 16, so...

[dire stag]

?

[haughty garden]

what part are you unsure about?

[dire stag]

17 is not the answer

[haughty garden]

uh

i didn't say that it was

[dire stag]

Picking one number in each pair (16) and the 8 (+1) is the maximum number of selections that can't guarantee the existence of a pair of elements whose sum is 16

[haughty garden]

there are 8 pairs

so you pick one number in each of the pairs

giving you 8 elements, and the extra 8

this is the maximum number of elements that can't guarantee that you have a pair of elements whose sum is 16

picking 1 more integer guarantees that at least one of the eight pairs will have both integers in its pair chosen

[dire stag]

so 9 then?

That's not one of the provided answers

I don't understand this either

Over 2 hours in, and I still don't understand