The oldest known musical instruments are a set of bone and ivory flutes from around 42,000 years ago. Paleolithic tribesmen undoubtedly played these instruments gathered around the campfire, as an addition to storytelling or religious ceremonies.

What I wonder about is, how did they play multiple musical instruments together. Multi-piece music can generally be divided into two types, homophony, where there is one primary part backed by secondary parts that play chords or octaves to harmonize, and polyphony, which is multiple parts that do not necessarily support each other, playing different tunes, but that hopefully sound nicely together.

Does the ability to harmonize come naturally to humans? Or would the first musicians play polyphonous music until someone 'invented' the concept of chords? When the first flautists gathered around a mammoth roast, did they immediately learn to harmonize with each other, or did they play their own tunes?

We can't go back in time but, as a musician I think I can answer.

It doesn't have to be invented because it occurs naturally.

When people chant together in a large group, they have different pitched voices. It's natural for women and children to sing at least an octave above the men.

However there are intermediate voices. They may not sing an octave but a fifth (which is also a fourth seen from the other direction).

Because of the construction of our ears, certain notes go well together. Firstly unison, then octaves, then fifths and so on.

As well as the sound-detecting hairs in our ears, there is a theory that pleasant sounds have a neurological basis. I remain to be convinced but time will tell.

The key to pleasant music may be that it pleases our neurons. A new model suggests that harmonious musical intervals trigger a rhythmically consistent firing pattern in certain auditory neurons, and that sweet sounds carry more information than harsh ones. https://www.newscientist.com/article/dn20930-why-harmony-pleases-the-brain/

Therefore anyone who is not tone deaf (another subject that can be discussed) will naturally tend to slide their own pitch towards one of these 'pleasant' intervals. You can clearly hear that adjustment in progress here https://youtu.be/V37k31746IM?t=102 The woman in question clearly has no idea of harmony or fine control of the pitch of her voice. She simply slides her voice around until it sounds good. She is 'inventing' harmony in that sense but has only a limited choice of what is pleasant.

Polyphony is an offshoot of call and response singing - specifically work-songs. If the call and the response overlap then you have elementary polyphony.

Another effect is to put a melody over the top of a drone. https://youtu.be/lN1NbYUE8Ck

Polyphony can develop from this by a lead singer singing over the top of a simple melody. https://youtu.be/veiJLhXdwn8?t=136

In traditional African singing it is common for someone to sing or shout a phrase when inspired to do so.

Once the classical era came along then the story gets more complicated. I could expand on this.

Finally, when you talk about pipes. There was no widespread standardising of pitch between musical instruments until the classical period. Original pipes were simple whistles with one or two holes added. They were mainly solo instruments often played by solitary shepherds. Singers would fit in with the pipe. In fact that still happens in modern-day orchestras where everyone tunes to an A provided by the oboe (a wind instrument that is difficult to adjust the tuning of).

EDIT with regard to the very useful answer by flox.

I agree with flox's exposition. However it doesn't say why naturally produced sounds are pleasant. I'll argue that it is the receiver that is important. For example two sufficiently out-of-tune instruments sound horrible because of the beat frequency. But beat frequency is a natural phenomenon as well. So the answer by flox doesn't explain why listening to a beat frequency is generally considered unpleasant. (Note: I'm aware of lots of acoustic theory about organ pipes using beats to produce notes that sound lower than what is being played). However none of that deals with the human aesthetic. I think I need to address in my answer the human anatomy that might explain that (I've already talked about the neurological factor).

As a start I'll talk about information processing. Humans are bombarded constantly with a barrage of sounds that they have to unravel in order to make sense of. This is equivalent to doing a Fourier analysis on the fly. We can distinguish individual pitches and even the direction they are coming from. If notes are in harmony (exactly as flox indicates) then they stimulate the sensitive ear transducers with a similar resonance. Thus to a human a note and an octave above it sound almost the same. This is because the tiny hair cells in the cochlea vibrate with the same laws that flox mentions. The result of this is less information processing. White noise is a mix of all frequencies and at that point our nervous systems give up trying to separate sounds and simply lump the frequencies together. In a crowded room the information processing is at its worst because of all the cross-talk and mixtures of timbre and pitch. Harmony takes most of the strain out of this situation and gives our nervous system a rest.

So, I argue, perceived harmony is a product of the receiving apparatus. If evolution had come up with a different mechanism we might never be able to hear harmony at all even if the mathematics 'out there' was as flox correctly asserts.

Harmony is natural in most instruments, and is actually universal mathematical phenomenon

I play the violin in an orchestra and you notice a few things about the strong link between mathematics and music.

If you play an 'open' string on a string instrument (ie, a tensioned string between two points, no fingering, on a violin or cello), you get a set frequency. Divide the string in half, and the frequency lifts up an octave. Divide that half into half, it goes up another octave, and so on.

Get an adjustable tube with a reed or mouthpiece (a common modern instrument is a trombone). Extend the tube by twice the length, and the sound drops an octave.

Get a glass and fill with water and a spoon. Hit it with the spoon and you get a note. Pour out half the water and hit it again, you get an octave higher. This is the same principle as a xylophone.

Same for harps, tubular bells, marimbas and many other instruments. It is universal and cross cultural. Octaves are the primal harmony, cultural factors affect how that octave is divided further, and different cultures divide in different ways (Korean music divides in 5, European in 8, and others differently) but essentially it all starts with that initial harmony.

The individual notes established, the only remaining factor in playing in a group is to match their base notes. This is called tuning.

In an orchestral setting, all instruments tune to a common instrument (usually the oboe) to 'set' their base note to a common frequency. If you do not do this, you immediately sense 'disharmony' or 'out of tune'. This is not just an emotion, it is a mathematical mismatch, which you can hear a 'wobble' as the two frequencies fight each other. Tuning a violin you must do so using only your ear, you find the right note when it no longer 'wobbles', and the frequency matches with the oboe and others.

What's more is you can easily know who is 'out of tune', their notes stick out like a sore thumb, and you don't need to be musically educated to sense this. Your group of flute players around your mammoth roast must adjust the length of their instrument to match each other prior to playing, otherwise it would be a mad jumble of incoherent frequencies, as can happen in modern orchestras today.

As far as "sounding nice together" goes, the simplest way to achieve this is the pentatonic scale. Of course "pentatonic" simply means "five notes", but a characteristic of the "major pentatonic" and "minor pentatonic" is that playing in those scales will automatically sound harmonious.

These scales also appear across a range of societies independently. This causes inevitable questions about whether this indicates something fundamental about our brains and pattern recognition.

Probably the most famous modern example of this is Bobby MacFerrin's World Science Festival presentation where he makes the audience sing a major pentatonic scale. A particularly remarkable element of this is that having introduced three notes in one direction, he "forces" the audience to predict the adjacent note in the opposite direction without giving them any other information and they do. The octave pattern can be predicted when the relative pitches are known, of course, but at no point does he tell the audience what scale he's using. He simply "jumps" them to the next note, and without thinking they pick it.

Yes, harmony must be invented

From the abstract of MacLachlan, et al., 2013,

The cognitive incongruence theory of dissonance was rigorously tested
in Experiment 2, in which nonmusicians were trained to match the
pitches of a random selection of 2-pitch chords. After 10 training
sessions, they rated the chords they had learned to pitch match as
less dissonant than the unlearned chords, irrespective of their
tuning, providing strong support for a cognitive mechanism of
dissonance.

The 'cognitive mechanism of dissonance' was proposed by Martha Guernsey in a 1928 paper (can't find a full text online?) where she

found strong effects of music training on consonance. This discovery
led her to suggest that consonance was associated with familiarity for
commonly used music chords.

The conclusion of the MacLachlan paper is that

learning to perceive consonance involves cognitive processes.

Therefore, you cannot know harmony without learning harmony, much as you cannot know multiplication without learning multiplication. So while both harmony and multiplication are facts of the physical universe, human perception of these concepts would necessarily follow the 'invention' of harmony, just as someone 'invented' multiplication.

Whilst I don't really like the question as it stands as the specifics of polyphony, monophony, what constitutes a harmony etc are debatable....

Aural harmonising is only learned in the same sense as watching one's parents and seeing how they move and mimicking that is learning.

Perhaps early an answer should address the references to 'musical appreciation is learned/cultural' and how it's not relevant to the question. /edits

The McLachlan paper does not claim that harmony is 'learnt,' in the useful sense of the word, but that the harmonies appreciated by different groups are different and can change. What my eyes are able to see has changed, it doesn't mean that using them in the basic sense is a learnt(or unlearnt) skill.

Accent is inherited, not in the sense that the physical matter that makes up the oral apparatus is different form region to region, but in the sense that one learns to speak from those who make the noises one mimics.

We all have had experiences of not understanding, or not liking, or liking differing accents that formally might be constructing the same word-forms and this is largely for the same reasons that people and cultures identify and favor 'valid' chords/notes/etc in music.

https://www.ideals.illinois.edu/bitstream/handle/2142/47304/081_ready.pdf?sequence=2
https://www.ncbi.nlm.nih.gov/pubmed/29077726

http://rspb.royalsocietypublishing.org/content/280/1754/20122798
https://en.wikipedia.org/wiki/Bird_vocalization#Learning
https://academic.oup.com/beheco/article/20/5/1089/211561

https://www.salford.ac.uk/research/sirc/research-groups/acoustics/psychoacoustics/sound-quality-making-products-sound-better/accordion/sound-quality-testing/roughness-fluctuation-strength

The desire to attain 'Harmony' is natural, though what constitutes a harmony is learned, as is the ability to attain it. For this reason multi-source music is of limited complexity until proficiency allows expansion, this is true of all musical cultures. Synchronised clapping or stamping or banging to a stable tempo is one thing, contemporary chord structure is quite another.

What would be demonstrative is a scientific paper that tested not different forms of music levels of memorization, responsiveness & appreciation by cultures other than where the music originated, but 'random varied' noise appreciation by culture.

Music being socially produced noise, it stands to reason also that cooperative production is not out of the question from the outset, if you put two children in a room and one starts banging a drum, the other is like as not to start banging something too.