Author |
Topic: Minimum Set S (Read 385 times) |
|
R
Senior Riddler
Addicted!!!
Gender: 
Posts: 502
|
 |
Minimum Set S
« on: Sep 26th, 2009, 12:28am » |
 Quote  Modify
|
Make a set of positive integers S, such that using at most 2 integers at a time from S, you can make all possible number in the range [1,n].
Part 1. Minimize |S|, i.e. the number of integers in set S.
Part 2. Minimize the total sum of integers in S.
An extension to the weekly puzzle of PuzzleUp.
|
|
 IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Minimum Set S
« Reply #1 on: Sep 26th, 2009, 12:35am » |
Quote Modify
|
Just give me a hint, not the complete solution/answer.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
sidharth
Newbie
Posts: 4
|
|
Re: Minimum Set S
« Reply #2 on: Sep 27th, 2009, 8:23am » |
Quote Modify
|
Giving an iterative approach to the solution. Believe a better solution does exist
let n=20
Step 1: create the initial list using the following:
for each X ( 1 <= X <= n), X = largest element of set + y.
If y does not belong to S, add y.
After step 1, S = {1,2,3,4,5,6,7,8,12}
Step 2:
Now beginning with the 2nd largest element (X) till end of set, check whether the larger elements can be replaced using a combination of the other elements or addition of new elements where sum of new elements < sum of to be replaced elements.
After step 2: 8, 12 are replaced by 13.
S = {1,2,3,4,5,6,7,13}
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Minimum Set S
« Reply #3 on: Sep 28th, 2009, 12:36am » |
Quote Modify
|
I solved that with a program.
There are patterns that work quite well, such as:
{1, 2, 3, ..., k-2, k-1, 2k-1, 3k-1, ...}
but you still need to find the best k and the solution isn't always optimal.
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Minimum Set S
« Reply #4 on: Sep 28th, 2009, 3:43am » |
Quote Modify
|
Looking for patterns is hard. Harder is seeing varying patterns. 
Doesn't any of greedy strategy, dynamic programming or anything help here?
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print