These are just normal functions
#discrete-math
faint narwhal
static rapids
what do they mean by f o g is onto
faint narwhal
Do you know what an onto function is
static rapids
im sorta confused on what the onto function is supposed to mean, from what i got from it, it means its injective meaning that f(a) = f(b) which corresponds to a=b
static rapids
oh yea i got them mixed up
my bad
how do i show that f o g is onto
@faint narwhal
faint narwhal
Do you know what onto means yet
static rapids
ye, its a surjection in where a is an element of A and b is an element of B with f(a) = b
its like..
for every b, there is an a such that (f(a) = b)
yea idk how to explain it well...
its a bit confusing for me tbh
@faint narwhal
faint narwhal
That's right
stray reef
@static rapids do you still need help with this
stray reef
there are 4C2 ways to pick the pair
once you've got the pair, the arrangement is uniquely determined
stray reef
if you arrange them so that each pair of lines intersects, and there are no three-way intersections or higher, then there are that many intersection points in total
@weary tiger
and there can't be any more because if there are no three-way intersections or higher then each intersection point is uniquely determined by the pair of lines it's on
pale epoch
Ann basically gave you a proof, what do you not believe about it
if you think you can get more intersections, try it
stray reef
ok what do you not understand about it then
pale epoch
you can also think of it another way
the n'th line can intersect at most n-1 previous lines
two lines can intersect at most once
so if you have for example 4 lines and you add a 5th line
you get at most 4 new intersections
stray reef
if you arrange the 9 lines so that no three ever meet at the same point, then there are exactly 9C2 intersections
@weary tiger do you agree with that y/n
in such an arrangement, each intersection point corresponds to a pair of lines
do you see how
...
it's the LINES that come in pairs.
not points.
each pair of lines
corresponds to one point
their intersection
do you agree
you were trying to say something about pairs of points
but i wasn't talking about pairs of points at all
i'm talking about the fact that a pair of lines uniquely determines an intersection point, and vice versa
stray reef
an intersection point uniquely determines a pair of lines
stray reef
do you agree now
that in this case there will be exactly 9C2 intersections
what do you mean by "doing" 9C2
choosing 2 lines is equivalent to choosing an intersection point
if you so insist, then yes
stray reef
i don't spell it out that explicitly because this is trivial to me
???
is this meant to be some sort of sarcastic remark on how i've got an inflated ego that needs popping
WELL FUCK YOU THEN, YOU'RE NOT GETTING ANY MORE HELP FROM ME ANYMORE.
because clearly you think of me as an asshole that makes others feel like fuckwits for no reason by stating that things they are learning are trivial to her
you couldn't have been more obvious in stating that save maybe for saying it outright
cerulean ore
@reef thistle What did you use for Graph Theory?
pale epoch
i remember when a professor of mine said "when i say something is trivial, i don't mean it's easy, it just means i thought a lot about it at one point so it's now trivial to me. your job is to do the same"
cerulean ore
@pale epoch Well said!
stray reef
yeah but let's just face it everyone here thinks i'm an asshole and would rather not interact with me if they could at all avoid it @pale epoch
pale epoch
i have the impression that most people like you, because you are among the most helpful
cerulean ore
My teacher has set a new bar in Mathematics by proving a property of an algebraic structure using an example.
Let S={0,1,2,3,4,5,6,7} and * denotes multiplication modulo 8. Check whether hte above algebraic structure forms a group or not.
For Associativity she said :
for every a,b,c belongs to S Let a=1, b=2, c=3 LHS = (1*2)*3 RHS = 1*(2*3) Since, RHS=LHS therefore, the associativity exists.
When we asked her like how can she use a specific example she said then find an example which shows that it doesn't follow associativity.
Wtf?
cerulean ore
I can take this matter to the academic coordinator now
She has fucked up 3 chapters, Recursion/Recurrence, Group theory, One was about finding characteristic equation and finding particular and homogeneous solutions.
stray reef
lmfaoo
wow
"here's one example. QED associativity"
"wow who cares about universal quantifiers or this 'for all' stuff"
@cerulean ore glad you can do something about this shitbag of a teacher though finally
stray reef
definitely not that, no
first off
are you sure you aren't missing any parentheses
and second
...
what even
vital dewBOT
euler/fermat:
vital dewBOT
euler/fermat:
stray reef
no seriously
that makes 0 sense
i don't even know how to fix that
your reasoning is just completely off-the-track nonsensical with literally no way to bend it into anything that even sounds reasonable
OH BUT I CAN'T SAY THAT CAN I YOU'LL ACCUSE ME OF MAKING YOU FEEL LIKE A FUCKWIT FOR NO REASON
cerulean ore
@stray reef Actually, I can only report her. The rest is on the management that sucks.
static rapids
@stray reef no I’m fine now thank you
scarlet anvil
I'm having a hell of a time with strong/weak induction proofs. Anyone have any recommended videos?
sour arrow
Want to post the question here, and we can talk it out? I don't know of any videos that Google doesn't show
vital dewBOT
euler/fermat:
stray reef
"the house one"?
sounds like incl-excl might be of use
mmmmh
ok fine
ok i guess you have no option but to list all of the possible configurations of finishes taking into account only which ones are the same and which are different
azure lichen
not all arrangements will have the same amount of symmetries. for example, in the example given above, rotating by 90 degrees will give a different arrangement, but rotation by 180 won’t
you can’t just naively divide by, say, 4
that’s a number alright
but it’s not a solution
cause I have no idea how you arrived at it
so I can’t tell you anything other than “this is a number”
but that’s not right necessarily
also what do you mean with “order doens’t matter”?
surely Stone/Wood/Brick/Stucco is different to Stone/Brick/Stucco/Wood, right?
and stone in front is probably different from stone on the left side, too
at least your problem did not indicate those would be considered the same
nor would common sense
are they?
the problem statement doesn’t say so
unless you didn’t give us the whole problme
no it’s not?
whether the wall facing the road or the wall facing the back is stone is different
it’s a house after all, you can’t just turn it around
yea and when you build it, you’ll have to choose which side is supposed to be stone
you can’t just say “well just put a stone wall somewhere and then rotate it around when we’re done building”
that’s not how houses work
I don’t have a smart solution
I have a brute-force solution in mind
well, not quite brute-force
but it’s not clever
stray reef
front
back
the problem says you can't really rotate the house
there's a fixed front wall
azure lichen
I’d start by listing all possible ways to arrange variables legally
like… ABCD would be one possibel thing (where each variable would be a different material). so would ABAB, but not AABC
list all those options
then for each, find out how many ways you can assign values
and sum it all up
that will definitely work
but it’ll be tedious
I agree
I can’t think of a better solution tho
you won’t learn zero from it tho
stray reef
he isn't allowed incl-excl
azure lichen
where does incl-excl show up there
stray reef
which would have given a better solution
@azure lichen count the configurations which have matching finishes on a pair of adjacent sides
then take complement of union
azure lichen
anyway unless I’m mistaken the only arrangmenents are ABCD, ABCB, ABAC and ABAB anyway, so that’s not too bad. and the middle two are exactly the same for calculation
stray reef
no @weary tiger, just because i am mentioning the words "union" or "complement" does not mean i have a venn diagram in mind
sascha already gave you what amounts to a massive hint
i've said this N times here now: yes, but i never got far in any of them
how long ago was what
my most recent math competition? probably like 4 years ago
don't remember what it was
yes
i was in grade 11 and we started calculus in like... grade 10? and i had self-studied it myself before that
idk
those people have trained specifically for competitions
it has nothing to do with how long one knew calculus
they probably studied things like past years' problems for the competitions they wanted to compete in
also, study time doesn't correlate positively with skill past a certain point
the only thing you can achieve by studying your ass off 16 hours a day is burnout
idk like
it just seems stupid to me trying to make study time a goal
the way you're saying it makes it seem like you're saying "i study so much but i still suck!!! what do???? :(((("
pale epoch
how do you even do serious math work for 8 hours a day
stray reef
beats me
stray reef
won't scale up well
if i ask you to count the solutions to $x+y+z=1000$ in nonnegative integers
vital dewBOT
Ann:
stray reef
OH MY GOD WHAT THE FUCK
WHY DID YOU DELETE THAT
NOW I DON'T HAVE THE ORIGINAL PROBLEM
WHAT THE FUCK
ok but why the fuck would you delete the message that fucking started this conversation
that's a dick move on your part
vital dewBOT
euler/fermat:
stray reef
yeah ok anyway so like
ever heard of stars and bars
ok fine forget it then
do you mind if i explain the solution of a more general problem
using the method i have in mind
ok
so the problem will be to count the solutions of the equation $$x_1 + x_2 + \cdots + x_k = n,$$ where each $x_i$ is constrained to be a nonnegative integer, and $k$ and $n$ are known
vital dewBOT
Ann:
stray reef
does the problem statement need any clarification before i continue
@weary tiger
ok
good
stray reef
...i'd gladly answer that if you weren't interrupting an explanation i'm about to give
no
discrete != discreet
anyway
it wasn't obvious that you were.
anyway.
can i talk now.
weary tiger
yeah but i didn't get what is discrete maths tho?
stray reef
ask in #discussion. this channel is currently occupied.
PLEASE DON'T FUCKING INTERRUPT ME, I REALLY FUCKING HATE IT WHEN PEOPLE DO THAT.
ok so
weary tiger
sorry
stray reef
with that out of the way
i'm going to reframe the problem in a more combinatorial light
or rather
weary tiger
...
weary tiger
ok i'm out
stray reef
i really don't want to deal with this right now
i was trying to
but then he shoved himself in my field of view
ok
can i talk now
for once
without being interrupted
ok great
so i'm going to reframe the problem in a more combinatorial light
or rather
i'm going to present a different problem and am then going to show that the two are in fact the same problem viewed from different angles
said problem is this:
there is a deck consisting of $n$ white cards and $k-1$ red cards. the cards are indistinguishable other than by color. how many ways are there to arrange the deck?
vital dewBOT
Ann:
stray reef
this is way off
this is like
numbering the white cards 1 to n, then the red cards 1 to k-1, then shuffling the whites and the reds separately and asking how many arrangements can be made out of THAT
the answer to this problem is $\binom{n+k-1}{k-1}$. there are a total of $n+k-1$ cards in the deck, and we're choosing $k-1$ places where the red cards would go.
vital dewBOT
Ann:
stray reef
can we move on now?
ok
so now as promised i'll now show that these two problems actually count the same thing
so i'll go from the cards to the equation first
take a deck of the structure i specified, perhaps shuffled in some way
count off as many white cards as needed from the top in order to reach the first red card
however many white cards you counted off, set x_1 equal to that
take off the red card
count off the number of white cards until the next red card
that's your x_2
take off the red card
count off the number of white cards until the next red card, that's your x_3
and so on
after taking off the last (a.k.a. the (k-1)st) red card, count how many white cards remain
and that's your x_k
does this all make sense?
ok
so now to go the other way
starting with a solution of the equation x_1 + x_2 + ... + x_k = n, build the deck as follows, from the bottom up:
place down x_k white cards
then a single red card
then x_k-1 white cards
then another red card
then x_k-2 whites, then a red
and so on
ending with the last red card and x_1 white cards
does this make sense
yes the point is that it's reversible in the first place
thus setting up a one-to-one correspondence between arrangements of the deck and solutions of the equation
so the counts must be the same
the arrangements of the deck and the solutions of the equation
wdym
well i did stuff on khanacademy
it was just a matter of learning the english words for concepts i was already familiar with
limits
derivatives
integrals
that stuff
stray reef
if you don't want casework then i'm afraid incl-excl is your only option
basically instead of counting the configurations that DON'T have any matching finishes on adjacent walls
count the ones that do
let $A_1$ be the set of all configurations with the same finish on the north and west walls \
let $A_2$ be the set of all configurations with the same finish on the west and south walls \
let $A_3$ be the set of all configurations with the same finish on the south and east walls \
let $A_4$ be the set of all configurations with the same finish on the east and north walls \
then the number you're after is $|A_1 \cup A_2 \cup A_3 \cup A_4|$
vital dewBOT
Ann:
stray reef
$|A_1 \cup A_2 \cup A_3 \cup A_4| = \ |A_1| + |A_2| + |A_3| + |A_4| \ - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_1 \cap A_4| - |A_2 \cap A_3| - |A_2 \cap A_4| - |A_3 \cap A_4| \ + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_1 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_4| - |A_1 \cap A_2 \cap A_3 \cap A_4|$
vital dewBOT
Ann:
stray reef
$|A_i| = 4^3 \ |A_i \cap A_j| = 4^2 \ |A_i \cap A_j \cap A_k| = 4 \ |A_1 \cap A_2 \cap A_3 \cap A_4| = 4$ \ (assuming $i, j$ and $k$ are distinct)
vital dewBOT
Ann:
stray reef
:???
i'm just applying incl-excl
nothing else
as far as i can tell, there are only three ways to do this problem: the casework sascha and i talked about yesterday, incl-excl, and just counting it all up one by one
but you seem to reject all three
honestly the incl-excl thing i wrote out isn't that bad
like in this case your sets are symmetric enough that the twofold intersections all have the same cardinality
as do all the threefold ones
and the sets themselves
cerulean ore
I am trying to sum the power series (x^n /n!) From n=0 to infinity
And it seems to be a difficult one
Any hint?
faint narwhal
There's no way to sum it up
I think you just have to recognize it
There are some hints
Like take the derivative of it and see what you notice
cerulean ore
e^n, that is what my calculus says ;-;
faint narwhal
Not quite
Having n in your final answer doesn't really make sense
n is just the summation variable
cerulean ore
Yeah, it should be e^x
faint narwhal
Right
cerulean ore
Thank you!
elfin lagoon
Exists an x in D such that x > 0 and x^2 = 2. provide an infinite domain
I know square root of 2 works
but i need an infinite domain
reef thistle
Infinite domain?
elfin lagoon
yeah an infinite number of elements in the set
elfin lagoon
an infinite set that satisfies the statement
reef thistle
Only one real number x satisfies x>0 and x^2=2
So, you can considering things that are not real numbers?
Provide an infinite set D?
@elfin lagoon
If so, the real numbers would work
elfin lagoon
real numbers is the "upper limit" for numbers in this course, so anything in real numbers is being considered, no complex numbers
are you saying that there is only one real number that satisfies the statement or that an infinite set exists?
reef thistle
I think they meant "provide an infinite set D such that the statement is true"
@elfin lagoon
azure lichen
among real numbers, there’s only one such number which satisfies x>0 and x²=2, namely √2
but if you set D=ℝ, then √2∈D and D is infinite
is a summary of what has been said above
that said, it’s not quite clear what the question is asking
at least to me
elfin lagoon
the question asks to find an infinite domain which makes the statement true. so for example, if we have the universal statement that for all x in D, x > 1 , then all natural numbers greater than 1 would be considered an infinite domain which makes the statement true
based on what has been said i guess no such infinite domain exists and there only exists a single answer in the reals
elfin lagoon
"provide the truth set of 1 <= x^2 <= 4 in all real numbers"
analog dagger
Wait so the domain has to be some common field?
elfin lagoon
the domain is all real numbers. the truth set is within all real numbers.
azure lichen
so the set of all values x such that that statement is true?
as in, {x∈ℝ | 1 ≤ x² ≤ 4}?
pale epoch
depends how often these invitations occur
ah sorry
I misread
isn't it just n choose 3 >= 365
why not solve it via the polynomial?
then it's possibly just trial and error
elfin lagoon
@azure lichen yes
lilac pivot
just choose some values of x and compute x choose 3 on a calculator
it increases pretty fast
you should get over 365 for a pretty small number
you can do it by hand if you'd like
that's a nice pen
wanton sable
can anyone help me figure out the time complexity of the addition algorithm (adding two non negative integers, x and y)?
my answer was O(log(x + y)), however, i don't feel like that is entirely correct
it may also be O(logx + logy) and i don't know which one is a tighter bound
summing x + y would give you the sum, and taking the log of that would give you how many bits are in the sum
but does that really tell you how many bits are accessed during the algorithm?
faint narwhal
You can simplify the second one a little
wanton sable
how so?
if you mean simplifying it to O(logx), i need to keep it in terms of both x and y
wikipedia lists the run time for this as Θ(log(N)) and Θ(n), for two n-digit numbers N, N
which is why i'm a bit confused here
this is implying that both numbers have the same digits, right?
which is not always the case for addition
https://cs.stackexchange.com/questions/68053/time-complexity-of-addition this talks more in depth about it, and one answer says that addition runs in O(log(N)) where N is the value of the sum
which is how i was kinda confused between getting both O(log(x+y)) and O(logx + logy)
honestly, the more i think about it, the more i have to go with O(logx + logy), because that tells you how many individual bits are being read during the algorithm
as opposed to O(log(x+y)), where this just tells you how many bits are in the sum which doesnt really indicate how many bits are being read during the algorithm
idk, i might be wrong on this.. i feel like i am
wanton sable
no wait.. its O(log(x+y)) right?
holy shit im confusing myself so much here
actually, it might even be O(max(logx, logy))
Suppose x and y are each n bits long; in this chapter we will consistently use the letter n
for the sizes of numbers. Then the sum of x and y is n+1 bits at most, and each individual bit
of this sum gets computed in a fixed amount of time. The total running time for the addition
algorithm is therefore of the form c0 +c1n, where c0 and c1 are some constants; in other words,
it is linear. Instead of worrying about the precise values of c0 and c1, we will focus on the big
picture and denote the running time as O(n).
i found this, but idk how helpful it is
because this assumes x and y are each n bits long
and we know in addition that numbers can't always be the same number of bits long
ok its definitely O(log(x+y))
i think
sage citrus
Hi, need help with DNF expression if anyone is available
elfin lagoon
what's a truth set in all real numbers that satisfies 1<=x^2 <= 4 ?
uneven phoenix
{ x in R : 1 <= x <= 2 } UNION { x in R: -2<= x <= -1 }
sage citrus
how do i convert an expression to DNF? I'm stuck with x1 or x1'x2
how can i know which expression is exactly of the type 'DNF'
uneven phoenix
what is that shortcut? ... normal form?
sage citrus
there are literally 2 examples in the book of going from normal form to dnf and the author jumps all the steps and just writes the solution lol
i have no idea what to do
also been googling for 30+ mins
uneven phoenix
When I did it once in 2015 I just used, as wiki says, "logical equivalences, such as double negation elimination, De Morgan's laws, and the distributive law" - are u familiar with those?
sage citrus
yep, but how do I know i arrived at the correct answer loll
why isn't x1 or (x1)'x2 in DNF`?
uneven phoenix
I don't understand your symbols, what is x1
sage citrus
x1 and x2 are input to unknown function f
elfin lagoon
@uneven phoenix how can that second set be part of the solution if 1 <= x^2 <= 4 was given?
how r u getting neg values
faint narwhal
what's (-2)^2
sage citrus
might have figured it out maxwell
u j ust want to include all the variables in each statement
probably lol
tranquil cargo
let (a,b) element to A x (B intersects C)
then a is in A and b is in B intersects C
then b is in B and b is in C
then (a,b) is in (A x B) and (a,b) is in (A x C)
(a,b) is in (A x B) intersects (A x C)
qed
now u do c
@blazing nova
faint narwhal
Do you know what contrapositive means?
faint narwhal
Then what's the contrapositive of the first statement
blazing nova
this is correct for 4a right?
cerulean tangle
can someone1 help me understand this answer
I don't get why the answer is what it is
lilac pivot
that looks like #linear-algebra
cerulean tangle
oh thx, I guess icne it's matrices, but the course is technically discrete math B
sterile sandal
can someone explain this for me? https://math.stackexchange.com/questions/1039900/properties-of-the-greatest-common-divisor-gcda-b-gcda-b-a-and-gcd
I'm not really getting it
obtuse minnow
What's the problem exactly? (same as in the stackexchange?)
scenic shard
Hi,
I have the following claim to prove:
for all integers n, if (13 divides 6n) then (13 divides n).
My first approach was to prove it with a direct proof, but I think I'm stuck after the first step.
1.) 6n = 13k for k ∈ Z
stray reef
you're going to have to make use of the fact that 13 is prime
scenic shard
Oh I see. Thanks 🙂 I'll try it now
Proof:
6n is divisable by 13 and we know that 13 is a prime number such that 13k where k ∈ Z (>0) is only divisable by 1 and 13.
This means n has to take an integer of 13k to become divisable by 13.
Therefore 13 | 6n holds and 13 | n holds, so the claim holds.
Q.E.D
is this a good proof? 🙂
scenic shard
haha yes I see it now that statement is not correct at all. Uhm I will try it again
obtuse minnow
Also consider the seemingly similar:
for all integers n, if (14 divides 6n) then (14 divides n). (this is false n = 21)
scenic shard
did you find the counter example just by bruteforcing or is there a proof tecnique which fits well in this kind of claims?
obtuse minnow
Er ... I hope I'm not giving too much away. And if I am you need to prove this lemma also.
If you have a prime p, and p divides ab, then p divides a or p divides b.
scenic shard
haha thanks i'll try to prove the lemma first then
ab are just natural numbers or integers?
obtuse minnow
Either or. It's true for both.
scenic shard
What I can see is a = 1 or p itself and b = 1 or itself? Am I right?
obtuse minnow
Just an example: If you have a prime 7, and 7 divides 99x, then 7 divides 99 or 7 divides x.
Um I think I'd use proof by contradiction.
If you haven't studied that, I'll try to think of another way.
scenic shard
Yes proof by contradiction is on next weeks lecture but I see that alot on the internet. Maybe it's a good way to already read about it
obtuse minnow
yeah the internet works.
If a prime p divides ab, and p does NOT divide a nor b, there is something very wrong.
scenic shard
Hahah yes I see. This makes a lot more clear. The description in my book is a little bit more confusing.
An integer n > 1 is prime if it is divisible by exactly two positive integers, namely
1 and itself. Note that a number must be greater than 1 to even have a chance of
being termed ‘prime’. In particular, neither 0 nor 1 is prime.
Thanks for the explanations 🙂
obtuse minnow
ah very nice.
gusty pasture
Can someone check my work? Its pretty simple but Im double guessing myself
faint narwhal
gusty pasture
nvm cant drop the venn diagram lol
but can
{u,x} = A ∩ C
if u,x is in the middle of the venndiagram
I know that {u,x} ∈ A ∩ C is true
but I dont really understand if u,x can "=" sets
faint narwhal
I'm not sure what you mean by u,x = sets
The first statement you write
{u,x} = A ∩ C
Is an equivalent of sets
{u,x} is the set containing u and x
gusty pasture
Okay lemme try again sorry for being confusing
So the question is looking for a true or false for two different questions
the first is
{u,x} ∈ A ∩ C
2nd is
{u,x} = A ∩ C
The venn diagram looks like ( ({u,x}))
if that makes any sense
faint narwhal
you can always take a picture
gusty pasture
Im fairly certain the first question is True, but the second one is throwing me off with the equal sign
faint narwhal
Well both A and C are sets right
gusty pasture
correct
gusty pasture
the same so A ∩ C is {u,x} and {u,x} = {u,x} so its true?
Ive just never seen anything mention this type of equation lol
thxs
faint narwhal
@gusty pasture Wait
What about the first question again
What does it mean for {u,x} ∈ A ∩ C
gusty pasture
well if A ∩ C is {u,x} and {u,x} ∈ {u,x} isnt possible so its false
faint narwhal
Correct
faint narwhal
Kinda
gusty pasture
xD
gusty pasture
gotcha
faint narwhal
{u,x} would be an element of something like {u,x,{u,x}}
One of the elements in that last set is itself a set
gusty pasture
Riiigghhttt im learning about that rn
faint narwhal
Yeah, if you know any programming, it's kind of like having an array of arrays
gusty pasture
Literally where I stopped my YouTube ruby tutorial lol
was a bit much for me
but I think discrete is going to help me with that
gusty pasture
Okay stuck on another, so if B = { 10, 11 }
and it wants B^3
Am I just simply multiplying this out or do I need to define some kind of equation.
The question is "When listing set elements, express your answer using roster and n-tuple notation where appropriate."
Is it as simple as doing BxBxB?
nvm
elfin lagoon
"if a, b are ints and a^2+b^2 is even, use a direct proof to show that a+b is even"
tranquil cargo
if a and b are integers and a^2+b^2 is even show that a+b is even
now we are asked to use a direct proof
what would you assume
for your proof
@elfin lagoon
elfin lagoon
i was going to ask if it is required for me to work from the top down as in do i have to start from a^2+b^2 and somehow get a+b out of that? or can i work bottom up and start with a, b
if the requirements are as rigid as i believe them to be, that would mean i have to start from a^2 + b^2 and then get a+b somehow
ripe ferry
that is what direct means
elfin lagoon
@tranquil cargo i would assume that a and b are integers and that a^2 + b^2 is even
tranquil cargo
yes
and from that show that a+b is even
thats a direct profo
proof*
now try it
elfin lagoon
what i was trying to do was to prove that x+y is even if x and y are both even or both odd but since the proof is direct i guess i cant do that
so hmm
elfin lagoon
ehh im stuck
tranquil cargo
ok
lets do it together
well
you now just proved x^2+y^2 is an integer
ok
lets do the proof
proposition:if a and b are integers and a^2+b^2 is even show that a+b is even
proof: suppose a and b are integers and a^2+b^2 is even
then by definition a^2+b^2 = 2k for some integer k
add 2ab to both sides of the equation
a^2+b^2+2ab=2k+2ab
factor lhs
(a+b)^2 = 2k+2ab
(a+b)^2 = 2(k+ab)
(a+b)^2 = 2(t) for some integer t (namely k+ab)
(a+b)^2 is even
then (a+b) is even ( can be proven )
qed
got it?
ripe ferry
you cant just do it for them
tranquil cargo
sorry
elfin lagoon
ok i see what you did there
elfin lagoon
would it be possible to prove the same thing without the choice of randomly adding 2ab into the mix?
and only deriving from what's given and/or definitions
ripe ferry
a) adding 2ab isnt random
b) theres really no other way
tranquil cargo
its just like a feeling
you wanna get something nice from that a^2+b^2
you know a^2+b^2+2ab
is a perfect square
idk how to explain it
you just get a sketch of hte proof before writing it
in proving sometimes steps can feel random
but if you think about what you want to do
if you consturct like a sketch in the profo
for the proof*
you get it easily and beautifully
writing out the proof is just for the technical details
the sketch should be in your brain
and ofc not the first sketch of the proof
is correct
got it?
i know nothing tho so idk XD
elfin lagoon
i understand. if i want to document the fact that im factoring in a step of my proof, is it more formal to say "factoring" or "distributive property"
tranquil cargo
ask sigma he/she is way more better
just write it out
doesnt matter
a^2+2ab+b^2 = (a+b)^2
( by factoring ))))) by whatever
doesnt really matter imo
ripe ferry
just say factor, i usually dont even put in those words and just do it
stray reef
there are a_{n-1} strings of length n-1 with no occurrence of 012
and so there are also that many strings that consist of one of these with an extra 1 appended on the left
@cerulean ore
cerulean ore
@stray reef That is not a_{n-1}*(n-1)? Written in the example
stray reef
it's poorly written
i don't think it's meant to be a_{n-1}*(n-1)
i would rephrase to separate the a_{n-1} and the (n-1) lol
cerulean ore
What does the author means then?
Does the author means if the first digit is 1 then there are a_{n-1} = n-1 length terms that also has 1 one left and doesn't has subsequence 012?
cerulean ore
How are we sure that there are a_{n-1} strings of length n-1 with no occurrence of 012?
stray reef
by definition of a_n...
no seriously that's just the definition of a_{n-1}
don't overthink it
cerulean ore
Aah, got this much part
Now, what if there is a 0 in starting?
Then we will have to avoid 12 in the starting
stray reef
and that's exactly what they're doing...
cerulean ore
So, for 0 in the starting we have a_{n-1} - (sequences with 12 in the starting of length n-1}
But, how does that becomes a_{n-3}?
If n-1 is the length of the sequence and 1 and 2 is in the starting then there are a_{n-1-1} sequences with no 012 in there sequence
aah
That's correct?
cerulean ore
Yep!
stray reef
exactly the same issue as before
cerulean ore
@stray reef I am following the book to learn recurrence relations.
stray reef
and?
cerulean ore
But, I doesn't seem to be able to follow it properly
stray reef
"I doesn't" 
cerulean ore
I mean that even after going through many examples the new examples doesn't looks intuitive
Unable to grasp the approach
I am following Applied Combinatorics by Alan Tucker
What could be the problem?
@reef thistle ?
cerulean ore
Trying to learn recurrence relations
reef thistle
and where are you stuck?
cerulean ore
@reef thistle learning the approach
Unable to apply the knowledge from previous examples to new ones
elfin lagoon
If I'm writing a direct proof am I allowed to make assumptions that aren't given to prove a point?
The given statement was that if a and b are integers and (a^2+b^2) is even, then a+b is even. In my proof I was able to derive that (a+b)^2 is even , but in order to take it one step further and prove that (a+b) is even, it seems that I have to prove that if the square of an int is even, then that same int is even. in order to do exactly that, I could prove this through contrapositive but I would have to make an assumption of an odd square
am i allowed to make the assumption of an odd square? in the original statement there is no odd anywhere and it kind of seems like i'd be doing a proof within a proof if that makes sense
cerulean ore
@reef thistle like, the author discusses about if there are n identical balls and k boxes. You have to put balls 2-4 in each of the K box. So, what are the number of ways.
stray reef
assuming 2k <= n <= 4k, i take it?
cerulean ore
I had to read it
So, I couldn't stumble upon the answer he suggested
Talking to me ann?
stray reef
yes
reef thistle
@cerulean ore You just want to be able to write recurrence relations?
So the idea is the same as dynamic programming (without memoisation). You just want to try to split it into disjoint cases for counting.
cerulean ore
@reef thistle Yep
Learning it so that I can take the concept to dynamic programming
dim marten
Hi anybody here?
Basically I don't understand the material, can somebody help me through it?
its on graphs
reef thistle
@dim marten What do you understand so far?
reef thistle
yeah, the idea is not too far off from recursion
dynamic programming
but you don't need memoisation
cerulean ore
So, going through this I can understand it. One can easily understand it after reading it multiple times.
But, how do I devise these methods by myself?
Understanding these algorithms looks like half memorization and half understanding.
reef thistle
It's about breaking into cases
Suppose A that makes the problem simpler. Solve it. Then suppose not A, that also makes the problem simpler. Solve it
cerulean ore
How would that come? By solving what type of questions?
cerulean ore
Maybe this?
reef thistle
yeah
Your state is number of balls and number of boxes
Since the boxes are distinct, we want to get rid of 1 box
A: We put 4 balls into box 1
Not A: We do not put 4 balls into box 1
That's the idea
cerulean ore
But, we can put 3 balls into box 1 as well
reef thistle
Yeah
So, we have 3 disjoint ways:
We put 4 balls into box 1
We put 3 balls into box 1
We put 2 balls into box 1
cerulean ore
What do you mean by disjoint ways?
reef thistle
Disjoint, as in if one happens, the other two CANNOT happen
stray reef
aka mutually exclusive
reef thistle
If I put exactly 3 balls into box 1, I cannot put exactly 2 balls into box 1
cerulean ore
But, if 4 balls are into box 1 then, there are 3 balls also inside it.
reef thistle
Okay, let me reexplain
3 disjoint ways:
We put exactly 4 balls into box 1
We put exactly 3 balls into box 1
We put exactly 2 balls into box 1
okay now?
cerulean ore
Yep
So, for box one the number of ways are : 3?
So, for 2nd box we again have 3 ways?
reef thistle
no
we don't multiply
we split into cases
the cases might use different subproblems
that's fine
upbeat minnow
If I have X={1,2,3,4}, and let's say R={(x,y)∈X∣ y≤|x−2|} , aren't my possible relations {4,2 4,1 3,1 and 1,1}?
faint narwhal
you really need more parentheses here
stray reef
upbeat minnow
In which part?
wraith tiger
The part where you listed your relations
upbeat minnow
So uh {{4,2,} {4,1}...} ?
cerulean ore
@reef thistle How do we relate our subproblems with problems
cerulean ore
Solved this question:
But, made it a bit complex
how do I write it in the Mathematical form
reef thistle
Can be simpler...
int* addSumOfPrev(int *arr, int len) {
if (len>1) {
arr[1] += arr[0];
addSumOfPrev(arr+1, len-1);
}
return arr;
}
@cerulean ore what do you mean by mathematical form?
cerulean ore
@reef thistle like this:
cerulean ore
You're a genius!
slender skiff
Have i made this hasse diagram correctly? (still need to remove the arrows, i know)
prime chasm
A donut shop had 6 types of donuts, how many ways are there to choose 6 donuts where at least 1 is chocolate?
This isn’t a distinguishable permutations question is it?
Donuts are unlimited and can be repeated
lilac pivot
one is chocolate, so you have 1* 6^5 possibilities
you can pick chocolate for the first donut
you can pick 1 of 6 donuts for the 2nd donut
you can pick 1 of 6 donuts for the 3rd donut
you can pick 1 of 6 donuts for the 4th donut
you can pick 1 of 6 donuts for the 5th donut
you can pick 1 of 6 donuts for the 6th donut
prime chasm
Wait I asked the wrong question but I think I got it. Choose 10 donuts with 6 variations and at least 1 is chocolate
10 donuts with 6 variations is 15C6
At least one chocolate is 14C5 and that makes sense by your logic, I now have 5 donuts with 9 possible positions... so 15C5.... unless it’s supposed to be 14C6... because all 6 could be chocolate...
stray reef
it's not clear whether order matters here tbh
bc if it does then this is just 6^6 - 5^6
but if it doesn't it might be trickier
if order doesn't matter then i guess you could do this with a modified stars&bars thing
uh
10C5? i may very well be wrong but this is what i get from a quick mental calculation
river yarrow
Any people good here with inductions with inequalities?
faint narwhal
river yarrow
Sorry. The question is to show that n^n >= 2^n for all integers n>=2, using mathematical induction
Base Step: Left hand: 2^2 = 4 Right hand: 2^2 = 4.
Induction Hypothesis: k^k >= 2^k
We want to show when it still holds for n=k+1, so I add 1: (k+1)^(k+1) >= 2^(k+1)
How the heck do i prove it in the induction step?
stray reef
$2^{k+1} = 2 \cdot 2^k \leq ; ?$
vital dewBOT
Ann:
river yarrow
I understand that part. Am I supposed to figure out what the question mark is?
stray reef
you're gonna want to use the inductive hypothesis in some way
i've given you the beginning of an inequality chain
river yarrow
Ok. Should I substitue k^k in place of 2^k?
stray reef
$2^k \leq k^k$ is your IH.
vital dewBOT
Ann:
stray reef
if you can use it, it's probably a good idea to do so.
river yarrow
Quick in-between question: When doing the induction step, would I always have to start with the statement when n=k+1 and use the assumption where n=k to solve it?
Or could i do the other way around
river yarrow
oh ok
stray reef
however with inequalities it's both ok and common practice to form an ineq chain beginning with one of the SIDES of the target ineq
and construct the chain from there
eventually getting the other side on the other end of it
river yarrow
Thanks. I'm glad you cleared that up. Now, for the chain, should I divid by 2 or something?
I'm kind of lost here
stray reef
divide what by 2
stray reef
both sides of what
river yarrow
What do you think I should do?
prime chasm
Using the letters A and B (can be repeated) how many 10 letter words can be formed? How many words with at least 2 As?
stray reef
@river yarrow 2 * 2^k <= 2 * k^k
prime chasm
I got 2^10 for 10 letter words
sour arrow
Looks right to me
prime chasm
The 2nd bit has me fucked up
sour arrow
Without the 2 As
prime chasm
Sure.
river yarrow
@stray reef Oh that makes sense. For the next step, should I multiply both sides by k? I got 2k^(k+1) >= (2^k)(2k)
stray reef
no that's a bit useless
vital dewBOT
euler/fermat:
river yarrow
What do you suggest i try to look for?
stray reef
i would argue that these aren't necessarily independent since Biff's point may very well be what wins them the game
river yarrow
what do i do
@tacit topaz im confused was that a response to me or do you need help on that?
rip pianoman
np
pale epoch
you just posted a picture and no question @tacit topaz
azure lichen
you still haven’t asked a question
obviously no one’s just gonna do your exercises for you
if you need help with sth you should at least say what you’ve tried and where you’re stuck
pale epoch
that's the probably of her seeing 2 shooting stars
stray reef
how did you get 0.36
0.6^2?
yeah, that gives the probability of seeing a shooting star in both hours
pale epoch
well, there are a lotta assumptions in that question anyways
stray reef
yeah
pale epoch
this doesn't seem like a discrete problem tbh
stray reef
#probability-statistics exists too yknow
you can put probability questions in there
no
stop this you're doing it again
stray reef
...
what
no don't do the problem deletion thing again
OH COME ON
WHAT THE FUCK
NO
pale epoch
great, now i seem like a lunatic
stray reef
JESUS FUCKING CHRIST THIS IS EVEN FUCKING WORSE
WE'VE BEEN OVER THIS
urrghhhhhh
i (really)^n don't want to deal with this atm
river yarrow
@stray reef Bro, I think I figured it out. Could you check my answer? k^k >= (2^k)k -> multiply both sides by k -> k(k^k)>=(2^k)*k -> k^(k+1) >= (2^k)*k
river yarrow
So is it right?
faint narwhal
"but yes"
river yarrow
i dunno man, was it a yes to my question "could you check our my answer?" or was it a yes to the validity of my answer?
pale epoch
no
more like you can't treat the 2 hours as independent events
because after 30 mins, she has a 60% chance to see a shooting star in the next hour
or after 1 second
or whatever
river yarrow
Is there some rule here against deleting posts?
stray reef
no it's just annoying when he does it
river yarrow
lol
spring temple
It's not a formal rule, but it's very disconcerting to find half a conversation about a problem.
river yarrow
i feel u bro
cerulean ore
Why everyone is trolling Ann these days?
atomic sapphire
Hi can anyone explain to me how to prove by induction? I know that it has to do something with P(n+1) but it's where I'm stuck, I don't know how to add numbers into the base case
Proof
Base case
Induction hypothesis
Induction step
I've been studying this for 2 weeks and I still don't understand 😭😭
lilac pivot
you prove you can reduce something to a base case
you prove the base case
that proves everything (since everything can be reduced to the base case, which was proven)
stray reef
Why everyone is trolling Ann these days?
my current working hypothesis is that i am, for reasons out of my control, an easy target
sour arrow
@atomic sapphire
"P(n)" here represents the statement.
The base case is to prove P(1). That is, prove the statement is true for 1. This is usually very easy, simply plug in 1 and show it fits the statement.
The inductive step is the hard part. You want to assume that P(n) is true, and with that, prove P(n + 1) is true.
atomic sapphire
@sour arrow could you give me an example of something to prove to see if I'm going in the right direction?
stray reef
why not try the classic "baby's first induction proof" problem
prove that 1 + 2 + ... + n = 1/2 n(n+1)
@atomic sapphire
sour arrow
You have a 3/4 probability that any given picture is bad.
After taking n pictures, there's a (3/4)^n probability that they're all bad.
Which means there's a 1 - (3/4)^n probability there's at least one good one
stray reef
at least 4/5 chance of a good picture = at most 1/5 chance of every picture being bad
sour arrow
Also can do that, yeah
stray reef
no?
calculate the probability that, upon taking n pictures, all n turn out to be bad
||it's (3/4)^n||
call a photo good if everyone's looking at the camera and bad otherwiwse
the probability of a good photo is 1/4 as given
so the probability of a bad photo is...?
now suppose you take 2 pictures
what is the probability they're both bad
and what if you take 3 pictures, what's the probability they're all bad
and if you take n pictures, what's the probability they're all bad?
the probability of getting at least one bad photo is at least 4/5
iff the probability of getting all bad photos is at most 1/5
stray reef
are you sure you haven't just burned yourself out for the time being
idk it sounds like you're burning out to me
maybe take a break
easy is subjective
also like no seriously set this aside
for as long as you need to
pale epoch
TIL geometry is much easier than probability
pale epoch
i think we have very different ideas of what geometry entails
you are talking about euclidean geometry, that you learned in school, so ok
faint narwhal
I mean everyone's good at different things
stray reef
easy is subjective
faint narwhal
I mean I was kind of the opposite in high school, relatively very good at probability and combinatorics and relatively very bad at geometry
stray reef
usefulness does not necessarily correlate with skill
geometry and probability both have their uses
pale epoch
tbh i almost never use probability in my daily life
stray reef
i use probability a fair bit when playing bridge
pale epoch
my phone does very little machine learning tbh
river yarrow
did I do this right?
Here is the original question: https://media.discordapp.net/attachments/496785905474994186/626820651386404875/Screen_Shot_2019-09-26_at_11.40.51_AM.png?width=501&height=38
Im supposed to prove that its valid using rules of inference
tropic cedar
I'd say every app that shapes according to your personal use of it is an example
sour arrow
Depends if you really know if it's 1/2
If you know this, then yes you have independence and the 29 times were an astronomical fluke
I think if something happens 29 times in a row, I'd bet it would happen again
Gambler's Fallacy is assigning a non-independent model to what should have an independent model. You hear gamblers say "I'm having good luck tonight" and stuff
I guess I'm not understanding what you're saying, no
faint narwhal
If you've seen 29 heads
The next one is still 50-50
29 heads and one tails in a row
Is just as likely as 29 heads and one head in a row
lilac pivot
isn't the gambler's fallacy wrongly associating past results with future probabilities
like zopherus said
if you see more heads in the past, there won't be more tails in the future to "balance" it out and get to 50/50 probability
stray reef
@weary tiger the probability of the first 29 of 30 coin flips coming up heads is 2^-29, and that of all 30 coming up heads is 2^-30
P(all 30 heads | first 29 heads) = 2^-30/2^-29 = 1/2
yeah the gambler's fallacy is failure to acknowledge that, however unlikely both streaks may be, the former has already happened and that fact affects the probability of the latter
cerulean ore
Pinter's Algebra book looks good
I am on 23rd page(trying to learn group theory)
and it is an interesting book
cerulean ore
If we would've talked about the set of non-negative integers
then the operation would have been a binary operation, right?
But, since, 4 and -4 both belongs to R therefore, that operation is not binary.
Right?
stray reef
it's not "this operation is not binary", it's "this isn't an operation at all"
it's binary alright
it takes two inputs
cerulean ore
Aah, thank you!
It was my mistake that I wrote "binary" without even thinking (even though the operation is binary but, it isn't even an operation)
1 and 0 are two integers, Let's assume that a*b = a+b / ab is an operation on the set Z. => 1*0 = (1+0)/0 => 1*0 = undefined According to the definition of an operation a*b for every a,b belongs to a set A the a*b should also belong to the set A. Since, the undefined doesn't belongs to set Z. Therefore, it is not an operation.
Book has explained it by : (and I cannot rely on my teacher)
Shouldn't I in the last line mention that Z is not closed under * as * can be an operation but, Z is not closed under *.
stray reef
honestly uh
your thing is ok idea-wise but very verbose
it's enough to say "1 * 0 is undefined, so this isn't an operation on Z"
i mean, it's ok to do what they did too
cerulean ore
Got it, I wrote it as same as I will be writing in the exams. (You know my intelligent teacher)
stray reef
what, does she dock points for failing to conform to that tongue-tying format?
cerulean ore
Suppose the question is of 15 marks but, can be proved in 4 lines.
But, 4<<15 for her so, add more lines.
cerulean ore
stray reef
if i gave a test and someone came up with a proof shorter than what i had for a problem, and the proof actually withstood scrutiny
i'd give them extra credit
also yeah no the pic you just posted is BS and you yourself just said exactly why
cerulean ore
https://www.math.wisc.edu/~mstemper2/Math/Pinter/Chapter02A (incase if you wanted to know the source)
I want to pursue Mathematics after my graduation but, not in India.
reef thistle
well
stray reef
you didn't need to post the link in a code block
reef thistle
I'm thinking just add "Let a = 1"
stray reef
now i have to copy paste it to open it
reef thistle
"Let b = 2"
cerulean ore
Sorry^
reef thistle
and so on, and your proof would hit 15 lines
stray reef
yes subtraction is an operation on Z
subtracting an integer from an integer gives you another integer
always
cerulean ore
Aah
I deviated from the basic definition of operation
and also misinterpreted :
a*b must be defined and be unambiguous
cerulean ore
lol
Why these books doesn't care to provide solutions, how do we check that if we're correct.
cerulean ore
What does it means by properties of an operation?
If it is an operation then it must follow the properties?
stray reef
:?
cerulean ore
Our teacher dictated us the properties of binary operation
Then, she mentioned that if these properties are followed then it is a binary operation.
cerulean ore
Closure, associative, commutative, identity, inverse, idempotent and distributive.
stray reef
uh
cerulean ore
omg, she is mad.
stray reef
yeah ok that's an odd mix
like
associativity and commutativity are properties an operation CAN have but aren't, like, mandatory
and if you want the operation(s) you're considering to have those, then you need to state those requirements yourself
an identity is an element in the operation's domain
which you need in order to talk about inverses (also elements)
idempotence is again a property of elements
distributivity is a relationship between two operations
yeah so like other than closure these aren't part of the defn of an operation lol
cerulean ore
Thank you very much for explaining!
cerulean ore
What is the generator of the group {0,1,2,3,4,5}?
what I know is a is the generator of group if a belongs to the group and b belongs to the group where b = a^n
But, online it says that 1 and 5 are generators of the above group
faint narwhal
Not a great description
But also, a set isn't a group, you need an operation on the set too
faint narwhal
I just think of the integers
and think about what conditions they satisfy
It's not too hard if you think about it as an abelian group plus a multiplication as well?
cerulean ore
That looks easy now
faint narwhal
Anyways, yes 1 and 5 are generators of that group