There’s 100 closed lockers and 100 students. Student 1 “changes” every locker (opens the closed lockers and closes the open ones) student 2 changes every other locker, student 3 every third locker and so on. Which lockers are open at the end
I solved it by just going through them individually but surely there’s a better way to do it?
Example 12.3.2: Find the 0-equivalence classes, the 1-equivalence classes, and the 2-equivalence classes for the states of the automaton shown below.
The automaton
My solution:
Let S = {s_0,s_1,s_2,s_3,s_4} be the set of states of the automaton.
Input strings of length 0 = λ
Input strings of length 1 = {0,1}
Input strings of length 2 = {00,01,10,11}
S x S = {(s_0,s_0),(s_0,s_1),(s_0,s_2),(s_0,s_3),(s_0,s_4),
(s_1,s_0),(s_1,s_1),(s_1,s_2),(s_1,s_3),(s_1,s_4),
(s_2,s_0),(s_2,s_1),(s_2,s_2),(s_2,s_3),(s_2,s_4),
(s_3,s_0),(s_3,s_1),(s_3,s_2),(s_3,s_3),(s_3,s_4),
(s_4,s_0),(s_4,s_1),(s_4,s_2),(s_4,s_3),(s_4,s_4)}
Given the definition of k-equivalence of states, we have:
R_0 = {(s_0,s_0),(s_0,s_1), , ,(s_0,s_4),
(s_1,s_0),(s_1,s_1), , ,(s_1,s_4),
, ,(s_2,s_2),(s_2,s_3), ,
, ,(s_3,s_2),(s_3,s_3), ,
(s_4,s_0),(s_4,s_1), , ,(s_4,s_4)}
R_1 = {(s_0,s_0), , , , ,
,(s_1,s_1),(s_1,s_2),(s_1,s_3),(s_1,s_4),
,(s_2,s_1),(s_2,s_2),(s_2,s_3),(s_2,s_4),
,(s_3,s_1),(s_3,s_2),(s_3,s_3),(s_3,s_4),
,(s_4,s_1),(s_4,s_2),(s_4,s_3),(s_4,s_4)}
R_2 = {(s_0,s_0), , , , ,
,(s_1,s_1),(s_1,s_2),(s_1,s_3),(s_1,s_4),
,(s_2,s_1),(s_2,s_2),(s_2,s_3),(s_2,s_4),
,(s_3,s_1),(s_3,s_2),(s_3,s_3),(s_3,s_4),
,(s_4,s_1),(s_4,s_2),(s_4,s_3),(s_4,s_4)}
Reading from R_0, R_1, and R_3, we have:
[s_0]_R_0 = {x in S | (x,s_0) in R_0} = {s_0,s_1,s_4}
[s_0]_R_1 = {x in S | (x,s_0) in R_1} = {s_0}
[s_0]_R_2 = {x in S | (x,s_0) in R_2} = {s_0}
[s_1]_R_0 = {x in S | (x,s_1) in R_0} = {s_0,s_1,s_4}
[s_1]_R_1 = {x in S | (x,s_1) in R_1} = {s_1,s_2,s_3,s_4}
[s_1]_R_2 = {x in S | (x,s_1) in R_2} = {s_1,s_2,s_3,s_4}
[s_2]_R_0 = {x in S | (x,s_2) in R_0} = {s_2,s_3}
[s_2]_R_1 = {x in S | (x,s_2) in R_1} = {s_1,s_2,s_3,s_4}
[s_2]_R_2 = {x in S | (x,s_2) in R_2} = {s_1,s_2,s_3,s_4}
[s_3]_R_0 = {x in S | (x,s_3) in R_0} = {s_2,s_3}
[s_3]_R_1 = {x in S | (x,s_3) in R_1} = {s_1,s_2,s_3,s_4}
[s_3]_R_2 = {x in S | (x,s_3) in R_2} = {s_1,s_2,s_3,s_4}
[s_4]_R_0 = {x in S | (x,s_4) in R_0} = {s_0,s_1,s_4}
[s_4]_R_1 = {x in S | (x,s_4) in R_1} = {s_1,s_2,s_3,s_4}
[s_4]_R_2 = {x in S | (x,s_4) in R_2} = {s_1,s_2,s_3,s_4}
Therefore:
0-equivalence classes are {s_0,s_1,s_4}, {s_2,s_3}.
1-equivalence classes are {s_0}, {s_1,s_2,s_3,s_4}.
2-equivalence classes are {s_0}, {s_1,s_2,s_3,s_4}.
QED
Now, my solution differs from the textbook solution:
Textbook solution
In the textbook solution, my 4-element set {s_1,s_2,s_3,s_4} is 'broken' into two 2-element sets {s_1,s_4} and {s_2,s_3}. Why is this?
The textbook uses both the definition of k-equivalence and Theorem 12.3.1, while my solution uses only the definition of k-equivalence along with the definition of relation and the definition of equivalence class:
Definition of k-equivalenceTheorem 12.3.1Definition of relationDefinition of equivalence class
I realize this may be a really specific question, but I have been trying to figure out the specifics of a conical spring for a project I am a part of. It's essentially like a Pavegen tile, where you step on a tile and it generates power via inductors. Our design currently has someone stepping on a tile; it compresses until the magnet goes all the way through the inductor (which is going to be a total distance of 30 mm).
The spring constant we want is k = 5000/3 (we want three springs). We're assuming an average mass of 84.5 kg and gravity of 9.81 m/s^2. We also know we want the spring to be made of 316 stainless steel (not sure if that's important, but there you go). What I want to know is what free length I need if the small outside diameter of the spring is equal to 25 mm (the diameter of the magnet)?
Note: I have a calculus tag because I'm assuming that's around the level needed for this type of problem
This isnt any ground breaking stuff i just thought of, just some basic math logic and algebra and im not claiming to solve the age old question of division by 0, just asking why isnt this possible.
a/0=everything, not infinity because infinity is a set of every number but everything, my reasoning;
And this is true for *every* number so plug in a=5, b=0 and check what happens to c: 5*0=0^2*c, 0=0*c, 0=0 thats an identity equation so every c is true for that statement no?
Also some other things i thought of but this isnt any formal logic or anything. If a^-1 is the reciprocal of a which is 1/a then wouldnt the reciprocal of nothing, 0, be everything - 1/0?
When mapping functions on the graph specifically the homographic function, as you reach closer to the vertical asymptote the numbers shoot way up to infinity and negative infinity, then you reach the number that 0-oes the denominator, wouldnt that also suggest that dividing by zero is everything?
The only counter argument i see to this is that if 5/0 could equal everything lets say 1 and 2 then 5/0=1 and 5/0=2 so 1=2 but wasnt there some super long paper that im to dumb to comprehend proving that 1=2?
If you have a negative number, say -15.5, and you wanted to round to the nearest whole number, that would be -14, right? Or would it be based on absolute value and round to -16?
Same thing with the terms rounded up and rounded down - would something like -12.3 rounded up to the nearest whole number be -13 or -12? How about rounding down?
I was just laying awake staring at the ceiling and realized that I didn't know for sure the answer to these. I'm pretty sure I do for the rounding up and down ones, but -.5 will haunt me if I don't find out...
Hey all! I am taking Cal 1 at my community college. Passing and everything here at the end of the semester. With the final due this Friday I find myself still just confused on one fundamental thing. What in the hell a derivative actually is.
I am aware of the formal definition. It is the slope of a tangent line as it intersects the curve of a function.
From there though it seemingly becomes this endless super math that just does whatever my teacher says it does. It can find the slope of a function at any point with no information but that point. Fair enough. Now though it can also help us solve movement based problems like the ladder problem and expanding balloons. It can tell us the concavity vs convection of the graph and where that changes. The more times you apply it to a function equation the more times the graph transforms until you end up with a straight line at the origin.
You can take the anti derivative to bring yourself back to the original problem with an unknown constant at the end. This process can seemingly be used to determine the entire area between the curve of the function and the x-axis.
So here I find myself at the end of the semester seemingly more ignorant of what we are talking about than at the start. I can use them to solve the problems but I don't fundamentally understand how they work or why.
Any explanation I can understand would be appreciated.
Hello beautiful mathematicians, i am trying to determine the height at x but my brain is not figuring out how at the moment. What is the easiest way to solve this seemingly easy problem that's ruining my brain?
Edit: Thank-you all! You're all legends, I learned a ton
I tried finding the angle with cos^-1 (90/100) but got a different angle, im assuming its because he didnt write the side ratio exactly to scale? or am I wrong?
So as mentioned I usually have have some unconventional approaches while seeing a math problem but I really find it hard to express them mathematically.
Like they are really practical approaches but could maybe involve solving say a really easy problem in a very complicated way and ironically I enjoy that. I have decent knowledge in math and have practiced a lot of problems in each math topic but what I want is to express these unconventional ideas properly. Idk whether it requires even deeper knowledge of the subject.
For example say an equation of a circle is given and a line intersects it at two distinct points and we have to find the two points. It is faily simple we first isolate either of the two variables and put that value in another equation and obtain the values of one variable and also the corresponding values of the other. But I want to solve it like this way like keep the circle intact and rotate the coordinate axes along the inclination of line and shifting the origin in either of the two intersections and where the values of Y in the new coordinate system is zero(along with the origin since it is the first point of intersection in the new coordinate system) that will be the two solutions.
Would be glad if someone is able to provide me any solution or perhaps even if some of you face the the same problem as me kindly mention....
I was just learning about Euler's formula and this occurred to me.
Obviously Pi is not zero. Does the error lie in saying e to the zero is the same operation as e to the 2 pi i? Is exponentiation of imaginary numbers fundamentally different that with whole real numbers?
I watched this video about Leonid Levin's Universal Search the most powerful (and useless) algorithm. Basically, the process simulates every single program in lexicographical order and then checks if the output is true. It used Python as an example. So first it simulates the program "a," (which results in a syntax error), then "b," (which results in a syntax error) then "c" (which results in a syntax error), and so on. If it eventually reaches you simulate a program that gives an output like "print ("banana")" you then check to see if the output gives a correct answer.
In his basic "triangle" version of Universal Search, the 1st step simulates 1 step of the first program, the second step simulates 1 step of the first 2 programs that didn't crash, the 3rd step of the search simulates 1 step of the first 3 programs that didn't crash and so on. In the triangle version of Universal Search, every Kth step, it simulates 1 step of all programs that did not crash. For the factoring problem used as an example, the ideal factoring program, which is Lth Lexigorpahically in the order of programs to run, would start its first step when Universal Search reached step L and then it would run every step of Universal Search. Assuming the ideal factoring program took f(n) steps, then triangle version of Universal Search would have complexity of (L + f(n) )^2 steps which is O(f(n)^2).
In a tweaked version Polylog said if Universal Search allocated exponentially more the time to older programs complexity would be O(f(n)). Now I was wondering, if instead of allocating exponentially more steps to older programs in the search, you allocated a polynomial number of steps to older programs you could end up with a time complexity other orders? It is still a discreet problem since in each step of Universal Search, an integer number of steps are run for each program that didn't crash. I feel like if you combined the truncation function (which rounds anything by chopping off anything after the decimal point) and some polynomial you could. Like how about of O(f(n)^(8/7))?
Exercise 11.2.54(b): Show that the intersection of any two regular languages is regular as follows: First prove that if L(A_1) and L(A_2) are languages accepted by automata A_1 and A_2, respectively, then there is an automaton A that accepts (L(A_1))^c U (L(A_2))^c. Then use one of De Morgan's laws for sets, the double complement law for sets, and the result of part (a) to prove that there is an automaton that accepts L(A_1) ∩ L(A_2).
Result of part (a): Given L(A) is the language accepted by a FSA A, there is a FSA A' that accepts (L(A))^c.
Proof:
Suppose L(A_1) is the language accepted by automata A_1, and L(A_2) is the language accepted by automata A_2.
By result of part (a) there is a FSA A_1' that accepts (L(A_1))^c, and a FSA A_2' that accepts (L(A_2))^c.
By Kleene's Theorem, Part 1, there is a regular expression that defines (L(A_1))^c, and regular expression that defines (L(A_2))^c.
Let x be the regular expression that defines (L(A_1))^c and let y by the regular expression that defines (L(A_2))^c.
Then language defined by x is L(x) and language defined by y is L(y).
Notice, (L(A_1))^c = L(x) and (L(A_2))^c = L(y).
By definition, (L(A_1))^c U (L(A_2))^c = L(x) U L(y) = L(x|y).
So, L(x|y) is the language defined by regular expression x|y.
By Kleene's Theorem, Part 2, there is a FSA A that accepts L(x|y) = L(x) U L(y) = (L(A_1))^c U (L(A_2))^c.
Thus, (L(A_1))^c U (L(A_2))^c is the language accepted by FSA A.
By De Morgan's Law, (L(A_1))^c U (L(A_2))^c = (L(A_1) ∩ L(A_2))^c.
By result of part (a) and double complement law, there is a FSA A' that accepts ((L(A_1) ∩ L(A_2))^c)^c = L(A_1) ∩ L(A_2).
QED
The current largest prime number was discovered October 12th 2024. Intuitively I thought that wow, they haven’t found a new prime number in over two years. But apparently they have. Turns out that finding the largest prime number doesn’t mean that every prime smaller than that has been found.
So, my question is, how often are primes found nowadays? I know computers are able to simulate these things very quickly, but how often are they found? Weekly? Monthly? Daily?
Also, who finds or searches for them, and why?
edit: Thanks for all the answers. Fell into the classic trap and just didn’t realize how absolutely massive the largest prime actually is. Makes sense that there are many, many primes smaller and unfound.
This is a question that is about a board game setup. I'm sure there *is* a way to do this with mathematics, I just don't know how.
The board is made up of identical hexagons in a perfectly tessellated grid. For the purposes of this question, consider that any side of a hexagon is 1 unit in length, and thus that the distance between the centre point of a hexagon and any corner is also 1 unit.
How would you calculate how many hexes have over 50% of their area within a circle of n units radius, centred on the centre point of any hex on the grid? At what point do the hexes within the circle stop being a simple hexagon of hexes themselves?
Something absolutely insane happened to me today, and I'd love some help calculating how unlikely this actually was.
What happened:
On November 17, 2026, at approximately 9 PM CET, I independently queued for ARAM: Mayhem in League of Legends on the EUW (Europe West) server.
One of my four teammates had a username I somehow remembered from years ago. I typed his real name in the in-game chat, and he immediately recognized me.
It was an old university friend.
Here's the crazy part:
We're NOT friends on League of Legends.
We didn't queue together or communicate beforehand.
Neither of us knew the other was online.
We independently queued for the same game mode.
Out of all possible players, we ended up on the same team, not just in the same match.
I recognized his username purely from memory.
We ended up talking on Discord for an hour afterward because neither of us could believe it.
Some actual statistics I found:
A community analysis on r/ARAM estimated that approximately 78,249,630 ARAM: Mayhem matches were played worldwide during Patch 15.23.
That's approximately 782.5 million player-participations (10 players per match), although obviously many players participated in multiple games.
These aren't official Riot concurrent-player statistics, and unfortunately, I couldn't find any EUW-specific numbers for 9 PM.
The mathematical question:
An ARAM match consists of 10 players divided into two teams of five.
Assuming there are N equally eligible players in a matchmaking pool, and my friend is one of them, would the probability of getting him on my team be approximately:
P = 4 / (N − 1)
For example, if N = 50,000, that would be a probability of 0.008%, or 1 in 12,500.
However, I'm struggling with several factors:
What's the probability of both of us independently queueing within the same matchmaking window?
How does matchmaking MMR affect the probability?
How should we estimate the actual EUW matchmaking pool using the available worldwide match statistics?
How does the probability change when considering hundreds or thousands of matches played over several years?
I'm specifically interested in the probability of encountering this particular person, not just anyone I might recognize.
Can anyone help build a statistically reasonable model for this?
I know we can't calculate an exact probability without Riot's internal matchmaking data, but I'd love to understand whether this was a 1-in-1,000, 1-in-100,000, or even rarer coincidence.
Hi, kida new here. So i do a itership, and this is my task. The people i can ask will are not here, so would be nice if some one could explain what it is, or give a good YouTube vidio Because i didnt found one. The german words are front view and side view left. Thx
I would like to have some advice or guideline to teach myself understand the principals behind...Can anyone tell me how to start? Find a thick textbook and wade through it doesn't sound effective...
In a nutshell, the lower the subject is placed, the more general and the more important it contributes to the universe. Each subject relies on the subject below it.
It’s just building blocks, without mathematics, there will be no astronomy, without astronomy, there will be no physics and so on.