ever heard of stars and bars?
#discrete-math
stray reef
i mean let's put it this way, how else would you even solve a problem like this
weary tiger
would you mind explaining a tl;dr of the stars and bars and why it works?
stray reef
do you want the general case or this particular problem
weary tiger
general case would be ok
stray reef
okay general case it is
so the problem we're dealing with is the following
put n indistinct objects into k distinct boxes, with no restrictions on box capacity or nonemptiness
count the number of ways to do that
does that make sense
does the problem statement make sense
weary tiger
yes
stray reef
okay great
so the basic idea is that there is a bijection between the set of all such arrangements of objects in boxes and - this is the part you seem to be struggling with - the set of all arrangements in a row of your n objects ("stars") and k-1 separators ("bars"), which are considered indistinct from one another and distinct from the stars, and are put on equal footing with the stars as far as arrangements go
weary tiger
so what do you do with those separators
stray reef
these separators structure the arrangement as follows
contents of box 1
separator 1
contents of box 2
separator 2
...
separator k-2
contents of box k-1
separator k-1
contents of box k
stray reef
the boxes here are abstract. in your particular problem, the boxes are represented by the three friends
stray reef
inside the box = given to the friend
stray reef
do you understand the structure i wrote up there
weary tiger
yeah, you just have a separator between each box but not "outside" the line of boxes
stray reef
,,, i mean yeah
oh and there's an important point i want to make
some of the "content" parts may be empty
which corresponds to two or more separators right next to each other
weary tiger
okay
stray reef
yeah so the number of arrangements of objects and separators is binom(n+k-1, k-1)
that's p much it
stray reef
yes
stray reef
yw
twin blaze
anybody knows what <S,L> <R,R> and all the alike stand for in this turing machine?
weary tiger
Are those the tape states?
Didn't a Turing Machine need states and a tape? The vertices are the states, I think, but it also needs a "tape", so is that what this notation means with the brackets?
twin blaze
I'm not sure
a, Z_0/Z_0, <S,R>
a is the input
Z_0 before the / is what's read from the stack
Z_0 after the / is what's written on the stack
but I don't know what <S,R> is
@weary tiger
weary tiger
I know Turning Machines, but I don't remember this notation.
twin blaze
it's supposed to be a machine that recognises languages L = {a^n b^n c^n | n > 0 } if that helps
weary tiger
Some authors might use custom notation. Did the author introduce their notation somehwere?
twin blaze
no
twin blaze
R L S might be right left stay I think
but I don't quite get what they mean in the context of the machine I sent before
hardy viper
I'd guess right left and stop but it's not english
weary tiger
start, left, right?
twin blaze
it's right left stay
weary tiger
Oh, stop is better.
Yes, stop, not start.
Because you want a stopping state when the string is accepted.
twin blaze
mmhh no I think it's right left stay
weary tiger
Oh, adding left to the string, right of the string, in order to balance it.
twin blaze
the stopping state is q_f
weary tiger
because you are producing a balanced language/string
That's sort of what you would have to do with EBNF, too.
twin blaze
it's not a translator it's just an interpeter
twin blaze
yes
weary tiger
It implements sort of a counter, in order to keep the symbols balanced.
The S,R,L symbols do that somehow, but I am still a bit unsure how precisely they use them, too.
twin blaze
sure
the counter itself is M I think
S R L refer to the tapes and how they are moved
weary tiger
q_f seems to be some kind of double stop, terminal.
twin blaze
but I don't get why there are 2 tapes
q_f is the accepting state
if the string doesn't reach q_f then it doesn't belong in the language L
weary tiger
Yes, if it doesn't reach q_f it's not in L.
I think the <...> are the tape states.
The tape states keep track whether one has to add more to the left or the right.
It basically keeps score of the balance left and right, which corresponds to the a's and c's, I think.
weary tiger
Tapes? THere's just one, right?
I think you are too much of a math person and might misinterpret the notation.
It might not be a tuple.
twin blaze
oh
weary tiger
It's unusual notation, so I think that threw both of us off, but we are making it more complicated than it has to be, maybe.
I would have written [a_0,a_1,a_2,...,a_n]. Maybe that's what it means.
For the tape.
twin blaze
wait
weary tiger
I would compare this to some other author. This string balancing/parsing is very common. If you see it in another notation, it might make it easier. It's also a common question for BNF grammars, which someone just asked about in another channel.
twin blaze
I think the first one is the stack tape
the second one the input tape
a, Z_0 / Z_0 <S,R>
weary tiger
Oh ... let me think.
weary tiger
Oh, that would make sense. The stack is keeping track then of the degree of imbalance.
twin blaze
a, _ / M, <R,R>
reads a so input moves right
reads nothing from stack and writes M so stack tape moves right
b, _ / _ , <S,L>
weary tiger
The way you explain it makes sense, on first glance.
weary tiger
The "read head" you mean?
twin blaze
yes
twin blaze
wait
in turing machine explanation it says that stack and input tape can move left, right and stay
so input tape could move left
weary tiger
twin blaze
but I don't get why you would move it left
like, you'd just go back one place, wouldn't you?
ok let's try this practically
string in consideration: aabbcc
weary tiger
That's a good idea.
weary tiger
Oh, I think I just solved the notational question: https://courses.engr.illinois.edu/cs373/sp2013/Lectures/lec19.pdf
twin blaze
reads b:
INPUT: abbcc
STACK: Z_0 M
reads a:
INPUT: bbcc
STACK: Z_0 M M
and it would loop here forever adding Ms to the stack
weary tiger
It actually looks like two stacks.
twin blaze
which is the 2nd stack tho?
weary tiger
It pushes a STOP symbol on top of the stack, then counts the number of a's, then reads b's, then c's, but in order to transition to the next stage, the STOP symbol has to be reached.
It is sort of how you would count with a stack or go through a tree.
Or how you balance parantheses. You push a "guard" or stop symbol (equivalent with an empty stack) and then pile all the symbols on top.
If you can pop off as many symbols for one token as you pop on for another token, you reach the STOP token, you know you are balanced, and can "pass" to the next stage.
twin blaze
so how would the iteration for the string aabbcc look like?
weary tiger
Hmm ... let me see ...
You get to q1 where you pile all the a's on top.
On the bottom of the stop you have your (first) S.
Then, when you start reading b's, you put another S on the stack, sort of like you keep a bookmark.
weary tiger
But is that important? Aren't those just dummies? It's just about which strings get you to the terminal state.
As long as they are balanced, you may "pass".
twin blaze
also wait
weary tiger
You basically have a stack of cards and at two positions you have an "S card". If you can take as many cards from the pile as you put on, and be at the "S card", you know you counted the same.
weary tiger
The first of the tuple is what gets on the stack, the second is what's done with the read head, no?
Some of the symbols seem kind of overloaded semantically.
weary tiger
Oh. I might have gotten it wrong then.
twin blaze
it looped on the second state indefinitely
weary tiger
q_1 is sort of a state that counts a's.
q_1 -> q_2 gets the machine into the next "stage", and it starts counting b's.
Then, it goes from q_2 -> q_3 when it starts to encounter c's to count those.
twin blaze
but why would the input head would move left?
weary tiger
And it knows it was balanced if it sees a STOP symbol after as many tokens of one symbol as in a previous stage.
Then, it's all "empty" <S,S>, i.e. nothing to read and nothing to pop off the stack, and it can terminate.
twin blaze
I dont get it
no I don't think it's like that at all
I will try to understand if I get it I'll tag you
weary tiger
Oh, okay. Sorry if I added confusion.
twin blaze
ok
I got it I think
<... , ...> represents the positions of the two tapes
first one is input tape
second one is stack tape
L = left
R = right
S = stay (not stop)
string in consideration: aabbcc
input tape: a (CURRENT) | a | b | b | c | c
stack tape: Z_0 (CURRENT) |
starts in q0
a is read from input
Z_0 is read from stack
Z_0 is written to stack
input tape stays
stack tape moves right
input tape: a (CURRENT) | a | b | b | c | c
stack tape: Z_0 | _ (CURRENT)
now in q1
a is read from input
nothing is read from stack
M is written to stack
input tape moves right
stack tape moves right
input tape: a | a (CURRENT) | b | b | c | c
stack tape: Z_0 | M | _ (CURRENT)
still in q1
a is read from input
nothing is read from stack
M is written to stack
input tape moves right
stack tape moves right
input tape: a | a | b (CURRENT) | b | c | c
stack tape: Z_0 | M | M | _ (CURRENT)
still in q1
b is read from input
nothing is read from stack
nothing is written to stack
input tape stays
stack tape moves left
input tape: a | a | b (CURRENT) | b | c | c
stack tape: Z_0 | M | M (CURRENT)
now in q2
b is read from input
M is read from stack
M is written to stack
input tape moves right
stack tape moves left
well... you get the hang of it lol
@weary tiger
basically
once it starts reading b's
if it encounters a c and Z_0 is not the current position of the tape, it means that number of b ≠ number of a
so it gets stuck in q2
otherwise it goes in q3
and once in q3, it starts from Z_0 and starts moving along the stack tape
if it reaches the end of input (_) and the stack tape doesn't point to a void cell as well, it means that number of c ≠ number of a's and b's
weary tiger
Reading ... hold on.
Just came back from the kitchen.
But where does the STOP symbol factor in?
It seems like it's a central piece, as it functions as a sort of "bookmark" on the stack, no?
Oh, you call it "void" it seems.
Yes, it seems like we're on the same page. I guess we just used different terminology to describe the same process.
Oh, and you call it "stay"? Hmm ...
Right, I think I might have mixed up the symbols. It's _ / _ (underline) that stands for the "void" states, not the S.
empty forum
Ignore the top bit where it says theorem:
Anyone know how to approach this? I’m not really getting it.
gleaming zephyr
whats a contrapositive/
sleek swallow
They've asked you to prove that it holds through contraposition @empty forum
So, the assertion is $2a \notin \bQ \implies a \notin \bQ$. So, the contrapositive of that is $a \in \bQ \implies 2a \in \bQ$.
vital dewBOT
Abhijeet Vats:
sleek swallow
-.- I don't like to be kept waiting, isaiahd. Please, at the very least, respond so that I know that you're done struggling with the problem.
empty forum
@sleek swallow sorry. I don’t use discord super often. I didnt think you’d help me in less than 10 minutes.
sleek swallow
No worries
empty forum
While I get that is the contrapositive. Do you know how to prove?
sleek swallow
Well, you know that $a \in \bQ$. What can you do with that?
vital dewBOT
Abhijeet Vats:
stray reef
@empty forum can you prove that 2 times a rational number is again rational
empty forum
Yeah
stray reef
then what's the problem
if you can prove a ∈ Q => 2a ∈ Q then why ask
wouldn't you be done then
empty forum
I wanted to see if there were extra steps to showing work
The way my professor does it is kind of long
And makes it look more complicated
stray reef
can you show the way your prof does it
empty forum
Yea
Like all the necessary steps for full credit.
This isn’t for the same problem by the way.
stray reef
i mean duh ofc it's not for the same problem
empty forum
Let me try to find the problem he’s referencing
stray reef
are you allowed to directly use the fact that Q is closed under multiplication
empty forum
It’s in my text
stray reef
actually here
let me be
as verbose as i can possibly go
you're asked to prove "if 2a is irrational then a is irrational"
PROOF (BY CONTRAPOSITIVE):
assume a is rational.
then there exist integers m, n such that n != 0 and a = m/n.
then 2a = 2 * m/n = (2m)/n.
since 2 is an integer and m is an integer, and the integers are closed under multiplication, 2m is also an integer.
since 2m is an integer, n is an integer and n != 0, (2m)/n is a rational number.
2a = (2m)/n, therefore 2a is rational.
is that the kind of proof your prof wants
empty forum
Wow
This is really thorough thank you
yes
basically we would look at the problem
and we have the given, which is the intended result. but we have to prove by contrapositive.
this was the problem he referenced btw.
by any chance do you have a resource that helped you understand this
he only uses our textbook for questions. he doesn't teach how to solve by whats written (in our text)
sleek swallow
What's the textbook ya'll are using?
stray reef
by any chance do you have a resource that helped you understand this
unfortunately i don't think i do
empty forum
that's fine. I think I'll look to youtube for more info. But thank you very much for the solution.
we just got intro'd to this
and i had bombed the last quiz so im buckling down so to speak.
sleek swallow
If you're just doing a proof class, then How to Prove It by Velleman is a common suggestion. The one I used is Fundamentals of Mathematics by Bernd Schroder
empty forum
It covers a lot of stuff. It’s a discrete structures course.
I’ll look into that tho
we don't do any actual coding in the class all of its been math
and logic
this is whats next
and i dont like the sound of recursions
weary tiger
Could someone point out my mistake please ?
I'm trying to solve the recurrence c(0) = 1, c(n) = c(n-1) + n + 2
The answer is: c(n) = (n^2)/2 + (5n)/2 + 1
weary tiger
It's called the iterative method, for solving recurrences
sleek swallow
Okay but you haven't actually derived the result
Like, you need to derive a result
Also, your approach doesn't work because the $c(n-1) \neq c(n-2)+n+2$
vital dewBOT
Abhijeet Vats:
weary tiger
Is it c(n-1) = c(n-2) + n + 2 + n + 2 ?
sleek swallow
$c(n-1) = c(n-2) + (n-1)+2$
vital dewBOT
Abhijeet Vats:
sleek swallow
So:
$c(n) = c(n-1)+(n+2)$
$c(n) = c(n-2)+(n+2)+[(n-1)+2]$
$c(n) = c(n-3)+(n+2)+[(n-1)+2]+[(n-2)+2]$
So, a pattern is emerging. We can see that:
$c(n) = c(0) + 2n + [n+(n-1)+(n-2)+.........+1]$
$c(n) = 1 + 2n + \frac{n(n+1)}{2}$
$c(n) = \frac{n^2}{2} + \frac{5n}{2}+1$
vital dewBOT
Abhijeet Vats:
weary tiger
Awesome! Thanks man
sleek swallow
You're welcome.
sleek swallow
From the (n+2)
elder oak
When it snows i don't go out. It snows. Therefore i don't go out.
is my though correct?
Snows -> ~go out
Snows
:. ~go out
modus tollens
anyone knows?
lyric pumice
That is modus ponens.
chrome ember
ayo
How would you go abou doing this?
i tried multiplying the nubers and adding sample numbers buti keep getting the ratio fked up
<@&286206848099549185>
delicate ridge
That... isn't discrete maths friend
Or university tbf
But substitute k' = 9k and m' = 4m into the first equation, then divide the new T by the old T and simplify
@chrome ember
chrome ember
oog
weary tiger
Hi can someone help me clarify one thing in conditional probabiltiy? I think notes I have are scuffed: I want to calculate conditional probabiltiy of this event: There are 3 white balls and 2 black ones. You pick one with returning it back. If you pick black first you put 2 more black balls to the box, same with when picked white first. Whats the probability that we get white ball on our 2nd try on condition that we picked white on first try?
I thought its (3/5 * 5/7)/(3/5) but notes say its (2/7 * 4/7) / (2/7)
weary tiger
maybe switched black with white
weary tiger
yo ok so we put 10 girls and 3 boys in the circle - whats the probability of boys not sitting next to each other? I think its $\frac{9! \cdot \binom{10}3 \cdot 3!}{12!}$
vital dewBOT
Godel:
weary tiger
would that be right?
we pick girls first, then 3 spots between the girls and 3! for permutations all over 12! possible seatings
near prawn
looks good
elder oak
A survey among graduates found that:
Students who graduated in 4 years, regularly attended lectures
and read systematically, or followed the standard curriculum.
Lena did not follow the standard program but graduated in 4 years .
Convert the above suggestions into categorical accounting and prove by export rules
Conclusions that Lena regularly attended classes and read regularly.
Use it as a field for defining the variables that will be defined by all students.
At each step of your proof, indicate which rule of conclusion you use.
Is the categorical logic for this
- P(x) -> (Q(x)^D(x)) v A(X))
2)-A(Lena) ^ P(Lena)
where
P(x)= x graduated in 4 years
Q(x)=regularly attented lectures
D(x)=x read systematicallya
A(x)=x followed the standard curriculum
weary tiger
Would the iterative method be a good way to solve this:
$a(n) = 3a(n-2) - 2a(n-1)$
vital dewBOT
total_sleezeball:
river reef
HELP HELP I has question
so
I got this an equation in this format
f(n+1) = a*f(n)+ b
wolfram alpha comes up with
where c1 is an arbritary parameter
so...where the hell does that come up?
can I resolve it with some initial value?
hardy viper
yea you can specify c1 and b with two initial values
that second term looks like a geometric progression like 1+a+a^2+...
I get this?
river reef
OK so i can give the intial value of
0,10?
The equation is the format of the calculation of Champion points
in elder scrolls online
I am attemtping to get the decceeleration in point gain given an initial value of 0 xp and 10 champions points
Tho I don't know if I should integrate first
but that would still leave the c
fuck math
robust mango
i see
weary tiger
trying to solve this recurrence relation, am I going about it right ?
a(0) = 1 and a(1) = 0
a(n) = 3a(n-2) - 2a(n-1)
soft thorn
What about it
sleek swallow
@woeful galleon $p \implies q \iff \lnot{q} \implies \lnot{p}$
vital dewBOT
Abhijeet Vats:
sleek swallow
So then, use modus ponens to conclude $\lnot{p}$
vital dewBOT
Abhijeet Vats:
sleek swallow
@weary tiger still need help?
woeful galleon
i got it ty
what about this one
i dont get the a/b part
where is that 0 and 1 coming from
stray reef
[0,1) is the interval consisting of all points between 0 and 1, including 0 but not including 1
another way to say what they said would be $0 \leq \frac ab < 1$
vital dewBOT
Ann:
woeful galleon
ah aight, what about this (pretty similar)
"we thus have" how do we thus have that
stray reef
needs more context
woeful galleon
that is all i got
this helps ?
but in terms of the exercise that is all i have
stray reef
theorem 12.3 is false as stated.
they should've said r ∈ {0, 1, ..., b-1}
anyway what they're saying is that 2 is the biggest integer ≤ 8/3 and so that's the quotient in the division of 8 by 3
woeful galleon
oh like 2 * 3 = 6 so good but 3*3 = 9 so bad, so q=2
stray reef
meh i guess if you wanna look at it like that go ahead
woeful galleon
sorry to be a pain in the ass lol
been studying for a while now. i am missing how that implies that step. anyone can enlighten me ?
stray reef
(13.5) and (13.6) are the definitions of y1 and y2 respectively being inverses of x mod m
stray reef
they're both 1 mod m
or do you dispute the fact that the relation of equivalence mod m is transitive
woeful galleon
yea so xy1 and xy2 are both 1mod m and i agree with that. that is 13.5 and 13.6
but now on 13.7 u are saying that xy1 (alone) = xy2 mod m ? how is this happening ? what rule are we using here. can u give me an example with real numbers ?
stray reef
do you agree that if a == b mod m and b == c mod m then a == c mod m
== for that equivalence sign
woeful galleon
i mean, i know u are right with that equality but as of right now i will say no because i dont know
(what rule is that lol)
woeful galleon
alright, i agree with that
do you agree that if a == b mod m and b == c mod m then a == c mod m
@stray reef
woeful galleon
i am assuming that 1 == xy2 mod m = xy2 == 1 mod m ?
stray reef
equivalence mod m is, as the name suggests, an equivalence relation
and so in addition to being transitive it is also symmetric
woeful galleon
so for my own sake a==b mod m = b==a mod m, correct ?
stray reef
i would be careful to put an equals sign between these
but yes those are the same thing
woeful galleon
alright, moving on xD what s next
oh
then just the transitive property
and we get xy1 ≡ xy2 mod m
13.8 ?
stray reef
xy1 - xy2 is straight up EQUAL to x(y1-y2)
but also like
do you actually know nothing about the relation $\equiv \pmod{m}$
vital dewBOT
Ann:
woeful galleon
u hit me hard with the rudeness lmao xD
there is a reason why i am here lol
so to answer your question. i got pretty much no clue in terms of properties of mod
stray reef
shouldn't your text have something on it though
like
surely
it just seems baffling to me that it wouldn't
woeful galleon
sure, it has 3 examples and the one u saw is one of them
stray reef
no like does the text you're reading not go over the definition of equivalence mod m and its properties
woeful galleon
can i get a book off of the internet and do it that way ? sure i can. and i did. am i still gonna come here.. yes i will
lol
we aint got an "assigned" book
stray reef
did i say assigned
no i did not
i am talking about the text you're reading
the one you're sending me screenshots from
given that you're seemingly at chapter 13 therein
shouldn't there be SOMETHING in there in the preceding chapters about mod
woeful galleon
i am pretty sure i answered your question. now, i appreciate the help but why the rudeness here ?
did i say assigned
no i did not
i have a def and that example. that is all i got
weary tiger
@stray reef don't be a wanker
stray reef
a what
weary tiger
A WANKER
stray reef
a what
woeful galleon
a contemptible person (used as a general term of abuse).
woeful galleon
i was just asking for help mate. idk why you acting like this
weary tiger
@stray reef was never a beginner, obviously
woeful galleon
I wish i was born all knowing. i wouldnt be in school lol
weary tiger
@weary tiger still need help?
@sleek swallow yup! if you have a minute
sleek swallow
i have exactly one minute
So i'm gonna say that you should look at your recurrence relation:
$a_n = 3a_{n-2}-2a_{n-1}$
$a_n -a_{n-1} = 3a_{n-2}-3a_{n-1} = -3(a_{n-1}-a_{n-2})$
So, you could use the fact that the differences between the terms follow a geometric progression. This might lead you to a way to solve the problem.
vital dewBOT
Abhijeet Vats:
elder oak
Students who graduated in 4 years regularly attended lectures
and read systematically, or followed the standard curriculum.
Lena did not follow the standard program but graduated in 4 years .
is this
Graduated -> ( Attended ^ read) v program)
-program ^Graduated
near prawn
what
plugged in where?
why?
u want to show that x_k+1 <4
given that x_k<4
which is exactly what they did
stray reef
do you agree that we KNOW $x_k < 4$ and we WANT to get $x_{k+1} < 4$
vital dewBOT
Ann:
weary tiger
@sleek swallow turns out I was missing some theory and iterative method is not right for that problem
weary tiger
Hi, this is in the context of showing that 2x is O(x^2)
Why did my professor go from "2x <= Cx^2" to "2x < ..."
What happened to "smaller than or equal to"
Is it just because if C = 1 then 2x can never be equal to x^2 ?
weary tiger
I see, so he really did just drop the equality
Why is he assuming C=1 ?
Should I always try with C=1?
faint narwhal
for the functions you work with, it doesn't really matter what you pick C to be
because youll always find some M such that if x >= M, then the inequality works
weary tiger
Right
By bad did you mean the steps are bad or the result is bad
Or just that my comprehension is lacking in a major way? Lol
faint narwhal
idk, just the way its written and stuff isn't the best
the way your professor wrote it
weary tiger
Ok that's on me, I tried to write the steps he wrote on the corner of my paper in Latex to make it clearer for you guys
weary tiger
Thx
solemn root
most likely the domain is restricted
yeah so it's just f, but only applied on A1
ignoring {2, 4}
no?
because f(1) = f(5)
little tide
pearl jewel
stray reef
@iron crescent there is but it's a bit convoluted
i can give you a somewhat clunky formula, or attempt to describe the method i'm thinking of in words
yeah no i'm gonna describe it in words
so say you have a function f: X -> Y with X and Y both finite and you want to count the subsets of A on which f restricts to a one-to-one function
do i have your undivided attention here @iron crescent
yeah so alright
so the first thing to do is to partition X into subsets based on which inputs map to the same output.
that is, for every y in the range of X, there is a corresponding subset of X consisting of all x such that f(x)=y
these subsets are pairwise disjoint and their union is all of X
in your particular problem, this construction would partition your domain into {1,5}, {2} and {3,4}
do you understand what i'm describing so far
what do you mean by "for 3"
what do you mean
what do you mean by "for (3, Saturn)"
a subset here need not consist of 2 elements only.
if you try to construct your subset element by element like this you run into a lot of things that are hard to account for
i'm trying to illustrate to you a general construction to shed light on a general method
that works on any function
and as such i ask: does what i described up there make sense to you?
alright great
so suppose we now have this partition, whose sets i will label X_1, X_2, ..., X_m
now the key thing to notice is that every set $A$ for which $f|_A$ is one-to-one is characterized by the property $|A \cap X_k| \leq 1$ for $k = 1, 2, \dots, m$.
vital dewBOT
Ann:
stray reef
in other words
for every set in our partition, A can include at most one point from it
yes
this now lets us write down the count we are looking for
$N = \prod_{k=1}^m (|X_k| + 1)$
vital dewBOT
Ann:
stray reef
no
(2+1)(2+1)(1+1)
the product and +1 in the formula are bc we're doing this choice independently for each X_k, and at every stage our options number one more than the elements of X_k
yes
oh and subtract 1 from the whole thing if you don't want to count the case $A = \rien$
vital dewBOT
Ann:
stray reef
though on the other hand the empty function is vacuously one to one so maybe not
an extension of g to A is a function on A whose restriction to A_2 is g
f is one of these definitionally
uh
i think you've got that wrong
the phrasing is "extension of <function> to <domain>"
really what they are saying is
how many functions from A to B are there whose restrictions to A_2 are g
stray reef
how many functions f:A->B are there such that f(1) = mercury and f(2) = mars
near prawn
analog sonnet
Well, there are 3 input values which you can map to 8 output values of your choosing
glossy pollen
Let G be a k-regular graph of even order that remains connected when any (k-2) edges are deleted. Prove that G has a 1-factor.
anyone have any ideas about this one. the book points to tutte's condition as a hint, which is fine and dandy, but i dont know how to set it up so that the condition is useful
weary tiger
Can someone give me useful denials of "one-to-one" and "onto".
stray reef
useful what
pale epoch
what you have is correct
can you find examples of onto functions for both a) and b), that might help you find a method to generate them
what do you think
what does that mean
ok, i know what you mean (i think)
it's just badly formulated
and yeah, that prevents the existence from a function A -> B that is onto
try to generate a few function that are onto
and some that are not
see what must be true
you could also try to find the number of functions that are not onto
because you know the number of total functions
that makes no sense
onto and one-to-one are not opposites of each other
weary tiger
How can 2 functions be big O of one another
If being big O means it will grow faster than another function
Big theta
pale epoch
thats not what big O means
@iron crescent that was a bad hint, calculating the number of onto function is easier
just think about how many choices you have for the image of the first, second, ... element
while making sure that the function is onto
sleek swallow
In that case, it'd be 4^6 and it still wouldn't make sense. Consider the function f = {(1,1),(2,1),(3,1),(4,1),(5,1),(6,1)}
That would be counted in there
pale epoch
hm, actually i find no "easy" way to answer this question
sleek swallow
You need to make sure that $\forall a \in A: \exists b \in B: (b,a) \in f$, where $f:B \to A$ is your function.
In other words, you need to distribute 4 elements across the 6 elements in B. Once you've chosen 4 elements in B to distribute them to, you can then focus on the remaining two elements in B.
vital dewBOT
Abhijeet Vats:
sleek swallow
Might want to break it up into parts in that case.
pale epoch
@iron crescent i mean this immediately gives you the solution
if you're able to calculate stirling numbers
which you probably are not
and i'm going to assume you didn't cover stirling numbers in class
and just googled for a solution
ok, then what is the problem
sleek swallow
It seems strange that you've covered them but you didn't think to use them before.
pale epoch
we use them when we want to partition a set
do you know what a partition is
if you partition your B into 4 non-empty subsets that gives you a surjection
go read your notes and think about why this is true
i know what a partition is, but i have my doubts you do
do your notes not have examples
no
sleek swallow
Read the definition again.
Work through it slowly, you're rushing through it. It does not talk about power sets at all.
pale epoch
with restrictions
woeful galleon
Hey boiz. sorry i am back lol. i got a little smarter so i can hopefully catch this shit a little better. can anyone help with this ?
weary tiger
which one?
woeful galleon
(all ultimately) but the first one rn. i still struggle with proofs 😄
woeful galleon
well, so far i tried to get some basic def down and think what method to use. (even odd defs), i found an example in my notes but it aint quite the same. it was proved with contrapositives
weary tiger
ok
so this question is just a weird of saying, prove every odd number is of the form 2k - 1
like with x = 5, we have k = 3
and I guess the definition your professor gave was, every odd number is of the form 2h + 1
as opposed to -1
woeful galleon
yes ^
sleek swallow
Let x be odd. Then, there exists an integer h such that x = 2h+1. Let h = k-1. Then, x = 2(k-1)+1 = 2k-1. That proves the backwards conditional.
Now, let x = 2k-1. So, you agree that x = 2k+2-1 = 2(k+1)-1. Let h = k+1. Then, x = 2h+1. Since h is an integer, by virtue of k being an integer, you've shown that x is odd.
That proves the result.
sleek swallow
They're learning proofs. I'd rather give one completely solved example so they can work off of that.
weary tiger
let him figure it out
woeful galleon
i still wanna know how, dont worry
sleek swallow
Okay anyways, have a look at what I've written above. Read every sentence carefully. Then, extend it to your other proofs.
Like I said, one worked example is going to be helpful in you understanding how to do the others.
woeful galleon
if we are proving that x = 2k -1 why in ur proof you say that x = 2h + 1 ? your let h = K-1 is gathered from ? it makes sense mathematically but i dont see it yet
Let x be odd. Then, there exists an integer h such that x = 2h+1. Let h = k-1. Then, x = 2(k-1)+1 = 2k-1. That proves the backwards conditional. referring to this
orchid pawn
because your definition of a odd number is 2h+1
sleek swallow
Precisely.
Then, I can pick h to be anything I want it to be and I chose something convenient.
orchid pawn
so to show that if x is an odd number, then it can be represented as 2k-1, you must begin from the fact that x can be written as 2h+1 simply because that is how you've defined an odd number
woeful galleon
okay, so no one is stopping me from choosing h = 1 ? at this point using the given def as long as we "play" with integers i can choose h to be anything ? (in this case k-1 because it makes things easy
orchid pawn
h=1 results in losing generality, so no, you can't take that as part of the proof
woeful galleon
that was the first # i clicked on lol. but just because it fails to prove something doesnt mean i cant choose it. not sure if what i am saying makes sense
orchid pawn
no I don't mean it like that
orchid pawn
you can choose h as a function of another general variable
sleek swallow
It just doesn't prove anything
orchid pawn
if you took h=1, you'd be proving it for a specific number
and not all odd numbers in general
woeful galleon
i am just talking of the freedom that i have in choosing it. choosing the RIGHT one is up to me but no one is stopping me from choosing random shit
sleek swallow
Yes
woeful galleon
aight cool (stupid questions but i wanna understand 100%)
sleek swallow
Not stupid questions.
Continue asking more questions if you're confused.
The whole reason why I gave you the solution is for you to fully study it and learn from it as much as possible.
woeful galleon
well, lets keep it rolling then. what exactly did i prove with this ?
u said backwards conditional
sleek swallow
Okay, so you proved that if x is odd, then x = 2k-1
That's what I meant by backwards conditional
sleek swallow
Now, the next step was to prove the forward conditional
orchid pawn
a iff b means if a then b as well as if b then a
sleek swallow
So, you assume that x = 2k-1 for some integer k. Then, you show that x is odd.
Also, hai flynn ❤️
orchid pawn
heyo
woeful galleon
i am looking at the second let you got
we choose h = k+1 this time
and we already know that x=2h+1 because it was given in the hint
and like u said we know that h is an int
and K is an int too
how the flip that does that yield x is odd? all the math makes sense. what am i missing
sleek swallow
woeful galleon
what did i say lmao
sleek swallow
You don't know if x = 2h+1. That's exactly what you're trying to prove.
So, you need to pick your integer h carefully.
If you begin with x = 2k-1 for some integer k, then x = 2k-2+1 = 2(k-1)+1. Since k-1 is an integer, we'll just use that as our choice for h and conclude that x = 2h+1 for some integer h. That proves that x is odd
sleek swallow
I apologize, that was a mistake i made then
@woeful galleon the argument i just gave makes more sense
The idea is the same, in the sense that your choice of h is going to depend on k and you can prove the result by choosing the correct h.
woeful galleon
aight cool. i was just a little confused cuz they were diff
sleek swallow
Yeap
glossy pollen
Let G be a k-regular graph of even order that remains connected when any (k-2) edges are deleted. Prove that G has a 1-factor.
Anyone got any ideas for how to go about this?
tranquil jewel
would the domain of g just be the red, and the range be the blue
faint narwhal
the domain is that yes
but codomain is Z
the range has a slightly different meaning
tranquil jewel
alrighty, for (b) tho is there any easy way to calculate the total elements?
besides like writing them all down and counting like the empty set, 1,2,3,4, etc with all the combinations
or is that just 6?
tranquil jewel
Whats the way to calculate that then?, I was thinking factorial but seems too big
pale epoch
consider an arbitrary subset of A
for each element in A you have 2 choices
include it or not
pale epoch
no
tranquil jewel
+2?
tranquil jewel
Ye
pale epoch
then each subset of A can be identified by a binary string of length 6
so like 000000 is the empty set
111111 is the set A
tranquil jewel
uh
pale epoch
101001 is the set {1, 3, 6}
pale epoch
i mean it's just 6 symbols
tranquil jewel
ye
pale epoch
1 means "in the set", 0 means "not in the set"
tranquil jewel
would 26 be wrong?
tranquil jewel
can you keep explaining your way
I get the length part
but I don't get how you are gonna get all the combinations from it
pale epoch
the problem just becomes counting the binary strings of length 6
tranquil jewel
if we took a diff example not mine
can you explain how you would do it with just S = (1,2,3)
pale epoch
no
tranquil jewel
okay go on then with the {1}
pale epoch
what's the powerset of that?
tranquil jewel
the empty set and 1?
tranquil jewel
mhm
pale epoch
what's the powerset of {1, 2}?
tranquil jewel
4 elements empty,1,2,12
pale epoch
yeah
notice how all the elements of the powerset of {1} are also in the powerset of {1, 2}
tranquil jewel
yea
pale epoch
in fact, you can take any element in the powerset of {1} and create 2 elements of the powerset of {1, 2}
by either keeping it as is
or adding 2
{} becomes {} and {2} and {1} becomes {1} and {1, 2}
tranquil jewel
so for if there was 3 elements it would be 8?
pale epoch
so the number of elements in the powerset doubles
yes
the pattern continuous this way
tranquil jewel
so I'm just multiplying by 2 ah
so its just
2^n where n is the number of elements?
pale epoch
yes
tranquil jewel
so mine is just 64?
tranquil jewel
alright that makes sense, do I also need the domain to get the range?
pale epoch
eh, yes?
tranquil jewel
cause yea im confused on the range now since it wasn't what I had
I thought it was the blue
pale epoch
that is the codomain
the range is a subset of the codomain
the codomain are all elements the function is "allowed" to map to
the range is the set the function actually maps to
tranquil jewel
would it just be 1-6?
pale epoch
why
pale epoch
are you just guessing?
pale epoch
yes
tranquil jewel
and its the absolute value of x right
like if -1 was in there it wouldn't be in the range
right?
pale epoch
i don't know would it
tranquil jewel
one sec
pale epoch
e.g. why do you think 7 is not in the range
pale epoch
cardinality of what is 6
tranquil jewel
A
pale epoch
is A in the domain of g?
pale epoch
ok
tranquil jewel
the set A is
pale epoch
yes
tranquil jewel
in the P(A)
pale epoch
then maybe you should go study
tranquil jewel
okay wait lets go back to the range without my "guessing"
the two | | are cardinality tho?, I thought it was absolute value at first
azure lichen
they are
what sorta things could be used as “x” in that function?
it might be illustrative to explicitly write out a few possibilities
and what value the function takes
tranquil jewel
the sets from P(A)
azure lichen
e.g.?
tranquil jewel
Empty set, 1, 2, 3, 12, etc
azure lichen
12?
tranquil jewel
{1,2}
tranquil jewel
Its just a pain clicking the { key cause I rarely use it but yea they arent
azure lichen
and g({1,2}) is?
tranquil jewel
is?
azure lichen
g({1,2}) = ?
tranquil jewel
2
azure lichen
yep
tranquil jewel
so it just wants me to list the range of all the cardanalities
from the P(A) inputs, i.e. there will only be 1 through 6 as the range?
would 0 be included?
azure lichen
I can think of one set in P(A) that has a different cardinality than 1–6
tranquil jewel
0-6 for the empty set?
azure lichen
the empty set has cardinality 0, aye
tranquil jewel
okay thanks
tranquil jewel
Just wanna be sure for
(d) its not surjective since target set doesn't equal range
(e) It is injective
(f) It's not bijective cause its not both injective and surjective
or would it not be injective since {1,2} and {2,3} from P(A) both are cardinality of 2
sleek swallow
@tranquil jewel Yes, so g({1,2}) = g({2,3}) but the two sets are not equal to each other
So it can’t be injective
tranquil jewel
alr ye
SoS with (a)
would proving it doesn't work if x1 = x2 suffice for showing f is surjective
sleek swallow
?
You need to find a number in R that doesn’t have a pre-image in A
Also, there’s a grammatical error in part b) 😄
tranquil jewel
ah I actually meant (a) my bad, not surjective. injective instead dont I need to show it for general all cases?
sleek swallow
Yes. So let f(x) = f(y)
sleek swallow
Then show that x = y
tranquil jewel
wait, okay im confused so I let them equal and I was simplifications but when I let x = y I got 3 = 1 which is not true
sleek swallow
Yea
tranquil jewel
so do I just manipulate that so if I do x is not equal to y it gives a contradiction?
oh wait
hold on
sleek swallow
You’re supposed to prove that f is injective. So, the question of them not being equal doesn’t come into play
sleek swallow
Yea that’s fine.
So you’ve proven injectivity
Now go ahead and do the other parts
tranquil jewel
skipping b for a moment, for the range is it just every real number that isn't x = 1/3
sleek swallow
??
Consider the real values of f(x) where f(x) is undefined or is asymptotic to. What are they?
sleek swallow
Yes, range(f) does not involve the values of x
Look up the definition of the range(f)
tranquil jewel
ye but like in this case "x" is just a variable it can just be z or something its still in the range isn't it
I’m trying to work from this to get the range
sleek swallow
No! You have to be more precise. range(f) = f(A) is the set of all values that f(x) can take. f(x) is asymptotic to 1/3. So there isn’t a value of x that gives the output f(x) = 1/3
sleek swallow
That’s precisely why f isn’t surjective. There exists a value in R which does not have a pre-image in A
tranquil jewel
or am I reading that completely wrong
sleek swallow
You are reading it completely wrong
Go and read up on what the range/image set of a function is
tranquil jewel
so I get what the target set is and the surjective defn but like, I'm confused how to write out the range
I get that the range is taking the function x/3x-1 and then using the A function as inputs where x cannot = 1/3
sleek swallow
$range(f) = {y \in R: \exists x \in A: (x,y) \in f }$
In words, you’re looking for all the values that f can take on.
vital dewBOT
Abhijeet Vats:
sleek swallow
So if you take any f(x) and tell me it’s in the range(f), that means that I should be able to find an x in A for which that is true
tranquil jewel
but there isn't an x in A that makes it true?
sleek swallow
Precisely. If you let y= 1/3, then there isn’t an x such that f(x) = 1/3
Now, try finding other real numbers that aren’t in range(f).
Assuming they exist, of course
tranquil jewel
would the negative not be in the range?
of 1/3
or none other exist cause x cannot equal 1/3 was the only restriction
sleek swallow
?
What you’re saying really doesn’t make sense
I suggest that you go back to the definitions and work through them again first
tranquil jewel
alr
naive saffron
lmao hi tabrizchiq
fossil pewter
In question 91 what would be the approach if all the n^2 balls were different
spiral cradle
can someone help me understand this better?
How would I know to use -3S?
and not anything else
faint narwhal
because your sequence is growing by 3 times
spiral cradle
Ok, I get that it's growing by 3x, but why minus?
faint narwhal
so things cancel out
stray reef
bc the 3, upon doubling, became 6. and the entire thing got shifted one to the right to line up
or in other words
spiral cradle
Oh ok
stray reef
same reason there's nothing above the 24576
spiral cradle
Ok thanks
stray reef
i don't think your drawings could pass off as "grids"
spiral cradle
only cause there isn't clear separation of the toothpicks right
obtuse lance
to be fair your idea of extending the pattern is consistent with what they've drawn
it looks like the pattern might be just put another triangle inside the middle, but by grid what they mean is all triangles are the same size
obtuse lance
you're welcome
tranquil jewel
@sleek swallow so after thinking, the range of f is just all real numbers besides 1/3 since it’s the asymptote right?
@naive saffron yes hi this is my second home
sleek swallow
There could very well be other numbers that aren't in the range of f.
But yes, 1/3 isn't in the range of f since there are no values of x in A such that f(x) = 1/3
tranquil jewel
How would I identify the other numbers then if any? Would Plugging in some x values to try to see the pattern of the output work
But yea 1/3 is the only value right, which is not in the range of the real numbers
sleek swallow
Well, you have a suspicion that 1/3 is the only value for which there doesn't exist an x in A such that f(x) = 1/3. Let's try and prove/disprove that.
Let $a \in \bR$. Then, let's see if there are any values of x that would give us an undefined $a$. The idea behind this is that we want to find an $a$ so that we'd have problems getting $x$. So, consider:
$a = \frac{x}{3x-1}$. Then:
$3ax -a = x$
$x(3a-1) = a$
$x = \frac{a}{3a-1}$
We can see that if $a = \frac{1}{3}$, then $x$ is undefined. $x$ remains defined otherwise. So, we conclude that $a = \frac{1}{3}$ is the only element of $\bR$ such that there doesn't exist a pre-image in A.
vital dewBOT
Abhijeet Vats:
tranquil jewel
Ah yea that makes sense also, I can graph the function and use that to determine the range, if it’s surjective and invective right?
sleek swallow
Well, there is an informal test that allows us to determine if something is a function or not. The vertical line test, for example, allows you to determine if some graph is the graph of a function. If it cuts the curve at two points, it's not a function (since every input is supposed to have one and only one image)
Then, there is the horizontal line test. That allows you to determine injectivity. So, if your horizontal line cuts the curve at two points, that means that $f(x) = f(y) \implies x = y$ is false, since the same y-value has two preimages.
vital dewBOT
Abhijeet Vats:
sleek swallow
I'm not quite sure if there is a test for surjectivity but you can use the graph to guide you in that regard
tranquil jewel
Ye we had this note
sleek swallow
Yes. Keep in mind that I did not, in fact, make use of those tests in order to determine the surjectivity of f. You must learn to do it analytically. Graphs are a great tool to guide you to the answer, though.
tranquil jewel
Of course yea
weary tiger
Formulating an inverse function is a good way to prove bijectivity
tranquil jewel
I’m not trying graph every function
How would I go about determining the inverse of g?, like does it want the function with x and y just flipped or like
sleek swallow
Well, the first thing you must check is if g is bijective or not.
That's going to determine if it is invertible
weary tiger
$y=\frac{x}{3x-1}$ switch $y$ and $x$ and solve for $y$ if you can solve that uniquely it is bijective
vital dewBOT
N/𝔄:
sleek swallow
You have the function:
$g:\bR \setminus {\frac{1}{3}} \to \bR \setminus {\frac{1}{3}}$
Clearly, this function is injective. In fact, you proved it in part (a). Then, you want to show surjectivity. We know that $g(\bR \setminus {\frac{1}{3}}) \subset \bR \setminus {\frac{1}{3}}$. Now, we just have to show it in the other direction. Consider an element in the set $D$. As we found out earlier, as long as that element isn't $\frac{1}{3}$, there will always be an $x$ such that $f(x) = a$, where $a$ is our chosen element. Since $a \neq \frac{1}{3}$, it follows that it belongs to the image set and therefore, it is surjective. Thus, it's bijective.
So, solving for an inverse is not going to be a problem at all.
vital dewBOT
Abhijeet Vats:
sleek swallow
Uh, what N\A suggested also works as well. It's entirely equivalent. I'm just presenting another approach.
tranquil jewel
Okay so I get that just one question to confirm, the target set and range both are the real numbers without 1/3 so it means they are equal
I.e why it’s surjective
weary tiger
@sleek swallow \left and \right would like to have a word with you
tranquil jewel
LOOOL
sleek swallow
Yes. The target set and range are the same, so that's why it's surjective.
fossil pewter
Reasking this because it got unanswered
In problem 91 what would be the approach if the balls were different instead of being identical
sleek swallow
@weary tiger No u
tranquil jewel
And this is the inverse right?
sleek swallow
Is it?
weary tiger
It is
Though you need to solve for y
Well it is equivalent to the expression of an inverse
sleek swallow
Wait what's the second thing, after /?
tranquil jewel
Okay
weary tiger
It's $\mathfrak A$
vital dewBOT
N/𝔄:
weary tiger
fossil pewter
stray reef
use the definitions of everything
it really is that easy
unless you don't know what an injective function is! in which case, tough cookies
@tranquil jewel
near prawn
🍪
sleek swallow
let me know if you have any trouble proving it