+ The Oktave Forum » Technical » Science and Mathematics » Discrete Mathematics (Moderator: sanket)
|-+ Divide equally
Username:
Password:

Pages: [1]
Topic Tools  
Read January 09, 2009, 02:12:17 am #0
shibashis

Divide equally

Here is an interesting problem I came across from one of my colleagues a few days back.

A string of beads has 2B black beads and 2W white beads (each in even number). You are allowed to cut the string into pieces with a pair of scissors multiple times. Given any arrangement of the beads in the string, what is the minimum number times you need to cut it so that the black and white beads can be divided equally between 2 persons, i.e. each person gets B black beads and W white beads?

To clarify further, for a certain arrangement like alternate black and white beads, cutting the string only once in the middle is sufficient. But for 'worse' arrangements, we may need to cut it more than once. We are interested in the minimum number of times we need to cut the string for the 'worst' arrangement.
Offline  
Pages: [1]
Jump to: