unnecessary casework
#discrete-math
stray reef
stray reef
you might as well pool A and B's hands together into one 26-card hand and ask for the probabiliy that it has all the aces
weary tiger
hmmm
stray reef
$\frac{\binom{48}{22}}{\binom{52}{26}}$
vital dewBOT
Ann:
weary tiger
thats the complement right
wait
Is that right what you wrote tho?
ok yeah
makes sense
thanks
oh also I was thinking about how woud I calculate the probability that each player has an ace. Surely it would be $\left(\frac{\binom{48}{12}}{\binom{52}{12}}\right)^4$?
stray reef
vital dewBOT
Godel:
stray reef
i don't think so
weary tiger
no
actually
48C12 times 36C12 times 24C12 I think
over 48C12 ^4?
no wait sorry im so tired let me think
I think its $\frac{\binom{48}{12}\binom{36}{12}\binom{24}{12}\binom{12}{12}}{\binom{52}{13}\binom{39}{13}\binom{26}{13}}$
would you agree?
vital dewBOT
Godel:
weary tiger
(Probability of each of four players having exactly one ace from drawing 13 cards)
vital dewBOT
jordan:
vital dewBOT
jordan:
digital cove
or less than equal to?
stray reef
≤
digital cove
sick
weary tiger
ann was what I said correct? Do you mind checking?
digital cove
if i have a statement
there exists x in D such that (P(x) and Q(x))
is that equaivalent to
there exists x in D such that P(x) and there exists x in D such that Q(x)
in truth values
weary tiger
yes
digital cove
and there are no examples against it
how do i prove it
i understand it like intuitively but do i need to take actual steps to prove that
weary tiger
show both statements are equivalent
I mean check when the first one is false and true
weary tiger
same would apply yes
weary tiger
why
weary tiger
yet you didnt know it
digital cove
well i thought there was something i was missing since it was so simple
weary tiger
guys halp
say I have a binomial product like this
$ (1+x)^6 * (1+2x)^7 * (1+5x)^3$
vital dewBOT
epelta:
weary tiger
what would be the fastest way to find coefficent of some power x term
say x^5
please ping me if anyone knows 😮
weary tiger
We want wireless mice who's price is greater than 100$ or of which we have more than 20 in stock.
We also want wired mice whose price is greater than 75$.
I defined :
W: The mouse is wireless
X: The mouse costs more than 100$
Y: The mouse costs more than 75$
Z: There are more than 20 in stock
P = f(W, X, Y, Z) = (W AND (X OR Z)) OR (~W and Y))
Looks good ?
drifting hazel
Edit: I don't need help anymore :)
I am currently doing a math problem for my project, I just need some help on how to go about solving this. I am looking for the method to solving not the answer, I can get that on my own after I know how to do it.
This is what I need to get in the end:
6. Select a Circuit and Travel Cost
Circuit:
Traversal Cost:
Hey, guys I just joined. I'm curious if this is a place I can look for a tutor for hire?
weary tiger
Given the set A={} is a null set, how can you rearrange the elements contained in A one time if there are no elements? It seems you can only have one arrangement of the elements within A and they cannot be permuted. Why is the result of evaluating 0! equal to 1? The definition of the word permute is litterally "to change the order of" according to a quick search. If I have 1 green cup I can't change the order because there is just one cup, if I have 2 cups a red and a green one I can change the order 2 times. If I have 3 cups, red, green, and blue then I can change the order of the cups 6 ways. These cases of factorial make sense but 0! and 1! do not, at least to me.
faint narwhal
if you have two cups, how can you change the order 2 times?
weary tiger
Okay so I think the question is if you have zero objects, then how can you rearrange them one time?
faint narwhal
By the exact same way as your one ordering of [red]
you'll have one ordering of []
weary tiger
If there is nothing in the set how can it be ordered?
faint narwhal
What's your definition of "an ordering of a set"?
weary tiger
I suppose the thing is, I don't see how you can rearrange nothing. There are no elements in the set. If we think about an array on a computer as a set it has elements and each element has an index so like an object with an index and some piece of information, like a integer, string, or a double etc. The order would depend on the index 0 being the first, 1 being the second, etc. But if there no elements within the array, then there's nothing to rearrange.
That's how I think of ordering in an set leftmost is the first element and rightmost is the last.
If a set is empty it doesn't have a left most element.
[]
I have heard of the empty set but it's empty, or does it contain the empty set aswell?
faint narwhal
That's really the problem, you need to come up with some rigorous definition of ordering to actually be able to do math
no, the set that contains the empty set is not empty, because it has an element
namely the empty set
weary tiger
Well I agree with that, I almost didn't say it because i'm like that must not be empty.
faint narwhal
Anyways, if you tried to come up with any rigorous definition of ordering, you'd see that the definition for 0 will give you 1
Like here's one definition that's probably the most common
The number of permutations on a set is the number of bijections on the set
If you know what bijections are
weary tiger
How would I start coming up with a rigorous definition for ordering?
ivory badge
How would you suggest?
weary tiger
I will think about it and get back to you.
robust mango
@smoky sandal You sure that's the question? n(2n-1) doesn't seem to work for n=2.
smoky sandal
yeah thats the question
stray reef
it works just fine for n=2 sup
robust mango
have I gone crazy? n(2n-1) for n = 2 gives us 2(3) = 6. Although it should be 5?
opal crescent
@smoky sandal have you got it yet?
smoky sandal
yeah I figured it out
- 11n-4n is divisible by 7 for any n >0
Mathematical induction yet again
opal crescent
11n-4n you're sure about that?
smoky sandal
11^n-4^n
smoky sandal
yeah lol sorry just realized formatting doesnt transfer over
opal crescent
k so have you tried anything or not?
smoky sandal
i know that the basis is divisible by 7 --> 11^1-4^1 = 7 ... 7=7
now i just need to prove it
opal crescent
well ok
let's suppose 11^n - 4^n is divisible by 7 for some n>0
you wanna show that 11^(n+1)-4^(n+1) is divisible by 7 from that right
smoky sandal
yes
opal crescent
11^(n+1)-4^(n+1) hmmm....
what would be cool is making our induction hypothesis appear in here
like i wanna see some 11^n and 4^n in there
how could you do that?
smoky sandal
11x11^ n-4x4^n
opal crescent
well i mean there's two ways you could split your powers here
either you make 11 * (11^n-4^n) or 4 * (11^n-4^n) appear
smoky sandal
?
opal crescent
sorry i typed enter too fast
smoky sandal
its all good
weary tiger
11=7+4
sour arrow
Quick maffs
opal crescent
well yea that's the rough idea
weary tiger
From this observation you should be able to continue
smoky sandal
7 * 11^n+ 4 * 11^n -4 * 4^n
weary tiger
exactly
opal crescent
yea
weary tiger
Btw dont check the base case, you have to believe the author the question is right.
smoky sandal
yeah but my teacher wants me to write it out so i mentioned it
so where do i go from here
weary tiger
factor out
weary tiger
and you can see its addition of two numbers divisible by 7
opal crescent
let's just not do the induction then
smoky sandal
so 7 * 11^k {div by 6} + 4(11^k-4^k) {div by 6 by assumption}
weary tiger
lel yeah looks fine
weary tiger
n2?
weary tiger
what
smoky sandal
- 1+3+5+…+(2n-1) = n^2 for any n>0
smoky sandal
It should be k^2+(2(k+1)-1)=(k+1)^2?
weary tiger
worth writing more
for example where did the first line come from
you should write 1 + 2 + ... + 2n-1 + 2n+1
and wrote using induction assumption its equal to n^2 + 2n+1
makes it more clear
smoky sandal
alright i made the changes but does it look right?
weary tiger
yes
smoky sandal
- Please show that an algorithm with complexity n^2 is more efficient than an algorithm with complexity 2^n. In other words,
starting from some n,
n^2 < 2^n
heres the next one haha
weary tiger
just prove it
smoky sandal
where do I start
weary tiger
by proving it
weary tiger
by using your brain
smoky sandal
may i borrow yours?
smoky sandal
okay lol
weary tiger
when you see n you do induction thats how math works
smoky sandal
yep
weary tiger
so dont post any more of those problems before like thinking about them for more than 5 seconds
if its indeed harder and you got nowhere ask for help
burnt atlas
Hi, I was trying to do Q2C (an equivalence class question) and I am not sure what combination would work. May I ask for your help?
burnt atlas
nvm I think I got it
atomic pulsar
Anyone know how to solve this?
I know both are arithmetic.
And left got An = 2+3n-3, right An = 1+4n-4
So I had a thought that: 2+3n-3-1 = 1+4n-4-11
n = 12
When n = 12 I find that A12 for left = 35
and for right = 36
So that would make sense if x = 36 and x-1 = 35
But when I add the sum for left and right they don't match
obtuse minnow
Don't you want Sn?
atomic pulsar
Yeah, I use that after when I've found when x is the same
12(2+35)/2 = 12(1+36) -> here we quickly realise it's the same BUT
right got -11
so 12(2+35)/2 is not the same as 12(1+36)/2 -11
😐
obtuse minnow
... no ... no ... you should use Sn on both sides.
2 + 5 + 8 + 11 is Sn ... each element of the sum is an An ...
atomic pulsar
But how can I apply n(a1+an)/2 when I don't know n yet?
obtuse minnow
you just solved your own problem. You know the formula for An ... so plug in an in the n(a1 + an)/2.
obtuse minnow
okay going more detailed here. for the left side (we'll use an on the left and bm on the right).
an = 3n - 1, no? That part is fine. Good work!
So if an = x-1, what is n?
obtuse minnow
it's a pretty messy problem.
atomic pulsar
Cause then x = 3n...
atomic pulsar
What do you mean by bm?
Haven't really done math since like 7 years back, not really good with english terms either 😄
obtuse minnow
bm = 1, 5, 9, 13, 17, 21 ...
you're doing fine. It's an involved problem without tricks.
atomic pulsar
oh okay
obtuse minnow
you don't know if the two sides have the same number of terms.
obtuse minnow
So here's the cool tricky part: you got n's on the left and m's on the right. BUT they are Both related to the variable x. So make all the m's into x's and all the x's into n's.
4m - 3 = x, 3n = x 🙂
atomic pulsar
hmmmm
obtuse minnow
er ... hmm ... what's a1?
atomic pulsar
a1 = 2 for left and 1 for right
obtuse minnow
a1 = 2 and b1 = 1 just humor me 🙂
So what is the sum of the left n(a1 + an)/2 right? Just make all the a's go away.
atomic pulsar
n(2+x)/2 ?
atomic pulsar
waiting
atomic pulsar
n(1+x)/2-11
obtuse minnow
well we don't know if the two sides have the same number of terms so we have to put a different variable.
m(1 +x)/2 - 11
atomic pulsar
alright
obtuse minnow
so 3n = x ... solve for n and replace all the n's in the equation.
ditto for m.
good luck with the resulting mess. 🙂 I'll be here but it's a quadratic.
atomic pulsar
Thanks, I'll give it a try (on paper) 😄
obtuse minnow
you are very welcome.
weary tiger
function maximum(array) {
let max = array[0];
for (let i = 1; i < array.length; i++) {
if (max < array[i]) {
max = array[i];
}
}
return max;
}
Hi, does this do 2n - 1 comparisons ?
keen oasis
desert edge
How can you apply the ant-colonisation method to the travelling salesman problem?
Isnt the objective to figure out the shortest distance between all points? It seems to create a network rather than a trip
Also is there any other biomimicry solutions related to this problem?
zealous mantle
@weary tiger Yes it does 2n - 1. You can count it, the one in the loop does n, and the inner one does n - 1. So n + n - 1 = 2n - 1
zealous mantle
rip
zealous mantle
You wrote it in JS, you could've added a counting variable too.
weary tiger
right
i should have
if my prof started the array at index 1
so that max = array[1]
and then for i = 2 to n { }
that doesn't change the answer does it?
wait wait
I just tested it with 7 items
function maximum(array) {
let max = array[0];
comparisons += 1;
for (let i = 1; i < array.length; i++) {
comparisons += 1;
if (max < array[i]) {
comparisons += 1;
max = array[i];
}
}
return max;
}
That results in 11 comparisons which is 7 * 2 - 3
zealous mantle
That's not right.
Firstly your not counting the loop comparisons, and you haven't defined comparisons.
weary tiger
let comparisons = 0;
function maximum(array) {
let max = array[0];
comparisons += 1;
for (let i = 1; i < array.length; i++) {
comparisons += 1;
if (max < array[i]) {
comparisons += 1;
max = array[i];
}
}
return max;
}
I thought I am counting the loop comparisons on line 7
On line 5 we count a comparison extra because if we don't enter the for loop we have still made a comparison
and line 9 we count the comparison in the if statement
zealous mantle
Right, but on line 9 the comparison counter will only increase if the comparison is true.
Even if the comparison is false, a comparison has occurred.
weary tiger
Ok, I have moved it to before the if
and now I get 16 comparisons for 9 items in the array
console.info(comparisons);```12
16
I'm pretty sure it should be 2n - 1.
Here's what I'm doing:
function maximum(array) {
let max = array[0];
let comparisons = 1;
for (let i = 1; i < array.length; i++) {
comparisons += 2;
if (max < array[i]) {
max = array[i];
}
}
return comparisons;
}
console.log(maximum([1,2,3]))
I set comparisons to 1, because there is an initial comparison at the start.
After that, 2 comparisons should occur on the i < array.length and max < array[i]
zealous mantle
Btw, idk if you know about this
function maximum(array) {
let max = array[0], c = 0;
for (let i = 1; (c++ || 1) && i < array.length; i++) {
if ((c++ || 1) && max < array[i]) {
max = array[i];
}
}
return c;
}
You can do this.
Although it looks weirder, it forces a counter within the comparisons.
weary tiger
looks too weird
zealous mantle
So you should get an accurate count of the comparisons
zealous mantle
Yeah you shouldn't.
But for your case of counting comparisons, that should give you a pretty accurate read.
zealous mantle
How can you apply the ant-colonisation method to the travelling salesman problem?
Isnt the objective to figure out the shortest distance between all points? It seems to create a network rather than a trip
Also is there any other biomimicry solutions related to this problem?
@desert edge
As far as I know ant-colonisation optimisation can be used on traveling salesman, but it will be like an exhaustive search.
TSP, wants to create the shortest path, which visits every node.
ACO, would begin attempting every path, whenever it finds a "short" path, it leaves "pheromones", but actually just increases a point/value on that path. Which means more "ants" will visit the path. Eventually the most visited path by the ants will be the shortest path.
anyone can help me with that demostration??
@keen oasis Ask #proofs-and-logic
zealous mantle
Need help with Regular Languages but will ask l8r.
desert edge
@zealous mantle I used an hilbert curve SFC on this. I got this route
Could I expect the same results from an ACO?
I tried doing it but I couldnt make it work
dont mind the bad drawing. Im doing it on ps for now before graphing
weary tiger
k(10) k(15) k(10, 10) k(10, 15) how do i determine if these have euler/hamilton cycles/paths
<@&286206848099549185>
shut fjord
Five distinct points are picked on the circumference of a sphere. Show that 4 of them must lie on the same closed hemisphere (where a closed hemisphere is half of the circumference, including the dividing circle).
SOLUTION: Pick two points, this defines a circle on the sphere. This splits the surface of the sphere into two hemispheres. By the Pigeonhole Principle, of the remaining 3 points,two of them must be in the same hemisphere. Thus all four of them are on the same closed hemisphere.
I found an image of this that resembles something to what this problem is describing:
but a hemisphere of course is when our points are the maximum distance away from one another (E.g; north and south)
faint narwhal
great circles
shut fjord
and this great circle is what cuts my sphere into 2 semispheres right?
faint narwhal
yes
shut fjord
Find the coefficient of x^2 in the expansion (x + 1/x)^10
Can someone help me with how to approach this type of problem?
obtuse lance
you know the binomial theorem?
shut fjord
yeah
but I don't know how to use it for a single term
I've seen it used with x and y
What I have so far is 10C?
10 choose ?
obtuse lance
ok so when you do it you end up with x^a y^b with some numbers a and b right
shut fjord
yes
obtuse lance
a+b=10
obtuse lance
try to focus on that with y=x^-1 that might help
keep an eye on what you're trying to make with your exponents
shut fjord
if y = x^-1
okay here's what I did
since I only have one term, I can treat my x term like a y term (like Merosity suggested)
then I can write my x in terms of j and n-j or (x)^j(1/x)^(10-j) = x ^ 2
then we solve for j
j comes out to 6
zealous mantle
@zealous mantle I used an hilbert curve SFC on this. I got this route
@desert edge You should get something similar with ACO. But not the same result.
zealous mantle
k(10) k(15) k(10, 10) k(10, 15) how do i determine if these have euler/hamilton cycles/paths
@weary tiger
- To find an Euler cycle, you need 0 odd degrees.
- To find an Euler walk, you need only 2 odd degrees.
- To find Hamiltonian cycle, you can either test it out, or use Ore's Theorem
- Ore's theorem states for all graphs with vertices >= 3, if the sum of two unconnected nodes is >= number of nodes, it has a Hamiltonian cycle.
K_10, will only have node will have 9 degrees.
K_15, will only have nodes with degree 14
K_10,10, will also only have nodes with 9 degrees.
K_10,15's top row will have nodes with degree 9, and bottom row with degree 14.
K_10 and K_15, there are no non-connected vertices, so it is automatically Hamiltonian.
For K_10, there will be 10 unconnected vertices on the top and bottom.
Each of them will have 10 degrees. So the sum of two unconnected nodes is 20.
Same thing with K_15.
zealous mantle
@shut fjord So to find the x^2 coefficient of (x + 1/x)^10, you use Binomial Theorem as Merosity said.
The easy way is to do this is by considering 1/x as x^-1.
So the binomial theorem is:
When you have (ax + by)^n, you can find each coefficient by using
nCi * a^(n-i) * b^i, where i, is basically like the nth value of the expanded form.
If you expand (1x + 1x^-1)^10, the powers will start at -10 and increase by 2
so it will be like x^-10 + x^-8 .... + x^8 + x^10
So x^2 will be the 6th iterations ((2+10)/2 = 6)
Which means we can use the binomial theorem:
But since the "a" and "b" part are 1's we can ignore it.
So the answer will be 10c6 = 210
Which means it will be like .. + 210x^2 + ..
zealous mantle
It says:
Normal distribution, positive x value
This is statistics not discrete maths
I assume the function describes a normal distribution
unreal berry
oh yeah you are right sorry.
zealous mantle
Yeah try #probability-statistics
ivory badge
not all infinities are the same
robust mango
I'm not sure but maybe it has got something to do with countability? set of integers is countable, set of reals isn't
stray reef
what
obtuse lance
you're saying f (g(1)) and f(g(2)) are distinct?
stray reef
g . f is a function from A to C yes
what
f . g isn't even defined
what are you on about
where do you even get anything about "changing g" from
there are many ways you could do that
but they all boil down to having g not be one to one.
obtuse lance
in the solution they write out f and g as sets, do the same thing for g of f and show us
it's just 3 tuples, seeing is believing I think
write it out like I said
stray reef
$g(f(1)) = \pi \ g(f(2)) = \pi \ \pi = \pi \ 1 \neq 2$
vital dewBOT
Ann:
stray reef
$(g \circ f)(1) = (g \circ f)(2)$ yet $1 \neq 2$
vital dewBOT
Ann:
deep tapir
To what extent can we find a generating function for a recurrence relation? If I have a linear recurrence relation, can I find the generating function for the sequence it produces? What about a system of linear recurrence relations?
obtuse lance
hmm yeah you could do that, never thought about it before but it should be simple enough I think
the generating function for the system of linear recurrence relations would have vector coefficients and the generating function would satisfy a matrix identity
well I should have answered your other question, yeah you can always do that with the linear recurrence relation, it's not too complicated to do
$f(x)=\sum_{n=0}^\infty a_n x^n$
vital dewBOT
Merosity:
obtuse lance
here's an ordinary power series generating function, just multiplying by x or removing coefficients and dividing by x gets you a way to shift coefficients
then you can add and multiply to satisfy the recurrence relation by linearity
just keep in mind you will "spill out" a finite number of terms where it doesn't overlap
deep tapir
🤔 I see
What if instead of sequences of numbers, we have sequences of functions? Would it make a difference?
obtuse lance
you can, and it is done
you can then sum over that variable in the "function" and switch the bounds to get identities and stuff
just look at the book generatingfunctionology lots of this stuff is laid out with examples
deep tapir
Thanks homie! @obtuse lance
obtuse lance
👍
stray reef
it's not "infinitely countable", it's "countably infinite"
it helps to know your way around the cardinalities of certain common sets like Q and R
R is uncountable, while Q is countable
removing a countable set from an uncountable set still leaves you with an uncountable set
what do you think
hint: this is a subset of N
correct
i don't know why they chose Z when they could've just as easily chosen N
but the point is that P can be injectively mapped to a subset of a countable set
subsets of countable sets are either finite or countable
and why
isdoes f(a) = aimpliesimply thatitsf is 1:1
check it against the definition of a 1:1 function
that is not the definition of a 1:1 function
and if a=b then f(a)=f(b)
this part is true for any function
...
if a != b then f(a) != f(b) is one of the two equivalent definitions of a one-to-one function
now check your function against it
it should become glaringly obvious
now check your function against it
your function is f: P -> Z defined by f(a) = a
is it true that if a != b then a != b
so what's the issue then
what
you are given the definition of your function
f(a) = a
can you tell me what f(7) must be
come back when you are in a clearer state of mind
P is a subset of Z
this is the simplest function possible
in some sense
it's 13:06 where i am
night crescent
Guys, me and my colleagues are confused with part C, some of us are saying the answer should be true, and the other part is saying it's false. Anyone who can explain with the right answer?
night crescent
@stray reef got it. I appreciate your help ^^
pale epoch
$\Gamma$
vital dewBOT
Lochverstärker:
pale epoch
its the capital gamma
vital dewBOT
Ovais:
weary tiger
How many students need to be so that atleast 6 students have the same grade (A, B, C, D, or E) ?
The answer is atleast 26 students according to my textbook.
I have tried "solve for x, (ceiling(x/5))=6" but that gives me 27, not 26.
obtuse lance
I wouldn't use a formula for this
just think about how you would avoid having 6 students having the same grade
if you have 25 students then you can avoid 6 by making groups of 5
but you're completely maxed out, no matter where you add an extra student
obtuse lance
yeah
weary tiger
Ok I gotcha on that
but I'm still curious why the formula doesn't work
"If n objects are placed in k boxes, then atleast one box has atleast ceiling(n/k) objects."
obtuse lance
well how are you getting 27
weary tiger
"solve for x, (ceiling(x/5))=6"
obtuse lance
ceiling(26/5) = 6
weary tiger
solve for x to know the number of students
obtuse lance
you're looking for the minimum x that satisfies it
26 and 27 both work but 26 is the smallest one that works
25 wouldn't work, so there's not a smaller choice
weary tiger
why would they give us a formula that doesn't give the smallest number lol
obtuse lance
they should say "solve for the smallest x"
it's not that exciting
$\min {x : ceiling(x/25)=6}$
vital dewBOT
Merosity:
obtuse lance
you can write something like this if you really want but it doesn't really help
just use your brain
obtuse lance
you're sick
26<27
you don't know how to compute something clearly
plug in x=26 to ceiling(x/25) @weary tiger
weary tiger
ok boomer
bruh we're trying to find 26
I'm not gonna plug it in
What you're saying is "Just plug in the unknown variable bro"
obtuse lance
,w ceiling(x/5)=6
vital dewBOT
Requested by Merosity#4936
weary tiger
weird
obtuse lance
nothing weird about it, ceiling function is just rounding
nothing magic happening
well your calc giving 27 is weird, that's messed up lol
obtuse lance
nah
relying on your calculator to compute ceiling is like using your calculator to add 3+5
it's idiotic
don't be idiotic
obtuse lance
lol I have to shame you out of using the calculator it's my job
faint narwhal
Are you sure that's reflexive?
What does it mean to be reflexive
why is that not transitive?
yes you do
But first of all, if you didn't have any relations that satisfied the "if" part, then it would still be transitive, vacuously
Why is it not?
Can you give me a,b,c such that aRb, bRc but you don't have that aRc?
weary tiger
ok my brain is not functioning and I just joined?
faint narwhal
So then its transitive?
you're allowing a = c here
why don't you allow a = b or b = c?
or both?
a = b = c
But again, you don't need any such thing to happen for it to be transitive
The empty relation {} is transitive
{(1,2), (2,3)} isn't transitive
The relation you gave was both transitive and reflexive
{(1,1), (2,2), (3,3), (4,4)} is both transitive and reflexive
How many times do I have to say this
You don't need a pair a,b,c such that aRb, bRc to be able to "have transitivity"
the empty relation {} is transitive
No your definition is correct
The empty relation satisfies that definition
For all a,b,c such that aRb, bRc, you have that aRb in the empty relation
The "if" part of the statement is never satisfied, but that's fine
This is an example of a vacuous truth
But, you do have plenty of triples a,b,c such that aRb, bRc in {(1,1), (2,2), (3,3), (4,4)}
like 1R1, 1R1
Is this reflexive
Is this symmetric?
Keep trying
Or, its possible that one doesn't exist
So then try to prove it
what
This makes no sense
why is bRc not true? It seems like you're assuming that bRc is true in your first statement
What
What are you trying to find a counterexample to
grand elm
(a \land b \implies b) holds by first order logic
vital dewBOT
Muf:
grand elm
well, we need to check 3 things, is it reflexive, is it symmetric, and is it not transitive
correct
it gets better once you build intuition for these concepts
dire panther
how this works?UnU
heady geyser
how can i go about proving that $f(x)=\left{\begin{array}{ll}
2x & x>0\
-2x+1&x\leq0
\end{array}
\right.
$ is surjective? Where x is an integer
vital dewBOT
l spacebaR l:
heady geyser
I think i should use the property that any positive integer is either even or odd then break it into cases
i dont know if thats the right line of thinking though
fossil pewter
It is surjective only when the codomain is natural numbers
heady geyser
yeah sorry i should have added that $f:\mathbb{Z}\to\mathbb{Z}^+$
vital dewBOT
l spacebaR l:
elder oak
is this induction correct
3^n > 2^ n for n>0
for n=1 it's true 3>2
i will prove for k+1 , k>0
3^k +1 > 2^k +1
since n>0 , 2^k >1 and 3^k>1 i can replace 1's
3^k +3^k > 2 ^k +2^k
23^k > 22^k
since 3>2 (proved for n=1 i can replace 2 with 3.)
33^k > 22^k
3^k+1 > 2^k+1
proved
Is this correct?
loud copper
pale epoch
this text is also close impossible to parse tbh
elder oak
mb it's because i proved it on first 1?
Yea i know but how u do write it fancy
is it latex?
pale epoch
it doesnt need to be fancy
but you need to escape *, if you use it for multiplication
otherwise it interprets it as cursive
and use brackets
"3^k +1 > 2^k +1"
is this 3^(k+1) or 3^k + 1
elder oak
second
pale epoch
and why is it there
elder oak
So i can prove if p(x) -> p(x+1)
vital dewBOT
Por:
Compile Error! Click the 
reaction for details. (You may edit your message)
pale epoch
it's just written down weirdly
pale epoch
and i don't get your references to n in your argument
what you are essentially doing is adding the inequality $3^k > 2^k$ to itself to get $2\cdot3^k > 2\cdot2^k = 2^{k+1}$
vital dewBOT
Lochverstärker:
pale epoch
which is fine
elder oak
/[ 3^n > 2^n , n<0 .
Say P(1)=3>2 true
will prove for k+1
P(k+1)= 3^(k+1) > 2^(k+1)
3^k>2^k => 3^k+1 >2^k+1
3^k +3^k > 2^k +2^k , because n>0 and 2^k>1 , 3^k>1
23^k >22^k
3*3^k>2^(k+1) , we replaced 2 with because 2>3
3^(k+1) >2^(k+1)
proved
/]
Yes but is my thinking correct to get the 3^(k+1) . Is this because we proved on step one for n=1 that 3>2 ?
pale epoch
why would you need to prove 3>2
vital dewBOT
Por:
elder oak
this needs to become
[3^(k+1)]
vital dewBOT
Por:
pale epoch
i mean sure, you use that $3\cdot3^k > 2\cdot3^k$
vital dewBOT
Lochverstärker:
elder oak
Yes
pale epoch
technically you only use the fact that $3\cdot3^k \geq 2\cdot3^k$
vital dewBOT
Lochverstärker:
pale epoch
which is clear?
elder oak
Yes
pale epoch
the only line that is problematic to me is
"3^k +3^k > 2^k +2^k , because n>0 and 2^k>1 , 3^k>1"
what is that n
and that is a non sequitur
elder oak
sorry it's k>0
elder oak
that's the
pale epoch
(which is the hypothesis)
elder oak
yes
pale epoch
3^k +3^k > 2^k +2^k does not follow from 2^k>1 , 3^k>1
elder oak
and i need to show that for each k>0 , p(k) -> p(k+1)
i dont get you , you mean how did i replace 1 with 2^k ?
and 3^k
elder oak
cause k>0 , then 2^k > 1 is true
pale epoch
yes
elder oak
i can't replace it then ?
elder oak
i do it so i can conlude to 2^k+1 which is what i need to prove.
pale epoch
well tbh "3^k>2^k => 3^k+1 >2^k+1" is also true
but irrelevant
as i said
what you are actually doing is taking the inequality "3^k>2^k"
which you know is true
and adding it to itself
to get 3^k +3^k > 2^k +2^k
pale epoch
the argument you gave is wrong, because it would just as well follow that "3^k + 2^k > 2^k + 3^k, because 2^k > 1 and 3^k > 1"
but that is wrong
so you can't just replace the + 1 with anything that is greater than 1
you still have to respect the inequality
elder oak
i followed this example
Prove that n<2^n for all natural numbers n.
[ 2^n>n for n>0
2k+1=2k+2k≥2k+1>k+1
]
vital dewBOT
Por:
pale epoch
this example doesn't change the fact that the argument you provided is wrong
pale epoch
yes
and that is fine
you can replace all "+1"'s in an inequality with something that is greater than 1
but what you did is replace it once with 2^k and once with 3^k
vital dewBOT
Lochverstärker:
pale epoch
this is true by hypothesis and bcs adding 1 on both sides doesnt change the inequality
pale epoch
but if i replace the left + 1 by 2^k and the right one by 3^k
then i get
$3^k + 2^k > 2^k + 3^k$
vital dewBOT
Lochverstärker:
pale epoch
which is wrong
because both sides are identical
and that is even though both 2^k and 3^k are greater than 1
elder oak
so if i want to replace 1 i need to replace them both with the same thing
to keep it balanced?
pale epoch
essentially yes
adding the same to both sides of an inequality doesn't change it
but what you can do is take the 2 inequalities $$3^k > 2^k$$ and $$3^k > 2^k$$
vital dewBOT
Lochverstärker:
pale epoch
and add them
elder oak
u posted 2 identical things
vital dewBOT
Lochverstärker:
pale epoch
in general you can add the inequalities $a > b$ and $c > d$ to get $a+c>b+d$
vital dewBOT
Lochverstärker:
pale epoch
this works
this is why the conclusion you had is still correct and everything after that works
but the reasoning you gave is wrong
pale epoch
that's why you should just add the inequality to itself
and forget about the +1
to make your argument work
elder oak
But how i say i have 3^k > 2^k and i will add 1 so i can prove P(k) ->P(k+1)
ur way what will i say.
pale epoch
you just add the inequality to itself
or better yet just start with $3^{k+1} = 3\cdot3^k \geq 2\cdot3^k > 2\cdot 2^k \geq \dots$
vital dewBOT
Lochverstärker:
pale epoch
and honestly you should review inequalities
pale epoch
go to khan academy and do the section on inequalities
pale epoch
you need a good grasp on inequalities and what you are allowed to do with them
elder oak
Thanks
vital dewBOT
Por:
elder oak
how do u do this in latex
a^(b+c) doesnt work .
weary tiger
$a^{b+c}$
vital dewBOT
Godel:
elder oak
thanks
weary tiger
I'm trying to find how many ways we can arrange 8 people in a line if there are 5 women, 3 men, and the men must not be next to each other
I start by saying there are 8! total permutations
And I think the best way is to subtract the ones where the men are together
I've tried 8! - (6! * 3!)
fossil pewter
The wordings of the problem is not clear it could mean
- No 2 men should be together
- All of them should not be together (which is the one you solved)
You should look at the problem again to be clear
For 1st one use gap method
weary tiger
It says "if the 3 men must be seperated"
Oh so with what I've solved, it would not count the ones where 2 men are together ?
fossil pewter
Yes
weary tiger
Oh cool thanks for the help
so I could do (total permutations - 3 men together - 2 men together)
or gap method, I will look into that, never heard of it
fossil pewter
Its easy look we don't want men to be together so just place the girls with one gap between them
- G - G - G - G - G - like this
Now that girls can be arranged in 5! Ways
And men have 6 positions to sit on
6P3
@weary tiger
weary tiger
Ok first off I will say that I am very very bad at these problemes
Why do you have 11 spots in your line ?
fossil pewter
I just placed the girls with 1 gap thats all, gaps can also be empty implying girls can be together
Since arrangements can start with a men or women hence the gap at start
weary tiger
Hmm
Sorry why is the line not represented like this ?
Each - could be a guy or girl
fossil pewter
Since we don't want any men together that's why we placed girls with 1 gap
What you did will give you total arrangements
weary tiger
Ok I understand the gap thing now
G - G - G - GG
3 spots there for the men
And 3 x 2 permutations for the men so 6 ?
fossil pewter
Why are there only 3 spots
We can have more spots but we need to fill ONLY 3
- G - G - G - G - G -
weary tiger
Okay
I accept your idea
I'm trying to wrap my brain around it
I'm trying to wrap my brain around it
In a line of 8 people in real life, there would not be 11 spots
there would be 8 spots
fossil pewter
Look at it like this After filling the 3 spots for men the gaps vanishes
weary tiger
Ohhhh
fossil pewter
So if you choose the first 3 gaps the arrangement would be
MGMGMGGG
weary tiger
oh okay totally
okay yea that makes total sense
and then for the permutation of men
it would be the same as when asked "How many ways are there to arrange 3 books from a shelf of 6"
nope lol
fossil pewter
6P3
weary tiger
6! / (6-3)! ?
I don't have that notation in my textbook
I just have P(n, k) = n! / (n - k)!
Or do you mean 6! * 3!
the answer is supposedly 14400
I can't get to it
oh
5! * 6P3
Permutations of women times permutation of men not together
@fossil pewter thx
fossil pewter
Np
brittle marsh
<@&286206848099549185>
pale epoch
have you tried just applying the definitions
brittle marsh
symmetrical difference
pale epoch
just compute $(B \cap \overline{A})$ first
vital dewBOT
Lochverstärker:
brittle marsh
{2,8}
pale epoch
yeah, then apply definition of $\oplus$
vital dewBOT
Lochverstärker:
pale epoch
not really
brittle marsh
hum, okay thank you
pale epoch
probably the matrix multiplied by itself 4 times
weary tiger
Why ?
pale epoch
there are theorems about it
the entry in (i, j) of the adjacency matrix to the power of s counts the number of paths of length s from i to j
judging from the text to the right this is exactly what is being done here
weary tiger
Oh okay I gotcha
so if I wanted the number paths of length s, just do M^s and that'll tell me
pale epoch
yes
weary tiger
thx
pale epoch
for a suitable definition of path
weary tiger
Would you use an ajency matrix for this @pale epoch
pale epoch
it depends what you want to do with it?
weary tiger
"How many trajectories with maximum 2 layovers come from and leave toronto"
Oh I could do a matrix
and sum whatever (i, j) represents toronto kinda
pale epoch
i guess
first translate the question into the language of graph theory
and then compute that probably using the adjacency matrix
weary tiger
@pale epoch is this right ?
It's asking how many paths with maximum 2 layovers from A to F
So I did M^2 and (1, 5) gives me 1 instead of 6
pale epoch
not sure, would have to check the theorem
this would give you paths of length 2 but don't you have to add the paths of length 1 as well?
weary tiger
Sure, but (1,5) is 0 with M^1
pale epoch
then it seems fine to me
weary tiger
the answer is 6, though
pale epoch
what's the definition of length of a path?
number of edges in it or number of vertices?
and what exactly does 2 layovers mean
maximum 2 cities between?
so that would mean it's path with 4 cities total
A-x-y-F
where x, y are arbitrary
pale epoch
yeah might be
check the definition of what exactly a path is
and what it's length is
and how to interpret "maximum 2 layovers"
minor zephyr
How many bit strings contain exactly five 0s and 14 1s if
every 0 must be immediately followed by two 1s?
I got 17*14*11*8*5 because when you group the '011's together, you have 17 choices for the first 011, 14 for the second, 11 for the third, and so on. Is there a more efficient way of thinking about this problem?
finite frigate
Not sure the number is that high
You have five 011s. That leaves 4 1s that each can be placed before, after, or in between two 011s
There are 6 possible spots to place each 1
4 are in between a 011, then there's the beginning or end
Not too familiar with combinatorics, but it's equivalent to asking "how many ways can you arrange 4 identical plates into 6 buckets, where order of buckets is significant"
Maybe (4 + 6 - 1)!/(4! * (6 - 1)!) = 9!/(4! * 5!) = 126
I also get 126 by computing f(6, 4), where
f(1, p) = 1
f(b+1, p) = sum [i=0..p] f(b, i)
b is the number of buckets and p is the number of plates
Maybe I'm getting ahead of myself
Ah, it's just called combinations with repetition
minor zephyr
mine's definitely wrong because it doesn't things into account some things I just thought of a minute ago. I'm not quite following ur thought process tho
finite frigate
Ya know, there's actually a much simpler way to think of it
So you have five 011s, and that leaves 4 1s right?
minor zephyr
yes
finite frigate
Let's just call a 011 an a and a 1 a b. So the question is how many ways are there to arrange 5 as and 4 bs
finite frigate
We have 9 total items to arrange, so 9! is the number of permutations of those items, but each a is identical, so we divide by 5!, and each b is identical, so we divide by 4!
9!/(4! * 5!)
minor zephyr
ah yep. Excellent approach. thank u
finite frigate
Lol much better than my first lmao
minor zephyr
It probably wants you to find a bijection from A to B.
stray reef
hhgmhmfmm low res.
since we know the set of all integers less that -8 is a subset of the set of integers and same goes for the even integers (the set of all even integers is just a subset of the set of integers) which means |A|,|B| <= |Z| but we know the cardinality of Z is the smallest one therefore both of them are equal to |Z|
incomplete
just because two sets are both subsets of Z does not mean they have the same cardinality as Z
your argument as stated would apply to A = {1} and B = {4, 5}
|A|, |B| ≤ |Z| is correct
but then you jump to |A| = |B| = |Z| with no explanation
uh
lemme read that
okay so
with A
the mapping f as stated is defined by f(a) = a-10 for all a ∈ Z^+ but f(a) fails to be a member of A except when a=1
so the function isn't defined properly
with B, the author attempts to introduce a function named g but then talks about a function named f
and says nothing of g at all
between what
A and B, or A and Z^+, or B and Z^+?
mmh
well
there are many ways
i mean. i could pull off something rube goldberg-esque and compose three different bijections
for example
f: A -> Z^+ given by f(a) = 8 - a
g: Z^+ -> Z given by g(n) = n/2 for n even, (1-n)/2 for n odd
h: Z -> B given by h(k) = 2k
f, g and h are all bijections individually
therefore so's their composition h.g.f
and that composition is the bijection you're looking for
it's not necessary to do it like this
distant glade
ann i'm trying to follow, is f(a) not a-9
or are you doing some backwards/inverse work?
sour arrow
I should say that noting both sets are countable and infinite is enough to know that they have the same cardinality. But that's using a lot more power than you need, since you can set up a bijection quickly
distant glade
ah i see
stray reef
and?
distant glade
i'm not too familiar with the notation so excuse the silly questions, but does it not say you mapped it to positive integers?
oh less than
🤦♂️
sour arrow
-9 → 0
-10 → 2
-11 → -2
-12 → 4
-13 → -4
...
Should work as a bijection, no?
stray reef
sure? maybe what i wrote even amounts to that
sour arrow
Oh I see mb
stray reef
i'm just too lazy to write down an explicit formula so instead i'm constructing mine as a composition of three easy to write down bijections
distant glade
one more silly question
what is the composition?
h.g.f
what does it mean
ah i see
sour arrow
Or x(fgh) if you're cultured
distant glade
damn that looks very interesting
stray reef
wdym
why this particular bijection?
i'm mapping the even naturals to the positive integers and the odd naturals to 0 and the negative integers
well
I've given a bijection
if you need me to, i can reproduce the proof that the composition of two bijections is again a bijection
to prove that g.f and hence h.g.f is indeed a bijection
bad wording
"h.g.f: A -> B is a bijection. therefore |A| = |B|"
that's it lmao
don't overthink it
distant glade
|X| is the cardinality of X correct?
stray reef
yes
stray reef
it varies honestly. but it is "discrete math" in some places
distant glade
alright ty
sour arrow
You can also say that f, g, h are each bijections and so their composition is as well
distant glade
what is the typical criteria before taking discrete maths
distant glade
alright thank you
weary tiger
no
balmy nacelle
Hey can you guys help I'm a little stuck on these two problems
a. Give two sets A and B, both subsets of ℕ, such that A ∩ B = B and A ≠ B.
b. Give two sets A and B, both subsets of ℕ, such that A ≠ B and A ∪ B = ℕ.
we can just start with a if anyone wants to help
balmy nacelle
I guess im stuck on like where to even start trying...
Im fairly new to this content
weary tiger
ok so do u know what these symbols mean in the first place?
usually you do these problems by trying first sets that come to your mind
A intersection B = B means B is in A right
balmy nacelle
Yeah I do understand all the symbols
weary tiger
Then just tell me what you tried so far, and if you havent, just do so
weary tiger
what does it mean for two sets to be equal?
balmy nacelle
sets yeah that's what I meant
balmy nacelle
but it says A union B = N
weary tiger
Ok so give your sets A and B
balmy nacelle
does that mean that A and B are all Natural numbers?
weary tiger
yes, they 'add up' to all naturals
weary tiger
union means elements of both sets
balmy nacelle
so like A={1,2,3} B={1,2,3,4}
weary tiger
so like A={1}, B={2}, their union would be {1,2}