so like this
#discrete-math
past burrow
but is n = 1 for the inductive step for C.)?
if n is 1, it doesn't it not go through the a_n + 2n formula
doesnt it stops at the base case
past burrow
a_1 is equal to 0
and because of have a definition for a_1
you don't use the a_n + 2n formula for 1
it only applies to positive natural numbers other than 1
so why isnt C.) a_(n-1) + 2n - 2?
stray reef
you don't use the a_n + 2n formula for a_1
yes, and?
why is it a problem that you do not use the a_n + 2n formula to find a_1?
past burrow
why is it a problem that you do not use the a_n + 2n formula to find a_1?
because the base case covers a_1
stray reef
i fail to see your point
past burrow
ok let me show u how i got what i thought was right for the inductive step for 2c.)
stray reef
...can you please put some line breaks in that
it's impossible to read
but in any case, it looks like you wrote $$a_n = a_{n-1} + 2(n-1)...$$
vital dewBOT
Ann
stray reef
you just didn't translate that properly to the n+1 form of the recurrence relation
and i still do not see how you would ever need to apply the recurrence relation to find a_1 at any point
past burrow
you just didn't translate that properly to the n+1 form of the recurrence relati...
if i translate it to the n+1 form i would a_n + 2n?
wait i would
so arent both of these equivalences
stray reef
yes...
past burrow
i see also the basis step for d.) is 1 right not 0
pale epoch
you mean finite length binary strings
and well, what you describe is (more or less) the definition of countable
so you have to show that such a bijection exists
depends what you mean by that
there is sometimes a distinction between first and second diagonal argument
the first is what is commonly used to show Q countable, something like that works
the second is used to show that R (or sets of infinitely long strings) are uncountable, this wont apply
stray reef
did the other person delete their thing
pale epoch
seems so
stray reef
bruh
weary tiger
Hey cant i solve this problem like this?
is it wrong to show the inductive step like that?
keen python
That’s fine to do
But for this to work, your base case needs to be big enough
You’ll have to check 28, 29, …, (figure out the highest number to go up to so that your step above makes sense)
weary tiger
how do you mean
how many numbers will i have to check?
in the basis step i mean
and how do you know how many numbers you have to check
keen python
I’ll leave you with a hint
Suppose you just did 28
Then the k-4 you wrote wouldn’t make sense because you didn’t cover 24
weary tiger
I dont understand, if i do 28, 29, 30 etc 24 will still be left unkown
keen python
k+1 relies on checking k-4
weary tiger
how can i check 24 if it says n must be greater than or equal to28
keen python
28 needs 24, 29 needs 25, etc. but these numbers are too small to have, so you need to have these in the base case.
Keep doing this in the base case UNTIL they’re big enough to be supported BY the base case
weary tiger
oh so until 32 then right
isnt this confusing i have to know how my inductive step will be before i write basis step
keen python
Well it’s a good exercise because sometimes the base case is the most work and the inductive step is easy
I’ll leave you to finish it
weary tiger
yeah yeah thanks one more thing tho
cant every stamp problem like this
be written using my method?
keen python
No, it’s because 5 and 9 are coprime and 28 is specifically large enough
weary tiger
its 5 and 8
keen python
Typo but yeah still
weary tiger
okay thanks
turbid swallow
What does it mean "The preferences in the triangle are symmetric"?
stray reef
permuting everyone except merg will not change the preferences
turbid swallow
permuting everyone except merg will not change the preferences
Does this mean we can also assume Alex and Buddy Joe are matched equally? Or Robin and Buddy Joe?
Could we pick any couple from the triangle for our primary assumption?
turbid swallow
without loss of generality
Alright, thank you for your helpful input
stray reef
was that sarcastic or genuine?
turbid swallow
was that sarcastic or genuine?
Genuine. I'm sorry I was trying to be non emotional
stray reef
ok
turbid swallow
I was trying to let you know that your response matters, I try to do that with everyone. If I see anything nice in people, I try to let them know.
stray reef
i am bad at detecting sarcasm and sometimes i get false positives
turbid swallow
i am bad at detecting sarcasm and sometimes i get false positives
No problem, I understand 🙂 Thanks for responding to my query.
stray reef
np
pale epoch
if f(x)=y what is f(x,y)=?????? where f: N^2->N
this doesn't make a lot of sense
tall oxide
this doesn't make a lot of sense
and that's why I'm asking cuz in surjective function should be f(x)=y and we're given f(x,y)
it doesn't make sense on my side too
pale epoch
that's a wrong assumption you have
if your function is N^2 -> N, it should take 2 arguments
so the notation f(x, y) makes sense
vital dewBOT
nomnom
pale epoch
can you add length to the binary string by padding with 0s in the front?
pale epoch
then i would try to use this
tacit drum
i tried doing something with logs but defining x is really hard
pale epoch
ye i cant think of an immediate way
tacit drum
maybe i chose a hard definition
pale epoch
maybe there is some trick
my idea is taking the binary representation of some n in N won't work
because it some length, that contributes
so we have to look at shorter binary strings ..
hm
maybe just take the smallest power of two smaller than your number
and then make a string of that length that adds the remaining stuff
that should work probably?
tacit drum
all good, i tried doing that but im running into issues with x_10
pale epoch
lets look at an example, say 200
then you have 2^7 = 128 is your power of two
so look at strings of length 7
tacit drum
yep
pale epoch
then you want a binary string of length at most 7 that represents 200-128 = 72
tacit drum
ohhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
so u just add padding 0s at the start of the string
right?
pale epoch
,w 72 in binary
vital dewBOT
pale epoch
so in that case you dont even need padding
but in general if you just add padding its fine
like 0000000 just gets mapped to 128
or am i making a mistake?
pale epoch
huh?
pale epoch
1001000 should get mapped to 200
pale epoch
and for the general case you just have to show that the difference between the number and largest power of two still smaller doesnt get too large
so that the binary representation still "fits"
here you can work with log i think
hearty elbow
anyone understand negabinary?
base negative 2?
Can someone explain to me how you would add two negabinary numbers
stray reef
same as in 'normal' binary except carries get interesting i think
stray reef
well okay so like
1 + 1 = 110 in negabinary i think
4 + (-2)
so you would carry 1 each to two places to the left of the one you're adding
stray reef
one moment
hearty elbow
111001 = -23 and 110100 = -12
sorry my brain is messed up from staring at my own work
hearty elbow
sorry
stray reef
now i have to do it all over again
hearty elbow
these are the correct ones
stray reef
why carry it two places to the left?
both two places and one place
hm
this might result in an infinite carry loop
hearty elbow
yeah
tacit drum
how do i go about proving this
vital dewBOT
Ann
stray reef
$\floor{\log_2(y)} + 2^{\floor{\log_2(y)}} \geq y$
vital dewBOT
Ann
stray reef
this?
tacit drum
ye
stray reef
why did you need this to be true anyway
cinder flint
hello
tacit drum
im proving a function is onto and i had to add 0s to the beginning of my string
as padding
cinder flint
can anyone help me regarding computer science
tacit drum
and i needed 0^(the equation above)
so the value has to be positive
but i guess it could be negative
hearty elbow
can anyone help me regarding computer science
?
cinder flint
I need a help for maths
stray reef
........
hearty elbow
I need a help for maths
okay and?
cinder flint
Do you know how to convert cartesian coardinates into cylindrical coradintes, its realted with linear algebra
lapis kiln
Um... not sure why u would post this here? But either I am oblivious or it is trivially easy to convert from cartesian into clyndrical
r^2 = x^2 + y^2
z=z
$tan(\theta) = y/x$
vital dewBOT
Elonmosqito96
lapis kiln
Do you know how to convert cartesian coardinates into cylindrical coradintes, it...
also not sure how this is related to linear algebra....
real blaze
Why post it in discrete-math, then?
lapis kiln
Why post it in discrete-math, then?
litterly what i asked above xD
tidal tulip
can someone confirm: the definition of a partition is it’s a set of subsets such that “…” conditions hold. — i want to confirm it’s a set of subsets
tidal tulip
k this is why if A = {1,2,3} S = {{1,2,3}} is a partition but X={1,2,3} is not
yeah ^?
floral nacelle
Is this the math used in computer sci
limpid fern
yes
tidal tulip
@cerulean wind thanks!
tall oxide
How is (f^-1 ∘ f ) = Identity A dom f???
keen python
The same way arcsin(sin(x)) and sin(arcsin(x)) being equal to x only holds for specific domains
stray reef
How is (f^-1 ∘ f ) = Identity A dom f???
is this not part of the definition of f^-1????
knotty phoenix
Lets say there is a function $f: \mathbb{Z} \to \mathbb{Z}$ with the forward difference operator $\Delta f = n \mapsto (-1)^{[P(n)]} \cdot [Q(n)]$ where $[P(n)]$ and $[Q(n)]$ are predicates in Iverson brackets. Notice that $img(\Delta f) = \lbrace -1,0,1 \rbrace$. What's the name of such functions $f$?
stray reef
latex is choking on those URLs
vital dewBOT
JohnDark
knotty phoenix
Basically this is a counterpart of continuous functions for $f: \mathbb{Z} \to \mathbb{Z}$
vital dewBOT
JohnDark
stray reef
you're looking for functions where adjacent values differ by at most 1 from the looks of it
knotty phoenix
@stray reef That's what I'm looking for
stray reef
idt there's a special name for these
if you want to make up a name then by all means go for it
knotty phoenix
So that I can apply some of the ideas of infinitestimal calculus for the discrete case. I found it weird that discrete calculus in general didn't care about those
stray reef
what ideas are you looking to apply?
knotty phoenix
For now just intermediate value theorem
And then maybe something else
@stray reef Thank you!
Sorry for the delay!
ornate cliff
Is it possible to draw a logic circuit of the blue expression using only 2 input gates? This is what I've come up with but it uses 3 input gates.
pale epoch
you have to check if one input is irrelevant
(either simplify the expression algebraically and hope it works or just draw a truth table and check manually)
ornate cliff
the blue equation was after I minimized a function from a karnaugh map. Are you saying it can be simplified even further?
pale epoch
i didnt check but it must be if the question is correct
although "simplify" might not be the correct term
ornate cliff
Thank you for your help!
pale epoch
i would look at a truth table and see if there is an input where 0/1 have no effect
(i.e. its the same in both cases for all other possible inputs)
ornate cliff
Thanks for the tip! I’ll review the truth table and see if there is an instance of that.
desert edge
if A = {a,b}
Then how is | Ø x A | = 0?
The cardinality of A is 2 but isnt the cardinality of Ø = 1?
Im watching trevtutor and he said the cardinality of the set containing the empty set is 1
|{Ø}| = 1
desert edge
<@&286206848099549185>
weary tiger
Hey guys, why does what I have underlined work?
I don't get it.
for example 2 cannot be written as product of primes
prime parcel
for example 2 cannot be written as product of primes
It's prime itself so 2 is prime factorization of 2
prime parcel
if A = {a,b}
Then how is | Ø x A | = 0?
The cardinality of A is 2 but isnt the ...
Cardinality of $B= \phi$ is $0$ while $B = {\phi}$ is $1$
vital dewBOT
it's Sam
pale epoch
so its a product of prime?
2 is already a product
a "degenerate" one somehow
but its a product with 1 factor
weary tiger
got it thanks
pale epoch
the statement even says one or more factors
(if you allow the empty product with no factors, you can even write 1 as a product of primes)
weary tiger
yep got it
stray reef
Cardinality of $B= \phi$ is $0$ while $B = \{\phi\}$ is $1$
do not use the letter phi to denote the empty set.
limber hamlet
Hey is there anyone who can help me out with this question? I'm seriously bad at discrete and dont know how to do this
iron mirage
Is 0 considered a natural number in PA?
desert edge
Cardinality of $B= \phi$ is $0$ while $B = \{\phi\}$ is $1$
ty:D sry late reply
pale epoch
Is 0 considered a natural number in PA?
it differs
i guess you probably want 0 to be natural to define addition better
desert edge
Why is there no line above intersect sign in de morgans law?
dire estuary
That would make union and intersection the same
desert edge
Huh?
dire estuary
If not (a or b) = not (a and b) you could remove not on both sides and they'd be equal. This is a contradiction. The correct equation is instead not (a or b) = (not a) and (not b)
desert edge
why am i having a hard time understanding that
so
not(a or b) = not ( a and b ) is not the same as not( a or b) = (not a) and (not b) ?
dire estuary
Right
desert edge
but the not is just distributed. why does that make a difference
dire estuary
Let's look at an example
(not true) and (not false) = false and true = false
not (true and false) = not false = true
Its in my discrete math playlist. Proofs in set theory
dire estuary
There are a lot of similarities between set operations, Boolean logic, and even arithmetic.
desert edge
dude this is such a mind fuck in a way, sorry the language
and it really bothers me why i cant see whats going on
So basically the bar above union, indicates a switch from or to and?
dire estuary
but the not is just distributed. why does that make a difference
The not isn’t just distributed! Distribution would be something like a(b + c) = ab + bc. Notice how both sides use +. However with De Morgan’s law, you don’t use ∪ on both sides; you use ∪ on one side and ∩ on the other side.
coral raven
so not(A or B) is the opposite of that
desert edge
Im gonna paint real quick, sec
oh i sorta see
no i actually got confused again
jesus christ
why cant i see why we dont just draw a full bar above a intersect b
cause not(a and b) =/= not(a) and not(b)
but that doesnt make any sense
to me
dire estuary
The bar means not
If you not separately on a and b, you only put a bar above a and b
coral raven
lelt A be if an apple is a fruit, and B be if an apple is a vegetable
then A and B is False, so not(A or B) is True
but not A and not B is True and False is False
desert edge
so thats just it? You dont put bar above, cause you do them separately
is that the indication?
coral raven
yeah
the bar is only over what it's inverting
on the left side the bar is inverting the whole thing
on the right side each bar inverts each thing, and then you do the and
desert edge
Is hta talso what happens here
He goes from x is not in B and C
to x is in notB or x is in notC
theres that switch from and to or again
dire estuary
If x isn’t in both B and C, then it must be at least absent from B or absent from C
desert edge
So we flip from intersect to union, if theres a not infront
by infront, i mean its affected by a not
dire estuary
Not just that, but you also invert the operands
$\overline{A \cup B} ≠ A \cap B \ \overline{A \cup B} = \overline{A} \cap \overline{B}$
vital dewBOT
foldr
desert edge
Ok im almost there I think
so the flip wouldnt happen if it was not(A) or not(B), right
dire estuary
Say you go to the store to buy milk and eggs. But the store is out of milk.
Did you get milk and eggs? No, you only got eggs.
Did you not get milk or not get eggs? Yes, you did not get milk or not get eggs.
desert edge
:DD fun example but I get the idea
desert edge
Shouldnt the one below be everything outside the circles too
as its not(A) and not(B)
desert edge
oh yeah
cerulean wind
Its the same as the first box
desert edge
cause not(B) is everything excluding B, so it includes A
cerulean wind
right
desert edge
and its the same case with not(A) so it leaves the intersection only
i need to learn how to use venn diagrams
dire estuary
If A and B overlap then not(B) does not contain all of A
desert edge
ok I think im pretty much set. It was mostly the flip that was causing issues
cerulean wind
i need to learn how to use venn diagrams
they're super useful
desert edge
Yeah for sure. Clarifies it alot
cerulean wind
drawing a venn diagram with, id say, more than three circles correctly is hard tho
vital dewBOT
dire estuary
Note that the law also goes the other way around
vital dewBOT
foldr
cerulean wind
there we go
desert edge
Trying to apply the egg milk analogy to this one
But I get the idea atleast and thats whats most important:D Clarification
dire estuary
I think the egg milk example actually used this law :p
desert edge
fair:D
fallow sundial
Can somebody help me understand why |a| and |b| must be less than p/2 here? I've been trying to see why it follows from the previous steps but I just don't get it
past burrow
can anyone check if i did this right pls
weary tiger
Anyone has any idea how to solve this? I have an idea how i would do it with mathematical induction, but don't know how to do it with WOP
cerulean wind
suppose that the set of natural numbers S = {n in N : the sum of the first n odd numbers is not n squared, n >1} is non-empty
then it has a least element, call it m
cerulean wind
sorta yea
cerulean wind
so m is at least 2
m - 1 is at least 1
and m - 1 is not in S
so the sum of the first m - 1 odd numbers is (m - 1)^2
use this fact to show that the sum of the first m odd numbers is in fact m^2
cerulean wind
is zero a natural number for u?
weary tiger
but i am not saying n >= 0
i am saying n > 0
it even says in the example
show for every positive integer n > 0
cerulean wind
because we know it’s true for n = 1. we need a nice floor/lower bound on S to make this argument work
the sum of the first odd number is 1 = 1^2, so 1 can’t be in S, i guess is the correct argument
that’s more analogous to the base case with induction
so lets rephrase a bit
weary tiger
okay
cerulean wind
suppose that the set S = {n in N : the sum of the first n odd numbers is not n^2} is non-empty
1 cannot be in S, since the sum of the first odd number is 1 = 1^2
weary tiger
okay so we start with 2
cerulean wind
so S is bounded below by both 1 and 2, and non-empty
so it has a minimal element by WOP
stray reef
isn't it possible to translate any induction proof into a WOP proof?
cerulean wind
isn't it possible to translate any induction proof into a WOP proof?
they’re equivalent
stray reef
yeah
cerulean wind
so it has a minimal element by WOP
call this minimal element m
then m - 1 is not in S
so the sum of the first m - 1 odd numbers is (m - 1)^2
weary tiger
right
cerulean wind
use this to show that the sum of the first m odd numbers is in fact also m^2
contradicting the fact that m was the minimal element of S
weary tiger
i got everything until this point
weary tiger
use this to show that the sum of the first m odd numbers is in fact also m^2
I just dont understand this
stray reef
||suppose we have proofs of P(0) and ∀n(P(n) -> P(n+1))
let S = {n ∈ N: !P(n)}; we know 0 ∉ S because P(0), so S is bounded below by 1.
suppose S is nonempty; then by WOP, m := min(S) exists and is greater than or equal to 1. since m ∈ S, we have !P(m).
since m = min(S), everything less than m is not in S; in particular, m-1 ∉ S and hence P(m-1).
but since we know ∀n(P(n) -> P(n+1)), in particular we know P(m-1) -> P(m), and hence P(m).
we now have both P(m) and !P(m). this is a contradiction.||
stray reef
I just dont understand this
they're saying to show that $1 + 3 + \cdots + (2m-3) = (m-1)^2$ implies $1 + 3 + \cdots + (2m-1) = m^2$
cerulean wind
I just dont understand this
if u look at this, i’m doing exactly the same thing that ann’s proof is saying
vital dewBOT
Ann
weary tiger
okay 1 sec
weary tiger
ahhhhh right
i got it now
thanks a lot Ann and c squared
you put a lot of effort into explaining this!
stray reef
i do think it's kind of silly to make you use WOP for something like this tbh
stray reef
it makes the proof needlessly convoluted
WOP is better when you already have something that talks about subsets of N
cerulean wind
i learned it from a dude in this server lmao
weary tiger
lol did he tutor you or something?
cerulean wind
nah we were just talking about some stuff
cerulean wind
right
stray reef
learn what
weary tiger
discrete math
cerulean wind
i thought u were referring to WOP equivalent to induction
weary tiger
I meant both, you learn WOP when you learn discrete math.
cerulean wind
i learned WOP and induction in an analysis class.
stray reef
i never really had discrete math as a class in its own right
cerulean wind
not even like a combinatorics/graph theory class?
stray reef
combinatorics and some basic graph theory were just part of math class i guess
placid cairn
how do I prove $A$ is countable $\iff A - {0}$ is countable
vital dewBOT
Hexagon
pale epoch
by writing down the bijection
placid cairn
then how do I show the other set is therefore bijective with N
cerulean wind
if A is finite, then it is in bijection with N_n = {1,2,…,n} for some n in N
if n = 1, that is, |A| = 1, then A - {0} is empty and ur done
otherwise, A - {0} is in bijection with N_{n-1} which should be really easy to show
(all of this is assuming that 0 is in A, otherwise A - {0} = A, in which case ur also done)
for the infinite case, try getting a bijection between N and N - {0} first (assuming ur natural numbers start with 0. if they don’t, just get a bijection between N and N - {1})
signal basin
How many quadratic submatrices does this matrix have?
I mean: is there a fast way of calculating it?
stray reef
what's a quadratic submatrix
signal basin
you know: e.g. n x n matrix. i think the common word in english is "square matrix". sorry @stray reef
stray reef
okay, so if you know they're more commonly called square, then why not call them square
so you want to ask how many square submatrices a 4 by 4 matrix has.
signal basin
okay, so if you know they're more commonly called _square_, then why not call th...
becuase it said "quadratic" in my textbook...
signal basin
so you want to ask how many square submatrices a 4 by 4 matrix has.
yes
stray reef
please do not reply-ping me so often.
signal basin
alright.
stray reef
...wait, can you show the problem as it appears in your textbook?
i'm getting a strange suspicion
i want to clear it before we proceed
signal basin
okay, let me find it in the textbook. i just the screen short from my professors slides in which she talks about something called TU matrcies.
direclty from the textbook:
stray reef
.......
well ok
it feels a bit weird that you saying quadratic = square means we can just ignore everything about this matrix except its size
anyway the answer would be $\sum_{k=1}^{n} \binom{n}{k}^2$; subtract 1 if you want only proper submatrices
vital dewBOT
Ann
stray reef
this sum is equal to $\binom{2n}{n} - 1$, for which there is a mildly pleasing combinatorial proof
vital dewBOT
Ann
signal basin
i understand that. but the context is operation research and I did not want to mention this since it's unnecessary.
thanks
signal basin
If A is TU, a ij ∈ {+1, −1, 0} for all i, j.
stray reef
ah.
and... are you sure your prof defined 'quadratic submatrix' to mean any square submatrix
stray reef
then you would have $\sum_{k=1}^{\min(m,n)} \binom{m}{k} \binom{n}{k}$
vital dewBOT
Ann
placid cairn
for the infinite case, try getting a bijection between N and N - {0} first (assu...
why are we considering N and not A here. shouldnt it be a bijection between A, N <-> bijection between A{0},N
cerulean wind
yes but getting a bijection between N and N - {0} is the missing link to prove this
frosty bay
started learning discrete maths and now i finally understand why the cartesian plane is called R^2
or why n-dimensions of space is R^n
cartesian products.....
frosty bay
quick question, if the ordered pair (a,b) can be expressed as {{a}, {a, b}}
does this mean that (a, b, c) can be expressed as {{a}, {a,b}, {a,b,c}}
cerulean wind
no
(a,b,c) is ((a,b),c)
so it is {{(a,b)},{(a,b),c}}
which is just more of a mess if u expand out what (a,b) is
frosty bay
oh huh, thats interesting but also kind of awful at the same time
i dont get why this definition for ordered n-tuples is used anyway
why not uh
(a, b) being {{0, a}, {1, b}} and so on
each element paired up with an ordinal
cerulean wind
that also works
the main thing you want ur definition of ordered pairs to do is to have (a,b) = (c,d) if and only if a = c and b = d
once you do that, u can do recursive defs for all of the n tuples pretty sure
frosty bay
(a, b) being {{0, a}, {1, b}} and so on
hmmm
i guess this doesnt work in the specific case of (0, 1) because that'd be {{0}, {1}} which doesn't imply a specific order
unless im mistaken
frosty bay
oh would there be a distinction between the "ordinal" and the actual number itself
cerulean wind
actually nvm
u can just tag the sets a diff way
so instead do {{{0},a},{{1},b}}
and it’s just a whole nother layer deeper
because now wat if a = {0}
b = {1}
nvm
frosty bay
lmao its an infinite recursion problem
{{{{{{{{0}}}}}}}}, a}, {{{{{{{{{1}}}}}}}}}, b}}
cerulean wind
this feels like a question for another guy ik on here whose really good with this stuff.
but what you can do is accept things like urr elements that aren’t sets, and use those. like extra reserved symbols added to your set theory
so instead just make
(a,b) = {{ :), a},{ :(, b}}
frosty bay
smiley face ordered pair
cerulean wind
yes. the best ordered pair
frosty bay
(a, b) being {{0, a}, {1, b}} and so on
yeah im curious if someone more knowledgeable can explain this, its pretty intriguing
cerulean wind
but then u run into the issue of, oh no. what if there’s only countably many symbols and i want to have an uncountable ordered tuple
frosty bay
wait
is that even possible
to ahve an uncountable ordered tuple
isnt the fact that its ordered means there's an inherent ordinality
cerulean wind
but then u run into the issue of, oh no. what if there’s only countably many sym...
let me check rq if i’m just saying crank math or not. hold up
frosty bay
this is melting my brain
cerulean wind
don’t think i am but i’m just not knowledgeable enough to say anything more about it.
frosty bay
crank math
pale epoch
yeah im curious if someone more knowledgeable can explain this, its pretty intri...
this is the original definition
with the added requirement that 0, 1 are distinct symbols different from the elements of the tuple
frosty bay
oh would there be a distinction between the "ordinal" and the actual number itse...
yeah this is what i mentioned here!
thats pretty cool
but im curious, if thats the original definition why is the Kuratowski definition more..popular?
or rather, why its not the standard in textbooks
pale epoch
it does not rely on additional symbols
frosty bay
ah thats fair enough
pale epoch
i mean ultimately it doesnt matter
you could just as well add tuples as primitives
you just dont want that for technical reasons so you have to come up with something else
also what is an ordered tuple 🤔
frosty bay
honestly the Kuratowski definition is insanely clever
but now im more interested in going through more set theory so i can understand why adding tuples as a primitive is problematic
pale epoch
its not problematic
you just want less axioms
like, tuples (or the idea of them) existed before formalized set theory
and when people decided to build all of math on ZFC, they had to build tuples
otherwise you would need more "overhead", like stating that the empty tuple exists and how to build tuples
better to just make them sets
frosty bay
ohhh i see
so its just a matter of us humans not wanting to muck things up by adding unnecessary axioms
pale epoch
pretty much
frosty bay
man, this is really cool
thank you
weary tiger
Hi again
Here it asks me show that integeres are powers of 3
however in recursive step it states xy
shouldn't it have said divisible by 3 ?
NVM got it
surreal sand
if you have this relation
how would you prove it's reflective, symmetric, asymmetric, transitive
are you supposed to move the equation arround so 3m - 1 = -n?
amber prism
how would you prove it's reflective, symmetric, asymmetric, transitive
Check them by definition
surreal sand
yeah i know but i don't know how to do it when both the variables are on the left haha
amber prism
Reflexive:
is it true that mRn = nRm in general?
surreal sand
only if it's symmetric right?
amber prism
oh sorry I meant symmetric
surreal sand
reflexive aRa for all A
amber prism
is it true that mRn => nRm for all (m,n) in A^2
surreal sand
no since - numbers right?
surreal sand
its in Z
amber prism
ok so yeah, it's not true
cause imagine the lines 3x+y=1 and 3y+x=1 over Z^2
They're 2 distinct lines that only cross once (not at a point in Z^2), so there's not even a single point where it's true let alone all of Z^2
surreal sand
If it was aRb 2a + 3=b i find it easy to prove everything but when i have both the variable on the left with 3m + n = 1 i find it very difficult
haha
timber cave
S denotes the set of real numbers strictly between 0 and 1. That is, S = {x ∈ R | 0 < x < 1}
Let a and b be real numbers with a < b, and suppose that W = {x ∈ R | a < x < b|. Prove that S and W have the same cardinality
Anybody able to do a in-depth explanation / workthrough? Really lost on cardinality of sets stuff
cerulean wind
this is just trying to find a bijection from (0,1) to (a,b)
timber cave
I'm not even particularly sure on how to prove two sets have a bijection
cerulean wind
a bijection between two sets X and Y is a function f : X --> Y that is both injective and surjective
timber cave
Yeah, I know the definition, just not really sure how to prove it
cerulean wind
well first you need a function from (0,1) to (a,b) to event attempt anything
timber cave
Do you just make up a function? And how would you know what it'd look like
cerulean wind
this one is easy enough to visualize and then write down
i would imagine the x-y plane, and focus on the interval (0,1) on the x-axis
then imagine all of (a,b) lying somewhere on the y-axis
actually, let me just draw it
timber cave
I can invision that, I just don't see how you'd get a function from it
cerulean wind
the red line is the function you want to make (it is not the only function that works, however)
from (0,1) to (a,b)
timber cave
so it'd be like..
f: S -> W
f(x) = ???
cerulean wind
do you know the equation of a line
timber cave
uhh
cerulean wind
(y_2 - y_1)/(x_2 - x_1) ring a bell?
timber cave
yeah
timber cave
so f(x) = b - a would be the function?
cerulean wind
no, we just found the slope of the line that will become our function
cerulean wind
so f(x) = b - a would be the function?
sanity check, b - a might not even be in (a,b), and b - a is a constant function. cant possibly be a bijection
so we know that our function will be of the form f(x) = (b-a)x + y_0 where x is in (0,1). we just need to find y-intercept, y_0
timber cave
y_0 is a isnt it?
cerulean wind
yup
now you just need to check that the function f : (0,1) --> (a,b) given by f(x) = (b-a)x + a is a bijection
timber cave
so to check that it's injective you'd want to
cerulean wind
there are several ways to do this. one could check that f is injective and surjective, or explicitly find the inverse
timber cave
pretty sure the way my professor wants is to check that it's injective and surjective
cerulean wind
okay, do you know how to check if a function is injective?
timber cave
not really
cerulean wind
a function f : X --> Y is injective provided that for all a,b in X, if f(a) = f(b), then a = b
a function f : X --> Y is surjective provided that for all y in Y, there exists an x in X such that f(x) = y
cerulean wind
now you just need to check that the function f : (0,1) --> (a,b) given by f(x) =...
for our problem, to check injectivity, let x,y in (0,1) and suppose f(x) = f(y)
you need to some how show this implies x = y (all this involves is some algebraic manipulations)
timber cave
Okay so it'd be like
(b-a)x + a = (b-a)y+a
divide both sides by (b-a) and then subtract a from both sides?
therefore x = y?
cerulean wind
divide both sides by (b-a) and then subtract a from both sides?
reverse this order. so subtract a from both sides, then divide by b-a, since its not zero
but yes
timber cave
okay
cerulean wind
nice, we showed that f is injective.
for surjectivity, fix y in (a,b). then a < y < b. we need to find x in (0,1) such that f(x) = y
timber cave
wym fix y in (a, b) ?
cerulean wind
just let y be any element in (a,b)
timber cave
oh, ok
cerulean wind
it cant move or change its value throughout the proof
its fixed in place
anyway, to get started, do you see that we have 0 < y - a < b - a from a < y < b?
wheat leaf
Can anyone help with these problems?
cerulean wind
we need to find an x in (0,1) so that f(x) = y. im just trying to move closer towards that
timber cave
ok
cerulean wind
anyway, to get started, do you see that we have 0 < y - a < b - a from a < y < b...
do you agree with this though?
timber cave
yeah makes sense
cerulean wind
okay, now divide everything by (b-a)
timber cave
0 < (y-a)/(b-a) < 1
cerulean wind
yup
timber cave
so the x is y-a/b-a
timber cave
ok, and since it's surjective and injective, there's a bijection, therefore same cardinality
cerulean wind
yea, you got it
timber cave
ok, thanks!
marble pivot
A guy said that $$\neg \forall x, P(x) \equiv \exists x , \neg P(x)$$ by De Morgan’s law
vital dewBOT
abs_0
dire estuary
If P(x) is not true for all x then there must be some x for which P(x) is not true. If there exists some x for which P(x) is not true then P(x) is not true for all x.
Forall corresponds to conjunction and exists corresponds to disjunction
Brb sleep
frosty bay
can someone explain or point me to a good explanation of strings?
the textbook im using only gives the definition using and some examples and its not super intuitive
Let n be a positive integer. Given a finite set A, a string of length n over A is an ordered n-tuple of elements of A written without parentheses or commas.
wait nevermind, i figured it out
it just means stringing together the elements of the set
marble pivot
Forall corresponds to conjunction and exists corresponds to disjunction
I understand intuitively why it’s true, but how is that formal? Do forall and exists have definitions based on more foundational logical operations, or are they at “rock bottom” so to speak?
paper sluice
My attempts for i and ii. Hoping someone could check those and also help me through iii as I don't know where to begin with that
stray reef
15i: your explanation amounts to saying E ⊆ Z and O ⊆ Z. that alone does not make {E,O} a partition.
15ii: S_1 is the set of all subsets of A which do not contain w. the very first thing you list as being a member of S_1 contains w despite it not being supposed to. i have a suspicion that the most crucial part of the statement of part ii just escaped your attention somehow.
also your slashes are the wrong way around in part iii. it's \ not /
paper sluice
15i: your explanation amounts to saying E ⊆ Z and O ⊆ Z. that alone does not mak...
I dont really remember being taught partitions so I'm kind of confused on how to do that one
stray reef
so you're expected to verify whether or not something is a partition without knowing what a partition is?
pray tell how they expect you to do so.
paper sluice
Also, I read part ii wrong, thanks
for part iii, i didnt really know why it was \ so thought they meant /.
stray reef
the set difference symbol is a backslash.
that's all there is to it
anyway, a partition of a set S is a collection of pairwise disjoint subsets of S whose union is all of S
you might say it is a collection of 'parts' which do not overlap and which together make the whole.
paper sluice
anyway, a partition of a set S is a collection of *pairwise disjoint* subsets of...
ohh ok thank you. I know of the definition but have never been told that its a partition
paper sluice
how can you know the definition but not the word being defined?
well when i say I know of, i just remember it being mentioned
maybe they did mention partition idk, but it must have been a vague mention
paper sluice
the set difference symbol is a backslash.
I've redone i and ii, but still dotn know how to do iii.
stray reef
do you have the laws of set algebra written out somewhere?
paper sluice
do you have the laws of set algebra written out somewhere?
No
I should probably write them down for future use
I've been googling it for now
stray reef
to be fair it's a little strange what they ask for here
it's gonna be an exercise in symbol pushing either way but it sounds like they explicitly do not want you to do an element-chasing argument
paper sluice
I think it does want me to
Cause I don't know what other way they want me to do
Something like this?
Feels like it's wrong
marble pivot
sorry, accidental ping
Does pairwise disjoint vs. disjoint mean that any pair of sets is disjoint, as opposed to the whole union being the empty set
stray reef
Something like this?
no this is bad
on two accounts
one, you're making a huge leap in logic, and two, separately from that you're starting your argument with your goal
if you're going to talk about complements then you should first say $$A \setminus (B \cap C) = A \cap (B\cap C)'$$
vital dewBOT
Ann
stray reef
then apply de morgan's law to get $$A \cap (B\cap C)' = A \cap (B' \cup C')$$
vital dewBOT
Ann
stray reef
then apply the distributive law as you did to get $$A \cap (B' \cup C') = (A \cap B') \cup (A \cap C')$$
vital dewBOT
Ann
marble pivot
did you mean the whole intersection
whoops, yes. Is the purpose of ``pairwise'' that it would prevent something like
$$S = {a, b, c, d}$$ $$pi_S = {{a, b}, {b, c}, {d}}$$ from being a partition?
stray reef
\{ \}
vital dewBOT
abs_0
stray reef
and... i guess you could say that
you don't want the same point to end up in two different parts simultaneously
stray reef
yes
elder steppe
how do you solve this problem
marble pivot
how do you solve this problem
first maybe figure out how many people have the same birthday
then within that subset, show that 7 of them must have the same initials
elder steppe
ok that makes sense but i'm a little confused on how to figure out how many people have the same bday
marble pivot
oh that's easy here
there are 365 days in a year, and there are 39 million people. The maximum amount of people with the same birthday is 39 million (they all have the same birthday), and the minimum amount is 39000000/365 ≈ 106,849 (each day in the year has the same amount of ppl)
does that make sense
idk if I did that right
stray reef
i think you're overcomplicating it
how many combinations of (birthday, first initial, middle initial, last initial) are there?
,calc 365 * 26^3
vital dewBOT
Result:
6.41524e+6
6.4 ish million
marble pivot
so there are 6.4 million unique (birthday, F, M, L) combinations?
elder steppe
oh ok this makes sense
vital dewBOT
Result:
3.849144e+7
this is less than 39mil
marble pivot
wait what's the * 6 about
paper sluice
thank you for your help, i get it now :D @.Ann
stray reef
wait what's the * 6 about
how many people we could have at most if no seven were to share the same bd and initials
elder steppe
Can someone check my answers for this?
stray reef
give us your answers :p
elder steppe
a) 10^6 b) 10 * 9 * 8 * 7 * 6 * 5 c) 10^6 - 9^6 d) 10 * 9^2 e) idk how to do this one
stray reef
d is wrong, everything else is correct
for e, count the following:
- the number of ways to choose 2 places within the string
- the number of ways to fill those 2 places with vowels
- the number of ways to fill the rest with consonants
marble pivot
how many people we could have at most if no seven were to share the same bd and ...
I've been trying to think about this, and I don't get it
stray reef
I've been trying to think about this, and I don't get it
if no 7 people share the same combo of bd and initials then there are at most 6 people having each combo and hence at most the number i calculated in total
elder steppe
for e, count the following:
- the number of ways to choose 2 places within the s...
for the first one, would it be 9! since 2 places would be a pair and that pair would count as one spot?
marble pivot
if no 7 people share the same combo of bd and initials then there are at most 6 ...
wow
you have a way of writing very concise but great explanations
lol
stray reef
thank you
stray reef
for the first one, would it be 9! since 2 places would be a pair and that pair w...
i'm not asking you to count the rearrangements of the word PPQRSTUVWX
elder steppe
i don't think this is right but i ended up with C(6,2) * 3^2 * 7^4 as my answer
so 15 * 9 * 7^4
@stray reef
stray reef
two different vowels, and also why 7^4?
elder steppe
i have no idea about the 4 tbh
elder steppe
d is wrong, everything else is correct
why is d wrong
stray reef
i can't even tell what your reasoning was for it
elder steppe
i was just following how my teacher did a similar problem
well how would you approach it?
elder steppe
i wouldn't say mindlessly lol i just did it how i understood it from class
where does the power of 4 come from?
stray reef
6C2 is the number of ways to pick two places within the string where the c's go
there are 4 more places left and each one can be filled with one of 9 letters
marble pivot
@.Ann is (e) this: ||7^3 * 3 * 2 = 2058 since there are 7^3 ways to do consonants and 3 * 2 ways to do two unique vowels||
stray reef
||7^4 not 7^3||
marble pivot
||ah because length 6. But I have a question (perhaps I'm overthinking this again): I feel like I'm only counting the strings assuming the first four letters are fixed as consonants and the last two are fixed as vowels. And now I need to count all the ways the order could change (eg c-v-c-c-c-v, v-c-c-v-c-c, etc) by multiplying the whole thing by 6!. I assume this is not necessary. Why?||
@stray reef ^ for ping in case
stray reef
||oh wait hold on no||
||you're missing 6C2 not 6! there||
wait
nvm
you've got me confused too now
marble pivot
lol
ok wait if you have three sets of symbols
{?, !, .}
{a, b, c, d, e, f}
{1, 2, 3, 4, 5, 6, 7, 8, 9}
and you want to count how many words you can make, with exactly one element from each set
how do you do that
stray reef
??? isn't this just 3 * 6 * 9 * 3!?
marble pivot
oh I guess that makes sense lol
wait where is the 3! coming from
number of ways to rearrange the letters for a given word?
stray reef
number of ways to rearrange the symbol sets yes
marble pivot
ok so then that would make the other problem with vowels just
7^4 * 3 * 2 * 6!
right?
marble pivot
wait why
marble pivot
{?, !, .}
{a, b, c, d, e, f}
{1, 2, 3, 4, 5, 6, 7, 8, 9}
can't you use the same reasoning as this?
stray reef
the symbol sets are not disjoint in this case
marble pivot
Oh wait yeah ur right
If we do 4 copies of the consonant set with subscripts b_1, b_2, … and one vowel set, then
When we say $7^4\cdot3\cdot2 \cdot6!$ we are counting $$b_1b_2c_1d_1ae\quad \text{and}\quad b_2b_1c_1d_1ae$$ as unique
vital dewBOT
abs_0
marble pivot
How do we fix that?
weary tiger
get an A on either test. Find: the number of students who got:
(a) an A on both tests;
(b) an A on the first test but not the second;
(c) an A on the second test but not the first.
Hey guys, how do we do b and c? I think (a) is 4 since 10 + 9 - 15 = 4. But i dont know about b and c.
I have to do it with inclusion-exclusion principle btw
prime parcel
```In a class of 30 students, 10 got A on the first test, 9 got A on a second te...
10 got A on first test and out of them 4 got A in both test so how many got A in first test only?
prime parcel
<@!734794827077648586> 6 right
For first yes
prime parcel
and 5 on the second but not first?
For c it will be 15-4
weary tiger
For c it will be 15-4
but that doesnt make any sense
everyone who got an A in second test did not get an A in first?
prime parcel
everyone who got an A in second test did not get an A in first?
Edit : There are 4 people who scored A in 2nd that scored A in 1st so it's 9-4 (I forgot it was 9)
weary tiger
so i was right?
prime parcel
Yes
weary tiger
Ok thanks a lot, really helpful
prime parcel
elder steppe
for the codomain, can I just pick any n value for x^n to find a y value?
btw the question is asking me to draw an arrow diagram for that relation
half lion
for the codomain, can I just pick any n value for x^n to find a y value?
yes. The relation says xPy if there is a positive integer n s.t x^n=y
so like {2,6} doesn’t have this relation, but some of P will
agile magnet
Not sure where else to drop this
say I have a number n
and I sum it's digits
so like 81 -> 9
I know the number of digits of n is ~log_10(n)
but is there a good bound on what that total value is?
coral raven
it's greater or equal to 0
agile magnet
coral raven
and less than 9 * ceiling(log_10(n))
coral raven
i mean i can explicitly give you something that has exactly that upper bound
9, 99, 999, should work
modulo an off-by-one error in the log function
keen lava
Where should I even start for this problem? I'm completely drawing a blank
coral raven
first find an injective function from Z to Z which is not surjective
and then for any element of the power set, take its elements and map them with that function
to another element of the power set
keen lava
Would something like f(x)={if x>=0 f(x)=x and if x<0 f(x)=x-1 work?
coral raven
that works
if you apply that to the power set you'll never hit anything with a -1 in it
wait
no i think that works
it's definitely not surjective
yeah should work
keen lava
I'm trying to think through your response, you are saying take some a in P(Z) and do what with it? Sorry, I'm new to functions and this shit is blowing my mind
coral raven
take some injective but non-surjective function f: Z -> Z
then define F: P(Z) -> P(Z) where F({z1, z2, ...}) = {f(z1), f(z2), ...}
cerulean wind
I'm trying to think through your response, you are saying take some a in P(Z) an...
try f(x) = 2x from Z to Z
keen lava
I don't see how that isn't surjective
cerulean wind
that one is not nice tho lol
coral raven
I don't see how that isn't surjective
f isn't surjective
keen lava
oh because it skips over 1 and 3 etc
keen lava
that makes sense my bad
cerulean wind
so for a subset S of P(Z), what would the image of S look like? (that is, what is f(S) if f(x) = 2x)
keen lava
would it just double each individual element?
cerulean wind
right. so for the set S = {-1,0,1}, we would get f(S) = {-2,0,2}, and we might as well call this set 2S
for notation sake
your pretty much done now
see if you can come up with what the function would be from P(Z) to P(Z)
keen lava
Okay, so I wrote F:P(Z) maps to P(Z) can be defined as F(S) = 2S where S is a subset of P(Z), would that work or am I missing the big picture?
or does scalar multiplication not work with sets like that? Would I need to do set builder notation?
cerulean wind
Okay, so I wrote F:P(Z) maps to P(Z) can be defined as F(S) = 2S where S is a su...
thats right
cerulean wind
or does scalar multiplication not work with sets like that? Would I need to do s...
2S is just an abbreviation/renaming for the set f(S)
keen lava
Alright, ty for the help
cerulean wind
you dont have to use 2S notation either, you could use f(S). i just thought it was neat that f(x) = 2x and F(S) = 2S (= f(S)) had kinda the same form if you write it like that
cerulean wind
Alright, ty for the help
and yw
keen lava
If you want to go for round two:
I understand the solution, I think at least, but I have no clue how to convey it mathematically
coral raven
define cardinality
keen lava
Size of the set, like {0,1} would have a cardinality of 2
cerulean wind
definition by example
lol, whats your working definition for when two sets have the same cardinality
keen lava
What do you mean?
Notation wise I think it would be something like |A| = |B|
sort of like magnitude with vectors
cerulean wind
typically "|A| = |B|" is an abbreviation for "there exists a bijection from A to B"
thats why we were asking
keen lava
Ah, I haven't seen that yet, my bad
cerulean wind
um... @coral raven you know how to work around this if we dont know what cardinality means? lol
keen lava
Oh, I said it earlier, it is the size of the set/number of elements in a set
I just don't know how to do a formal proof with it
coral raven
??
no
the precise definition is that there's a bijection from A to B
so basically you want to show that if there's a bijection from A to B and they're finite, then any injection is a surjection also, ie. it's another bijection
keen lava
We haven't used that definition in class, I think we are supposed to assume it means they have the same number of elements. Other wise proving that it is surjective would be trivial since it would be a bijection
coral raven
no
it's not the same bijection
or it doesn't have to be
you have an injection
it should be a bijection, but you have to show it is
given that some other bijection exists
might be utterly off my rocker i am very tired
cerulean wind
nah ur good bro
having an injection says that each element from A gets mapped to a unique element in B
keen lava
What I have right now is: Each a in A has a unique b in B, since |A| = |B| (using my definition) and every a in A has a unique b in B, all of B is mapped by A therefore f is surjective, would that work?
cerulean wind
since u have an injection f from A to B, then |A| = |f(A)|
but that means |f(A)| = |B|
spoiler:||and since f(A) is a subset of B, then you have to have f(A) = B||
keen lava
I understand everything up until the last line, how do you know that they are equivalent?
cerulean wind
B is finite and has |B| elements. the number of |B| element subsets of B is |B| choose |B| = 1
B is the unique subset of B with cardinality |B|
past burrow
how do i tell which are O(n^2)
weary tiger
Also I don’t understand this string of modulo for finding x, how is there a modulo of a modulo like that?
floral field
Why are generating functions important? If we already know the closed form of a sequence, what use is the generating function?
Currently in the early stages of reading about it
cerulean wind
typically you use them when you dont know the closed form of a sequence of numbers. its like a way of encoding data. like if you want to solve a recurrence relation to get an explicit formula, one way you could approach the problem is to use generating functions
floral field
Hmm interesting. Will ask more things as I read through
Combinatorics seems interesting
cerulean wind
Also I don’t understand this string of modulo for finding x, how is there a modu...
wot
cerulean wind
its not a modulo of a modulo. its short hand for saying that x is congruent to -8 modulo 7, which is congruent to 6 modulo 7
weary tiger
is it two parts? Like x is congruent to -8 modulo 7 and -8 is congruent to 6 modulo 7?
cerulean wind
yea
past burrow
how do i tell which are O(n^2)
pls some1
cerulean wind
how do i tell which are O(n^2)
first, is O(n) a subset of O(n^2)?
stray reef
@mystic elbow repost your question here and clarify what your prof wants when she says "optimal way to distribute the yoyos"
as-is, i can see two options:
- create a spanning tree for your graph in a way that minimizes its total weight
OR - create a list of shortest routes between any pair of vertices
mystic elbow
<@750639066420215858> repost your question here and clarify what your prof wants...
ok wait
stray reef
i would like to wait as little as possible.
i don't like to receive 10 hours of silence followed by an inane response that clarifies nothing.
mystic elbow
stray reef
yes, ok, this is the problem statement as it was given to you.
it is not clear what "way to distribute the yoyo" means.
mystic elbow
ill confirm that
stray reef
will you disappear now or can we still discuss problem 2?
stray reef
what did your teacher say?
mystic elbow
he wont reply anytime soon
mystic elbow
still thinking
stray reef
do the words 'euler path' mean anything to you?
mystic elbow
edge of the graph that has exact once
mystic elbow
what
stray reef
i cannot parse the string "edge of the graph that has exact once"
mystic elbow
what did your teacher say?
It means find mst
mystic elbow
i cannot parse the string "edge of the graph that has exact once"
path that uses every edge exactly once
stray reef
It means find mst
minimal spanning tree? then i've already told you what you'll get. would you like to object to my statement that taking just the edges of cost 1 gives you the minimal spanning tree for that graph of yours?
if you decide that you now agree with me then please say "okay, i agree that the answer to problem 1 is to take the edges of cost 1"
if you decide that you want to object then please say "no, i do not agree with you"
mystic elbow
if you decide that you now agree with me then please say "okay, i agree that the...
okay, i agree that the answer to problem 1 is to take the edges of cost 1
stray reef
great
weary tiger
How to prove that if $G$ is a connected graph and $diam(G) \ge 3$, then $G'$ is connected
vital dewBOT
diavolo
weary tiger
diam(G) is max value of eccentricity in G
And G' is the compliment graph of G
I have no idea on where even to begin
stray reef
@weary tiger try this: since diam(G) ≥ 3, there exist two vertices v and w whose neighborhoods are disjoint
weary tiger
Hmm I am kinda slow why exactly is this disjoint case true
stray reef
it's not a 'case'
the contrapositive is that if no two vertices have disjoint neighborhoods then diam(G) ≤ 2.
weary tiger
Oh
Alright I think it gets easier for me now
Thanks a lot
I will be back if I get stuck again
mystic elbow
@stray reef
we will end after selecting all the edges with weights = 1
cos anything else will form a cycle
a hamiltonian path might be more correct?
like this is what i drew based on kruskal
but lets say if I am at point A (middle point covered by my line), if I want to go to points D and H, I will need to go to H, back to A again, to B then to D, which is much longer than from A to D directly
weary tiger
Hey guys i have been trying to understand this problem for a while now
During a month with 30 days, a baseball team plays at least one game a day, but no more
than 45 games. Show that there must be a period of some number of consecutive days during
which the team must play exactly 14 games.
Solution: Let aj be the number of games played on or before the j th day of the month. Then
a1, a2,...,a30 is an increasing sequence of distinct positive integers, with 1 ≤ aj ≤ 45. Moreover, a1 + 14, a2 + 14,...,a30 + 14 is also an increasing sequence of distinct positive integers,
with 15 ≤ aj + 14 ≤ 59.
The 60 positive integers a1, a2,...,a30, a1 + 14, a2 + 14,...,a30 + 14 are all less than
or equal to 59. Hence, by the pigeonhole principle two of these integers are equal. Because the
integers aj , j = 1, 2,..., 30 are all distinct and the integers aj + 14, j = 1, 2,..., 30 are all
distinct, there must be indices i and j with ai = aj + 14. This means that exactly 14 games
were played from day j + 1 to day i.
in the solution, i get that when we add 14 we see that there 60 distinct integeres are less than or equal to 59
but what does this have to do with number 14? cant you prove it the same way with any other number?
weary tiger
what why?
coral raven
45 - 30 = 15
weary tiger
yeah but if they play 14 twice
they have to play one game on other days as well
nvm
i see
@coral raven wait
if they play 14 games on day 1
and 14 games on day 2
thats 28 games right?
coral raven
sure
weary tiger
and 28 days left
coral raven
ok
weary tiger
where they must play at least once