Reputation
340
Top tag
Next privilege 500 Rep.
Access review queues
Badges
1 11
Newest
 Tumbleweed
Impact
~4k people reached

  • 0 posts edited
  • 0 helpful flags
  • 36 votes cast
Jul
16
comment Brain teaser solution in Graph Theory / Ramsey Theory
Absolutely, I will update my post tonight to link to this answer!
Jul
16
comment Brain teaser solution in Graph Theory / Ramsey Theory
@dtldarek Thanks, that's a great answer! For those interested, I worked through this in a lot more (painstaking!) detail here: boldlyforward.wordpress.com/2015/07/16/…
Jul
16
accepted Brain teaser solution in Graph Theory / Ramsey Theory
Jul
16
comment Brain teaser solution in Graph Theory / Ramsey Theory
@john I'm not sure what you think I'm looking for, but I would actually prefer that you use your brain to answer. I don't care, and didn't specify, what type of proof you use, the point is just that coming up with a way to test the batteries isn't sufficient, you also need to prove that you can't do it in fewer trials. So if you can "easily" do it, I'd love to see it in an answer.
Jul
15
comment Brain teaser solution in Graph Theory / Ramsey Theory
Very helpful answer, but I agree with Greg, I'm not seeing the final conclusive step to the proof, and it doesn't even require a tie. Imagine for instance you have four vertices connected in a ring. They each have degree two, so we color them black. The remaining four are connected as two disjoint pairs, so each has a degree one, and is colored white. But each white connects to another white, so this configuration of six edges works. Of course, that doesn't prove that you can guarantee finding a match with six tries as required by the riddle, but I don't think this answer has proven you can't.
Jul
15
revised Brain teaser solution in Graph Theory / Ramsey Theory
added 115 characters in body
Jul
15
comment Brain teaser solution in Graph Theory / Ramsey Theory
@Sisi Good catch, thanks!
Jul
15
asked Brain teaser solution in Graph Theory / Ramsey Theory
Jun
3
comment Name of the highest power of 2 smaller than or equal to a given number
Order of magnitude is spot on, but you do need to be clear that's is base-two, because almost evey body will interpret it as base 10.
Apr
30
comment Constructor theory distinguishability
Seems like a reasonable idea. I haven't gone back to validate your proof, but it appears sound. Thanks!
Apr
30
accepted Constructor theory distinguishability
Apr
23
revised Constructor theory distinguishability
added 8 characters in body
Feb
24
comment Big-O complexity of iterating over every substring
@Tryss: Thanks, would you be able to explain this a little? In fact, I actually need to add a third nested loop, which iterates j/2 times, so I'm not sure how to extrapolate from your answer to a more general solution.
Feb
24
asked Big-O complexity of iterating over every substring
Feb
20
awarded  Tumbleweed
Feb
13
asked Constructor theory distinguishability
Feb
7
awarded  Popular Question
Sep
24
awarded  Autobiographer
Jul
2
awarded  Curious
Jun
11
accepted How to denote domain and range