Reputation
22,696
Next tag badge:
353/400 score
96/80 answers
Badges
4 18 61
Newest
 Nice Answer
Impact
~402k people reached

2d
revised Geometric proof of $QM \ge AM$
added 629 characters in body
Sep
1
comment Geometric proof of $QM \ge AM$
@QuangHoang Both ellipses have the same focal points, yet the blue one intersects the circle only in two points (its shorter axis is equal to the diameter) while the green in 4 (the tip of the green triangle and its 3 reflections). Actually it is enough to consider the blue ellipse, because it encompasses the circle—tips of triangles with perimeter equal to the blue give the ellipse, but I thought with two ellipses it would be more visual.
Sep
1
revised Geometric proof of $QM \ge AM$
added 182 characters in body
Sep
1
comment Geometric proof of $QM \ge AM$
@QuangHoan Take two ellipses with focal points at endpoint of diameter. It's obvious the blue one is bigger, because it contains the red circle, while the green intersects it in 4 points.
Sep
1
answered Geometric proof of $QM \ge AM$
Aug
29
comment We all use mathematical induction to prove results, but is there a proof of mathematical induction itself?
If you have trouble with induction, you can try an alternative understanding: an inductive proof of $\forall n\in\mathbb{N}.\ P(n)$ is a promise that for all $n$'s there is a method to construct a valid proof of $P(n)$. Observe that there is no actual infinity involved—it is the number $n$ given first, and only after that we need to provide you with a proof of $P(n)$—in other words, it is for arbitrarily high _finite_ numbers. Yet, a realizable promise that you can produce such proofs is just a proof of $P(n)$ for any $n$. This last step can be thought of as an reason why induction works.
Aug
27
revised Can we express a $\forall x\in S \exists y\in T ~P(x,y)$ statement solely through $\land, \lor, \Rightarrow$?
added 293 characters in body
Aug
27
comment Can we express a $\forall x\in S \exists y\in T ~P(x,y)$ statement solely through $\land, \lor, \Rightarrow$?
@NoahSchweber If the universe is finite you can extend the language with a finite set of labels, one for each element and use them to express the conjunction. Sure, the are subtleties, but I doubt the OP had in mind the quantifier-free theories of the pure set or similar things, at least these weren't mentioned. Nevertheless, thank you for your concern, I will add a short note to address this issue.
Aug
27
answered Can we express a $\forall x\in S \exists y\in T ~P(x,y)$ statement solely through $\land, \lor, \Rightarrow$?
Aug
25
revised convert to CNF and can anyone guide me with the steps??
added 110 characters in body
Aug
25
answered convert to CNF and can anyone guide me with the steps??
Aug
25
comment convert to CNF and can anyone guide me with the steps??
@MathBot Rather math.stackexchange.com/help/notation and meta.math.stackexchange.com/questions/5020/…
Aug
20
comment Program languages recommended for complexity theory
I would certainly recommend implementing a few standard algorithms and data structures. On the other hand, with more advanced algorithms it is often quite hard to implement them. Even if doable, it takes a lot of time that could be better spend on other things.
Aug
20
comment The locker puzzle - predetermined strategy
Nice, I didn't suspect it would have such a clean solution $\ddot\smile$
Aug
18
comment The locker puzzle - predetermined strategy
@ManuelLafond Your condition is not sufficient. Take 4 prisoners 2 tries each, then there are two non-isomorphic "regular" strategies: one gives 8-cycle and the other gives two 4-cycles. The latter is the strategy described by the OP and it is better: it contains 4 different perfect matchings (permutations), while the former can contain at most two.
Aug
18
comment The locker puzzle - predetermined strategy
@ManuelLafond If you mean that the underlying bipartite graph is regular, then no, I've checked with bruteforce for some small numbers of prisoners.
Aug
16
comment The locker puzzle - predetermined strategy
My intuition is that if prisoner $A$ fails, then prisoner $B$ should want to fail too (or at least have his probability of failing decreased instead of increased), so that the bad outcomes coincide as much as possible. That means the more dependent the probabilities are, the better for the prisoners—dividing them into two groups like you said seems to do exactly that. I wonder if it is possible to formalize the idea, e.g., as some kind of potential function, then a prisoner would change strategy to match a strategy of some other prisoner, perhaps displacing choices of others in the process.
Aug
11
answered Matching and greedy matching.
Aug
11
comment Proof that there isn't a graph search algorithm that is complete with finite memory
You have to at least store where you currently are, which takes $\log_2 |V|$ memory.
Aug
10
comment Standard notation for the transform that turns a function $A \rightarrow (B \rightarrow C)$ into a function $B \rightarrow (A \rightarrow C).$
In Computer Science this function is usually called flip, e.g. see here, but I doubt you can use it without definition.