Вы можете использовать NSMutableArray -removeObjectsAtIndexes: для удаления всех объектов по определенным индексам одновременно:
NSMutableArray *array = ...;
NSMutableIndexSet *indexes = [[[NSMutableIndexSet alloc] init] autorelease];
// Some loop to populate 'indexes' with the indices of the odd/even items
[array removeObjectsAtIndexes:indexes];