Is a world with constant/decreasing entropy theoretically impossible? We can imagine many changes to the laws of physics - you could scrap all of electromagnetism, gravity could be an inverse cubed law, even the first law of thermodynamics could hypothetically be broken - we've all imagined perpetual motion machines at one time or another.
However, the second law of thermodynamics seems somehow more 'emergent'. It just springs out of the nature of our universe - the effectively random movement of physical objects over time. Provided you have a Universe whose state is changing over time according to some set of laws, it seems like the second law must be upheld, things must gradually settle down into the state of greatest disorder.
What I'm particularly wondering is if you can prove in any sense (perhaps using methods from statistical mechanics)? Or is it possible to construct a set of laws (preferably similar to our own) which would give us a universe which could break the second law. 
 A: The microscopic laws are reversible in time (if you also change chirality and the sign of all charges). Thus one cannot prove what you'd like to prove.
Statistical mechanics, which is the discipline in which one derives the second law from microphysics, always makes one or the other assumption that induces the direction of time actually observed in our universe: That entropy increases (unless the whole world is in equilibrium, which it currently isn't).
However, you could run the whole universe backward, and it would satisfy precisely the same microscopic laws (if you also change chirality and the sign of all charges). But entropy would decrease rather than increase.
I don't think your friend would like to live in such a world.
A: Arnold Neumaier's answer is correct but doesn't seem to have included enough detail to convince people, so here is an answer with a more in-depth explanation.
We have two fundamental theories of physics:  general relativity and the standard model of particle physics.  The standard model has CPT symmetry, and general relativity has local time-reversal invariance. Although neither of these is technically the same as global time-reversal invariance, for the purposes of the following discussion it's sufficiently accurate to say that the laws of physics are time-reversal invariant. Sometimes you will hear people state this by saying that the "microscopic laws" are time-reversal invariant, the intention presumably being to exclude the second law of thermodynamics, which explicitly distinguishes a forward direction in time. But this is an anachronism, since the second law is no longer considered fundamental but derived.
The question that then arises is, how in the world can you derive a time-asymmetric theorem from time-symmetric assumptions?
Consider the simulation shown below. On the right we have a box that has three areas marked with three colors, and $N=100$ particles that are free to move around in the whole box. (The vertical lines at the boundaries are just visual -- the particles cross them freely.) The simulation was done using this applet. The particles are released at random positions, with random velocity vectors, and their motion is simulated using Newton's laws, which are time-reversal symmetric. The graph on the left shows the number of particles in each area as a function of time.

Since the particles are initially placed randomly, roughly one third of them are initially in each region. At any randomly chosen time, the number of particles $n$ in, say, the red region has a mean of $\bar{n}=N/3$ and a standard deviation of about $\sqrt{\bar{n}}\approx 6$. Once in a while we get unusually large fluctuations, such as the one marked with a green arrow at $t=19$.
We can now state a derived law L:
(L) If we observe a statistically unlikely value of $n$ at some time $t_0$, there is a high probability that the values of $n$ both before and after $t_0$ (for $t\lesssim t_0-3$ and $t\gtrsim t_0+3$) are closer to the mean.
As $N$ gets larger and larger, L becomes more and more secure; the probability of seeing it violated becomes smaller and smaller. When $N$ gets as big as Avogadro's number, the probability of a violation becomes zero for all practical purposes.
This derived law is still completely time-reversal symmetric, so it doesn't appear to be quite the same as the second law of thermodynamics. But now consider the case where somebody artificially prepares the particles in the box so that they are all initially in the center. (If you run the applet at the link above, this is actually what it does.) The result is shown below.

An observer who doesn't know about the initial preparation of the system, and who only gets to see its behavior during the interval $0\lt t \lesssim 2$, will empirically arrive at a time-asymmetric "law" describing the behavior of the system: the system always evolves from high values of $n_{\text{black}}$ to lower ones. Not knowing the initial preparation of the system, but wishing to believe in a naturalistic theory of the operation of this little "universe," the observer might speculate that the initial, high value of $n$ was an extreme statistical fluctuation. Perhaps at $t\lesssim -2$ the system was in equilibrium. The observer can then explain everything in terms of the time-symmetric law L.
The same analysis applies to the conditions we observe in our universe, with some modifications:


*

*The discussion in terms of $n$ can be replaced with a discussion in terms of the number $\Omega$ of accessible states for a given set of coarse-grained observables -- or we can talk about $\ln\Omega$ or $k\ln\Omega$, i.e., entropy, which is additive.

*In the original statement of L we had a constant time 3, which was an estimate of the equilibration time for the toy model. For the real universe, this has to be replaced by some estimate of the equilibration time of the whole universe, which might be very long.

*And finally, we have the role played by the mischevious person who secretly initialized the system with all the particles in the center. This naughty trickster was effectively setting a boundary condition. In our universe, this boundary condition consists of the fact that, for reasons unknown to us, our Big Bang had a surprisingly low entropy. If there were some naturalistic principle that the Big Bang should be a typical state rather than a very special one, then our universe should have started out already in a state of maximum entropy.
In the world around us, we see various arrows of time. There is a psychological arrow (we can remember the past, but not the future), a thermodynamic one (candles burn but never unburn), a cosmological one (the Big Bang was in our past, not our future), and various others such as a radiative one (we often observe outgoing spherical radiation patterns but never their time-reversed versions). All of these arrows of time reduce to the cosmological one, which arises from a boundary condition.
The OP asked:

Is a world with constant/decreasing entropy theoretically impossible?

No. In fact, the world that is overwhelmingly the most probable and natural is one in which the entropy is, always has been, and always will be the maximum possible -- but in such a universe there would not be hairless primates tapping on computer keyboards. It is also certainly possible to have a universe in which entropy is always higher in the past and lower in the future. In fact, our own universe is an example, if we simply interchange the arbitrary labels "past" and "future."
A longer discussion of these ideas, with lots of historical context, is given in Callender 2011. Historically, there has been a lot of debate and confusion on these issues, and unfortunately you will hear a lot of this confusion echoing down the halls a hundred years later, perhaps due to the tendency of textbooks to hew to tradition. For example, Ritz and Einstein had a debate in 1909 on the radiative arrow (as discussed in Callender and references therein). Ritz's position, that the radiative arrow is fundamental, is no longer viable.
References
Callender, Craig, "Thermodynamic Asymmetry in Time", The Stanford Encyclopedia of Philosophy (Fall 2011 Edition), Edward N. Zalta (ed.), http://plato.stanford.edu/archives/fall2011/entries/time-thermo
A: You may or may not be satisfied with this answer, but I found the question fun, and so I gave it a shot.  
Take the classic bowls and balls multiplicity set-up.  We have four balls, labeled A,B,C,D and two bowls to put them in.  Normally, two balls per bowl is the macrostate with the highest multiplicity, and so for the sake of argument let's say that's where you start the system off at.  
Now, each microstate has a particular probability of occurring, and that probability was the item I decided to pay attention to for this exercise.  The Complex Klein-Gordon lagrangian allows for negative probability densities (from the current 4-vector $j_\alpha =\psi^{*}\overleftrightarrow{\partial_{\alpha}}\psi$), which is one of the reasons it went out of style for electrons.  But it also maintains conservation of probability, $\partial_\alpha j^\alpha =0$.  
So, consider the bowl example, except let three of the microstates corresponding to the "two balls per bowl" macrostate have negative probability of occurring (for whatever reason $j_0$ for these states leads to negative probability).  Then when one sums up the probabilities, the "two balls per bowl" macrostate still has the highest multiplicity, but does not have the greatest probability of occurring, so if the system started out in the "two balls per bowl" state, it is likely that it would evolve into a different state (most likely the "three balls in one bowl" state).  Of course, another microstate would have to gain probability to pick up the slack to conserve it.
I don't know if that tickles your fancy but its the first thing that came to mind when I read the question.  Someone might have a slightly more reasonable answer. 
A: The short answer is that such a universe cannot be envisaged, not with relevance to our known physics.
Entropy as defined in statistical thermodynamics is proportional to the logarithm of the number of microstates of the closed system, the universe in your question.
You would have to devise a universe where the number of microstates diminishes with time. 
The great multiplier of microstates  in our universe is the photon, which is emitted at every chance it gets, and thus increases the number of microstates. Photons are emitted by electromagnetic interactions and by all bodies consisting of atoms and molecules due to the black body radiation effect. Each  emitted (or absorbed, because the state of the atom that absorbed it has changed) photon defines a new microstate to be added to the number of microstates, whose logarithm  defines entropy.  A universe without electromagnetism would not have atoms.
It is worth noting that all biological systems decrease entropy, as  does the crystallization of materials, but this is possible because the systems are open and the energy exchanges create a large number of microstates  thus obeying in the closed system the entropy constraint.
A: It seems to me that the concept of maximum entropy cannot become a reality. As Cambridge experiments have shown 'zero point energy' occurs before energy reaches absolute zero. Of course this relates to open systems. I'm not sure about closed systems. Although I suspect as long as a closed is able to provide energy to other systems it does not reach M E.Also if a system was able to reach ME it would, by definition cancel itself out and could not exist. It's like saying lets get rid of 'left' and only keep 'right' If left no longer existed right could not exist.
