Welcome to Smogon! Take a moment to read the Introduction to Smogon for a run-down on everything Smogon, and make sure you take some time to read the global rules.
Alice and Bob are playing a game. Alice draws 5 random cards from a standard 52 card deck. Alice may then show Bob 4 of the cards in whatever order she likes. They win the game if Bob can precisely guess the 5th unrevealed card in one try. What strategy should they employ?
Each of the cards can be assigned a numeric value from 1 to 52. For the four cards shown to Bob, they should be considered in relative order (1st largest, 2nd largest, etc), and there are 4! = 24 possible relative orderings which are also assigned a numeric value. The value assigned to the largest card out of the four shown to Bob is added to the value assigned to the relative order in which they were shown, and that value modulo 52 is equal to the number assigned to the fifth card.
Usually, the largest card should be chosen as the fifth unrevealed card. However, if the difference between the largest and second largest card is greater than 24, then the smallest card should be chosen as the unrevealed card instead. For example, if the five cards are (1, 2, 3, 4, 29), then Alice cannot show (1, 2, 3, 4) to Bob since 4 + 24 is not enough to reach 29. However, Alice can choose to show (2, 3, 4, 29) in the relative ordering corresponding to 24, and the result is (29 + 24) % 52 = 1. Increasing the gap between the largest and second largest card decreases the gap when looping back around, so it is always possible to pick the fifth card such that it is possible to reach it from the largest card in the set shown to Bob.
Each of the cards can be assigned a numeric value from 1 to 52. For the four cards shown to Bob, they should be considered in relative order (1st largest, 2nd largest, etc), and there are 4! = 24 possible relative orderings which are also assigned a numeric value. The value assigned to the largest card out of the four shown to Bob is added to the value assigned to the relative order in which they were shown, and that value modulo 52 is equal to the number assigned to the fifth card.
Usually, the largest card should be chosen as the fifth unrevealed card. However, if the difference between the largest and second largest card is greater than 24, then the smallest card should be chosen as the unrevealed card instead. For example, if the five cards are (1, 2, 3, 4, 29), then Alice cannot show (1, 2, 3, 4) to Bob since 4 + 24 is not enough to reach 29. However, Alice can choose to show (2, 3, 4, 29) in the relative ordering corresponding to 24, and the result is (29 + 24) % 52 = 1. Increasing the gap between the largest and second largest card decreases the gap when looping back around, so it is always possible to pick the fifth card such that it is possible to reach it from the largest card in the set shown to Bob.
I solved it with a similar method. With 5 cards, at least two of them will be the same suit. Use the first revealed card to indicate the suit. The remaining 3 can be permuted as you mentioned to indicated +1 to +6 on the first card, and you can choose the first card so that the gap is less than 6 when you consider looping in much the same way you mention.
Logic riddles. No looking up answers. If you solve, post a new riddle.
Three prisoners are each given a hat. The hats come in 3 colors (black, white, and red) and it is possible for multiple prisoners to have the same colored hat. Each prisoner can only see the hats of the other two prisoners, and has to guess the color of their own (they can't hear other guesses). If at least one of them guesses right, all of them are set free. If all three guess wrong, they are sentenced to death. Find a strategy for the prisoners to guarantee success.
Here's a simpler solution (I think it's more verbose but more understandable where the difficulty is coming from).
I'll start with 2 prisoners 2 colors. Let's say its color 0 and color 1 and list the possibilities as (0,0), (0,1), (1,0), (1,1). Basically, given any strategy, you as an individual prisoner have a 50% chance of getting it right and that means you can get two right, but that means you will get two wrong too. The secret to this puzzle is knowing you can choose which two you get right and get wrong, and you can make it so the ones you get right, the other prisoner gets wrong and vice versa. The key is that you both can't get a possibility right or you will both get one wrong.
So you have to split up the possibilities.
So it's like: (0,0) - prisoner 1 will say: I want (0,0)! So if prisoner 1 sees a 0 he will guess 0. So this means he will get (1,0) wrong. So prisoner 2 will say ok I will get (1,0). So if he sees a 1 (remember, (1,0) means prisoner 1 has the 1) then he will guess 0. So that means he will get (1,1) wrong. So prisoner 1 will say ok, I will get (1,1). So if prisoner 1 sees a 1 he will guess 1. But that means he gets (0,1) wrong. So prisoner 2 says if he sees a 0 he will guess a 1!
So:
If prisoner 1 sees a 0 he will guess 0. (Covering (0,0))
If prisoner 1 sees a 1 he will guess 1. (Covering (1,1))
If prisoner 2 sees a 0 he will guess 1. (Covering (0,1))
If prisoner 2 sees a 1 he will guess 0. (Covering (1,0))
So if you see that you might ask - can prisoner 1 cover any two possibilities?
Well for sure he can't cover (0,0) and (1,0) - if he sees a 0, he can only guess either a 0 or a 1. Can he cover (0,0) and (0,1)? Well that means prisoner 2 has to cover (1,0) and (1,1), but he can't do that, because when he sees a 1 he can't guess 0 and 1.
The non obvious thing is seeing if this will work with 3 prisoners / colors but it does give a clue on how to do 3 prisoners and colors. It does roughly but it's a lot of work to type out!
So the first thing to note is the naive solution doesn't work.
Let's say prisoner 1 says I want (0,0,0), so I need help with (1,0,0) and (2,0,0). So prisoner 2 says I will do (1,0,0) and prisoner 3 says I'll take care of (2,0,0). Now prisoner 2 will get (1,1,0) and (1,2,0) wrong so prisoner 1 and 3 will do that in that order. Let's say you keep continuing it in this order. You'd get something roughly like this (the number after the triple is the order in which you'd pick that triple - you need 27 triples because there are 3*3*3 color combinations).
And we see the 15th choice is incorrect because prisoner 3 cannot cover both (1,0,1) and (1,0,2)! The algorithm I used to pick the triple is basically the oldest "forced pick" asks for help on that forced pick.
So the real reason for modular arithmetic is finding a nice way to cover all the possibilities.
You have (0,0,0) - (2,2,2) and you need to partition so that prisoner 0 has a strategy for (0,0) - (2,2) = 9 policies and the same for prisoners 1 and 2. Each policy represents getting one guess right, so you have to make sure these policies don't overlap. You can do thsi with mod arithmetic, each tries to get the sum mod 3 equal to 1 less than their prisoner number.
So:
If prisoner 1 sees a (0,0) he will guess 0. (Covering (0,0,0))
If prisoner 1 sees a (0,1) he will guess 2. (Covering (2,0,1))
If prisoner 1 sees a (0,2) he will guess 1. (Covering (1,0,2))
If prisoner 1 sees a (1,0) he will guess 2. (Covering (2,1,0))
If prisoner 1 sees a (1,1) he will guess 1. (Covering (1,1,1))
If prisoner 1 sees a (1,2) he will guess 0. (Covering (0,1,2))
If prisoner 1 sees a (2,0) he will guess 1. (Covering (1,0,0))
If prisoner 1 sees a (2,1) he will guess 0. (Covering (0,2,1))
If prisoner 1 sees a (2,2) he will guess 2. (Covering (2,2,2))
If prisoner 2 sees a (0,0) he will guess 1. (Covering (0,1,0))
If prisoner 2 sees a (0,1) he will guess 0. (Covering (0,0,1))
If prisoner 2 sees a (0,2) he will guess 2. (Covering (0,2,2))
If prisoner 2 sees a (1,0) he will guess 0. (Covering (1,0,0))
If prisoner 2 sees a (1,1) he will guess 2. (Covering (1,2,1))
If prisoner 2 sees a (1,2) he will guess 1. (Covering (1,1,2))
If prisoner 2 sees a (2,0) he will guess 2. (Covering (2,2,0))
If prisoner 2 sees a (2,1) he will guess 1. (Covering (2,1,1))
If prisoner 2 sees a (2,2) he will guess 0. (Covering (2,0,2))
If prisoner 3 sees a (0,0) he will guess 2. (Covering (0,0,2))
If prisoner 3 sees a (0,1) he will guess 1. (Covering (0,1,1))
If prisoner 3 sees a (0,2) he will guess 0. (Covering (0,2,0))
If prisoner 3 sees a (1,0) he will guess 1. (Covering (1,0,1))
If prisoner 3 sees a (1,1) he will guess 0. (Covering (1,1,0))
If prisoner 3 sees a (1,2) he will guess 2. (Covering (1,2,2))
If prisoner 3 sees a (2,0) he will guess 0. (Covering (2,0,0))
If prisoner 3 sees a (2,1) he will guess 2. (Covering (2,1,2))
If prisoner 3 sees a (2,2) he will guess 1. (Covering (2,2,1))
And these policies don't overlap because if they overlapped they'd have the same sum mod 3 but they don't. Now a good question is is this the only set of policies that work? I'm not sure but don't really want to think about it rn. Well here's a way to think about it.
How do you decompose (0,0,0) -> (2,2,2) so no policies overlap?
Well what does it mean for a policy to overlap?
It means that they have two of the same number. So (0,0,0) and (0,0,1) overlap for prisoner 3. So you could make a graph where the triples are vertices and they're connected if they overlap.
So (0,0,0) is connected to (0,0,1), (0,0,2), (0,1,0), (0,2,0), (1,0,0) and (2,0,0). So each thing is connected to 6 things. And you need to find a way to pick 9 vertices where none of them are connected to each other. And you need to do this for each prisoner!
I tried working it out but it doesn't work out with a naive solution so there may be no "intuitive" reason this is the only decomposition. The following is just some work but it's nothing really, might be helpful for someone
My guess is showing it any partition is equivalent to the mod partition is very similar to trying to enumerate the solutions to https://en.wikipedia.org/wiki/Eight_queens_puzzle so it's computational in the sense that maybe more solutions not equivalent to mod exist for higher colors / # of prisoners etc. or the solutions aren't intuitively derivable really. Even the mod solution is "obvious" in the sense that mod is the way to evenly divide things and normally you want to evenly divide things but it's not obvious that the mod solution works in that I don't see any more like general more naive principle behind it (there might be one though!) A final (?) note: the lack of intuitiveness is because of the tension between the "intuitive" visualization of (0,0,0) to (2,2,2) as a 3x3 cube and the more complicated structure of the (using this pages notation) P_3^3 grid graph https://mathworld.wolfram.com/GridGraph.html and also the complexity of a graph with 27 vertices.
(addtl edit) I think some intuition can be gained by noting two vertices are connected if they are next to each other in Z_3 x Z_3 x Z_3. (I'm not sure the standard way to visualize this but basically in {0,2}^3 if you draw it like a 3x3x3 cube and draw lines next to points that are next to each other you notice (1,1,1) is connected to all the things it'd be connected to as above. So one way of thinking about this is looking at Z_3 x Z_3. The only way to tile Z_3 x Z_3 so that you can split up its 9 points so that no partition contains two points which are connected to each other are through taking mod or something equivalent to mod and the challenge would be to show there's some structure on Z_3^3 that comes from Z_3^2 that applies to this problem. The point of this edit is showing that unless Z_3^2's partition into three sets is "intuitively" mod, it's not obvious why Z_3^3's partition into three sets with mod may not really be intuitive so that means there's some interesting thing going on with mod / better way to interpret mod!
(addtl edit) Here: let's say someone is like partition Z_3^2 into three sets such that no two elements in the partition are next to each other. You could say:
simply partition (x,y) in Z_3^2 so that by f(x,y) = x+y mod 3.* Clearly the sets are disjoint because an element can only have one mod. Now this is true but the interesting thing is that the elements within the partition are not next to each other. But you can't say anything that much more general because most statements don't really hold strongly for Z_4^2.
*Note here that the intuitive part is in the x+y, not in the mod 3. All the mod 3 does is really allow you to tile (x+y), (which is a downward sloping line) but any function which goes through three points that aren't connected work! For instance x-y mod 3 works too. Edit (not 100% sure about if any is 100% correct but it's p close if not correct if only bc there aren't that many functions hahaha)
**SIMPLEST SOLUTION**
I think the simplest solution to the 2x2 solution that really reveals why this is somewhat complicated is by putting yourself in prisoner 1s state of mind. It's similar to the first solution but even more explicit. This is VERY non-math friendly.
Let's say you're prisoner 1.
You're trying to think ahead so you say: what if I see a 0?
You can either guess 0 or 1. If you guess 0 then you're safe if you have a 0. But if you have a 1 you are not safe.
So if you have a 1, then prisoner 2 sees a 1.
If prisoner 2 guesses 1 when he sees a 1 then if you have a 1 and he has a 0 (if it's (1,0)) you both guessed wrong so that doesn't work out.
So prisoner 2 has to guess 0 when he sees a 1.
So the takeaway is you guess 0 when you see 0 and prisoner 2 has to guess 0 when he sees a 1.
Now the following are solutions with and without notation - if you were doing this irl you might realize thinking about it like this takes a long time and using specialized notation might make it easier to think about, especially if you were dealing with more than 2 colors and 2 prisoners.
So what if you see a 1?
Then the possibilities are (0,1) or (1,1).
Let's say you want to cover (0,1). Then you guess 0 when you see a 1. So prisoner 2 needs to cover (1,1). But prisoner 2 already guesses 0 when he sees a 1, so he can't cover (1,1). So you need to backtrack. Does it work if you want to cover (1,1)? That means when you see 1 you have to guess 1. Well then prisoner 2 would have to cover (0,1). So when he sees a 0 he has to guess 1.
So what if you see a 1?
You can either guess 0 or 1. If you guess 0 then you're safe if you have a 0. But if you have a 1 you are not safe.
So if you have a 1, then prisoner 2 sees a 1.
But prisoner 2 already guesses 0 when he sees a 1.
So that doesn't work. So if you see a 1 what happens if you guess 1? Then you are safe if you have a 1, but if you have a 0 you are not safe.
So prisoner 2 needs to guess 1 when he sees a 0.
So the takeaway combining the first and second parts are:
if you see 0 guess 0, if prisoner 2 sees 1 guess 0, if you see 1 guess 1, if prisoner 2 sees 0 guess 1.
And that seems like it works and it's checkable!
So (using notation) the complicated part is really that if you cover (0,0), you can't just blindly cover (0,1), you have to try out (1,1) as well.
Suppose the ocean is a 2d grid that extends infinitely in every direction. At some integer coordinates in the ocean, there's a submarine. The submarine moves a constant, integer distance in both directions every day. So for example, maybe the submarine is at (20, 5) and it moves (-3, 14) every day. So day two it would be at (17, 19), then day 3 it would be at (14, 33), and so forth.
You have an infinite arsenal of ballistic torpedos, and you can fire one per day at any point on the grid. If the submarine is there you destroy it (good). You don't know how much it's moving or where it started. What strategy can you employ that guarantees that you'll eventually hit the submarine?
Suppose the ocean is a 2d grid that extends infinitely in every direction. At some integer coordinates in the ocean, there's a submarine. The submarine moves a constant, integer distance in both directions every day. So for example, maybe the submarine is at (20, 5) and it moves (-3, 14) every day. So day two it would be at (17, 19), then day 3 it would be at (14, 33), and so forth.
You have an infinite arsenal of ballistic torpedos, and you can fire one per day at any point on the grid. If the submarine is there you destroy it (good). You don't know how much it's moving or where it started. What strategy can you employ that guarantees that you'll eventually hit the submarine?
First, simplify the problem by assuming that the submarine starts at (0, 0). In this case, it is only necessary to guess the movement vector, since multiplying it by the number of days passed gives it's location. For example, if we were to guess that it moves by (-1, 2) on day 10, then we would shoot at (-10, 20).
By progressing our guesses in a square spiral starting at (0, 0) as shown in the below image, we will eventually guess the correct movement vector when it is reached on the spiral. The first few shots will be (0, 0) on day 1, (1, 0) * 2 = (2, 0) on day 2, (1, 1) * 3 = (3, 3) on day 3, etc.
Now back to the original problem where the submarine can start at any position. Each shot will make a guess at both the movement vector and starting position, and the shot location will be <movement vector> * <current day> + <start position>. We can also guess the start positions using a square spiral, ensuring at every combination of start position and movement vector will eventually be guessed in a finite number of steps along the spiral.
This can be done by advancing by 1 position along the spiral for movement vector guesses, and then guessing each preceding position on the spiral for the starting location. For example, when we reach position 10 on the movement vector spiral (-1, 2), we will iteratively guess positions 1, 2, 3, ... , 10 for the start positions (which correspond to (0, 0), (1, 0), (1, 1), ... , (-1, 2)). In each guess, the current day is updated so that it gives the position of the submarine assuming that the guess for start position and movement vector are correct.
Here's another one:
There are n passengers getting on a plane with n seats, and they all have an assigned seat number. However, the first passenger gets in the wrong seat. Subsequent passengers board the plane one at a time, choosing their assigned seat if possible and choosing a random unoccupied seat otherwise. What is the probability that the last passenger will be able to sit in their assigned seat?
First, simplify the problem by assuming that the submarine starts at (0, 0). In this case, it is only necessary to guess the movement vector, since multiplying it by the number of days passed gives it's location. For example, if we were to guess that it moves by (-1, 2) on day 10, then we would shoot at (-10, 20).
By progressing our guesses in a square spiral starting at (0, 0) as shown in the below image, we will eventually guess the correct movement vector when it is reached on the spiral. The first few shots will be (0, 0) on day 1, (1, 0) * 2 = (2, 0) on day 2, (1, 1) * 3 = (3, 3) on day 3, etc. View attachment 552969
Now back to the original problem where the submarine can start at any position. Each shot will make a guess at both the movement vector and starting position, and the shot location will be <movement vector> * <current day> + <start position>. We can also guess the start positions using a square spiral, ensuring at every combination of start position and movement vector will eventually be guessed in a finite number of steps along the spiral.
This can be done by advancing by 1 position along the spiral for movement vector guesses, and then guessing each preceding position on the spiral for the starting location. For example, when we reach position 10 on the movement vector spiral (-1, 2), we will iteratively guess positions 1, 2, 3, ... , 10 for the start positions (which correspond to (0, 0), (1, 0), (1, 1), ... , (-1, 2)). In each guess, the current day is updated so that it gives the position of the submarine assuming that the guess for start position and movement vector are correct.
Here's another one:
There are n passengers getting on a plane with n seats, and they all have an assigned seat number. However, the first passenger gets in the wrong seat. Subsequent passengers board the plane one at a time, choosing their assigned seat if possible and choosing a random unoccupied seat otherwise. What is the probability that the last passenger will be able to sit in their assigned seat?
The idea is cool and I haven't really seen it before but I'm not sure it actually works in its current state. I think it does work with a modification:
Current problem:
Let's say the movement vector is (0,0) and the start position is (1,0). You might not make a guess that implies ((1,0), (0,0)) ever (or I don't think it's obvious that you will) since you are only guaranteed to guess start positions less than the movement vector I think (where less means w.r.t to the number implied by the spiral).
Quick fix:
Instead of only advancing by 1 along the spiral for movement vector guesses, keep a counter for both movement vector guesses and start position vector guesses.
After you advance by 1 (starting at 0) along the spiral for movement vector guesses, (and iteratively guess positions for the start positions, as before), you keep track of your position on the movement spiral. Then, advance by 1 (starting at 0) along the start position spiral and iteratively guess positions for the movement vector. You have to keep track of your position on the start position spiral.
Then, you go back to the position you kept track of for the movement spiral and advance by 1. You repeat the same thing and after you finish you go back to the position for the start position spiral and advance by 1 and repeat.
In essence you have to make sure you hit not only (0,n),...(n,n) but you also have to hit (n,0),...(n,n). This way double counts (n,n) but otherwise its good and its not too hard to modify it I think.
Note that this is a bijection from n->(n,n) that I think isn't commonly taught! Very cool.
EDIT: Slightly edited to clarify wording
EDIT2: ftr the edit was something like saying "less than the position on the movement vector spiral" as opposed to "less than the movement vector"
The idea is cool and I haven't really seen it before but I'm not sure it actually works in its current state. I think it does work with a modification:
Current problem:
Let's say the movement vector is (0,0) and the start position is (1,0). You might not make a guess that implies ((1,0), (0,0)) ever (or I don't think it's obvious that you will) since you are only guaranteed to guess start positions less than the movement vector I think (where less means w.r.t to the number implied by the spiral).
Quick fix:
Instead of only advancing by 1 along the spiral for movement vector guesses, keep a counter for both movement vector guesses and start position vector guesses.
After you advance by 1 (starting at 0) along the spiral for movement vector guesses, (and iteratively guess positions for the start positions, as before), you keep track of your position on the movement spiral. Then, advance by 1 (starting at 0) along the start position spiral and iteratively guess positions for the movement vector. You have to keep track of your position on the start position spiral.
Then, you go back to the position you kept track of for the movement spiral and advance by 1. You repeat the same thing and after you finish you go back to the position for the start position spiral and advance by 1 and repeat.
In essence you have to make sure you hit not only (0,n),...(n,n) but you also have to hit (n,0),...(n,n). This way double counts (n,n) but otherwise its good and its not too hard to modify it I think.
Note that this is a bijection from n->(n,n) that I think isn't commonly taught! Very cool.
EDIT: Slightly edited to clarify wording
EDIT2: ftr the edit was something like saying "less than the position on the movement vector spiral" as opposed to "less than the movement vector"
Oops, you're right that my solution doesn't quite work. Alternatively, you could just swap the orders after each guess (except when they're equal). Like you guess <movement spiral 7> and <start position spiral 3> and then afterwards guess <movement spiral 3> and <start position spiral 7>. It's basically the same thing but tracked differently.
Here's another one:
There are n passengers getting on a plane with n seats, and they all have an assigned seat number. However, the first passenger gets in the wrong seat. Subsequent passengers board the plane one at a time, choosing their assigned seat if possible and choosing a random unoccupied seat otherwise. What is the probability that the last passenger will be able to sit in their assigned seat?
The important insight here is that there will always be 1 or 0 "homeless" people in line to get on the plane whose seat is occupied. At the start of the puzzle whoever owns the seat that the first passenger got into is the only one. If someone who's not that person enters, then the number doesn't change cause they just sit in their own seat. But if that person enters, they will either sit in the first person's seat (reducing the homeless count to 0) or sit in the seat of a person still in line (increasing the count by 1, but decreasing it by 1 because they entered).
If at any time there are 0 homeless people in line, everyone remaining will just sit in their own seat, including the final person. This only happens when the first person's seat is occupied.
With n people remaining (one of whom is homeless), each time a person enters, there's a 1/n chance that they are the homeless person. If they aren't the homeless person, they enter and we repeat the process with n-1. But if they are homeless, there's a 1/n chance that they sit in the first person's seat, and a (n-1)/n chance that they sit in someone else's seat. So at each step, we have a 1/n^2 probability that no one is homeless any more, otherwise we go onto the next step.
f(n) = f(n-1)(n^2-1)/n^2 + 1/n^2. If n=2, then it's a probability of 0. But this is easier to think about if we define it the other way, where we're computing the probability that they miss their spot, not get their spot.
f(n) = f(n-1)(n^2-1)/n^2 (so this is the probability that they miss their spot, and it's a probability of 1 if n=2).
We can write it iteratively: it's the product of (i^2-1)/i^2 for i from 2 until n. So, 3/4 times 8/9 times 15/16 and so forth. Not sure if there's a pop cute closed form for this. And the solution is 1 minus that product. As n approaches infinity this approaches 1/2.
Here's another one:
There are n passengers getting on a plane with n seats, and they all have an assigned seat number. However, the first passenger gets in the wrong seat. Subsequent passengers board the plane one at a time, choosing their assigned seat if possible and choosing a random unoccupied seat otherwise. What is the probability that the last passenger will be able to sit in their assigned seat?
Correct me if this one is wrong, its been a while since ive done these sorts of problems
Simplify the problem to having the first passenger pick their seat randomly, there are 3 outcomes: they pick the last passenger's seat (if the last passenger's seat is filled not by the last passenger ill call it "lose") 1/n of the time, they pick their own seat 1/n of the time ("win", if anyone who is not the last passenger sits here) and they pick neither (n-2)/n of time.
if lose, the last passenger can't fill their seat, if win they will (as every other passenger will get their own seat) so it only matters each time someone is has to choose a random unoccupied seat if they choose the last passengers or the first passenger's seat
so p(win) = sum(i = 1,n) p(neither win or lose up to i)*p(the ith person's seat is occupied)*1/(n-i)
p(lose) should be the same sum, as the probability you have not in a lose or win position or if the seat is occupied is the same for each i.
so 1) p(win)=p(lose) and 2)there are only 2 outcomes lose or win once all passengers board, so 1)+2) => p(win)=p(lose) = 1/2
but for the above scenario, the first passenger is not completely random as they can never sit in their own seat, so there is a (n-2)/(n-1) probability that they do not sit in the last passengers seat, it which case it is just the simplified scenario where the above reasoning shows that p(win)=1/2
so p(the last passenger sits in their own seat) = 1/2*(n-2)/(n-1)
another answer if you want to really think out of the box (hehehe) could be a canary. canaries were used in mines as primitive carbon monoxide detectors and when they died that was the signal the mine was dangerous.
so
1) they're used in mines
2) they're shut in wooden cases
3) and they could be considered to be used by everyone in the form of warrant canaries. some of the most notable websites use (or no longer use!) warrant canaries, such as reddit which you could say is used by "almost everyone"
this one isn't too difficult: you have a standard chessboard with the 2 white corners removed, and 31 dominoes (2 squares x 1 square). place all the dominoes on the chessboard such that none overlap (you can't stand them on their side, or have any hanging off the chessboard).
The chessboard described has two more black squares than white squares, and since every domino can cover exactly one white and one black square, after you cover all of the white squares with the dominoes you'll have two black squares left over which can't be covered by a single domino. (Disclaimer: I've seen this problem before)
Working on a longer answer, I've actually found a cool idea to explain kind of how this trick works, haven't checked if it's new
Here's another riddle:
I'm not a dragon, even though I sound like one. But if you look at my name, you'd know I can't quite breathe fire (although I come close)!
Hint 1: (I'm where you are, not to be creepy!)
Hint 2: (It's a bilingual pun!)
Edit: added disclaimer
Edit 2: added new riddle
Edit3: changed Edit -> Edit 2, made Hint -> Hint 2, added Hint 1
