0
votes
0answers
24 views

Tournament payouts, or more number partitioning/change-making

I was thinking of this when confronted with the problem of tournament payouts... Let's say I have \$100 to be parceled out to 10 different people, each of whom is due $n_1, n_2,..., n_{10}$ dollars. ...
4
votes
3answers
79 views

Number of ways of partitioning a number $n$ in unique ways.

Given any number $n$, what is the method of finding out how many possible ways (unique) are there in which you can partition it - with the condition that all the numbers in each 'part' must be greater ...
0
votes
1answer
65 views

General term of this sequence

I wanted to know the General term or the function to generate this sequence I found on OEIS. It is the number of ways to express $2n+1$ as $p+2q$; where $p$ and $q$ can be odd prime number and even ...
6
votes
1answer
71 views

Maximal Zero Sums Partition

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
1
vote
1answer
49 views

Balancing two sets while items in one are unmovable

I'm working on a following problem: Given two sets containing jars, each of which is assigned a random weight (weight is a real number), find a way to balance two sets by weight, i.e. the difference ...
4
votes
4answers
188 views

Algorithm to partition sum between buckets in all unique ways

The Problem I need an algorithm that does this: Find all the unique ways to partition a given sum across 'buckets' not caring about order I hope I was clear reasonably coherent in expressing ...
2
votes
1answer
1k views

Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ...
3
votes
2answers
377 views

Enumeration of partitions

The Stirling number of the second kind $S(n,k)$, where $S(n,k) = \frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k-j}\left(\begin{array}{l}k\\j\end{array}\right)j^n$ Gives the number of unique unlabeled, ...
10
votes
1answer
1k views

For what coinage systems does a greedy algorithm not work in providing change?

For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins. However, for a coinage system with 12 cent coins, a greedy ...
5
votes
2answers
332 views

How can I reduce a number?

I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
0
votes
2answers
787 views

Partition Problem, verifying solution in polynomial time

I add a look at the partition problem, this problem is know as the Easiest hard problem since it is NP-complete and seems pretty easy. From wikipedia on NP-complete: In computational complexity ...
8
votes
1answer
1k views

On problems of coins totaling to a given amount

I don't know the proper terms to type into Google, so please pardon me for asking here first. While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
2
votes
4answers
3k views

Algorithm for generating integer partitions

I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that ...