All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Tough Negotiations (Posted on 2007-02-27)
In a surprise move, N. Crocosia agreed to halt its nuclear program in return for 20 million iPods. According to the terms of the agreement, all iPods should come read-only, prerecorded with the same 10 tracks, 1 hour long each. The first half of each track is a speech by the country's leader followed by music in the second half without any pauses.

The Ministry of Songs provided 24 songs for the musical part, all with different durations in whole minutes. In addition, they requested that two of the leader's favorite songs, 10 and 12 min long, be together, as well as two others, respectively 4 and 13 min long.

Can these conditions be met?

 No Solution Yet Submitted by Art M No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer search | Comment 1 of 3

There are 300 minutes to fill, which is also the sum of the first 24 whole numbers, so all the first 24 whole numbers are used. The 10 and 12 can be treated together as a second 22, and the 4 and the 13 together as a second 17.  The following program tries all possibilities but finds none.

DECLARE SUB fill (n!)

CLEAR , , 9999

OPEN "tuffnego.txt" FOR OUTPUT AS #2

DIM SHARED avail(24)
DIM SHARED track(10, 10), tot(10)
FOR i = 1 TO 24
avail(i) = 1
NEXT
avail(4) = 0
avail(10) = 0
avail(12) = 0
avail(13) = 0
avail(22) = 2
avail(17) = 2

fill 1

CLOSE

SUB fill (n)
r = 30 - tot(n)
IF r > UBOUND(avail, 1) THEN l = UBOUND(avail, 1): ELSE l = r
FOR i = track(n, track(n, 0)) TO l
IF avail(i) THEN
avail(i) = avail(i) - 1
track(n, 0) = track(n, 0) + 1
tot(n) = tot(n) + i
track(n, track(n, 0)) = i

IF n = 1 AND i = r THEN
FOR j = 1 TO track(n, 0)
PRINT #2, track(n, j);
NEXT
PRINT #2,
END IF
IF i = r THEN
IF n = 10 THEN
FOR j = 1 TO 10
FOR k = 1 TO track(i, 0)
PRINT track(i, k);
NEXT
PRINT
NEXT
PRINT
ELSE
fill n + 1
END IF
ELSE
fill n
END IF

tot(n) = tot(n) - i
track(n, 0) = track(n, 0) - 1
avail(i) = avail(i) + 1
END IF
NEXT
END SUB

found no instances where all the 30-minute slots could be filled.

As a check on the program's thoroughness, the file produced shows all the possibilities gone through for the first track:

1  2  3  5  8  11
1  2  3  5  19
1  2  3  6  7  11
1  2  3  6  18
1  2  3  7  8  9
1  2  3  7  17
1  2  3  8  16
1  2  3  9  15
1  2  3  24
1  2  5  6  7  9
1  2  5  6  16
1  2  5  7  15
1  2  5  8  14
1  2  5  22
1  2  6  7  14
1  2  6  21
1  2  7  9  11
1  2  7  20
1  2  8  19
1  2  9  18
1  2  11  16
1  3  5  6  7  8
1  3  5  6  15
1  3  5  7  14
1  3  5  21
1  3  6  9  11
1  3  6  20
1  3  7  8  11
1  3  7  19
1  3  8  18
1  3  9  17
1  3  11  15
1  5  6  7  11
1  5  6  18
1  5  7  8  9
1  5  7  17
1  5  8  16
1  5  9  15
1  5  24
1  6  7  16
1  6  8  15
1  6  9  14
1  6  23
1  7  8  14
1  7  22
1  8  21
1  9  20
1  11  18
1  14  15
2  3  5  6  14
2  3  5  9  11
2  3  5  20
2  3  6  8  11
2  3  6  19
2  3  7  18
2  3  8  17
2  3  9  16
2  3  11  14
2  5  6  8  9
2  5  6  17
2  5  7  16
2  5  8  15
2  5  9  14
2  5  23
2  6  7  15
2  6  8  14
2  6  22
2  7  21
2  8  9  11
2  8  20
2  9  19
2  11  17
3  5  6  7  9
3  5  6  16
3  5  7  15
3  5  8  14
3  5  22
3  6  7  14
3  6  21
3  7  9  11
3  7  20
3  8  19
3  9  18
3  11  16
5  6  8  11
5  6  19
5  7  18
5  8  17
5  9  16
5  11  14
6  7  8  9
6  7  17
6  8  16
6  9  15
6  24
7  8  15
7  9  14
7  23
8  22
9  21
11  19
14  16

The recursion to n+1 similarly goes through all the possibilities for the remaining tracks, using the remaining song lengths for each possibility of track 1.

I realize I could have stopped the program when the first track passed having used the 1-minute song, as it could have been assumed that the first track would have the 1-minute song without loss of generality.

 Posted by Charlie on 2007-02-27 10:52:17

 Search: Search body:
Forums (0)