The Art of Problem Solving (original) (raw)

Find total execution time of the program ?? [Jan. 28th, 2015|04:25 pm]The Art of Problem Solving
[**Tags**|algorithms, complexity, digitalcollaboration]A CPU has a five-stage pipeline and runs at 1 GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional branch until the branch outcome is known. A program executes 9 10 instructions out of which 20% are conditional branches. If each instruction takes one cycle to complete on average, the total execution time of the program is: (A) 1.0 second (B) 1.2 seconds (C) 1.4 seconds (D) 1.6 seconds
link 1 comment|post comment
(no subject) [Feb. 25th, 2013|10:03 am]The Art of Problem Solving
Hello mathematics. It's a long shot, but does somebody know how to express generalized hypergeometric functions pFq(ai,bj,z) with p>2 as continued fractions? As far as I understand from the wikipedia articles on gauss' continued fractions and contiguous hypergeometric functions one would probably need to derive continued fractions from recurrence relations involving four functions instead of three...
link post comment
Помогите мне донести информацию об олимпиаде "Третье тысячелетие" туда, где о ней не знают [Feb. 5th, 2013|12:42 am]The Art of Problem Solving
Оригинал взят у matholimp в Помогите мне донести информацию об олимпиаде "Третье тысячелетие" туда, где о ней не знаютПрежде всего, я хочу поблагодарить olenenyok , tiina , al_med , vasily_sergeev , urfin1657 и многих других, давших ссылки на мой пост http://matholimp.livejournal.com/1162423.html , и-или на обзоры, в которых он был упомянут. Но гораздо выше ценится прохождение "последней мили". В данном случае речь идёт о школьных учителях, которые проведут олимпиаду в своих школах.Если, прочитав этот пост, кто-то сообщит об олимпиаде "Третье тысячелетие" в школу, где прежде о ней не знали, напишите об этом в комментарии. Если затем из такой школы поступит работа, претендующая на диплом олимпиады, то автор комментария автоматически станет претендентом на приз в 1000 (тысячу) ЖЖЖ. Их получит тот комментатор, "чей" участник займёт самое высокое место.Другую тысячу (1000) ЖЖЖ я назначаю в качестве приза за помощь в расширении географии олимпиады. Да, уже сейчас она весьма обширна, но "дыр" в ней очень много. Даже в России и Белоруссии, где число участников выражается многими тысячами, есть несколько сильных школ (включая интернаты при университетах), из которых работ почти не поступает. В Грузии, Казахстане, Украине и Эстонии легче перечислить школы, из которых работы приходят почти ежегодно. А в других бывших советских республиках у нас нет даже "базовых" школ. В США и Израиле живёт много русскоязычных математиков, но практически нет школьников, которые могли бы понять и решать задачи без перевода. Ещё острее проблема перевода стоит в Венгрии, Вьетнаме, Германии, Польше, Румынии, Финляндии и других странах.
link 2 comments|post comment
Result related to Brauer-Fowler theorem? [Nov. 11th, 2012|09:44 pm]The Art of Problem Solving
Let G be a finite group with involution x such that the centralizer of x coincides with the subgroup generated by x. Then |G:G' =2.I think this has something to do with Brauer-Fowler, but I don't see how the derived subgroup comes up
link 3 comments|post comment
Journal question [Oct. 25th, 2012|01:33 am]The Art of Problem Solving
Kind of a dumb question perhaps, but how do Proceedings of the AMS and Bulletin of the LMS compare in terms of prestige? They seem to serve the same purposes (national journals for short papers) so I'm finding it hard to see which is 'better'. Are they more or less equal in prestige?
link 4 comments|post comment
Logic/Induction [Sep. 13th, 2012|02:29 am]The Art of Problem Solving
Problem: 1000 perfect logicians are imprisoned. 500 have blue eyes, 499 people have brown eyes, and one has green eyes. They can see each other's eyes but not their own, and cannot communicate eye colors to each other. At the end of every day, those who have deduced their own eye color are freed. The guard states, "At least one of you has blue eyes." Who gets freed and when?Answer: If one guy has blue eyes, he sees no other blues and realizes it's himself on the first day. If there are two blues, the guy who sees only one blue sees that that guy doesn't figure it out on the first day, so he must be blue as well. If there are 3 blues, each blue will see the other two blues not be freed after two days so they must be blue as well. By induction, the 500 blues will be freed on the 500th day.Question: Since there are more than one blue present, each prisoner already knows that at least one prisoner has blue eyes, so seemingly, the guard's statement adds no new information, but seems to be a necessary requirement for induction. Why is that so? If it's not so, then the browns would be freed on the 499th day, right? Since they're perfect logicians and know that everyone can see at least one blue and one brown, can they not simply infer the base case without the guard stating it out loud?
link 18 comments|post comment
Please help me find a simple (geometric?) problem [Sep. 1st, 2012|03:12 pm]The Art of Problem Solving
For an example for some research I'm working on, I need to think of a problem - it can be anything, but a simple (possibly geometric) problem would be ideal - where the problem can be formulated as a number of inputs, say I_1, ..., I_n, and we are interested in several properties of the problem (outputs O_1, ..., O_m) that can be calculated from the inputs in some way.*edit*The important thing is that we need to have at least two outputs, say X1 and X2, and the set of inputs determining X1, say J1, and the set of inputs determining X2, say J2, have the property that J1 != J2, J1 not subset J2, and J2 not subset J1. They can intersect, but I'd like each to contain elements not in the other.I have a few ideas, but none of them are fantastic. If there's an easily understood geometric problem that captures this behaviour nicely, that would be truly awesome :D.Thanks, all!A small example: polynomials over a field F, say f = a_n x^n + a_{n-1}x^{n-1} + ... + a_1 x + a_0Inputs: a_0, ..., a_nOutput 1: derivative of f, depends on a_1, ..., a_nOutput 2: y-intercept of f, depends on a_0(I would ideally like something more interesting than this, where there's at least one more output and some of the input dependency sets intersect.)
link 4 comments|post comment
Conjugate gradient [Jun. 22nd, 2012|04:26 pm]The Art of Problem Solving
I often hear people reference the conjugate gradient algorithm as though it can be used as a general algorithm for minimizing any continuous function, though one may have to assume that it is Lipschitz or convex.When I try to understand conjugate gradient (e.g., the "without agonizing pain" tutorial), it sounds like conjugate gradient is meant for problems only of the formAx=bwhere A is a matrix and x and b are vectors (x unknown, solving for x).How can I use conjugate gradient to solve a problem of the form: find an x that is a local minimum for f(x)? Is there a conversion between these two problem types that I'm missing? Can conjugate gradient be used in this way?
link 2 comments|post comment
The Axiom of Infinity [May. 9th, 2012|09:25 pm]The Art of Problem Solving
What am I missing here? These definitions are taken from Smullyan's Set Theory and the Continuum Hypothesis.A class W is called inductive if(f) ∅ is an element of W and for any set x in W, x ∪ {x} is also an element of W. We call a set n a natural number if(f) it belongs to every inductive set.From this alone, we don't seem to be guaranteed that there are even any natural numbers, for we don't seem to be guaranteed that there exists an inductive set. Clearly the class N = {∅, {∅}, {{∅}}, ...} exists as an inductive class, but we aren't guaranteed it's a set. Indeed, we need the axiom of infinity to deem it a set.So if we define ω to be the class of all natural numbers (i.e. the class of all sets which belong to every inductive set), then I don't see how we've actually defined anything except the empty class, ω = ∅. It seems like we need an axiom asserting that there exists an inductive set, which I've seen some authors do.So is Smullyan's text lacking in some way? Is there a better introduction to set theory? Or is there something I'm just missing about this whole setup?
link 1 comment|post comment
Harmonic functions [May. 6th, 2012|06:04 pm]The Art of Problem Solving
Let G in C be an open set and take a in G. Suppose that u(z) is harmonic in G-{a} such that lim_{z-> a} u(z) exists and equals A. Show that U:G-->R given by U(z)=u(z) for z=/=a and U(a)=A is harmonic in G.Somehow this relates to the Dirichlet problem, but I only know how to solve it for a disk and can't figure out quite how it applies to this problem. Any help is appreciated!
link post comment