anyone can assist me this question 🙂
#discrete-math
fading snow
sand cipher
so smthing like this?
south bay
Hi all I have the following sequence:
B0 = 0
B1 = 1
Bn = Bn-1 * (Bn-1 + 2 * (Bn-2 + ... + B0) + 1)
So, for example, we have B2 = 2 B3 = 10 B4 = 170.
My question is how can I use this definition to formulate a formula for calculating the nth element of this sequence directly?
(i.e. without having to calculate intermediate results of the sequence first)
weary solstice
so smthing like this?
Exactly, looks good!
sand cipher
then from there i make 2m=q
where x=2q and q is some integer
and 2|x here x is some integer
is that enough as proof?
fading snow
hello, can anyone assist me this question 😄 thank you so much
weary solstice
@sand cipher, sorry I was afk for a bit. After x = 2(2m), you could right away => 2|x, since the fact m is an integer implies 2m is an integer. Then that, in turn, => x is in B, completing your proof
sand cipher
<@192859973410226176>, sorry I was afk for a bit. After x = 2(2m), you could rig...
Is that all the proof needed nothing else?
Should I provide examples?
forest latch
I have problems with (a), why in the end 2^n-3? Whence in such problems two in some degree?
stray reef
In the fourth case, there are 2^(n-3) possibilities
in the fourth case your string ends in 000, and the other n-3 bits in the string can be whatever
each bit has two options for it: 0 or 1
@forest latch
forest latch
> In the fourth case, there are 2^(n-3) possibilities
can you explain why exactly two and why degree? because im not sure that i get it and i can solve other problems
2 because we have two options right?
oh its like product rule
stray reef
you're multiplying several copies of 2 together, one copy for each bit you have control over
you have n-3 bits to set arbitrarily
plucky patio
I have no idea where I'm supposed to ask this so I hope that this is the right channel. I'm supposed to show that if I swap two characters in a code word in the linear variant of ISBN-10 then it is no longer a code word. So apparently the set of all code words is $${ v \in (\mathbb{Z}/ 11\mathbb{Z})^{10} ; | ; v_1, \ldots, v_9 \neq X \text{ and the scalar product of } v \text{ and } (1, \ldots, 10) \text{ is congruent to 0 mod 11 } }$$ and if I take away the requirement that $v_1, \ldots, v_9 \neq X$ then this is apparently linear but tbh I don't even know what the X means. So like if I have $(9, 1, 0, \ldots, 0)$, which is a code word, then I can just swap 9 with 7 and 1 with 2 and the result will still be a code word, right? What am I missing?
vital dewBOT
Tokidoki ✓
plucky patio
it's supposed to say "and the scalar product of v and (1, 2,..., 10) is 0 mod 11"
maybe it's supposed to mean that if I permute two characters like a transposition then the result will not be a code word?
storm drum
Hello, How can i formally prove that Aâ–³X = A and there is only one X that can match this equation and this X is empty set?
plucky patio
what is the triangle thing?
storm drum
symmetric difference
plucky patio
okay so this is $(A - B) \cup (B-A)$ right?
vital dewBOT
Tokidoki ✓
plucky patio
where A-B is the set difference
storm drum
ye
plucky patio
okay then assume that X is non-empty
storm drum
Like
how can i show that for EVERY set that i will pick that is not empty the equation will be false?
i am struggling with the FOR EVERY
i get the idea of it
plucky patio
okay so your goal is to show that Aâ–³X = A for X = empty set?
for only the empty set X
storm drum
you want to look at this
I dont see anything
plucky patio
wait what happens if X and A are disjoint?
storm drum
what do you mean?
plucky patio
yeah sorry never mind I'm tired
so assume that X is non-empty, that it has at least one element.
plucky patio
**Tokidoki ✓**
now look at this latex
storm drum
i dont see anything
storm drum
ah ok
plucky patio
yeah so there are now two cases, either A or X are disjoint (share no common elements) or not. What happens in either of these cases?
plucky patio
so assume that X is non-empty, that it has at least one element.
so assume this and assume that the equation holds
storm drum
case 1: you combine them cuz they aint sharing common elements
case 2: they share elements and then there is a group that is combining elements from both sets
plucky patio
yeah. So in case 1 you just get A union X and this is clearly not A since X is non-empty by assumption. This is a contradiction. Do you see what to do in case 2?
plucky patio
I mean you have this channel
storm drum
ye i didnt mean in dm
plucky patio
if I will be here then I will try to help
storm drum
i meant here
north girder
south bay
How can I find a closed expression for the nth term of the following sequence? https://www.wolframalpha.com/input/?i=a_0+%3D+0%2C+a_1+%3D+1%2C+a_n+%3D+a_(n-1)*(a_(n-1)+%2B+2)+-+a_(n-2)*(a_(n-2)+%2B+1)
languid moss
is a correct and what would b be?
haughty garden
The universal set is the set of all even integers from 1 to 21
So elements like 3, 9, ... are not elements of U
languid moss
oh shit i missed that thank you
is that better?
im just confused on the 20 < x^2 <250
haughty garden
Yep, A looks good
For B, note that since x^2 lies between 20 and 250, x^2 is a monotone function (i.e. it's strictly increasing). This is equivalent to finding all x in U such that sqrt(20) < x < sqrt(250) which is the same as finding all x such that 4 < x < 16
languid moss
so it would be 6,8,10,12,14?
haughty garden
Yup
languid moss
thank you 😄
opal harness
Discrete Math: I will post a screenshot of the problem here, involves relations, equivalence relations and equivalence classes.
I just dont understand where to start with this. I do not get how to count equivalence classes on a relation that isnt defined.
https://cdn.discordapp.com/attachments/903486480075354182/907471471394304050/unknown.png
https://cdn.discordapp.com/attachments/903486480075354182/907471496010686474/unknown.png
pld
pls
unreal stump
Discrete Math: I will post a screenshot of the problem here, involves relations,...
Take the given languages as "kernel" of your equivalence
opal harness
Take the given languages as "kernel" of your equivalence
can you elaborate on kernel
ive never come across that tertm
unreal stump
So,you can map an element to it's equivalence class. If 2 elements map to the same equivalence class,you can think of the set as "shrinking"
For example you can think b~aab
And think of them as the "same element"
Ok,kernel is not the right word
opal harness
So,you can map an element to it's equivalence class. If 2 elements map to the sa...
right but how do i tell what maps to what equivalence class if i dont know the relation
all i know about the relation is that it is an equivalence relation
unreal stump
You construct an equivalence relation such that all elements in that L_eo set map to the same equivalence class
opal harness
i construct my own?
unreal stump
Yea
exotic valley
hi
unreal stump
There is only one obvious map that will do what you want
opal harness
um
unreal stump
|| Let w1 and w2 be words, and a_1,b_1 be number of a's and b's in w1. Similarly define a_2,b_2.
Define w1~w2 iff a_1%2=a_2%2 and b_1%2=b_2%2||
exotic valley
what is w1
im year 1
im jk
im year 6
but i haven't learn these yet
i only know sutff like
2+x/5=10
so 2+x= 5x10
2x = 50
so to find x
50 divded by 2 = 25
so x is 25
so am i right or wrong i need feedbck thx :D!
feedback*
opal harness
|| Let w1 and w2 be words, and a_1,b_1 be number of a's and b's in w1. Similarly...
what does the tilde mean here
~
unreal stump
equivalent
opal harness
does % mean mod or is that smth diff
exotic valley
equivalent
is it = or ~
unreal stump
does % mean mod or is that smth diff
Yea mod
unreal stump
so how do we get to counting the equivalence classes
Ok, that's correct but that's also not complete
exotic valley
how is = different to ~
exotic valley
hi
opal harness
exotic valley
oh ok
unreal stump
You use a textbook right? Look up the definition of equivalence classes defined by a language
exotic valley
thx 😄
opal harness
You use a textbook right? Look up the definition of equivalence classes defined ...
its written by the instructor who does not define things well
but i will look
exotic valley
is there a section for primary schools or secondary?
opal harness
http://www.cse.msu.edu/~torng/360Book/RegLang/Equivalence/
you dont know how much i dislike my prof
opal harness
thats all he has said about equiv classes
unreal stump
nvm, there are 2 equivalence classes
My understanding of equivalence classes here was wrong
opal harness
man
im gonna get fucked on this assignment
deadline in 2 mins
gg
ive been on this one problem
the rest
are done
unreal stump
Ok,put 2
And then the 2 equivalence classes are {words whose count of a and b are both even}
and words which are not that
hasty tapir
Find the reminder when (2021^55555)/7
haughty garden
Euler's theorem tells you that 2021^(phi(7)) = 1 (mod 7) since gcd(2021, 7) = 1. Note that phi(7) = 7 - 1 = 6. So 2021^6 = 1 (mod 7). Try and write 55555 as 6q + r. Then you have 2021^55555 = 2021^(6q + r) = 2021^(6q) * 2021^r = (2021^6)^q * 2021^r which is congruent to 2021^r (mod 7)
forest latch
is it possible to represent x*y by NOR logic gates?
red wharf
How do I ratio people
stray reef
what?
forest latch
when you say multiplication do you mean AND
sorry, yes I mean AND
stray reef
well it's possible to do negation as NOT x = x NOR x, so it is possible to write x AND y as (NOT x) NOR (NOT y)
forest latch
thanks!
limber lava
good evening, I am struggling with a thought experiment I made myself:
You are flipping a coin n times.
How many permutations exist where you have k amount of heads and b times occurrences of at least m consecutive tails that do not overlap with each other.
Here are two examples:
You flip a coin 4 times. How permutations exist where you have gotten 1 heads and 1 occurrence of at least 3 consecutive tails. The answer is 2: HTTT and TTTH.
You flip a coin 6 times. How permutations exist where you have gotten 1 heads and 1 occurrence of at least 4 consecutive tails. The answer is 4: TTTTHT, TTTTTH, HTTTTT, THTTTT
I am trying figure out a general formula for this problem, but it's pretty complicated since I am working with 4 parameters here... I tried to brute force some solutions for multiple values for each parameters, but I sadly don't see a clear pattern yet.
Does anyone know a good way I can continue working on this?
deft olive
Could someone explain to me what this means? A is a set with 3 elements but what is T(A)?
karmic prairie
T_A would be the set of all maps from A to A ?
deft olive
That sounds familiar! Could you give me an example what exactly T_A would be here?
Would it be {aa, ab, ac, bb, ba, bc, ...} ?
karmic prairie
well it would be {a map, another map, another map, ...} and i don't think you can simplify further
unless you want to express maps as sets but it would be very ugly
an element of T_A for example would be {(a,a), (b,b), (c,c)}, the identity map
tidal tulip
if i wanted to prove A ∩ B ⊆ A ∪ B., would this proof work: assume x in A ∩ B, then for all x in A, x is also in B. thus x is in A or B for all x in A ∩ B, hence we see that A ∩ B ⊆ A ∪ B
deft olive
if i wanted to prove A ∩ B ⊆ A ∪ B., would this proof work: assume x in A ∩ B, t...
Yes that would work
tidal tulip
ty @deft olive
deft olive
ty <@!207110539833376768>
np :)
karmic prairie
mmh it looks a bit weird, if you "assume x in A ∩ B", then you can't say "for all x in A"
I would simply do: Let x in A ∩ B. Then x is in A. Therefore x is in A U B.
raw musk
Show, without using Menger’s theorem, the following result: if a graph
G is k-connected (k ≥ 1), then for each edge e of G, G − e is
(k − 1)-connected.
Any hints for this?
tidal tulip
@karmic prairie how about this: assume x in A ∩ B, then this means x in A and x in B, since x in A and x in B, this means x is also in A or B, thus x in A U B. therefore any x in A ∩ B is in A U B, thus A ∩ B ⊆ A ∪ B
autumn horizon
do yall know mathematical induction?
elder steppe
can anyone help me with this?
sharp ledge
Alice, Bob and Charles have a coke, lemonade, orange juice and cranberry juice between them. Alice doesn't like orange juice, Bob doesn't like lemonade, and Charles doesn't like coke. In how many ways can we allocate the drinks so that everyone gets exactly one drink and no one gets a drink they don't like?
elder berry
Alice, Bob and Charles have a coke, lemonade, orange juice and cranberry juice b...
I fail to see how this would have a nice solution, I think it's just casework. I'd split the casework as: 1) check every possible way ignoring the cranberry juice, 2) check every case where one of them must have a cranberry juice
hybrid ether
Hi
grim kraken
hello crying baby
honest barn
Hello crying baby
quaint star
Hello three crying babies
tidal tulip
can someone check this proof. i rewrote it a little
prove A ∩ B ⊆ A ∪ B:
assume for an arbitrary but specific x, x in A ∩ B
=> x in A and x in B,
=> x in A U B.
since x was arbitrary, then we see for any x in A ∩ B
x is in A U B
thus A ∩ B ⊆ A ∪ B by the definition of subsets
forest latch
who can explain why 3 blocks? I thought we should use as few blocks as possible. Why 3, if i can cover or 1s with 2 blocks
stray reef
where did this come from
forest latch
where did this come from
Rosen's discrete math and its app
forest latch
i'm asking you to show the original problem
stray reef
and the answer to part d was just that map and nothing else?
stray reef
ok so it looks like they specifically wanted to draw your attention to the fact that y'z' is a redundant block
forest latch
soo here right kmap will be with only two blocks?
stray reef
yes
tidal tulip
can someone check this proof. i rewrote it a little
can i get a proof check on this
proven silo
Its fine
tidal tulip
ty
forest latch
what does it mean "ternary strings"?
ok i understand what is it ternary strings
but now i dont know how to solve it
I counted length of n=1,2,3,4,5
but i dont see there pattern
forest latch
@stray reef can you help me?
stray reef
ternary strings are strings consisting of 0, 1 and 2
they're like binary strings except there are three things each symbol could be
forest latch
they're like binary strings except there are three things each symbol could be
how to find reccurence relation? I did like other task were solved, so i gor An=2An-1+2An-2
but it isnt work
stray reef
should be $a_n = 2a_{n-1} + 2a_{n-2} + 3^{n-2}$ i think
vital dewBOT
Ann
stray reef
the possible things a valid string of length n could be are:
0 + (valid string of length n-1)
2 + (valid string of length n-1)
10 + (valid string of length n-2)
12 + (valid string of length n-2)
11 + (whatever of length n-2)
@forest latch this last option is what you missed
forest latch
<@515412357220925443> this last option is what you missed
thank you!! you are the best
wait, I understand it little bit wrong, why we add 3^(n-2)?
if its case when string ends with 11, why we add it
stray reef
look at the bold part in my last message
whatever of length n-2
the number of ternary strings of length n-2 without extra requirements is 3^(n-2)
by definition there are three options for each symbol
forest latch
but 3^(n-2) its all ternary strings of len n-2, there can also be two consec. 1s
or I understood smth wrong?
stray reef
ah wait hold on
no, i misread it this time
you want the ones that DON'T contain any 11s
forest latch
yeas
stray reef
in which case that last term would be absent
forest latch
stray reef
so your recurrence relation should be correct and you just need to make sure you have the initial conditions right
A_1 = 2 and A_2 = 8
forest latch
why a1=2?
forest latch
hmmm
stray reef
for lengths 1 and 2 you can just list them out explicitly
forest latch
so my reccurence rel probably right?
stray reef
yes your recurrence is fine
hybrid ether
@stray reef what proof book you have referred to ma'am?
leaden dust
i have a question about a a cardinality proof if someone could take a look for me
hybrid ether
@stray reef book for learning logic and proof prior to stepping into advanced mathematics
stray reef
i did not use any such book, so i cannot recommend you anything
leaden dust
young crest
well whats the damn quesition
leaden dust
haha
Determine the cardinality of each of the sets, A, B, and C, defined below, and prove the cardinality of any set that you claim is countably infinite.
A is the set of negative odd integers
young crest
idk you gotta make a bijection to the naturals
leaden dust
so i proved first that its injective and then its surjective
young crest
thats good
leaden dust
and then a one to one correspondence with the N
young crest
well thats implied by the injection and surjection
young crest
I
leaden dust
this was the other 2 sets B and C
young crest
am trying to read it but its kinda hard to make out
leaden dust
this was the other 2 sets B and C
B is the set of positive integers less than 1000
C is the set of positive rational numbers with numerator equal to 1.
young crest
really if you apply a bijective function (such as f = 2x) that necessarily generates a bijective mapping
leaden dust
i did that at the end though right?
young crest
sorry I didnt actually read ur image
leaden dust
it's easier on the phone lol
leaden dust
@young crest so for this one
positive integers less than 1000
i said it's a subset of all positive integers and we know that Z is countable infinite
and then i demonstrated the sequence B = {1, 2, 3...., 999}
so we know the cardinality of B is |999| as there are 999 positive integers less than 1000
young crest
makes sense
leaden dust
haha of course it makes sense but these damn TAs are out for blood
young crest
it's kinda obvious that it's true but you could otherwise use induction
show that a set {1, 1+1, 1+1+1... n} has n elements
leaden dust
i like it
i'll sprinkle that in
and for the set C the set of positive rational numbers with numerator equal to 1
i stated that rational numbers are the quotient p/q where p>0 and q>0
C is a subset of all positive rationals
the set of all positive rationals is countabley infinite
i basically showed that the function is 1/n... 1/n+1 etc.....
which is kind of what you suggested up for set B
young crest
{1} is clearly one
given set X of all elements < x, cardinality n with the addition of an element x (which must be greater than all other elements due to it being 1 larger) the new cardinality is n+1
thus, a set expressing a sequence of positive integers from 1 to n has n elements
young crest
and for the set C the set of positive rational numbers with numerator equal to 1...
wouldn't it make sense to just express the function f(x) = 1/x then point out that this function is inversible everywhere except x=0
or I guess you have to prove that the function really is inversible, presumably with induction as well!
leaden dust
what's wrong with 1/n, 1/n+1 etc....
doesn't that prove a correspondence with the set of positive rationals?
young crest
well if you write it as 1/1, 1/2 etc sure
but the variable is just n, it doesnt turn into n+1
it's a function that turns n into 1/n, thus turning 1 into 1/1, 2 into 1/2 ...
leaden dust
so n is = q and q>0
young crest
yes indeed
young crest
1/n, 1/n+1 confusingly implies two different functions
but you're writing a single function over all possible values of n
young crest
yeah but still that doesnt make sense in terms of math notation
the actual sequence would just be written {1/1, 1/2, .... 1/n ...} where n is natural
leaden dust
ok i see where you're coming from now
that does make more sense
n+infinity doesn't make sense
i wanted to do a bijection proof again but i wasn't sure how because i'm not given an actual equation like before
would the equation then be 1/n?
young crest
f(n) = 1/n
leaden dust
awesome i'll get back to it thanks for the direction
young crest
this is also its own inverse
leaden dust
i did have one more question about Big O notation and finding witnesses
young crest
so f'(n) = 1/n
leaden dust
this is a bigO notation proof
to prove (xlogx)^2-4 and 5x^4 are O(x^4)
basically just tried to find my witnesses
for 5x^4 <= Cx^4
it's obvious C = 5 and K can be > 1
and for (xlogx)^2 -4
i used desmos to find the POI and see where x^4 starts gaining
so i chose C=1 and k > 2/5
young crest
I guess I dont know much abt that
leaden dust
damn lol
void lake
Can anyone help me get started on this problem? I understand that if 001 is in B, then 11001, 10001, 0001 are also in B right? Would a2 be 11001 and a3 be 10001? I do not see a relationship between these, how would I start to make a recursive definition given this bit string definition?
young crest
(0|1(1|0))*001
void lake
Could you explain that more by chance?
young crest
its a regex
all strings in this language are matched by the regular expression of 0 or 11 or 10, repeated some number of times, followed by 001
first, it seems that no combination of two additions will overcount
in other words, a string can only be derived in one way
void lake
Sorry I am confused, I understand that every b in B will also make the strings 11b 10b 0b in B, but how do I define this? Is it by the regex expression you gave? We haven't done that in class.
young crest
yeah no the regex is not necessary here
I just noticed that it can be rephrased using one
void lake
Oh ok, I guess I am just confused on what form of answer this is asking for
young crest
yeah so first, let's ignore the 001
how many ways are there to generate "0" and "1"? how many for 00, 01, 10, 11?
void lake
for 0 and 1, it would be 2 right? (1 and 0) Then 4?
young crest
ah yes, but I was talking about that system above
it allows you to generate a 0 using rule 3
but you can't just generate a 1, you can only generate 11 or 10
void lake
Oh I see, so for 00 it would be using step 3 twice, is that what you mean? 10 would be step 2, etc
young crest
yes indeed
thus the amount for 00 is 1
since there is only 1 possible way to generate it
void lake
Ok that makes sense
young crest
now, 11 has 1 way, 10 has 1 way, 01 has.... zero ways! 00 has 1 way
void lake
Right, so the set will include all but 01
void lake
Ok that makes sense, because you skip "010" and go to "011" = 3
young crest
hmm
not sure what you mean
notice that it adds those numbers to the left
not the right
thus if 0 is a valid string, 110 100 00 are valid
but 010 can be derived by doing a 10 then a 0
void lake
Ok so whenever there is a 01, it follows with a 0
young crest
that is true
void lake
So basically, going back a bit, this recursive set includes all values except those skipped from the "01, follows with a 0" numbers right?
void lake
Am I trying to find which numbers are not included? What will the final answer look like? (Like the form)
young crest
yes
which numbers/strings have 0 derivations
then just subtract these impossible strings from 2^n
since if all bit strings were allowed, an = 2^n
void lake
Ok, so 1/4 of the new numbers from b (b is in B) will be impossible right? From 11, 01, 10, 00, - 01 is impossible?
young crest
if you count the even-length string additions yeah
odd strings can only be derived by adding a 0 to an even string
also write a recurrence relation
void lake
What does the recurrence relation look like? Just the form of it I guess, I thought that the answer was the recurrence relation lol. Is it the form an = ... or is it just a list of values?
young crest
an = something a(n-1)
void lake
Ok, in this an equation do you still use bit strings or do you convert them?
void lake
Ohh I see I was thinking of the problem wrong, ok one second
for a3, isnt a bit string of length 3 only going to be "001", so a3 would be 1?
void lake
ok so a4=1, a5=2 (001->11001,10001), a6=2, something like that?
young crest
what abt 00 001
void lake
Oh that’s right, so a5=3, a6=5 I think?
young crest
well you basically add 10 and 11 to n-2 and add 0 to n-1
void lake
Oh ok that does make sense, I was slowly getting there lol, ok awesome thank you for the help! I have to go but I understand the problem a lot more
Thank you again!
weary tiger
ok how does that last statement implies x_1 = x_2.
I can only see it if $\frac{x_2-1}{x_1-1} = 1$
vital dewBOT
Outlander
past burrow
i have a question for 3c.)
is this the correct inductive hypothesis of a proof by mathetmatic induction
young crest
that doesnt seemm right
you can multiply each side of < by (n+1)
but you cant just transform n into n+1 in one step
(n+1)n! < (n+1)n^n
past burrow
i deleted some steps after the 2nd line cuz my friend said i didnt need it
he said that (n+1)n! < (n+1)n^n does not belong anywhere
past burrow
so with the inclusion of those steps is it good
young crest
"we know that n < n+1" is a bit too obvious but the rest is good
also I just noticed but you didnt need to prove all that
n! < n^n is literally the inductive hypothesis
thats question c
proven silo
n is not in R, the "so" part is what you want to prove, not clear that is what you mean. Get rid of "we know that n<n+1".
Start with (n+1)! and chain it all together, something like
(n+1)!=(n+1)n!<(n+1)n^n<(n+1)^(n+1)
past burrow
n! < n^n is literally the inductive hypothesis
wdym
young crest
the inductive hypothesis ≠the proof
P(n) is the hypothesis
P(n) -> P(n+1) is proof
past burrow
n is not in R, the "so" part is what you want to prove, not clear that is what y...
ya mb n is in N and im confused on wym by chaining
proven silo
I started with (n+1)! and wrote equalities and inequalities all the way through until I got to RHS
and showed LHS<RHS
young crest
the "so" part is not what you want to prove
young crest
it can be done by multiplying both sides by n+1
young crest
but thats not what the so part says!
proven silo
his RHS should be (n+1)^(n+1)
but as I said don't write "so", write we want to prove this or something
proven silo
he wants to prove (n+1)!<(n+1)^(n+1)
fine to write what you want to prove at the top like that
just make it clear that is what it is
young crest
its not a goal its just a derivation step bruh
proven silo
he wants to prove n!<n^n, he showed base case and assume true for n, then wants to show for n+1, which is (n+1)!<(n+1)^(n+1)
what?
young crest
uh yes
the "so" part is correct
the actual proof is at the bottom with "therefore"
past burrow
young crest
srsly
past burrow
uhh so
young crest
whats up
past burrow
is it good?
young crest
well it's a correct proof but its not the right answer to c
past burrow
wait why
young crest
remove everything besides P(n) = n! < n^n
past burrow
ok i did
past burrow
ohhh cuz inductive hypothesis isnt proof?
coral raven
i deleted some steps after the 2nd line cuz my friend said i didnt need it
firstly it should be for n in N
secondly the statement is still false even if it's for n in N, as it fails for the base case n = 1
past burrow
i said ik its n in N thats not an updated picture
past burrow
ya
weary tiger
Im confused about how this was solved:
Compute the remainder when $202^{202}$ is divided by $11$:
vital dewBOT
jswatj
coral raven
FLT
weary tiger
They did $202 \equiv 4 \mod(11)$
vital dewBOT
jswatj
weary tiger
then brought up both to the power of 202
which makes sense
because of the rule
but then they broke $4^{202}$ into $(4^{5})^{40}\cdot 4^2$ and used the fact that $4^5\equiv 1 \mod (11)$ and substituted $4^5$ for $1$, but I dont understand why you can do that
vital dewBOT
jswatj
coral raven
i don't see the problem
weary tiger
There is no problem
coral raven
i don't see what you don't understand*
weary tiger
its just i dont understand how you can substitute $4^5$ as $1$ since $4^5\equiv 1 \mod (11)$ in $4^{202}\equiv (4^{5})^{40}\cdot 4^2 \mod(11)$
vital dewBOT
jswatj
young crest
yeah the whole thing is periodic
coral raven
if 4^5 = 1 mod n
then 4^5^40 = 1^40
weary tiger
OHHHH
coral raven
it's just simple that way
young crest
isnt P(n) supposed to be a proposition rather than a value?
P(n): x = y
not P(n) = x
well
what property is supposed to be proved here anyway
ah
find some an = .... that does not involve a_n-1
for example if I have an = 2a[n-1] then an = 2^n
you can break down multiplication into a bunch of additions, or put the additions back together into multipkication
thats basically whats being asked: find a formula that calculates an without needing to calculate an-1 first
basically it's an = 1 - n
prove that as a proposition
north raptor
Newbie here, how would I communicate that there exists 5 different numbers from the set of integers that satisfy a certain condition. So say that the mean and median of 5 different integers needs to equal 22.
Exists there an elegant way of communicating this?
Thanks.
past burrow
did i do my 2b correctly
knotty pulsar
weary tiger
raw musk
A roller coaster car has n rows of seats, each of which has room
for two people. If n men and n women get into the car with a man and a
woman in each row, in how many ways may they choose their seats?
The answer is n!*n!, right?
crude nymph
Can somebody help me on this?
I said the Base case was n = 4 but im having trouble prooving it using the induction method.
proven silo
Expand LHS and RHS, apply inductive hypothesis and use some inequalities (then when writing down proof start with LHS and write inequalties until you get RHS)
stray reef
intuition says the difference between RHS and LHS ought to be an increasing function of n from some point onward
so you could let f(n) = n^4 - 3n^3 - 2 and examine the expression f(n+1)-f(n)
see if you can manage to prove it positive for the values of n you care about
brittle stone
Anyone?
stray reef
@brittle stone how can we help you when you didn't tell us which part(s) you're struggling with and what progress you've made so far?
brittle stone
I have trouble with the whole question. And I did try a few of them also.
stray reef
well show us what you tried
stray reef
(iii) is $p \land (q \lor r)$, not just $p \land q$
vital dewBOT
Ann
stray reef
(iv) is not t xor u right
we know maria has an id, so t is true
(v) is wrong but its wrongness is based on that of (iii), so once you fix (iii) you should be able to also fix (v)
(i) is much simpler than the rest, being simply $p \lor s$. did this just not occur to you?
vital dewBOT
Ann
stray reef
(ii) is (D is of age or M is of age) --> (D has ID and M has ID)
@brittle stone you didn't forget about the existence of (inclusive) OR, did you?
brittle stone
<@884083162928517181> you didn't forget about the existence of (inclusive) OR, d...
I didn't but I am not sure about its usage.
stray reef
what's there to not be sure of?
brittle stone
I didn't understand inclusive OR
stray reef
inclusive or can be interpreted as "at least one of these is true"
it can also be interpreted as "this or that or both"
brittle stone
Okay...got it
brittle stone
stray reef
your answer for (iv) now reads "Maria has an ID"
and not "Maria has an ID but is not allowed to see the show"
may i remind you that the operators AND and NOT exist
"t and not t"?
do you even read the things you write?
north raptor
Newbie here, how would I communicate that there exists 5 different numbers from ...
Any advice on this?
young crest
basically just say abcde are distinct
there exists a b c d e from Z such that a b c d e are distinct
north raptor
there exists a b c d e from Z such that a b c d e are distinct
Thanks, didn’t know how to start out; this clears some of it up. Appreciate it
young crest
you could write a≠b, b≠c etc
but the problem is that youd need to write every possible combination
north raptor
Ah I see
young crest
cuz a≠b and b≠c does not imply a≠c
north raptor
That’s true, just for clarification this isn’t for some homework or anything like that. I was just curious if there was a way to neatly communicate this with set theory/logic for fun. More or less just naively seeing if I can cook something up for myself. Thanks!
young crest
otherwise you might say that abcde are part of a set A such that |A| = 5
north raptor
What does | | refer to here?
north raptor
Ah, right. Thanks
young crest
the cardinality does not change when you add redundant elements
north raptor
Neat
young crest
thats bc sets are necessarily defined by distinct elements such that {1} = {1,1,1}
hybrid ether
stray reef
@hybrid ether in case you didn't see this
also, i can't help but mention something else: it's "didn't understand", not "didn't understood"
hybrid ether
also, i can't help but mention something else: it's "didn't understand", not "di...
@stray reef thankyou a lot for correcting my English
hybrid ether
if x is even, x² is even
Yeah same parity. Now i understood. I think it's due to minimising the algebraic manipulations. Thankyou@young crest
crude nymph
Expand LHS and RHS, apply inductive hypothesis and use some inequalities (then w...
Can you check my ans?
silver knoll
Can anyone help me translate this into plain English?
∀x∀yP (x, y) → ∀xP (x, x)
The things I come up with just doesn't make any sense
shadow grove
Uhhh,
Let P be a binary predicate, such that P(x,y) means x is the mother of y.
For all x's and y's such that x is the mother of y, they fulfil that for all x_1, x_1 is the mother of x_2
I think the idea is, that you're supossed to note, that the three x's are different x's, and that the two "all" predicates bind differently.
But I am in the need of my own help
I have been given the clue, that (9,2) is the number of digits, such that
a=b<c.
I understand that if a=b, then we just need to pick one number (let's call it d, such that d=a=b) and another number c, such that d<c.
But surely, the binomial formula 9 onto 2 just means pick any 2 numbers between 1 and 9?
How can I be sure, that the numbers picked between 9 and 2 are all greater than d?
silver knoll
I don't get it still though
pale epoch
i mean its hard to "translate" into english
if for all x, y the statement P(x, y) is true then for all x the statement P(x, x) is true
shadow grove
Now ze German can help me, please 🙂
pale epoch
is the hint even correct
pale epoch
oh ok
well, just pick any two distinct digits and let a=b be the smaller one, and c the larger one
hence there are \binom{9}{2} ways for that
shadow grove
thanks
that's the hint
but why
As I understand it;
The binom simply says (n k) = number of ways to arrange k elements, that are unique, from a total of n elements.
pale epoch
arrange?
shadow grove
But just because $ d \neq c -> c<d$
pale epoch
i dont know what that means either
shadow grove
i dont know what that means either
Okay
A = {a,b,....,n}
We take k elements from A. How many unique sets, can we make
pale epoch
ok, yes
shadow grove
Yes
If this is true, then
A = {1,2,3,4,5,6,7,8,9}
k = 2
Then one example is
{2,1}
This fulfills my "definition" of the binomial, but not
d <c
oh...
It does...
Damn
pale epoch
you know that one of them has to be smaller
so you just assign the smaller picked value to that
shadow grove
you know that one of them has to be smaller
Jep
You are right
Wow
Haha, thank you, this made a lot of sense actually...
pale epoch
(although i dont think this immediately solves the original question?)
shadow grove
(although i dont think this immediately solves the original question?)
It did not, but I have divided it into 3 parts:
-
There are 9 cases of a=b=c
-
There are 2 * 36 cases of two variables being equal and one being larger
-
The case of a<b<c
pale epoch
yeah, that should work
shadow grove
Also, is this a thing, or have I just discovered it:
plucky slate
Anyone who's pretty damn good at Graph Theory able to help me out with part c on this question at all?
I'll post the graph that I have identified in a second
This is 1 of the 2 needed graphs...unsure about how I can get the other
stray reef
so what we want is a 3-connected graph on six vertices and nine edges that's not iso to what you just drew there, right?
plucky slate
Yes, A 3-regular graph with 9 edges and 6 vertices that's not isomorphic to the graph above
Oh, and vertex connectivity 3
I've done 3 graphs where only one of them follows everything apart from the not isomorphic part. Or at least I think it's isomorphic
stray reef
hm
can you show it
just to be sure
i have only been able to come up with... i think the triangular prism graph
but that isn't 3 connected
or is it? hold on
3-connected needs to survive the removal of any two vertices right
plucky slate
Almost,
The graph needs to be considered "Optimally Connected"
So it needs to have at minimum 3 vertices removed in order to be disconnected.
I'll send over my graphs in a second
Here are my (badly) drawn graphs. I did them on paper originally so that explains this.
The third graph is where I'm a little stuck.
|V| = 6
|E| = 9
k(g) = 3
But is it isomorphic to the original?
shadow grove
If I have a 16x16 board, and I have
4 of each of these numbers (1,2,3,4), how many ways can I fill out that board?
Am I correct in stating it is 2386?
stray reef
Here are my (badly) drawn graphs. I did them on paper originally so that explain...
ah the third one is what i got too
plucky slate
I want to say the third is not isomorphic to the one I put before as you can swap 2 vertices around and you get the same graph...Hmmm
stray reef
there's a 3 cycle
hollow garnet
Prove that 3 divides n3 + 2n whenever n is a positive
integer.
33. Prove that 5 divides n5 − n whenever n is a nonnegative
integer.
34. Prove that 6 divides n3 − n whenever n is a nonnegative
integer.
∗35. Prove that n2 − 1 is divisible by 8 whenever n is an odd
positive integer.
∗36. Prove that 21 divides 4n+1 + 52n−1 whenever n is a positive integer.
∗37. Prove that if n is a positive integer, then 133 divides
11n+1 + 122n−1.
guys i didnt understand number 36
shadow grove
Is there any obvious way of manipulating these two formulas, such that they become the same?
I cannot figure out a way to get q on the other side of the ->
pale epoch
remove -> from both, hope it works
shadow grove
remove -> from both, hope it works
Do you have a theorem for that? Not asking for the solution, but I have no logical equivalencies written in my notes about ->
pale epoch
A -> B is equivalent to not A or B
shadow grove
oh
raw musk
Show, without using Menger’s theorem, the following result: if a graph
G is k-connected (k ≥ 1), then for each edge e of G, G − e is
(k − 1)-connected.
I tried induction to no avail. Any ideas guys?
shadow grove
Am I going down the right path here?
This is what I got A to. The first picture is what I got B to.
Can I use associativity on ?
shadow grove
what you did works
In what regards?
Are they alreay equal?
Well, I know they're equal, but surely it hasn't been shown yet?
pale epoch
why not?
logical equivalence is transitive
so if they are both logically equivalent to $\neg p\lor q\lor r$, you are done
vital dewBOT
Lochverstärker
shadow grove
But I haven't shown, that A is logically equivalent to that formula
Can I remove the parantheses in A, since they have the same precedence?
Is that "Legal"?
pale epoch
wait what is your A currently?
shadow grove
Right, but then I get
pale epoch
you also have already used that fact
pale epoch
Am I going down the right path here?
here
you removed the parentheses when you distributed the negation
shadow grove
Right, but there are not negations on both numbers? Is it the same, just without negations then?
But this is waht I can manipulate A to. I could make the argument, that since we could make whichever position of the parantheses, A is equal to B.
But I would really like for a way, such that A is the exact same as B.
pale epoch
and B is $\neg p \lor q \lor r$?
vital dewBOT
Lochverstärker
shadow grove
yes
pale epoch
ok, so first of all my point was that you removed the parentheses like this:
technically the correct manipulation is to do
$$ \neg(p \land \neg q) \lor r \equiv (\neg p \lor \neg(\neg q))\lor r $$
vital dewBOT
Lochverstärker
pale epoch
you already removed the parentheses in this step
which is fine since \lor is associative
i mean if it wasnt then statements like $A\lor B \lor C$ would not make sense
vital dewBOT
Lochverstärker
shadow grove
ahhh
pale epoch
because you wouldnt know if that is supposed to be $(A\lor B) \lor C$ or $A \lor (B \lor C)$
vital dewBOT
Lochverstärker
pale epoch
so for associative operations, where it doesnt matter, the convention is to just not write parentheses
which you did once so i dont really see why its a problem for you now to drop them
shadow grove
which you did once so i dont really see why its a problem for you now to drop th...
I don't see the problem either, when you put it like that. Thank you very much for the clarification 🙂
hushed iron
Hey does anyone now how to prove that f(x) = (xlogx)^2-4 is 0(x^4)
ik i need to find K and C but idk how i can find K
haughty garden
You can use the fact that, for all x > 1, log(x) < x
icy gyro
Are well orders and total orders the same?
cerulean wind
Are well orders and total orders the same?
no
well orders are stronger in a sense than total orders, since every non-empty subset has a smallest element
icy gyro
for total order there has to be the property that aRb or bRa for all a,b is a member of A
what are the requirements for
well order?
cerulean wind
well orders are stronger in a sense than total orders, since every non-empty sub...
this
its a total order with the property that every non-empty subset has a least element with respect to that order
cerulean wind
for total order there has to be the property that aRb or bRa for all a,b is a me...
yes if extended from a partial order
icy gyro
alright got it thanks
cerulean wind
just an example, R with the usual ordering is totally ordered but not well ordered, while the set of natural numbers with the usual ordering is well ordered
icy gyro
for every non-empty S ⊆ A there is an x ∈ S such that xRy for all y ∈ S
is what i understand
cerulean wind
yes
icy gyro
there we go
cerulean wind
thats the additional property that well orderings have that total orderings dont necessarily have
icy gyro
yep got it!
cerulean wind
they all have a choice of unique representatives
weary tiger
Okay
cerulean wind
and yes
because 1 mod 5 is not 2 mod 5, then [1] != [2]
the classes [0], [1],…,[n-1] are the standard choices of representatives in Z_n
mystic elbow
Can anyone please help prove it
I’m having trouble with this
This is what I have but it’s wrong
Ping me too
stray reef
flipping a column will mess with the parity of colors in each row, so this argument won't do
however you can say that the global parity of white and black doesn't change (i.e. taken over the whole board)
@mystic elbow
mystic elbow
however you can say that the **global** parity of white and black doesn't change...
can u explain more
stray reef
what else is there to explain?
mystic elbow
like how to prove it
stray reef
well how did you prove that flipping a row preserves the parity within it?
or did you just assert that and hope you wouldn't be asked to prove it?
mystic elbow
what i sent is all i have
stray reef
okay, so you just asserted it without having written down any actual proof. got it.
take one row or column to be flipped. let x be the number of black squares in the row before you flip it.
there are four kinds of cells that we care about: black cells in the row, white cells in the row, black cells not in the row, and white cells not in the row
(when i say 'the row' i mean 'the row (or column) that will be flipped')
let x and y be the numbers of black cells inside and outside the row respectively
\begin{tabular}{c||c|c}
& In the row & Not in the row \
\hline
\hline
Black & $x$ & $y$ \
\hline
White & & \
\end{tabular}
vital dewBOT
Ann
stray reef
are you able to fill out this table?
and do you understand what i've been talking about here?
mystic elbow
wait
mystic elbow
are you able to fill out this table?
y x?
stray reef
is that supposed to mean "the second row should be filled with the numbers y and x in that order"?
stray reef
did you just guess this or do you have some reasoning to support that answer?
mystic elbow
like probability / guess
stray reef
okay so you guessed it instead of actually thinking about it. fine.
then i'll just have to take you through it.
how many cells are in our row, in total?
this is something you should be able to answer immediately without any guessing nonsense.
just by looking at the problem setup again.
mystic elbow
including title?
mystic elbow
In the row & Not in the row
stray reef
i asked you a question
how many cells are in our row, in total?
we are flipping a row of the chessboard. how many cells are we flipping?
mystic elbow
4
mystic elbow
6?
stray reef
are you just guessing again???
look at the chessboard
you have right there a picture of the chessboard
what are the dimensions of a chessboard?
mystic elbow
2
stray reef
????????? please stop playing dumb, it's not funny
a chessboard is how many cells by how many cells?
mystic elbow
8?
stray reef
how many cells did i highlight?
mystic elbow
8 right?
mystic elbow
its 8
stray reef
this is a kindergarten level question i asked you but you overthought it to hell and back
yes it's 8. each row has 8 cells in it
now
there are x black cells in the row.
the number of white cells in the same row is...?
mystic elbow
same as black
which is 8
well i did say 8 long back and u didnt say anything that if its right or not thats why i asked 8 right?
stray reef
no, its_me!
there aren't 8 black cells in the row! and there aren't 8 white cells!
certainly not both at the same time!
mystic elbow
why
stray reef
there could be 1 black and 7 white, or 2 black and 6 white, or 5 black and 3 white...
we are talking about an arbitrary board state, not the initial or the final
i was unable to get you to write this:
\begin{tabular}{c||c|c}
& In the row & Not in the row \
\hline
\hline
Black & $x$ & $y$ \
\hline
White & $8-x$ & \
\end{tabular}
vital dewBOT
Ann
stray reef
do you not understand this?
is this some sort of language barrier, or are you intentionally playing dumb every time, or what
stray reef
okay now can you tell me how many white cells there are not in the row?
mystic elbow
so for Not in the row would it be the same?
stray reef
no it wouldn't be 'the same'
mystic elbow
8-y
mystic elbow
ok
stray reef
look at this picture again, how many cells are not highlighted?
stray reef
okay great
\begin{tabular}{c||c|c}
& In the row & Not in the row \
\hline
\hline
Black & $x$ & $y$ \
\hline
White & $8-x$ & $56-y$ \
\end{tabular}
vital dewBOT
Ann
stray reef
so we now have this
now tell me
before we flip anything, how many black cells are there in total
stray reef
in case it was not obvious, i'm looking for an answer in terms of x and y
you should grow accustomed to the fact that not all sub-questions will have a purely numerical answer
mystic elbow
i meant x+y
stray reef
if you mean x+y then why aren't you writing x+y?????
how are we supposed to know what you mean if you don't say what you mean?
mystic elbow
by mistakeee
stray reef
okay so there are x+y black cells before the flip
how many black cells will there be after the flip?
stray reef
no it's not x-y
mystic elbow
same as in x+y
this?
stray reef
no, it wouldn't be x+y either
stray reef
no????
do you understand what "flip" means
cause i think you don't and you're trying to guess your way through this again
stray reef
no, that's not what it means...
stray reef
here is the original problem again because apparently this needs a reminder again
at each step we switch the color of every cell in one row
black cells become white and white cells become black
seriously, you WILL NOT GET ANYWHERE if you keep IGNORING crucial problem data like this
it's frustrating
having to remind you again and again and again
mystic elbow
k
mystic elbow
black cells become white and white cells become black
where does it say this
stray reef
For each move, you can switch all the colors of one row or one column at a time.
there are only two colors: black and white
there are no other colors on the board
mystic elbow
alrightt
stray reef
do you still need it to be said explicitly that switching colors means turning black into white and vice versa???
mystic elbow
i know what that meanss
stray reef
great, so why aren't you applying this knowledge
i'm trying to take you through very simple reasoning but i'm having a hard time getting you to follow
or do anything on your own
the moment i try to get you to answer any question by yourself without me spoonfeeding you the answer you start floundering
mystic elbow
but how many black cells are there when flipped?
ok
i think i got it
ill try to prove and show u
stray reef
but how many black cells are there when flipped?
black cells in the row become white, and white cells in the row become black.
everything you need to count the new number of black cells is in the table.
you just need to put some effort in
stray reef
judging by your hour-long silence, i'm going to assume you abandoned the problem.
mystic elbow
everything you need to count the new number of black cells is in the table.
just to confirm after the flip we get 8 - x y
X 56 - y ?
stray reef
how am i supposed to read this?
mystic elbow
wdym
stray reef
great, so why couldn't you have sent me this much clearer picture in the first place?
yes, this is what the board state becomes after the flip
stray reef
no
all you need to think about is:
how many black cells are there before the flip?
how many black cells are there after the flip?
are these quantities always the same parity?
velvet pine
@stray reef And I thought I was a bit harsh with people not understanding LMAO
stray reef
oh i've had dozens if not hundreds of such accusations thrown my way
stray reef
"these people"?
velvet pine
Yeah, those who don't understand
stray reef
most of the time, yes
velvet pine
How
mystic elbow
I see how would we eliminate all
All of 1 color
Not sure how to end up with just 1 black
stray reef
it seems you are again not paying attention to what i am saying
what's the point of coming here for help if you're going to ignore the things people tell you
mystic elbow
parity would change if black and white were a different sign original?
im not ignoringgg
stray reef
yes you are
mystic elbow
just confusedddddddddddd
stray reef
oh you're confusedddddddddddddddd
why not try to answerrrrrrrrrrrrrrrrr the questions i gave youuuuuuuuuuuuuuuuuuuuuuuuuu
stray reef
all you need to think about is:
how many black cells are there before the flip?
...
these questions
but no, you instead attempt to think in different and unproductive directions
stray reef
you should be able to answer these questions immediately
mystic elbow
stop with roasting
stray reef
the first two at least
it's just a matter of reading things out
i'm not roasting you
i'm just telling you not to take hours on things that take less than ten seconds
mystic elbow
all you need to think about is:
how many black cells are there before the flip?
...
x + y black
8 - x + y
so thats 8 + ( y - x)
stray reef
yes exactly
so we have x+y black cells before and 8+y-x black cells after
do you understand how to show that these numbers have the same parity
mystic elbow
yes
So x + y and y - x have the same parity
So if x + y even
we end up with even
Because 8 + even = even
And , if x + y = odd ,
we will get 8 + odd = odd
@stray reef
mystic elbow
u there?
stray reef
...i guess this is good enough
mystic elbow
think we'll never get 1 black
Because every swap gives us an even total number
mystic elbow
...i guess this is good enough
is it?
tidal tulip
Let's say j=9, then how would I write out the B's in (c) would it be like B1 intersect B2 intersect ... intersect B10
{1,2} intersect {2,3} intersect {3,4} ... {9,10} intersect {10, 11} = empty set?
pale epoch
how would this be different from (a)?
tidal tulip
it isn't, so that's why i know this is wrong
pale epoch
tbh it's a bit weird
you have to fix a j first and then consider $\bigcap_{i=j}^{j+1}B_i$
vital dewBOT
Lochverstärker
tidal tulip
lets say j=9 so it satisfies the 1<=9<10 constraint
pale epoch
then this is $\bigcap_{i=9}^{10}B_i$
vital dewBOT
Lochverstärker
pale epoch
you said j=9
pale epoch
as i said, you have to fix a j first, or it doesnt make sense
tidal tulip
ok i see
pale epoch
the "loop variable" if you will is i
tidal tulip
ahh
pale epoch
so j has to be fixed
tidal tulip
ok i see