Yes it struck me as a bit arbitrary - and I can imagine a teacher asking school kids to do it for a specific case. Solving in the general case is a post-doc maths project!
I think you would have to do it manually. Eg. you could assign each state a value, or create territories. MapPoint is limited to a pre-defined set of palettes. Yes these are pastel shades - one of them does cover the spectrum, so this is best you'll find.
The only other option if you really must have four bright colors is to draw each shape and (again) set the colors manually. Eric Frost's "Single State Mapper" could be used for this (yes we resell it
but it is also available on this site here). This comes with the States set to white. You then manually set each one to a bright color.
Richard