text:
# Master’s Research

I worked under the supervision of Dr. Stephen Wright to complete a research project for my Master of Science at Miami University.

Our goal was to find efficient ways to solve the nonlinear resource allocation problem (P):

$\begin{array}{cll} \min &{\displaystyle \sum_{i=1}^n f_i(x_{i})} &\\[0.5em] {\rm s.t.} &{\displaystyle \sum_{i=1}^n g_i(x_i) \leq c}, & c \in \mathbb{R} \\[0.5em] & \ell_{i} \leq x_{i} \leq u_{i}, & i = 1,2 ,\ldots, n \end{array}$
where $$f \colon \mathbb{R}^n \to \mathbb{R}^n$$, $$g \colon \mathbb{R}^n \to \mathbb{R}^n$$ are separable, convex, and differentiable functions. We assume without loss of generality that $$f_i$$ and $$g_i$$ are monotone. In particular, we studied three speci fic real-world applications including strati ed sampling, quadratic knapsack, and manufacturing capacity planning. This work was motivated by Dr. Stephen Wright and his previous experience with stratified sampling.

The nonlinear resource allocation problem has been studied extensively and can be approached using several di erent methods. Lagrange multiplier methods rely heavily on the Karush-Kuhn-Tucker (KKT) conditions and require maximizing a concave piecewise linear function q of one variable. A simple approach to find the maximum is to use an iterative method like a bisection search. Due to relatively nice structure of (P) we may utilize more specialized algorithms. For example, using the optimality conditions and the tangent criterion allows us to identify breakpoints (locations where $$q’ = 0$$ or $$q’$$ is undefined). By searching these breakpoints we can find approximately where $$q’ = 0$$ and then interpolate to find the location of the maximum.

An alternative approach to solving (P) is using a variable fixing (or pegging) method. A pegging algorithm fixes an active variable to its upper (or lower) bound at each iteration and then solves the smaller subproblem. Since each iteration fixes at least one variable, the complexity of this class of algorithms is at most $$O(n^2)$$. We successfully implemented an algorithm (PEG) from Bretthauer & Shetty (2002) in Matlab and improved it using work from Kiwiel (2008).

The new work we accomplished in this project relied on interior point methods (IPMs). An IPM travels through the interior of the feasible region to find a solution. A barrier or penalty function prevents the algorithm from approaching the boundary. The methods we used were primal-dual path following algorithms, where the iterates follow an arc of strictly feasible points. By perturbing the complementary slackness property of the KKT conditions, we can identify the central path (an arc of strictly feasible points where the complementary slackness conditions have the same value for all indices). The general framework of solving interior point problems involves solving a Newton system (which can be solved extremely efficiently by exploiting the structure of problem (P)). We implemented two interior point algorithms. The first was a linearly convergent predictor-corrector method and the second was a quadratically convergent method
(IPMQ) based on work by Sun & Zhao (2000).

Since pegging methods worked so well on solving problem (P), a natural extension of this project was to study the area of variable indicators. An indicator is a function that identifies whether a variable is active or inactive. By identifying which variables are active early on in an iterative procedure like pegging methods or IPMs, we may reduce the computational complexity. Among the many indicator functions to choose from, we used the Tapia indicators (1994) which use a quotient of successive Lagrange multipliers and the quotient of successive slack variables. To be able to use the indicators, we require that the iterates of our iterative algorithm converge superlinearly to a solution. To accomplish this, we combined the Tapia indicators with (IPMQ) and then used (PEG) as a subroutine which we called (IPMQ-PEG).

Our numerical tests showed that (IPMQ-PEG) was competitive at solving problem (P) for the three applications we considered but was dominated by (PEG). Since a closed form solution could be found for the subproblems solved in (PEG), we believe that our algorithm would work as well or better than (PEG) on classes of problems where a numerical routine would be needed to solve the subproblem.


text:
• Create Account

# Creating Constructive/Social Behaviour in Online Worlds !

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

95 replies to this topic

### #81Kylotan  Moderators   -  Reputation: 3107

Like
Likes
Like

Posted 08 June 2002 - 11:11 AM

quote:
Original post by Marc De Mesel
By ridiculing an analyzes of the word 'recreate' as an 'etymological fallacy' is a poor argument to the point that Jay tried to make. We use all kinds of things to try to get a point through. Etymological analyzes of words can learn you a lot and if appropriate can serve you in expressing your vision on a subject. And that was exactly what Jay tried to do, give his vision on game design. That was the message, you should criticize that message!

I already did, in a previous post. The 'ridiculing' of which you speak was because he was appearing to use the etymological fallacy to back up his claim that the point of recreation is to recreate, which it isn't. It can be one perfectly valid type of recreation, but it is not the only way or the 'correct' way.

quote:
Losing stuff in a game feels the same as losing stuff in real life, it indeed can never be that intense as in RL but you can make efforts to approach it.

All the problems revolve around the intensity of the feeling. You can't just ignore that.

quote:
But if you link some things to that character his life that are important to him (the real player) for being successfull in that world, like social connections, status in the world, a body that he has grown, some property maybe, than the loss of that character means something to him. He won't like it to die and will watch out for it, more than he would if he could not loose those things that he had to build up.

This is all true, but these things already exist on games and have proven insufficient for controlling grief players. Additionally, you have suggested implementing measures that reduce the effects of such losses or punishments, such as allowing multiple characters.

I've lost track of what it is that you want to achieve. You started off saying you wanted constructive and/or social behaviour, and to cut out anti-social behaviour, but since then you've gone on to say that you embrace player-killers. It doesn't make much sense. And I don't see what you're offering that's any different from existing MMORPGs.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ]

[edited by - Kylotan on June 10, 2002 7:48:46 PM]

### #82coderx75  Members   -  Reputation: 401

Like
Likes
Like

Posted 08 June 2002 - 12:46 PM

quote:
Original post by Kylotan
I don''t have a problem with you trying to go for more simulation in a game in the belief that it makes a game more fun, but you were suggesting that "recreation" should be about the act of "recreating" something, which you justified through linguistic wordplay to suggest that you were somehow ''right''. The words did had a common origin but that is irrelevant - the meanings are now different.

Yes, it is irrelevant. The point I was trying to make, however, had to do with "Creating Constructive/Social Behaviour in Online Worlds". My point was made in my example of people being entertained by "The Sims". The "linguistic wordplay" in no way is used to say I am right. It is only to say that people enjoy recreating real life things (not all things, of course). Perhaps, you don''t but you are not the entire gaming population.

We could go back and forth on this but it''s pointless really. I''m interested in how society and economy can emerge from a PC and/or NPC population while you seem only interested in the aspects of dealing with griefers. As I''ve said, and emergent society might be fun and it even might reduce griefing. As I''ve also said, anything is possible, but it''s really not my point. I''m only interested in _how_ society emerges. Everything else is just cake.

- Jay

"Strictly speaking, there is no need to teach the student, because the student himself is Buddha, even though he may not be aware of it." - Shunryu Suzuki

Get Tranced!

### #83deClavier  Members   -  Reputation: 122

Like
Likes
Like

Posted 08 June 2002 - 07:03 PM

The key to designing communities is designing by emotion, not action. Games these days all say "you can do x, you can do y" but neglect to mention that all the things you can do are all combat related.

When designing a game about community you need to ask, "how else can I express myself?"

There are four basic emotions - aggression :<, depression , love and fear :0 (which babies demonstrate versions thereof) - most games deal with two! (yet another reason to push for the design of games from the language perspective). There have been some experiments with game design along these lines; I don''t remember the title but someone designed an online game about the schoolyard - players could include/exclude players from groups, play nice or bitch - it highlighted how involved people became when social status was what was being manipulated (as opposed to other people''s health levels). It also highlighted the limits of the potential for "emergence" where survival/score principles are predominant - it wasn''t designed to be a very stable social environment.

Maybe what you need is to define the game in terms of group powers only, then individual dissent becomes a social issue, not a gameplay feature.

Marc de Mesel! Forcing permanently stable status quos? You''re dealing with a self-defeating scenario - that''s what I''m saying.

"We lived peaceful lives for a long time, for years we ignored a heap of metal that lay in the corner of our field. We were happy, we talked amongst one another and passed the time idly. Then one day, Hamish, who often complained at his father''s orders, went to the corner of the field and picked up the BFG9000. That was a sad day for all of us; things have changed now, as you can see."

You may not put a BFG in your game but its the principle I''m trying to highlight. You won''t see the problem until you step out of the designer shoes (sic!) and ask yourself what players will want to do to get the power you had in designing the game. Are you going to prevent players from exercising the "will to power" (and not the "will to observe")? Apparently, from your comments about Kant, you don''t like the idea. Jay''s "emergence" design philosophy is much more self-consistent.

[Mental note: MM voyeur game based on the "will to observe"... players are compelled (survival) to visit NPCs in the game at which point various social taboos have a probability of being broken. The rest of the game is spent running around with a camera trying to get other player''s misdeeds on film.]

### #84coderx75  Members   -  Reputation: 401

Like
Likes
Like

Posted 08 June 2002 - 07:45 PM

quote:
Original post by deClavier
When designing a game about community you need to ask, "how else can I express myself?"

There are four basic emotions - aggression :<, depression , love and fear :0 (which babies demonstrate versions thereof) - most games deal with two!

Computers are rather cold little devices. Although, Micro$oft is pretty good at causing "fear" with their software by adding that "Blue Screen of Death" feature in everything they produce =) My agents have to be spawned... I''ve been interested in how players would feel about eachother if they spawned other players. This could make for some interesting emotional ties. Not as strong as real life but cool nonetheless. quote: [Mental note: MM voyeur game based on the "will to observe"... players are compelled (survival) to visit NPCs in the game at which point various social taboos have a probability of being broken. The rest of the game is spent running around with a camera trying to get other player''s misdeeds on film.] MUAHAHAHAHA!!! That''s the about the whackiest idea I''ve heard yet. I dig it! =) - Jay "Strictly speaking, there is no need to teach the student, because the student himself is Buddha, even though he may not be aware of it." - Shunryu Suzuki Get Tranced! ### #85MarcDM Members - Reputation: 122 Like Likes Like Posted 10 June 2002 - 01:36 AM Hi Jay, Thanks for your email. Now back to business. When you talk about a 'social system' what is it exactly that you mean? And correlated to your project what is it that you expect from your 'social system'. If you mean with this social system the interdepended relations between the animals, plants and npc's than it's more an ecological system that you are trying to get balanced. I wouldn't talk of a social system here. A description of a social system would be something like this: quote: "Tribal society is the stable social system with a division of labour organised around extended family relations. This division social division of labour is almost exclusively based on kinship relations, within a relatively closed circle, wherein the character of an individual’s labour is determined by their age, sex and position within the family. A tribe consists of more than one formallly recognized kinship group, termed clans, which exchange marriage partners. Land belongs to a particular clan, not to the whole tribe. However, the number of people in a tribe is still low enough that everyone knows everyone else by name and relationships. A few hunderd seems to be the upper limit for group size compatible with everyone's knowing everybody. Because almost everyone is related to everyone else, by blood or marriage or both there is no need for police, laws and other conflict-resolving institutions of larger societies. When 2 villagers get into an argument they will share many kin who will apply pressure on them to keep it from becoming violent. This would be part of a description of the social system of a game about being part of a tribal community. I know that you are not working at such a kind of social system but I would love to know if you are planning for some kind of simple social system, some kind of cooperation between the npc's or maybe some kind of cooperation between your animals. ( In sugerscape there emerged cooperation from the simple rules the agents followed. quote: To be more clear, there are personal needs, not social needs. Social needs are emergent. The only personal needs I've implemented is food and protection. Of course, protection is an emergent need and requires other game elements to acquire. The Sims had a social need to that was simply displayed by one stat, other stats were hunger, comfort, hygiene, bladder(?), energy, fun and room (and social). You can see it on this screenshot (http://www.gamegenie.com/cgi-pub/pic-gg.pl?&url=/reviews/pc/images/thesims-2.jpg). I don't understand that social needs are emergent. I don't think that is the case. We as humans are geneticaly engeneered as such that we will look for contact with other living beings and will want to live with it. I do understand that your desire for protection will be furfilled through other actions yo have to undertake like making good friends, a strong house or whatever. [edited by - Marc De Mesel on June 10, 2002 8:41:53 AM] ### #86MarcDM Members - Reputation: 122 Like Likes Like Posted 10 June 2002 - 04:43 AM quote: All the problems revolve around the intensity of the feeling. You can''t just ignore that. Damnit Kylothan I did not ignore that in my previous post. I clearly stated that the intensity of virtual life for a human being can never be as intensive as in real life. I did not ignore this, not even in that same post!! (since by now it''s clear that you seem not be interested in looking for the other arguments mentioned in the other posts by that person). quote: This is all true, but these things already exist on games and have proven insufficient for controlling grief players. Indeed, this is true, the measures I would take, that are not yet done in todays MMOW would be: - The Physical Weakness of every character even if they have lots of political or financial power. (like RL) - The Birthing System that makes shure that newbies are protected by the parents and surrounding community and at the same time those newbies, since they are little and weak do not have the power to harm a lot, kill adults. (They wouldn''t mind griefing those children since they did not invest a lot of time in their character yet but if they want to become physical as powerfull as the adults and have access to other power structures and attractive things like a girlfriend, a house they will have to work for it, eat, invest time, fight, use your people skills. By the time they are big they are a very part of the commmunity and have a lot to lose if they start to grief. - The ''Trust'' System, making trust of other players possible and necessary by having Repeated Interaction (the people live in a tribal community, together and can''t easily go to other tribal communities, they will live together and see eachother a lot), Interaction History (I will make shure that people have planty of downtime(time that you are waiting for something and do not have to do anything) to chit chat and will that way talk a lot about eachother.) and Persistent Distinct Identities (It will be very difficult to have exactly the same character as somebody else.) I might have forgotten other things that are important to implement if you want to grow organized societies with a lot of constructive social behaviour in it (next to a lot of destructive social behaviour, which is a very part of it). Or I might not yet even have discovered, found other necessarily features you have to implement to realize such a dynamic living society. quote: Additionally, you have suggested implementing measures that reduce the effects of such losses or punishments, such as allowing multiple characters. Allowing multiple characters was a solution to the prison sentence talked about in the other post. It was a solution to having nothing to do. I now realize that it was not a good solution as the effect of punishment would be lost if the player could just play another character (while this one is in prison). That way the player wouldn''t mind much doing the same crime again because he would not feel prison as a punishment. I came upon that feature, being able to grow several characters at the same time (not moment) in the same world because this allows for real roleplaying. Since the other people don''t know that ''Gina'' and ''Jack'' are the same real person you can experiment a lot thanks to this mask being offered. If there are some strategies in it like tribal communities fighting eachother you could grow a personage in multiple communities and have valuable information thanks to this. This way somebody who knows how to play different roles would maximize his possibilities for success in that world. quote: I''ve lost track of what it is that you want to achieve. You started off saying you wanted constructive and/or social behaviour, and to cut out anti-social behaviour, but since then you''ve gone on to say that you embrace player-killers. It doesn''t make much sense. And I don''t see what you''re offering that''s any different from existing MMORPGs. What I mean with ''embrace Player Killers'' is that the possibility to kill players, the power of attacking other players ingame, the power to have impact on other players is a must you need for a self policing system. You need the option of killing other people or hurting them in order to create constructive social behaviour among the players. I embrace it because there lays the solution to the griefer problem. Of course this alone does not solves the griefer problem. Why the griefer problem is there is simple. If you are invulnarable and there is no other people or godlike system of preventing you to kill that newbie than it is possible and as such will happen. (If you even gain something by doing this than it will happen a lot, is that the case in current MMORPG''s? I don''t know that.) Before explaining what it is exactly that I offer that is different from current MMORPG''s I want to say something about the personality that you are playing in this thread. You are not looking for solutions (or that is the impression you give) for today''s problems that arise from the systems we play/live in. Sometimes it seems like you feel treatend by the ideas being proposed certainly if they are about MMORPG''s, stats, griefers and such. I bet you are quite happy with today''s MMORPG''s and do not desire any other things, true? A constructive discussion with people who are quite happy with current systems is difficult. You have to convince them that they can gain something too with this new system. If it is absolutely clear that they can only loose (or so they think) when implementing such a new system it is impossible to discuss with them. This sort of people is not inspiring in the search for solutions. However the stupid things they constantly and repeatedly say train you very well in building up arguments and expressing your ideas as you constantly have to repeat them. The nerving thing when discussing with such people however is that they constently seem to forget other things that have been said about the subject before, even when those are easily accesable, and often jump on just a part of the argument or simply rip things out of context. If you stick to this role you play Kylotan you will be reduced to the observer role as you do not understand how these new systems work or are created. I would want to ask you to put some energy in the understanding of. Still here Kylotan? If so then now clear your mind and forget all the insults that I have trown upon you. This is difficult but it is necessary in order to understand some new things I''m going to try to explain you here. So here we go, especially for you Kylotan repeat and reformulate the ideas that I, Jay and some others have tried to explain until now. The difference between today''s MMORPG''s and the game we propose is that we simply want a deeper simulation incorporated in our world. We want the simulation as deep as possible with lots of interdependent relationships between all the things you find in that world and the systems that guide them. If you offer such a simulation than the need for missions given by the gamedesigner is not necessary anymore because the world already allows for massive experimentation and possibilities. (Simcity) So if we would make a gta serie (Grand Theft Auto, a popular game) we would try to go as deep as poossible in the simulation of a today''s city while keeping the focus on the sorts of activities that players from the series like (such as being a criminal, gang leader, cop, taxidriver, hooker, ...). Although you can do all this with ai, creating a dynamic living society) and do not need other players in the game world I personaly am very much attracted by using only real players as citizens because it allows for again a more real like experience (ai npc''s can''t simulate real living beings yet and for a long time probably). (I could also give an example of how the game would be different from Everquest for instance while keeping the same setting, environment, themes and roles but I''m just not familiar with that world and therefore have not fantasized yet about such a world in that setting and how it would feel, play.) So as a player you would experience the difference in that you have no defined objectives from the gamedesigner and you would also notice that you can do a lot in that world. The difficulty is, How do we create such a deep simulation of a city, certainly when a lot of real players are active in that world? I''m going to stop here. Somehow I do like your presence as it is way better than no responce at all. At least you live. -Marc (This is my name if you speak to me, mentioning the back name feels ''teachy'', if you know what I mean) ### #87coderx75 Members - Reputation: 401 Like Likes Like Posted 10 June 2002 - 05:35 AM quote: Original post by Marc De Mesel When you talk about a ''social system'' what is it exactly that you mean? And correlated to your project what is it that you expect from your ''social system''. If you mean with this social system the interdepended relations between the animals, plants and npc''s than it''s more an ecological system that you are trying to get balanced. I wouldn''t talk of a social system here. I don''t feel a social system alone is really a social system. A social system effects the world and vice versa. Ecology, economy, society, trade, etc. all go hand in hand. Sure, I could just have food spring out of the ground like magic, but the ecological system is a very trimmed down version of the social system. Some animals pack together and follow a leader. This is just practice before the big game, so to speak. It also makes the world a little more interesting. quote: ...I would love to know if you are planning for some kind of simple social system, some kind of cooperation between the npc''s or maybe some kind of cooperation between your animals. No cooperation between animals and npc''s is planned (such as dog and man). Animals are there for food... and fight. The carnivores need to eat too. This puts the initial fight into the world and gives primitive "human" agents a purpose. quote: I don''t understand that social needs are emergent. I don''t think that is the case. We as humans are geneticaly engeneered as such that we will look for contact with other living beings and will want to live with it. I do understand that your desire for protection will be furfilled through other actions yo have to undertake like making good friends, a strong house or whatever. You''ve actually made my point. Social needs are emergent. But, I see your point as well. Society IS programmed to some extent. The need for agents to be together is to fulfill protection and to get more done. To an agent, another agent is just a resource. How much that resource is used depends on the value of their relationship. This is where society emerges. ----------- BTW, don''t worry so much about Kylotan''s posts. I don''t think he''s really on the same page as us. As I said a couple posts ago, he''s more interested in taking care of the grief problem. Although that was originally part of the topic, we''ve moved away from the issue. You''ll notice his criticisms are aimed at that issue. Whether my system or yours will "banish" griefers, I doubt HIGHLY but I hope they will make them a little more interesting as everything you do in a social system requires some bit of strategy and always involves cause/effect. Either way, it''s not something I''m taking into account, just seeing it as possibility. At first, I thought Kylotan was just talkin'' outta his a$$... spouting criticism without doing his homework. But on closer inspection, he''s got his target on a different problem... and his arguments are good. I told him in an earlier thread to ut some more thinking behind his replies. Sorry, Kylotan, if you took offense to this. We just weren''t at all on the same page. =) Perhaps, you [Kylotan] should start another thread on the topic of griefers so we can battle it out there =) Hehehe - Jay "Strictly speaking, there is no need to teach the student, because the student himself is Buddha, even though he may not be aware of it." - Shunryu Suzuki Get Tranced! ### #88Kylotan Moderators - Reputation: 3107 Like Likes Like Posted 10 June 2002 - 01:06 PM quote: Original post by MarcDM Damnit Kylothan I did not ignore that in my previous post. I clearly stated that the intensity of virtual life for a human being can never be as intensive as in real life. I did not ignore this, not even in that same post!! Then let me rephrase - you have failed to address it. In my opinion. quote: You need the option of killing other people or hurting them in order to create constructive social behaviour among the players. I embrace it because there lays the solution to the griefer problem. Death is only one method. Is death permanent? (I may have missed you clarifying this.) If so, then you will still probably lose more good players than bad this way, unless you have something very interesting set up to prevent this. After all, the ability of the average grief player is usually higher than the average player overall. (Excluding verbal grief players, who usually just indulge in harassment that tends to be easy to shut out or prevent using in-game methods, if you allow them.) If death is not permanent, then it is not necessarily a better deterrent than other methods. quote: Before explaining what it is exactly that I offer that is different from current MMORPG''s I want to say something about the personality that you are playing in this thread. You are not looking for solutions (or that is the impression you give) for today''s problems that arise from the systems we play/live in. Sometimes it seems like you feel treatend by the ideas being proposed certainly if they are about MMORPG''s, stats, griefers and such. I bet you are quite happy with today''s MMORPG''s and do not desire any other things, true? Not true. I am not impressed by the current crop of MMORPGs at all. I am looking for solutions just as the rest of you are, except I have spent a long time listening to the likes of Raph Koster and Damion Schubert who have learned from their mistakes in the design of such games. Which is why I''m very sceptical when people come in and say "more ecological systems and player policing is the answer" when in fact both of those systems were among the first to be tried, and discarded due to their inadequacy. This doesn''t mean they can''t work - it just means they need a new approach in order to work, and I don''t see that here. For example, making players more vulnerable by reducing the difference in power between newbies and experienced players is largely already in Ultima Online. The skill cap means that most people are approximately the same. But this isn''t enough to solve the problem. quote: A constructive discussion with people who are quite happy with current systems is difficult. Lucky I''m not one, then. I just see as many problems in your systems as I do in existing ones, largely because your ideas have already been tried in some form or other, as far as I can see. quote: The nerving thing when discussing with such people however is that they constently seem to forget other things that have been said about the subject before, even when those are easily accesable, and often jump on just a part of the argument or simply rip things out of context. The whole of the context is available above in this thread for anyone who wants to see it. quote: If you stick to this role you play Kylotan you will be reduced to the observer role as you do not understand how these new systems work or are created. I would want to ask you to put some energy in the understanding of. On the contrary... I actually run an online world right now, albeit a small one. I have been dealing with grief players and fostering societies before anybody here even heard of Ultima Online. I don''t say that to imply that I know more than the rest of you - just to let you know that I do have some experience of the process. quote: The difference between today''s MMORPG''s and the game we propose is that we simply want a deeper simulation incorporated in our world. We want the simulation as deep as possible with lots of interdependent relationships between all the things you find in that world and the systems that guide them. If you offer such a simulation than the need for missions given by the gamedesigner is not necessary anymore because the world already allows for massive experimentation and possibilities. (Simcity) This is all well and good. I don''t have a problem with the simulationist approach. I partly subscribe to it myself. However I feel this aspect is orthogonal to the whole society/grief-player aspect, and doesn''t really help it. In fact, it possibly hinders it in that simulation has less directed goals, which in turn could mean less in the way of a ''shared vision'' and consequently less cooperation. [ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ] ### #89MarcDM Members - Reputation: 122 Like Likes Like Posted 10 June 2002 - 01:40 PM I don''t understand what you are saying to me Declavier. It''s not that I don''t want to it''s just to difficult. Just think of me as a litle boy and explain it. sorry, Marc ### #90coderx75 Members - Reputation: 401 Like Likes Like Posted 10 June 2002 - 03:24 PM quote: Original post by Kylotan Not true. I am not impressed by the current crop of MMORPGs at all. I am looking for solutions just as the rest of you are, except I have spent a long time listening to the likes of Raph Koster and Damion Schubert who have learned from their mistakes in the design of such games. Which is why I'm very sceptical when people come in and say "more ecological systems and player policing is the answer" when in fact both of those systems were among the first to be tried, and discarded due to their inadequacy. This doesn't mean they can't work - it just means they need a new approach in order to work, and I don't see that here. Games may have attempted to create economic or social systems, but they've never created an emergent system that the players don't have total control over. No game has ever attempted anything this ambitious. The game AI would create the world and the player would have to try to influence this world. Players would have to gain funding and popularity before they could do anything. I'm creating such a system now as we speak but I'm not creating a game. This is just an experiment. I hope to one day grow the idea into a game system. I would appreciate your opinion on such a system in a single- and multiplayer environment as you seem to have some background. Where do you see these failing? What have you seen happen in the past? There is a somewhat similar system that is being implemented now in a game called "Republic". Check this out if you are interested: Republic - GameSpy ...and some more. "Strictly speaking, there is no need to teach the student, because the student himself is Buddha, even though he may not be aware of it." - Shunryu Suzuki Get Tranced! [edited by - coderx75 on June 10, 2002 10:26:01 PM] [Edit - The quote was attributed to Marc when actually it should have been me, so I changed it to avoid confusion -- Kylotan] [edited by - Kylotan on June 11, 2002 8:32:37 PM] ### #91MarcDM Members - Reputation: 122 Like Likes Like Posted 11 June 2002 - 12:37 AM quote: Original post by coderx75 I don''t feel a social system alone is really a social system. A social system effects the world and vice versa. Ecology, economy, society, trade, etc. all go hand in hand. Sure, I could just have food spring out of the ground like magic, but the ecological system is a very trimmed down version of the social system. Some animals pack together and follow a leader. This is just practice before the big game, so to speak. It also makes the world a little more interesting. So a social system refers to the system of cooperation that emrges between animals or between human being or between human beings and animals. Cooperation between the fauna and flora is an ecological system. (Just to get it straight that we mean the same thing if we talk about a social system.) quote: You''ve actually made my point. Social needs are emergent. But, I see your point as well. Society IS programmed to some extent. The need for agents to be together is to fulfill protection and to get more done. To an agent, another agent is just a resource. How much that resource is used depends on the value of their relationship. This is where society emerges. Indeed so society is an emergent phenomena that is created because of the (programmed) desire of human beings to have protection, and maybe some other programmed needs. But the social ''needs'' themselves are not emergent phenomena, maybe if you look from it from an atomair approach, yes than maybe as intelligence itself is an emergent phenomena but they do not emerge from the need of protection. The social needs are the cause of emergence. The cause that there emerges a society from it. The social needs are simply there just as the need for sex is simply there. Making friends are consequences from the social needs. Making a house is a consequence of the need for protection. But it are not emergent phenomena in that due to the programmed need for social contact there ''emerges'' the quest for friends. It''s simply a consequence. I looked for some definitions of emergence. This one might serve us : Emergence is the phenomenon wherein complex, interesting high-level function is produced as a result of combining simple low-level mechanisms in simple ways. Marc ### #92coderx75 Members - Reputation: 401 Like Likes Like Posted 11 June 2002 - 05:56 AM quote: Original post by MarcDM Emergence is the phenomenon wherein complex, interesting high-level function is produced as a result of combining simple low-level mechanisms in simple ways. This proves my point. No social need is programmed. If you are aiming at programming a social need, then it is not emergent and you are making more work for yourself. If you feel that controlling these things is beneficial to your game, then more power to you. But, it's still not truly emergent. The needs of the singular agent are all programmed. Other agents are also a need as I've stated before, but this is only to fill its own needs, not the needs of a society. Example: sex is a need of the RLIfe individual, however, you can probably trace an entire war back too it. If an ALife individual has the need for food, it has the option to find it, grow it or trade for it with another agent. If he grows it, he may sell it to others. A system of basic economy and trade have just emerged because of the singular agent's need for food. The need for food is a simple low-level mechanism where the economy is a complex, interesting high-level function. What I said earlier was incorrect. In order to have an emergent system you can not have ANY society-related programming. To do so is to remove emergence within the system. Programming emergence is very simple and any high-level, complex programming is just excessive and probably requires some redesign, especially if its human players and not AI. When you go my route of AI socializing, you can't help but get into some tricky techniques but they're still applied to the individual only. - Jay "Strictly speaking, there is no need to teach the student, because the student himself is Buddha, even though he may not be aware of it." - Shunryu Suzuki Get Tranced! [edited by - coderx75 on June 11, 2002 12:58:21 PM] ### #93 Anonymous Poster_Anonymous Poster_* Guests - Reputation: Likes Posted 11 June 2002 - 06:20 AM There is a game where social and political structures have been formed as you describe. Its called Asheron''s Call. If you are not familiar with it I will briefly describe the allegiance system that the programmers implemented to promote social interaction. There are no set realms in AC. Players can choose to be a monarch or to follow another person by swearing allegiance to him. The patron recieves a fraction of the experience points his vassal produces thereby giving the patron incentive to help the newer player. In non-pk servers on AC thats all there really is to it but on Darktide the pk-only server allegiances come into play as much more important. The allegiance you are in defines what you are like to other people. If you are in the monarchy of "Blood" people autamatically know that you are hostile to everyone and will attack them, however if your monarch is "xanthro" people recognize you to be a protector of good and justice and will only attack known pk''s such as "blood"s In the pk-server(darktide) it is essential to join a monarchy for protection. Each monarchy attempts to control certain areas of the world and many of the guilds allow only their members to use dungeons or towns that they control. In Asheron''s Call, darktide there is a great political and social structure with NO influence from the programmers aside from the allegiance system. ### #94coderx75 Members - Reputation: 401 Like Likes Like Posted 11 June 2002 - 07:54 AM quote: Original post by Anonymous Poster There is a game where social and political structures have been formed as you describe. Its called Asheron''s Call. Oh God help us... it''s a Micro$oft game! Wow, this is actually cool as hell. Hey Marc, this is exactly what you were looking to do... and didn''t Kylotan say that it would fail? Guess not, eh?

Well, no ones done the AI society thing yet (except republic, but that''s somewhat structured). You guys should check out this link... I''ve read it and I''m trying to get the hard-on to go down =b

Asheron''s Call

- Jay

"Strictly speaking, there is no need to teach the student, because the student himself is Buddha, even though he may not be aware of it." - Shunryu Suzuki

Get Tranced!

### #95Kylotan  Moderators   -  Reputation: 3107

Like
Likes
Like

Posted 11 June 2002 - 01:35 PM

quote:
Original post by coderx75
Oh God help us... it''s a Micro\$oft game! Wow, this is actually cool as hell. Hey Marc, this is exactly what you were looking to do... and didn''t Kylotan say that it would fail? Guess not, eh?

I am not sure if you are being sarcastic or not. In this whole thread, I have had AC''s hierarchical system in mind, and now you''re acting as if you''d never heard of it. Odd. And no, I don''t believe I ever said such a thing wouldn''t work. Please find the relevant quote. However, Asheron''s Call doesn''t do half of the things that have been asked for in this thread, which is a large part of why I''ve said that making clans and guilds is insufficient to create cooperative behaviour.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ]

### #96coderx75  Members   -  Reputation: 401

Like
Likes
Like

Posted 11 June 2002 - 02:59 PM

quote:
Original post by Kylotan
I am not sure if you are being sarcastic or not. In this whole thread, I have had AC''s hierarchical system in mind, and now you''re acting as if you''d never heard of it. Odd. And no, I don''t believe I ever said such a thing wouldn''t work. Please find the relevant quote. However, Asheron''s Call doesn''t do half of the things that have been asked for in this thread, which is a large part of why I''ve said that making clans and guilds is insufficient to create cooperative behaviour.

- Jay

"Strictly speaking, there is no need to teach the student, because the student himself is Buddha, even though he may not be aware of it." - Shunryu Suzuki

Get Tranced!

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS

format: plain


text:
Question

# If ${{\text{S}}_1}$ and ${{\text{S}}_2}$ are respectively the sets of local minimum and local maximum points of the functions $f\left( x \right) = 9{x^4} + 12{x^3} - 36{x^2} + 25,x \in R$, then write the elements contained by the two sets ${{\text{S}}_1}$ and ${{\text{S}}_2}$.${\text{A}}{\text{. }}{{\text{S}}_1} = \left\{ { - 2,1} \right\};{{\text{S}}_2} = \left\{ 0 \right\} \\ {\text{B}}{\text{. }}{{\text{S}}_1} = \left\{ { - 2,0} \right\};{{\text{S}}_2} = \left\{ 1 \right\} \\ {\text{C}}{\text{. }}{{\text{S}}_1} = \left\{ { - 2} \right\};{{\text{S}}_2} = \left\{ {0,1} \right\} \\ {\text{D}}{\text{. }}{{\text{S}}_1} = \left\{ { - 1} \right\};{{\text{S}}_2} = \left\{ {0,2} \right\} \\$

Hint- Here, we will proceed by differentiating the given function once and then putting $f'\left( x \right) = 0$ in order to obtain the values of x where local maxima and local minima can occur according to the sign of $f''\left( x \right)$.

The given function in x is $f\left( x \right) = 9{x^4} + 12{x^3} - 36{x^2} + 25{\text{ }} \to {\text{(1)}},x \in R$
It is also given that ${{\text{S}}_1}$ corresponds to the set of values of x where local minima occurs and ${{\text{S}}_2}$ corresponds to the set of values of x where local maxima occurs.
Let us differentiate the given function with respect to x, we get
$\Rightarrow \dfrac{{d\left[ {f\left( x \right)} \right]}}{{dx}} = \dfrac{d}{{dx}}\left[ {9{x^4} + 12{x^3} - 36{x^2} + 25} \right] \\ \Rightarrow f'\left( x \right) = \dfrac{d}{{dx}}\left[ {9{x^4}} \right] + \dfrac{d}{{dx}}\left[ {12{x^3}} \right] - \dfrac{d}{{dx}}\left[ {36{x^2}} \right] + \dfrac{d}{{dx}}\left[ {25} \right] \\ \Rightarrow f'\left( x \right) = 9\dfrac{d}{{dx}}\left[ {{x^4}} \right] + 12\dfrac{d}{{dx}}\left[ {{x^3}} \right] - 36\dfrac{d}{{dx}}\left[ {{x^2}} \right] + 0 \\ \Rightarrow f'\left( x \right) = 9\left( {4{x^3}} \right) + 12\left( {3{x^2}} \right) - 36\left( {2x} \right) \\ \Rightarrow f'\left( x \right) = 36{x^3} + 36{x^2} - 72x \\ \Rightarrow f'\left( x \right) = 36x\left( {{x^2} + x - 2} \right){\text{ }} \to {\text{(2)}} \\$
Since, we know that local maxima or local minima are the points where local maximum and local minimum values will be occurring. At local maxima and local minima, for any function f(x) the necessary condition is $f'\left( x \right) = 0$.
By putting $f'\left( x \right) = 0$ in equation (2), we get
$\Rightarrow 0 = 36x\left( {{x^2} + x - 2} \right) \\ \Rightarrow x\left( {{x^2} + x - 2} \right) = 0 \\ \Rightarrow x\left( {{x^2} - x + 2x - 2} \right) = 0 \\ \Rightarrow x\left[ {x\left( {x - 1} \right) + 2\left( {x - 1} \right)} \right] = 0 \\ \Rightarrow x\left( {x - 1} \right)\left( {x + 2} \right) = 0 \\$
From the above equation, we have
x=0 or $x - 1 = 0 \\ \Rightarrow x = 1 \\$ or $x + 2 = 0 \\ \Rightarrow x = - 2 \\$
So, the points where maxima or minima can occur are x=0,1,-2
Also we know that for any function f(x) to attain local maxima at a point x=a, $f''\left( a \right) < 0$ and for this function f(x) to attain local minima at a point x=b, $f''\left( b \right) > 0$.
By differentiating the equation (2) both sides with respect to x, we get
$\Rightarrow \dfrac{d}{{dx}}\left[ {f'\left( x \right)} \right] = \dfrac{d}{{dx}}\left[ {36x\left( {{x^2} + x - 2} \right)} \right] \\ \Rightarrow f''\left( x \right) = 36\dfrac{d}{{dx}}\left[ {{x^3} + {x^2} - 2x} \right] \\ \Rightarrow f''\left( x \right) = 36\left[ {\dfrac{d}{{dx}}\left[ {{x^3}} \right] + \dfrac{d}{{dx}}\left[ {{x^2}} \right] - 2\dfrac{{dx}}{{dx}}} \right] \\ \Rightarrow f''\left( x \right) = 36\left[ {3{x^2} + 2x - 2} \right]{\text{ }} \to {\text{(3)}} \\$
Put x=0 in equation (3), we get
$\Rightarrow f''\left( 0 \right) = 36\left[ {3{{\left( 0 \right)}^2} + 2\left( 0 \right) - 2} \right] = - 72$
Clearly, $f''\left( 0 \right) < 0$ so x=0 is a point of local maxima i.e., corresponding to point x=0, the given function f(x) has local maximum value. So, x=0 is a value in the set ${{\text{S}}_2}$.
Put x=1 in equation (3), we get
$\Rightarrow f''\left( 1 \right) = 36\left[ {3{{\left( 1 \right)}^2} + 2\left( 1 \right) - 2} \right] = 36\left[ 3 \right] = 108$
Clearly, $f''\left( 1 \right) > 0$ so x=1 is a point of local minima i.e., corresponding to point x=1, the given function f(x) has local minimum value. So, x=1 is a value in the set ${{\text{S}}_1}$.
Put x=-2 in equation (3), we get
$\Rightarrow f''\left( -2 \right) = 36\left[ {3{{\left( { - 2} \right)}^2} + 2\left( { - 2} \right) - 2} \right] = 36\left[ 6 \right] = 216$
Clearly, $f''\left( -2 \right) > 0$ so x=-2 is a point of local minima i.e., corresponding to point x=-2, the given function f(x) has local minimum value. So, x=-2 is a value in the set ${{\text{S}}_1}$.
So, set ${{\text{S}}_1} = \left\{ { - 2,1} \right\};{{\text{S}}_2} = \left\{ 0 \right\}$
Hence, option A is correct.

Note- In this particular problem, we have used second derivative test i.e., if $f''\left( a \right) < 0$, then x=a is a point of local maxima and if $f''\left( a \right) > 0$, then x=a is a point of local minima. Also, if $f''\left( a \right) = 0$occurs then x=a is a point of inflection. Here, the local maximum value of function f(x) is obtained by substituting x=0 in the function and the local minimum values of f(x) is obtained by substituting x=-2 and x=1 in the function.


text:
# Colloquium: Zabrodsky lectures - Camillo De Lellis (University of Zurich) - "The oriented Plateau problem and a question of Almgren"

The Plateau problem, named by Henry Lebesgue after the Belgian physicist, consists in finding the surface of least area which spans a given contour. In order to tackle such question, generations of mathematicians have investigated the very fundamental notions of surface'', boundary'' and area'', proposing a variety of different theories. In this talk I will give a brief exposition of the so-called theory of currents, introduced by Federer and Fleming in the 60es after the pioneering work of De Giorgi in the case of hypersurfaces. I will then discuss an open question relating the shapes of the contour and that of the minimizer, posed by Almgren in the early eighties and recently solved in a joint work with Guido de Philippis, Jonas Hirsch and Annalisa Massaccesi.

## Date:

Thu, 26/04/2018 - 14:30 to 15:30

## Location:

Manchester Building (Hall 2), Hebrew University Jerusalem


text:
## anonymous one year ago My question is with respect to problem set 1, 1c-7. I don't understand the solution. In particular, what is the connection between the area of the parallelogram and the max value of the determinant? Could someone please explain in detail.

1. phi

given two vectors <a,b> and <c,d> they can define a parallelogram |dw:1442232715212:dw| We know the magnitude of the cross product of vectors x and y has the definition $|x\times y| = |x| |y| \sin \theta$ where theta is the angle between the vectors x and y This expression also represents the area of a parallelogram defined by x and y Thus, given two vectors <a,b> and <c,d> if we extend these to vectors in 3D by setting the z component to 0 <a,b,0> and <c,d,0> we can form the cross product <0,0, ad-bc> and the magnitude is $$\sqrt{0^2+0^2 +(ad-bc)^2} = ad-bc$$ and ad-bc is the determinant of a matrix whose columns are <a,b> and <c,d> I don't know that this gives any intuition about why a determinant is linked to area, but it does show there is that condition.

2. anonymous


text:
Dielectron azimuthal anisotropy at mid-rapidity in Au + Au collisions at $\sqrt{s_{_{NN}}} = 200$ GeV

The collaboration
Phys.Rev.C 90 (2014) 064904, 2014.

Abstract
We report on the first measurement of the azimuthal anisotropy ($v_2$) of dielectrons ($e^{+}e^{-}$ pairs) at mid-rapidity from $\sqrt{s_{_{NN}}} = 200$ GeV Au+Au collisions with the STAR detector at RHIC, presented as a function of transverse momentum ($p_T$) for different invariant-mass regions. In the mass region $M_{ee}\!<1.1$ GeV/$c^2$ the dielectron $v_2$ measurements are found to be consistent with expectations from $\pi^{0}$, $\eta$, $\omega$ and $\phi$ decay contributions. In the mass region $1.1\!<M_{ee}\!<2.9$ GeV/$c^2$, the measured dielectron $v_2$ is consistent, within experimental uncertainties, with that from the $c\bar{c}$ contributions.

• #### Figure 19 (exp. data)

Experimental data from Figure 19

10.17182/hepdata.96269.v1/t1

The dielectron $v_2$ in the $\pi^0$ Dalitz decay region as a function of $p_T$ in different centralities from Au +...

• #### Figure 19 (sim. data)

Simulated data from Figure 19

10.17182/hepdata.96269.v1/t2

Expected dielectron $v_2$ from $\pi^0$ Dalitz decay as a function of $p_T$ in different centralities from Au + Au collisions...

• #### Figure 21 a (exp. data)

Experimental data from Figure 21 a

10.17182/hepdata.96269.v1/t3

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV for...

• #### Figure 21 b (exp. data)

Experimental data from Figure 21 b

10.17182/hepdata.96269.v1/t4

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV for...

• #### Figure 21 c (exp. data)

Experimental data from Figure 21 c

10.17182/hepdata.96269.v1/t5

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV for...

• #### Figure 21 d (exp. data)

Experimental data from Figure 21 d

10.17182/hepdata.96269.v1/t6

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV for...

• #### Figure 21 e (exp. data)

Experimental data from Figure 21 e

10.17182/hepdata.96269.v1/t7

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV for...

• #### Figure 21 f (exp. data)

Experimental data from Figure 21 f

10.17182/hepdata.96269.v1/t8

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV for...

• #### Figure 21 a (sim. data)

Simulated data from Figure 21 a

10.17182/hepdata.96269.v1/t9

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV expected...

• #### Figure 21 b (sim. data)

Simulated data from Figure 21 b

10.17182/hepdata.96269.v1/t10

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV expected...

• #### Figure 21 c (sim. data)

Simulated data from Figure 21 c

10.17182/hepdata.96269.v1/t11

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV expected...

• #### Figure 21 d (sim. data)

Simulated data from Figure 21 d

10.17182/hepdata.96269.v1/t12

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV expected...

• #### Figure 21 e (sim. data)

Simulated data from Figure 21 e

10.17182/hepdata.96269.v1/t13

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV expected...

• #### Figure 21 f (sim. data)

Simulated data from Figure 21 f

10.17182/hepdata.96269.v1/t14

The dielectron $v_2$ as a function of $p_T$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV expected...

• #### Figure 22 (exp. data)

Experimental data from Figure 22

10.17182/hepdata.96269.v1/t15

The $p_T$-integrated dielectron $v_2$ as a function of $M_{ee}$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV.

• #### Figure 22 (hadron data)

10.17182/hepdata.96269.v1/t16

The $v_2$ of hadrons $\pi$, $K$, $p$, $\phi$ and $\Lambda$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200...

• #### Figure 22 (sim. data)

Simulated data from Figure 22

10.17182/hepdata.96269.v1/t17

The $p_T$-integrated dielectron $v_2$ as a function of $M_{ee}$ in minimum-bias Au + Au collisions at $\sqrt{s_{NN}}$ = 200 GeV,...


text:
시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 7 4 4 66.667%

## 문제

Malaysia’s Independence Day -- also known as Hari Merdeka -- is celebrated each year on 31 August to commemorate the independence of Federation of Malaya from British colonial rule in 1957. During the whole month of August, many Malaysians express their patriotisms and loves toward their country by raising Malaysian flag on their home’s balcony and on any vehicles they have (baby stroller included). This independence day celebration is usually incomplete without shouting “Merdeka!” seven times.

For the next year Independence Day celebration, IIUM plans to put up a long banner around IIUM’s main campus. The committees want to write meaningful and motivating words in this banner to inspire students (and possibly professors too). To make things interesting, they agree that all words should be written without spaces in one single line. Moreover, they also agree that words are allowed to overlap each other. For example, “WORDER” contains the words: “WORD” and “ORDER”. For ease of explanation, let say whatever is written on the banner as text.

The committees have compiled a list of words and assigned each word with a score which will be counted as the text’s score for every occurrence of such word in the text. For example, if the value of WORD is 5 and ORDER is 8, then the text WORDER has a score of 5 + 8 = 13; WORDWORDER has a score of 5 + 5 + 8 = 18 (notice that WORD occurs twice in this example).

Aside from words, the committees also want each character in the text to appear as fancy as possible, thus, each written character will be specially handcrafted. Of course this cause another problem: handcrafting each character requires additional cost and obviously the committees’ budget is limited.

Your task in this problem is to help the committees to determine what text should be written on the banner such that its score is as high as possible while the cost of writing such text is within the given budget. To make things easier, you only need output the score.

## 입력

The first line contains an integer T (T ≤ 30) denoting the number of cases. Each case begins with three integers in a single line: N (1 < N ≤ 26), M (1 ≤ M ≤ 100) and B (10 ≤ B ≤ 200) denoting the number of characters, the number of words, and the committees’ budget. The next N following lines each contain one character Hi (A-Z) and one integer Ci (1 ≤ Ci ≤ 3) which represent the cost of writing one character Hi in the text. You may assume Hi are unique for all i = 1..N. The following M lines each contain one word Wi (1 ≤ |Wi| ≤ 100) and one integer Si (1 ≤ Si ≤ 100) denoting the score of such word. Assume all characters in the given set of words exists among Hi.

## 출력

For each case, output “Case #X: Y” (without quotes) in a line where X is the case number, starting from 1, followed by a single space, and Y is the highest possible score which can be obtained in the corresponding case.

## 예제 입력

2
3 3 10
A 2
B 2
C 3
AA 10
AAA 30
ABC 60
14 8 200
M 2
I 3
R 2
A 1
O 2
E 2
C 2
L 2
F 1
V 2
Y 3
H 1
U 2
N 2
MIRACLE 100
FLUFFY 40
LOVE 100
IVY 10
VEN 30
AYE 20
HOE 10
EURO 80

## 예제 출력

Case #1: 130
Case #2: 2600

## 힌트

The text with highest score is AAAAA. There are 4 occurrences of AA and 3 occurrences of AAA, which makes the score to be 4 * 10 + 3 * 30 = 130. Writing AAAAA requires 5 A each costs 2, thus the total cost is 10.


text:
# A sum of a random number of Poisson random variables

in my probability class I was given this question on which I am stuck concerning a sum of random number of Poisson random variables:

Let us define the countable set of independent random variables $X_i \sim \mathrm{Pois}(\lambda _i)$ and the random variable $N$ independent from the rest of the $X_i$ which also has a Poisson distribution $N \sim \mathrm{Pois}(\lambda)$. We are asked to check if the following sum $Y = \sum_{i=1}^N X_i$ also has a Poisson distribution and if so, with what parameter? As a hint we are asked to look at the characteristic function of the variable to check.

I know the deterministic finite sum of Poisson random variables is again a Poisson random variable with the sum of parameters, but I cannot solve it for a random number of summands that is also Poisson-ly distributed, I know the characteristic function of a Poisson distributed random variable $\Phi(t) = e^{\lambda (e^{it}-1)}$. I thank all helpers who can show me a way out of this.

In the case where all $\lambda_j$ are equal, let's say to $\mu$, you can compute
$$\mathbb E\left[ \exp(itY) \mid N \right] = \exp(\mu (e^{it}-1) N)$$ so that $$\mathbb E[\exp(itY)] = \mathbb E [\exp(\mu(e^{it}-1)N] = \exp(\lambda ( \exp(\mu (e^{it}-1))-1))$$ which is not the characteristic function of a Poisson distribution. However, things are more complicated if the $\lambda_j$ are not all equal.
EDIT: In general, let $s_n = \sum_{j=1}^n \mu_j$. In particular $s_0 = 0$. Then $$\mathbb E \left[\exp(itY) \mid N \right] = \mathbb E \left[\exp(s_N (e^{it}-1))\right] = \exp(-\lambda) \sum_{n=0}^\infty \dfrac{\lambda^n}{n!} \exp(s_n (e^{it}-1))$$ Letting $z = 1 - e^{it}$, we want to know if there is a formula $$\exp(-\lambda) \sum_{n=0}^\infty \dfrac{\lambda^n}{n!} \exp(-s_n z) = \exp(-\rho z)$$ where $\rho > 0$. If this is valid for $z = 1 - e^{it}$, by analyticity it must be valid in the right half plane. Now as $z \to +\infty$, the limit of the left side is $\exp(-\lambda)$ (since $s_0 = 0$), while the limit of the right side is $0$. So this is impossible: the distribution is not Poisson.
• Thank you Robert the case that all parameters are equal is now clear to me but is there a simple method to determine the distribution if the $\lambda$s are not equal? Could it be a Poisson distribution – Don John Prep Mar 21 '16 at 20:04


text:
What does lsmeans report for a generalized linear model, such as Poisson mixed model (fit with glmer)?

I am analyzing the eye-tracking data from a designed experiment. A simplified version of my data looks like this (You can get the dput() data here),

head(lookDATA)

participant fixationImage fixationCount
1           9    Automobile            81
2           9          Bird            63
3           9         Chair            82
4           9           Dog            64
5           9          Face            90
6           9         Plant            75

where participant is a unique identifier for each subject, fixationImage is what picture category they fixated on, and fixationCount is the number of times they fixated on that picture category.

I fit a poisson model to the data using glmer() from the lme4 package.

model<-glmer(fixationCount ~ fixationImage + (1|participant), family = poisson, data = lookDATA)

I used lsmeans() from the lsmeans package to examine the differences among the factor levels,

cld(lsmeans(model,"fixationImage"))

which provides the following output:

fixationImage   lsmean         SE df asymp.LCL asymp.UCL .group
Chair         3.786022 0.05764923 NA  3.673018  3.899026  1
Bird          3.866201 0.05750641 NA  3.753476  3.978925   2
Dog           3.868768 0.05751010 NA  3.756037  3.981500   2
Body          3.883644 0.06040952 NA  3.765230  4.002059   23
Plant         3.893327 0.05746744 NA  3.780679  4.005975   23
Automobile    3.901939 0.05745528 NA  3.789315  4.014563   23
Face          3.946848 0.05832549 NA  3.832519  4.061178    3

According to my (perhaps limited) understanding of the using lsmeans vignette the lsmean column should represent the average number of looks to a given category predicted by the model.

However, these values seem uncomfortably far from simple descriptive statistics for these numbers,

summaryBy(fixationCount ~ fixationImage, data = lookDATA)

fixationImage fixationCount.mean
1    Automobile           55.18750
2          Bird           53.25000
3          Body           57.12821
4         Chair           50.39450
5           Dog           53.82883
6          Face           56.76389
7         Plant           54.71429

suggesting perhaps that I do not correctly understand what the lsmeans represent here, or perhaps that I've misspecified the model.

Any assistance would be greatly appreciated.

The output represents predictions from your model for each image. With the poison family, the default link function is the natural log - so those values are on the log scale. If you do lsmeans(..., type = "response"), it will back-transform the predictions to the original response scale.
• Thanks so much for the swift answer. I changed my syntax to cld(lsmeans(model,"fixationImage",type="response")) but got the following error: Error in \$<-.data.frame(*tmp*, "sep", value = ",") : replacement has 1 row, data has 0. For the record I am using R version 3.1.2 (2014-10-31) 'Pumpkin Helmet' and lsmeans version 2.17. Nonetheless, you've answered my question and I will transform the output manually. Thanks again! – Marcus Morrisey Apr 26 '15 at 21:59
• I'm not sure why the error occurs but it looks like it comes from the cld side of things. Take it out and see if it works. And use pairs instead of cld to test the comparisons (in a separate call). That's a better route anyway because cld makes black-and-white decisions. – rvl Apr 26 '15 at 22:59
• @MarcusMorrisey I have fixed the bug in cld that created the error. Thanks for reporting it. Send me an e-mail (see Maintainer field) if you want me to send the updated package. Else it'll be updated on CRAN in a few weeks. – rvl Apr 27 '15 at 16:01


text:
# Compute eye space from window space

This page will explain how to recompute eye-space vertex positions given window-space vertex positions. This will be shown for two cases. Case 1 uses gl_FragCoord in its entirety. Case 2 uses only gl_FragCoord.xyz. Both require access to the projection matrix.

## Definitions

Before we begin, we need to define some symbols:

Symbol Meaning
M The projection matrix
P The eye-space position, 4D vector
C The clip-space position, 4D vector
N The normalized device coordinate space position, 3D vector
W The window-space position, 3D vector
Vx, y The X and Y values passed to glViewport
Vw, h The width and height values passed to glViewport
Dn, f The near and far values passed to glDepthRange

## From gl_FragCoord

gl_FragCoord contains the window-space position Pwnd. This is a 3D vector quantity. gl_FragCoord.w however contains the inverse of the clip-space W: ${\displaystyle gl\_FragCoord_{w}={\tfrac {1}{C_{w}}}}$.

Given these values, we have a fairly simple system of equations:

{\displaystyle {\begin{aligned}{\vec {N}}&={\begin{bmatrix}{\tfrac {(2*W_{x})-(2*V_{x})}{V_{w}}}-1\\{\tfrac {(2*W_{y})-(2*V_{y})}{V_{h}}}-1\\{\tfrac {(2*W_{z})-D_{f}-D_{n}}{D_{f}-D_{n}}}-1\end{bmatrix}}\\{\vec {C}}_{xyz}&={\frac {\vec {N}}{gl\_FragCoord_{w}}}\\C_{w}&={\frac {1}{gl\_FragCoord_{w}}}\\{\vec {P}}&=M^{-1}{\vec {C}}\end{aligned}}}

In a GLSL fragment shader, the code would be as follows:

vec4 ndcPos;
ndcPos.xy = ((2.0 * gl_FragCoord.xy) - (2.0 * viewport.xy)) / (viewport.zw) - 1;
ndcPos.z = (2.0 * gl_FragCoord.z - gl_DepthRange.near - gl_DepthRange.far) /
(gl_DepthRange.far - gl_DepthRange.near);
ndcPos.w = 1.0;

vec4 clipPos = ndcPos / gl_FragCoord.w;
vec4 eyePos = invPersMatrix * clipPos;

This assumes the presence of a uniform called viewport, which is a vec4, matching the parameters to glViewport, in the order passed to that function. Also, this assumes that invPersMatrix is the inverse of the perspective projection matrix (it is a really bad idea to compute this in the fragment shader). Note that gl_DepthRange is a built-in variable available to the fragment shader.

## From XYZ of gl_FragCoord

This case is mostly useful for deferred rendering techniques. In deferred rendering, we render the material parameters of our objects to images. Then, we make several passes over these images, loading those material parameters and performing lighting computations on them.

In the light pass, we need to reconstruct the eye-space vertex position in order to do lighting. However, we do not actually have gl_FragCoord; not for the fragment that produced the material parameters. Instead, we have the window-space X and Y position, from gl_FragCoord.xy, and we have the window-space depth, sampled by accessing the depth buffer, which was also saved from the deferred pass.

What we are missing is the original window-space W coordinate.

Therefore, we must find a way to compute it from the window-space XYZ coordinate and the perspective projection matrix. This discussion will assume that your perspective projection matrix is the standard OpenGL perspective matrix, as produced by glFrustum or gluPerspective. If you are using a different matrix, you may need to change this math accordingly.


text:
Article

Inverse problems for Schrödinger equations with Yang–Mills potentials in domains with obstacles and the Aharonov–Bohm effect

Journal of Physics Conference Series 04/2005; 12(1). DOI:10.1088/1742-6596/12/1/003
Source: arXiv

ABSTRACT We study the inverse boundary value problems for the Schrödinger equations with Yang-Mills potentials in a bounded domain Ω 0 ⊂ R n containing finite number of smooth obstacles Ω j , 1 ≤ j ≤ r. We prove that the Dirichlet-to-Neumann opeartor on ∂Ω 0 determines the gauge equivalence class of the Yang-Mills potentials. We also prove that the metric tensor can be recovered up to a diffeomorphism that is identity on ∂Ω 0 .

0 0
·
0 Bookmarks
·
28 Views
• Article: An inverse hyperbolic problem with many boundary measurements
Communications in Partial Differential Equations 01/1991; 16(6-7):1183-1195. · 1.03 Impact Factor
• Source
Article: Significance of Electromagnetic Potentials in the Quantum Theory
[hide abstract]
ABSTRACT: In this paper, we discuss some interesting properties of the electromagnetic potentials in the quantum domain. We shall show that, contrary to the conclusions of classical mechanics, there exist effects of potentials on charged particles, even in the region where all the fields (and therefore the forces on the particles) vanish. We shall then discuss possible experiments to test these conclusions; and, finally, we shall suggest further possible developments in the interpretation of the potentials.
Physical Review - PHYS REV X. 01/1959; 115(3):485-491.


text:
# Build a ring around Earth, then remove the supports

What would happen if we decided to build a giant ring that managed to wrap around the whole world, end to end that was supported with pillars all along the ring and then the supports all suddenly removed?

Would the ring float in place? or if it fell, what direction would it fall?

## 5 Answers

Why not try this at home by using the Coulomb force or magnetism instead of gravity?
Although all those forces are different in nature, mathematically they are the same: $F(r) = -\frac{const.}{r^2}$
Edit: Magnetism is different as pointed out in the comments, but it still works for illustrating the problem. In fact, the result is the same for any $\frac{-1}{r^c}$ force with $c>1$.
Take a small magnet and place it inside a keyring on top of a table. You will find that even despite the friction helping you to keep both parts concentric, the slightest asymmetry will result in a non-zero force and make them snap together.

To compute the force on a ring, I drop all constants, set the ring radius to 1 and place the earth at the origin, also I use complex numbers to represent the vectors. The ring is parametrized as $e^{i \varphi}, \varphi \in [0,2 \pi]$, The force on a concentric ring is then given by
$$F = \int_0^{2 \pi} \frac{e^{i \varphi}}{|e^{i \varphi}|^3} d\varphi$$ this is trivial and the solution is zero, now we shift the ring slightly to the right
$$F(\varepsilon) = \int_0^{2 \pi} \frac{\varepsilon + e^{i \varphi}}{|\varepsilon +e^{i \varphi}|^3} d\varphi$$
I imagined this to be not that much harder to solve, but 20 minutes later Maple went up to 400 MB of memory usage and still hasn't produced a result so I evaluated it numerically instead

As soon as the ring is displaced, it experiences a force in the same direction which results in further displacement (up to $\varepsilon<1$, then it hits the ground, earlier if the earth has a non-zero radius)

• However, if you spun the ring at a high velocity... – Albert Renshaw Jan 22 '17 at 2:43

This is a fun what-if. I really wish I was xkcd right now so that I could include pictures and humour, but I'm not.

If we built a giant ring around Earth at just the right height everywhere, then in theory, the ring would just float there once the supports were removed. However, (and this is the reason not to try it) this is an unstable state. If you so much as tap on one side of the ring, the whole thing will come crashing down. It's like balancing a pencil on its point or a bicycle upright while stopped (no training wheels!). Possible, but instability is a b!%#.

But let's back up to how you might go about doing this. The pressures on the ring would be enormous, so you would have to make it very thick and out of really strong materials. Carbon nanotubes would be great but expensive. Odds are we'd go with steel for cost and just make it thicker.

Then you need to build it in exactly the right place and at the right height. And the supports would be none too stable also (why would we not just build this as a giant global bypass and leave the supports in place?). But let's say you got it built. To pull off this feat, you need to remove the supports simultaneously and quickly. That won't be easy since they'll be huge and firmly in place. Best synchronized demolition ever!

Ok, now you have this ring floating. It had to be built above the atmosphere because any winds or atmospheric effects could bring it down. But also, it had to be built at the right altitude to avoid all that space junk we have floating in orbit. (One stray satellite and BAM! we'll bring a whole new meaning to the phrase "Hey look at that huge metal ring that's crashing down to Earth!")

And, to make this easier for us, somehow we got it spinning (not very fast) so that angular momentum and orbital mechanics could help us out (Okay, those don't actually help the ring, but neither do they hurt it and they make it look cool; a spinning ring in space. I call that a net gain, so it helps).

Before the day is out, we have a problem. We forgot one crucial thing. That darn Moon! The tidal forces from the Moon (wherever it is at that time) upset the delicately balanced and unstable ring system. Now we have something that we should have considered; the extremely massive ring of steel we built is crashing towards Earth. It's going to leave a dent and kill lots of folks. On the plus side, building a massive ring like that will look good on your resume.

• What would happen if the ring was rotated to orbital speeds before removing supports, such that free bodies at the circumference would circularly orbit? Would that assist with stability? – Involute Jul 24 '15 at 6:18
• @YourAverageMechEng assuming a perfectly rigid ring, no — the total forces would still add up the same. Assuming a somewhat flexible ring that would deform under stress: I haven't done the math but it would probably be even worse. As soon as it was off center it would start precessing, tidal braking, and vibrating, and my guess is that all that chaotic motion would probably result in some piece colliding even sooner than in the non-rotating case. – hobbs Oct 3 '16 at 20:59
• @hobbs Please, rotating never made anything more dangerous (he said, while sitting next to a table saw). And looking cool is completely worth any minor increases in risk. Checkmate – Jim Mar 13 '17 at 12:44

If the ring elements are actually in orbit (i.e. each part would follow the ring shape by itself without need for a pillar), then you get this:

If each ring element is "closer" to the Earth (i.e. they don't revolve fast enough for their altitude), then the pillars offer sustenance. If you remove them, then the ring is stable in the north-south axis, but not laterally. That is, if you build the along the Earth equator, and then remove the pillars, then the ring will crash somewhere on the equator (the north-south stability should ensure that the ring will remain in the equatorial plane), but it will crash.

(Of course, we don't know any material sturdy enough to prevent the ring from deforming under the pressure; in practice it would crash in many places at once, all along the equator.)

If each ring element is "farther" from the Earth then the "pillars" are really cables that keep the ring elements from flying away; if you remove the pillars then things will depend on how the links between the elements resist to the tension. As long as they don't break, you should get a ring that will stay there, like orbiting satellites by rotating faster than they should.

People considered (An electromagnetic space elevator? ) a superconducting ring with a high current in space above the equator. The weight of the ring can be balanced by the force due to Earth's magnetic field acting on the current.

Well, we have people expounding on the equilibrium being unstable but, uh, wouldn't the net force result in an attraction between the centres of mass? To me, that seems like an essentially stable setup, at least before taking rotation into account.

• Except it's not stable, cf this post. – Kyle Kanos Nov 12 '14 at 19:10
• No. Gravity can only be treated as acting on the center of mass for an object small enough that the force of gravity is uniform. Obviously, for a ring encompassing a planet this is not the case. – user27118 Nov 12 '14 at 20:31


text:
# Hypothesis testing: Test statistic, P-value and significance levels

A manufacturer claims his light bulbs have a mean life $μ = 1800$ hours. A consumer group tested a random sample of $n = 250$ bulbs and found them to have a sample mean life $\bar{x} = 1790$ hours and a sample standard deviation $s = 50$ hours. Assess the manufacturer's claim.

1. what is $H_0$?
2. What is $H_a$?
3. What is the value of the test statistic?
4. In what range does the P-value reside?
5. Are the results statistically significant at the .05 level of significance?

So I have the following information:

$μ = 1800 = H_O$

$n = 250$

$\bar{x} = 1790 = H_a$

$s = 50$

My test statistic would follow from the equation $\dfrac{\bar x - μ}{s/\sqrt{n}}$, giving $\dfrac{1790 - 1800}{50/\sqrt{250}} = -3.16$. This gives me a P-value of $0.0008$.

This means that the P-value resides in the range $P ≤ 0.01$. I think???

For the last question, I simply don't know what to do. Does it involve finding $Z_{0.05}$, then comparing it with the P-Value?

• We likely should have $H_a$ be $\mu\ne 1800$, though there is a reasonable argument for $H_a$ being $\mu\lt 1800$. Your choice of $H_a$ is not how one does things. For one thing, $H_0$ and $H_a$ are chosen before the experiment. – André Nicolas Jun 16 '14 at 19:18

## 1 Answer

This depends on how you define range, but you have computed the test statistic and p-value correctly. The last question is much easier than you think. In order for the results in a hypothesis test to be statistically significant (in other words, to be able to reject the null hypothesis with sufficient statistical evidence), if we let $p$ be the p-value and $\alpha$ the significance level, we must have $p \leq \alpha$. Since you have calculated $p = 8 \times 10^{-4}$ here, it is clearly true for $\alpha = 0.05$ that $p \leq \alpha$. Thus, the answer to the last question is yes. Note that there are several ways to evaluate statistical significance, but this is one that is convenient in this context. To echo the comment of @AndréNicolas, I recommend changing the alternative hypothesis to $H_a : \mu \neq 1800$ (remember this is two-sided and the p-value is computed differently than in a standard one-sided test) or $H_a : \mu < 1800$, since this is the convention. The sample mean has nothing to do with the choice of hypotheses in practice.


text:
# Which ion of iron is produced in a reaction between iron and copper(II) sulfate?

Using these equations: \begin{aligned} \text{(Fe2):}&&\ce{ Fe + CuSO4 &-> FeSO4 + Cu}\\ \text{(Fe3):}&&\ce{ 2Fe + 3CuSO4 &-> Fe2(SO4)3 + 3Cu} \end{aligned}

Beginning with $0.78\:\mathrm{g}$ of iron, the theoretical yields of copper are $0.89\:\mathrm{g}$ (with $\ce{Fe^{2+}}$) and $1.33\:\mathrm{g}$ (with $\ce{Fe^{3+}}$), and the actual yield was $0.78\:\mathrm{g}$ of copper. I know to find of the ratio of the moles of iron used to the moles of copper formed (88% for $\ce{Fe^{2+}}$, 58% for $\ce{Fe^{3+}}$), and so the clear choice would be that this reaction formed $\ce{Fe^{2+}}$ ions, but my teacher said this would form $\ce{Fe^{3+}}$ ions, but why is that? Shouldn't it have formed $\ce{Fe^{2+}}$? The reaction formed $0.12\:\mathrm{mol}$ of copper, compared to the $0.14\:\mathrm{mol}$ in the theoretical yield, and the other $0.02\:\mathrm{mol}$ could have just been lost somewhere along the reaction process.

When "doing" science, usually you try to (in-)validate a model of the workings of the world. In the case of chemists, this world is mostly confined to the scale of molecules.

That said, let's proceed with

# A Theoretical Model

Listed below are some standard reduction potentials I've gathered from the Handbook of Chemistry and Physics, 95th ed. (probably paywalled for you): \begin{align} &&E^0_\text{red} / \mathrm{V}\\ \hline \ce{Fe^{2+} + 2e- & <=> Fe} & -0.447 \\ \ce{Fe^{3+} + 3e- & <=> Fe} & -0.037 \\ \ce{Cu^{2+} + 2e- & <=> Cu} & 0.342 \\ \end{align}

Now we can calculate the potential (and the resulting electromotive force EMF) for each of the reactions: \begin{align} E^0_\text{(Fe2)} = E^{0}_\text{red}(\text{red}) - E^0_\text{red}(\text{ox}) &= 0.342~\mathrm{V} - (-0.447~\mathrm{V}) = 0.789~\mathrm{V} \\ E^0_\text{(Fe3)} &= 0.342~\mathrm{V} - (-0.037~\mathrm{V}) = 0.379~\mathrm{V} \end{align}

It is clear that the reaction (Fe2) releases more energy and thus should be preferred over the other reaction. This means that we expect a yield of 100% Cu and not 150% Cu.

Now that we have gathered some theoretical understanding of the matter, let's proceed to the interesting part, which is

# Confirmation With Experimental Results

You have correctly calculated the theoretical yields for copper to be 0.89 g and 1.33 g, respectively. The corresponding amounts of copper are 0.014 mol and 0.021 mol.

You have measured the amount of copper produced, and it clocks in at 0.78 g. This is already a strong indication that we should side with (Fe2) on this one. But just to really be sure, let's look at the error that we would have if it was (Fe3): $$\varepsilon = \frac{\Delta x}{x} = 41.4\%$$ This is a very high error, especially when compared to the error for (Fe2), which is only 12.1%. Assuming that you did not perform the reaction with pure Fe but a mixture of iron with some iron oxides as contaminants, did not use an analytical scale and performed the experiment in fairly uncontrolled conditions (are you sure the reaction was complete when you aborted?) this error is not as bad as it seems.

With the experimental results in our pocket, we can now move on to the final part:

# The Conclusion

We have shown, using theoretical predictions and experimental confirmation, that the reaction observed was the oxidation of iron to iron(II) under reduction of copper(II) to copper.

By the way, most of the calculations I did with an iPython Notebook, which you can view here. I might have messed something up, you never know.


text:
# The pentagonal number theorem

Here's a strange fact:

$\displaystyle\prod_{k=1}^\infty (1-x^k) = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} + \cdots = 1 + \displaystyle\sum_{a=1}^\infty (-1)^a x^{a(3a \pm 1)/2}$

There's a pattern here, but it's hard to spot. Terms like $x^n$ will only appear when $n = \frac{a(3a \pm 1)}{2}$, where $a$ is an integer greater than 0. This means that if we continued this expansion we would run across terms like $x^{35}, x^{40}, x^{51}...$, but in order to know this for certain we need to prove that this pattern exists.

To get started, we should forget about the righthand side of the equations above and just focus on the left. We have the expression $(1-x)(1-x^2)(1-x^3)\cdots$ for all powers of $x$. Multiplying this out will give us every multiplicative combination of $1, x, x^2, \dots$ possible as a result. Thinking in reverse, we can ask about how terms like $x^n$ may arise from this. Since $x^n$ must come from some multiplicative combinations of $1, x, x^2, \dots$, we know that $n$ must come from an additive combination of $1, 2, 3, \dots$ (since $x^a x^b = x^{a+b}$).

$x^5 = x^{1+4} = x^{2+3}$ $x^6 = x^{1+5} = x^{2+4} = x^{1+2+3}$ $x^7 = x^{1+6} = x^{2+5} = x^{3+4} = x^{1+2+4}$

A breakdown of $n$ into smaller parts added together is known as a partition. Here, we're dealing specifically with partitions into distinct parts. If we apply this reasoning to $(1-x)(1-x^2)(1-x^3)\cdots$ by keeping track of the signs, we will see a neat pattern: terms of the form $x^a$ will be negative, $x^{a+b}$ will be positive, $x^{a+b+c}$ will be negative, and the pattern continues. This means that "odd" partitions will have negative coefficients while "even" partitions have positive coefficients. It follows that the coefficients of all terms on the right will have this form.

$(\text{\# of even partitions of n} - \text{\# of odd partitions of n}) \cdot x^n$

Which means that all of the numbers which show up in $1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} + \cdots$ must have an imbalance of even and odd partitions into distinct parts; otherwise they will have a coefficient of $0$. 5 and 7 have one more even partition than odd ones, while 12 and 15 have one more odd partition than even ones.

Why is it that the number of even and odd partitions balance out for most numbers except the ones equal to $a(3a\pm 1)/2$? It has to do with how partitions can be found from other partitions. Consider 6, which partitions into 6, 5 + 1, 4 + 2, and 3 + 2 + 1. Starting from the first partition, 6, we can create a new partition by "shaving" one off the top of it to make 5 + 1. Likewise we can do this for the other two. To make this argument clearer, we can visualize partitions with dots on a hidden grid, known as a Ferrers diagram. Here are all the partitions of 6 represented by Ferrers diagrams.

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet & \bullet \end{array} \qquad \begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & & & & \end{array} \qquad \begin{array}{c}\bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & & \end{array} \qquad \begin{array}{c}\bullet & \bullet & \bullet \\ \bullet & \bullet & \\ \bullet & & \end{array}$

We can see that 6 has just as many odd partitions as it does even, so $x^6$ doesn't appear in the expansion. Since there are an equal number of even and odd partitions, it makes sense to ask if there's a one-to-one mapping between them. One possible scheme comes from a "shaving" method, where the largest parts of a partition are "shaved" by 1. This works, as moving from 6 to 5 + 1 changes the partition from odd to even. Likewise, moving from 4 + 2 to 3 + 2 + 1 changes an even partition into an odd one.

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet & \color{#D61F06}{\bullet} \end{array} \longleftrightarrow \begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet \\ \color{#D61F06}{\bullet} & & & & \end{array}$

$\begin{array}{c}\bullet & \bullet & \bullet & \color{#D61F06}{\bullet} \\ \bullet & \bullet & & \end{array} \longleftrightarrow \begin{array}{c}\bullet & \bullet & \bullet \\ \bullet & \bullet & \\ \color{#D61F06}{\bullet} & & \end{array}$

Under this scheme, 5 + 1 doesn't map to 4 + 2 because the shaving operation doesn't change the number of rows. However, 6 doesn't map to 3 + 2 + 1 either since the shaving operation can only add one new row in a Ferrers diagram at a time. Larger partitions such as 5 + 4 will have both parts shaved to yield 4 + 3 + 2.

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \color{#D61F06}{\bullet} \\ \bullet & \bullet & \bullet & \color{#D61F06}{\bullet} & \end{array} \longleftrightarrow \begin{array}{c}\bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \\ \color{#D61F06}{\bullet} & \color{#D61F06}{\bullet} & & \end{array}$

Since this scheme is supposed to be a one-to-one map between partitions, we can ask about doing this in reverse. The partition 5 + 3 + 1, for example, has no way of shaving off the top that works. 4 + 3 + 1 + 1 is disallowed since every part must be distinct, and 2 + 3 + 4 is disallowed since it doesn't change the oddness of the partition. Instead, 6 + 3 is the only partition which works under this mapping.

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & & \\ \color{#D61F06}{\bullet} & & & & \end{array} \longleftrightarrow \begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet & \color{#D61F06}{\bullet} \\ \bullet & \bullet & \bullet & & & \end{array}$

The key benefit to having a one-to-one mapping is that we can think of partitions as existing in pairs of even and odd partitions. If every odd partition of $n$ can be paired with an even partition of $n$, then the expansion of $(1-x)(1-x^2)(1-x^3)\cdots$ will not have an $x^n$ term. This means that the shave mapping doesn't work for some $n$.

There are some pathological partitions that don't work under this scheme.

$\begin{array}{c}\bullet & \bullet & \bullet \\ \bullet & \bullet & \end{array} \longleftrightarrow \times$ $\begin{array}{c}\bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \end{array} \longleftrightarrow \times$

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \\ \bullet & \bullet & \bullet & & \end{array} \longleftrightarrow \times$

$\begin{array}{c}\bullet & \bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \bullet & \\ \bullet & \bullet & \bullet & \bullet & & \end{array} \longleftrightarrow \times$

If you were to count them up, you'll notice right away what the pattern is. Since these partitions do not map to anything, their terms in the expansion of $(1-x)(1-x^2)(1-x^3)\cdots$ won't fully cancel out to $0$. Let's generalize this pattern. These partitions are made up of squares of length $a$ and triangles with base length $a$ or $a-1$.

$\begin{array} {ccc} \bullet & \bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \bullet & \\ \bullet & \bullet & \bullet & \bullet & & \\ \newline = \\ \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet + \bullet & \bullet & \bullet \\ \bullet & \bullet & \\ \bullet & & \end{array}$

All the possible $n$ where this can happen is then just a sum of the number of dots in each shape.

$n = a^2 + \frac{a(a+1)}{2} \quad \text{and} \quad n = a^2 + \frac{(a-1)a}{2}$

We can conveniently combine both cases into one equation.

$n = a^2 + \frac{a(a \pm 1)}{2}$

$n = \frac{a(3a \pm 1)}{2}$

So the only terms that will show up in the expansion of $(1-x)(1-x^2)(1-x^3)\cdots$ will have an exponent with the form $\frac{a(3a \pm 1)}{2}$. Their sign depends on the "leftover" pathological partition, which is negative when the partition (a) is odd and positive when the partition (a) is even. Putting this all together gives us the pentagonal number theorem.

The pentagonal number theorem $\displaystyle\prod_{k=1}^\infty (1-x^k) = 1 + \displaystyle\sum_{a=1}^\infty (-1)^a x^{a(3a \pm 1)/2}$

Historically, the pentagonal number theorem was conjectured by Euler, but he failed to find a proof of it for several years. He did eventually find it, but to me his proof felt really unnatural and hard to follow. Instead, I presented a simpler proof by the mathemtician Fabian Franklin.

Note by Levi Walker
2 months, 1 week ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
• Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Really cool! @Levi Walker

You know you can try explaining Riemann's hypothesis in great detail.

I read the wiki on Brilliant and Wikipedia but they don't satisfy me...

- 2 months, 1 week ago

Thank you! I've actually been thinking of doing something like that. It's only a matter of time :D

- 2 months, 1 week ago

No problem!

I'll be eagerly waiting...

P.S. You're welcome for reminding you about thinking of doing something like the Riemann hypothesis.

- 2 months, 1 week ago


text:
# Difference on the invariance of operators and their transformations under unitary operators

I am confused about, what I believe, refers to passive and active transformations in QM. What I have understood so far is that the matrix elements $$\langle \psi| \hat{H}|\phi\rangle$$ should remain unchanged under transformations; this implies that $$\hat{H} = \hat{U}^\dagger \hat{H} \hat{U}$$.

On the other hand, under certain transformation $$\hat{U}$$, an arbitrary operator $$\hat{\Omega}$$ transforms as $$\hat{U} \hat{\Omega} \hat{U}^\dagger$$.

1) Why should the matrix elements of the hamiltonian remain unchanged under a transformation? Is that the same as saying: "The evolution of the state is governed by the hamiltonian; under a transformation the system should still evolve in the same way, hence the matrix elements should be conserverd"?

2) What does $$\hat{H} = \hat{U}^\dagger \hat{H} \hat{U}$$ mean? Is that talking about how the hamiltonian transforms? Or is it only a condition on the transformation $$\hat{U}$$?

3) What is $$\hat{\Omega} \to \hat{U} \hat{\Omega} \hat{U}^\dagger$$ opposed $$\hat{U}|\phi\rangle$$. Does an active transformation mean applying $$\hat{U}$$ to every state, while a passive transformation is leaving vectors as they are and transforming the opeartors as $$\hat{\Omega} \to \hat{U} \hat{\Omega} \hat{U}^\dagger$$? Or does applying a transformation mean doing both of the above?

$$\langle \psi | \hat{H} | \phi \rangle$$ should remain unchanged under transformations.

This is certainly not true in general for an arbitrary transformation. I think perhaps what you meant is that $$\langle \psi | \hat{H} | \phi \rangle$$ should remain unchanged under a basis transformation.

This implies that $$H = U H U^\dagger$$.

This is not true. What you are asserting here is that $$[H, U]=0$$, which has no reason to be true without additional assumptions.

I think your confusion lies in what actually constitutes a unitary basis transformation. If we go to a different basis, the transformation prescription is

\begin{align*} &|\psi\rangle \mapsto U|\psi \rangle\\ &\langle \psi | \mapsto\langle \psi | U^\dagger\\ & \hat{H} \mapsto U\hat{H}U^\dagger. \end{align*}

Plug these transformations into $$\langle \psi | \hat{H} | \phi \rangle$$ and you can clearly see that that it is invariant under a basis transformation.

• > This implies $\hat{H} = U^\dagger H U$. Note the difference conjugate to the left, instead of the right. Does that change anything? From what I was told $\hat{H} = U^\dagger H U$ refers to the invariance of the Hamiltonian, not to how it transforms – Daniel Duque Mar 16 '19 at 13:21
• Would the left hand side $H$ refer to the non-transformed Hamiltonian, and the right hand side $H$ refer to the transformed Hamiltonian? In that case $H = U^\dagger U H U^\dagger U$? – Daniel Duque Mar 16 '19 at 13:26
• The left dagger is just a matter of which one you want to call the inverse, it makes no difference since they’re each daggers of one another – InertialObserver Mar 16 '19 at 17:23