When a balloon pops and lets a brick fall, where does the energy come from? Let's say a scientist attaches a 1 kg brick to a large helium inflated balloon, lets the balloon go, and then it reaches an altitude of 10 000 meters before it pops, dropping the brick.
The brick falls and hits the ground with with a kinetic energy of approximately 100 000 joules.  (Actually a bit less, it gives some of that energy as air resistance, but it still stored that much energy.)
For reference, a rifle shot is about 2 000 joules.
But where did this energy come from?  The scientist just inflated a balloon and tied a string.
 A: Your estimate that the brick would lose "a bit" of its energy to air resistance is incorrect. It would lose most of its energy. The terminal velocity of a brick (http://physicsbuzz.physicscentral.com/2018/01/ask-physicist-which-falls-faster-brick.html) is reported to be around 95 m/s. This will be its speed when it hits the ground, so the energy it will deposit into the ground will be 4,500 J, not 100,000 J. Assuming your math is correct, over 95 percent of its energy is lost to air resistance.
When the balloon rises, what's making it rise is the atmosphere pushing up on it. The gain in potential energy of the brick is equal to the loss in energy of the atmosphere; as the balloon rises, the atmosphere, filling in the space below it, becomes, on average, very, very, slightly lower to the ground. So the energy comes from the gravitational potential energy of the atmosphere*.
*In principle, the thermal energy of the atmosphere also has to be taken into account, since temperature decreases quickly with altitude in the troposphere. This means that the original gain in gravitational potential energy of the atmosphere also slightly decreased its thermal energy, while the loss of gravitational potential energy of the atmosphere is countered somewhat by a gain in thermal energy. These energy transfers are likely small compared to the changes in gravitational potential energy, though (and even if they weren't, the ability to do work using the temperature gradient is hampered by thermodynamic considerations).
A: Energy will be lost due to air resistance during the fall. As pointed out in the comments it is a very small effect, but the energy is also lower because $g$ is 9.81 ms$^{-2}$ at the surface - it will be slightly lower higher up ... 0.3% lower at 10 km altitude as pointed out by @probably_someone.
As the balloon is filled it does work on the surrounding air of $P\Delta V$ where $P$ is atmospheric pressure where the balloon is filled and $\Delta V$ is the volume of the balloon.
As the balloon rises in effect air from above the balloon fills the space left behind by the balloon. Thus air drops in height and loses energy and gives it to the balloon. -- But ultimately the air was 'pushed up higher' by filling the balloon with gas... so ultimately the brick gained potential energy (and then kinetic energy) from the work done inflating the balloon. 
A: tl; dr The energy comes from the conversion of buoyant potential energy to gravitational potential energy. That energy came from filling the balloon with enough helium to lift it and the brick off the ground.
Imagine you haven't filled up your balloon yet--you have a deflated balloon tied to a brick and sitting on the ground. Let's call the balloon brick system the airship.
The airship is at equilibrium sitting on the ground. It has no potential or kinetic energy. But then you hook up your balloon to your canister of helium and start to fill it up. As the balloon starts to fill, the volume of atmosphere displaced by the helium increases, until the weight of that displaced air becomes greater than the weight of the balloon filled with helium (this only works to lift the balloon because helium is less dense than the surrounding air). That buoyancy provides an upward force on the balloon and the airship. At this point the balloon is floating above the brick, but still lacks the force to lift the airship off the ground. The brick itself is still at equilibrium.
You keep filling up the balloon with helium, and eventually the force of buoyancy from the larger balloon provides enough upward force on the airship to overcome the force of gravity on the airship--so you stop pumping helium into the balloon by disconnecting your canister. The airship is now out of equilibrium by being on the ground and begins to rise to achieve a lower energy state.
Gravity doesn't change as your airship rises (it technically increases a little bit from the extra atmosphere beneath you, but we can ignore that). If your balloon was strong enough, you'd eventually get to a point high enough up in the atmosphere such that buoyant force exerted on the balloon decreases to the point that the airship is in equilibrium again--the buoyant force balances the gravitational force on the airship. Your airship now has a lot of gravitational potential energy! But where did it come from? It actually comes from the buoyant force which was constantly acting on the airship during the ascent. Your airship, once it was filled up enough to start rising off the ground, gained buoyant potential energy. So as your airship ascended, it was converting that buoyant potential energy to gravitational potential energy. The catch is that during the ascent, there was actually another force acting on the airship as well--the force from air resistance. So you actually lose potential energy overall by having your airship float into the sky! But that's a good thing--because if it didn't lose potential energy by ascending, it wouldn't ascend in the first place.
You might ask, where did the buoyant potential energy come from though? It came from filling the balloon with enough helium to overcome the force of gravity on the airship.
Here's a nice succinct reference I found that goes over the problem with equations: https://aapt.scitation.org/doi/pdf/10.1119/1.1466552
A: The kinetic energy comes from gravitational potential energy
The gravitational potential energy comes from the buoyant energy (force * elevation) lifting the balloon and brick into the air
The buoyant energy comes from the helium. So why should helium have buoyant energy?
Imagine taking a balloon full of normal air, and trying to push it underwater. That takes energy. Rather than gravitational potential energy, it is..... buoyant potential energy. The deeper you push the balloon of air into the water, the more potential energy you give the balloon of air. 
The same goes for helium, except with the atmosphere. Helium has high potential energy near the ground, and expended potential energy high in the atmosphere.
The energy in the brick comes from the energy expended to collect helium and bring it to the ground. For example, some sources of helium that cost energy:


*

*Fusing hydrogen

*Mining out of the ground


*

*the geological processes that embedded hydrogen in the ground rather than the atmosphere in the first place


*Filtering/collecting out of the atmosphere

*and then the energy to pressurize and purify it into a compressed source of helium, which is used to fill the balloon


That is where the energy comes from!

Small tangent/elaboration: 


*

*As mentioned in the comments, "Buoyant potential energy" (BPE) can be seen as another manifestation of gravitational potential energy (GPE). If I were to elaborate this in as simple terms as possible, it would be the following: By pushing an air balloon into the sea (or helium down to the ground), the buoyant potential energy of the balloon (or helium) is = the gravitational potential energy of the water (or atmosphere) displaced. When you push a balloon of air into the ocean, you are one in the same displacing ocean water at a lower elevations to higher elevations. So if you reach the bottom of the ocean with your balloon of air, then there is a column of water above the balloon which you lifted against gravity (since the balloon displaces the water). The distance you lifted the column of water is the average height of the balloon. So the balloon's BPE = the displaced water's GPE. Then in the atmosphere, the helium's BPE = the atmosphere's GPE. It would be inaccurate to say the balloon itself has GPE, but it is indeed accurate to note GPE is involved. It is just the atmosphere, not the balloon that has GPE (if we are being very precise and technical when we speak about this).

A: To answer your question we need to ask "Where did the energy come from to make the balloon/rock system (B/R) rise?" Some force did work on B/R, transferring energy to it.
In an near-inertial system (zero local gravitational field) such as the International Space Station (ISS) one could inflate balloons all day with different gases and the balloons would not "rise"; they would simply stay where they are placed (ignoring miniscule accelerations present because it's not perfectly inertial). Next consider what would happen if the ISS left its orbit such that there was a local field toward Earth. Some balloons would fall toward Earth and some would rise away. Why?
One of the characteristics of a gas is pressure. If we create an isolated system like B/R, the pressure on one hemisphere of the system results in a net  force toward the bisector plane that defines the hemisphere, and the pressure on the opposite hemisphere results in a net opposite force.  If there is not acceleration field (gravity) the pressure is the same everywhere and the net force on B/R is zero. The pressure is there whether there is gravity or not, so inflating a balloon does require some work, but still the balloon doesn't rise (or fall). Pressure results from collisions of molecules and transfers of momentum and kinetic energy.
The presence of an acceleration field will produce a pressure differential in in the atmosphere along the line of the acceleration. So, gravity causes the pressure of the atmosphere closer to Earth to be greater than higher up. This means that the downward (same direction as gravity) force due to atmospheric pressure on the top hemisphere will be smaller in magnitude than the upward force from the atmospheric pressure on the bottom hemisphere. The result is that from the atmosphere in a gravitational field there is a net upward force.  But that's not all.  Gravity is also acting on the mass of B/R. In order for B/R to rise, the net upward atmospheric force must be greater than than the weight. (This is all summed up in Archimede's Principle, but that hides the gravitational field fundamentals.)
Finally, the buoyant force of the atmosphere is doing work on B/R, and that's coming from the gravitational field (space-time curvature due to Earth's mass??) and the gravitational field is directly doing work on the mass of B/R. So the energy gained by B/R ultimately comes from the gravitational field.
A: At the start of the experiment, you have a balloon+brick at ground level, and a balloon+brick sized pocket of air at 10,000m. When the balloon has reached altitude, now you have a balloon+brick sized pocket of air at ground level, and the balloon+brick at 10,000m - they've simply swapped places.
Because the balloon+brick floats, we know that the balloon+brick weighs less than the equivalently-sized pocket of air. They have both moved the same vertical distance. Therefore, the descending air has lost slightly more PE than the balloon+brick has gained.
The energy stored in the brick came from the PE that was already stored in the atmosphere.
A: This is my second answer. It is an attempt to clarify some points in my first, obviously not very popular, answer and to add a couple of additional points that are still appear to be missing in many good answers from other people.
So, again, where did the energy lifting the brick come from?
Most people, including myself, agree that the source of the increasing potential energy of the rising brick is the decreasing potential energy of a column of air coming down.
Some use the term "buoyant potential energy", but that it is just another, less direct, way to express the same idea: the fact that the column of air "wants" to go down can be interpreted as a balloon "wanting" to go up.
OK, so, where did the potential energy of the column of air come from? 
Here the opinions differ. 
Some people suggest that it comes from the act of inflating a balloon. Others say that it is somehow a property of helium. Others - that it is due to the gravitational field. Some don't say anything. 
In my unpopular answer, I said that this potential energy is "built into the atmosphere and therefore has the same sources as the potential energy of the atmosphere, which is, mostly, gravity and sun". This answer was mostly downvoted and the arguments around it continues to this day. So, I'd like to clarify what I mean by "potential energy built into the atmosphere" and why I think it is a correct answer.
If we choose the sea level as a reference (zero potential level), we'll need to lift air molecules up to give the atmosphere any positive potential energy. This is achieved by heating the air. If, today, we increased the temperature of the atmosphere, it would expand and its potential energy would increase. If we cooled the atmosphere, it would contract and its potential energy would decrease. If the temperature somehow became zero, the atmosphere would collapse and its potential energy (relative to the sea level - our reference point) would become zero.
So it takes both gravity and heat, not just gravity, to build up the potential energy of the atmosphere.
The expression "potential energy built into the atmosphere" just reflects the fact that air molecules, suspended at various heights above the ground (due to their kinetic energies or temperature) and making up the atmosphere, have some combined potential energy - the potential energy of the atmosphere.
Can we say that the energy came from the inflation of a balloon? 
Sure, we can say that by inflating a balloon, we displace (lift) a certain amount of air and, by doing it, we increase the potential energy of the atmosphere, but, it does not mean that this particular energy will be used or will be needed for the column of air to go down or the balloon to go up. 
If, while inflating the balloon, we sucked in and compressed (or otherwise remove) ten times as much air as goes into the balloon, the column of air would still go down and the balloon would still go up.
So, if the potential energy that is used to lift the balloon is already built into the atmosphere, what is so special about helium that makes the balloon rise? Why would not air in the balloon would do the same?
Here comes a trickier part of the answer: in order to make a column of air go down, we just need to create some room for it, which would open a path for reducing its potential energy - otherwise, its potential energy would not decrease, transfer or otherwise be realized. 
As an example, instead of inflating a balloon, we could compress some air and that would allow a column of air to go down.
As another example, we could untie a piece of wood stuck at the bottom of an ocean and thus release some potential energy stored in the water column above it.
A balloon filled with air just does not create that room, since replacing it would not reduce the potential energy of the air column above it.
So, the problem with the balloon is not only about the source of energy, but also about a method of releasing or transferring the existing potential energy. 
The amount of energy spent in the process may be about equal (energy for inflating a helium balloon), greater (energy for compressing air) or smaller (energy for untying a piece of wood at the bottom of an ocean) than the potential energy being released. 
In other words, the explicitly spent energy in the process of making room for the column of fluid to go down and release/transfer its potential energy, is incidental - not essential - part of the energy release/transfer.   
A: I disagree that the energy "comes from" inflating the balloon.
Helium that's below the atmosphere "contains" potential energy due to buoyancy, in the same way that a rock at the top of a hill "contains" potential energy due to gravity.  Thus the potential energy is already there; by attaching the brick to the balloon, you're translating the helium's potential bouyant energy into the brick's potential gravitational energy.
If the brick were not there, that energy would be translated into the helium's kinetic energy, which would rise much faster without the brick.  That's true with or without a balloon.

The next logical question is, where did that buoyant potential energy come from?  The answer is, whatever energy was used to bring the helium below the atmosphere to begin with.
In the real-world, this would be the chemical energy from whatever reaction separated the helium (or, one could argue, the latent buoyant energy in the reactants), but it's the same logic as if we pulled a giant bag full of helium down from outer-space.  The amount of energy used to pull the bag down through the atmosphere is the same as the amount that can be gained from the helium rising back up (minus losses due to air resistance).
A: The energy comes from filling the balloon.
Imagine the following scenario which is equivalent to yours but more intuitive:
1-Imagine a mass dropped in the ocean and attachement to a generator. When it is dropping, the generator produces energy.
2-Now imagine the mass was equipped with an underwater lifting bag (https://en.wikipedia.org/wiki/Lifting_bag) with a tube attached to it to feed it air from the surface.
3-An air pump is activated to fill the underwater lifting bag. The mass rises up out of the water. In the process, it made the generator produce energy again.
Now it's easy to see that either this is a free energy device (which it is not) or either the energy comes from filling the underwater lifting bag (the balloon in your exemple).
A: The energy initially comes from a collapsing star that produces heavy radioactive elements like Thorium and Uranium. When the Earth was formed these radioactive elements were present in the crust. Over time when these elements decayed they produced Helium via alpha decay that collected in natural gas reserves, which is where most of today's Helium comes from.
A: With the assumption that the balloon and payload rose from ground level to 10,000 m, and that the volume displaced by the balloon and payload is entirely from n moles of helium, then the PE gained by the balloon and payload is equal to the PE lost by n moles of air moving from 10,000 m to ground level. (Ignore KE)
Since air is denser than helium, it loses PE faster while falling than the helium gains it while rising. 
The molar mass differential is what allows helium to lift loads. As long as you clear the threshold amount of helium, and have a strong enough balloon, it is only a matter of time before a brick can reach a height worth 100kJ. Just add more helium to arrive there sooner.
For every mole of helium (4g) rising, a mole of air (~29g) falls to take it's place, which is a differential of 25g/mol*. In other words a mole of helium can lift approximately 25g of payload in Earth's atmosphere. In practice, add more helium to get the lift going at a reasonable pace, and maximum height is limited by strength of the balloon trying to contain the helium that keeps expanding as it rises. 
*(This is equivalent to 1g/L at sea level, but seeing as how gas volumes are sensitive to differing pressures, I try to avoid this unit of measurement for the scope of this question specifically, which involve changing heights) 
A: Yes, all the energy comes from the energy needed to inflate the balloon.
This is a bit more intuitive if you imagine how little the typical balloon can carry (less than one gram), and how violently the tanks of compressed air you use to fill balloons can explode. 
Here's the quantitative calculation. It takes approximately an energy 
$$E = P_{\text{atm}} V$$
to fill up a balloon of volume $V$. This is the work you need to do to "push the atmosphere away" when creating the balloon. An energy cost of $PV$ to create a volume $V$ is very commonly used in physics; it appears in both the enthalpy and Gibbs free energy.
This energy goes into the gravitational potential energy (GPE) of the entire atmosphere, as the air you pushed away when blowing up the balloon pushes away other air, and so on, ultimately raising air away from Earth. As the balloon rises through this atmosphere, the GPE of the air converts into GPE of the balloon and brick, because the balloon's rising allows air to fall. 
If you want, you can call this GPE of the air the "buoyant potential energy" of the balloon. It's just the same thing; the whole meaning of potential energy is "some other kind of energy we are black boxing". We already black boxed the gravitational field energy of the air and Earth as GPE of the air, and you can choose to black box that again as "BPE" of the balloon. So all the answers here are really saying the same thing.
Anyway, to be quantitative about it, the work done on the brick by the air is
$$W = \int F \, dx = \int \rho g V \, dx = V \int \rho g \, dx = V \Delta P$$
where $\Delta P$ is the drop in the atmospheric pressure between the bottom and the top. That is to say, if the balloon rises very far, up to where the pressure is negligible, all of the GPE of the atmosphere has been transferred to the balloon. Now if the brick falls, it is converted to kinetic energy.
This energy originally came from the energy needed to fill the balloon. You might say it takes no energy to open the tap on a compressed air tank. Sure, but then the energy came from whatever put the air in the tank in the first place.
A: Updated.
I think we can say that the energy comes from two sources.
First, since helium used in the balloons is produced, by radioactive processes, underground, it already possesses potential energy that would later propel the balloons upwards.
So, where does this potential energy come from? 
Originally, I stated that it came from uranium, but after some good discussions in the comments and some thinking, I realized it was not the case. The atmosphere, as well as oceans or other bodies of water, have potential energy built in them, which could perform work on (lift) any object lighter than air or water, respectively. 
So, although helium molecules are created as a result of radioactive decay, their buoyant potential energy is due to the potential energy built into the atmosphere and therefore has the same sources as the potential energy of the atmosphere, which is, mostly, gravity and sun. 
So, we can say that the buoyant potential energy of protons and neutrons inside uranium atoms is about the same as the buoyant potential energy of alpha particles and helium molecules they eventually become, but they can rise only when they get freed up from heavy uranium atoms.   
*Adding in response to the first comment:
When helium is created underground, it is not compressed and, since it is lighter than air, it would rise, if it was not trapped. 
If helium was produced at the top of a mountain, someone would have to perform work against the force of buoyancy to bring it down to the ground level and, thus, build up its potential energy, which, eventually could be used to lift the balloon.* 
Second (skipping all intermediate steps), some significant energy must be spent in the process of compressing helium into a tank, where this energy is stored until it is used to inflate the balloon. 
A: A simple and intuitive answer might be what is required.  Allow me to make some restrictions  and conditions for the following scenario:
1 There is no helium, except at 10,000 m, with a pressure of 0 psi.
2 The energy required for a spaceship to "get' the helium is not counted.
3 The volume of helium required to lift 1 kg to 10,000 m is V (@ 14 psi).
4 The energy required to compress volume V to 14 psi = 100,000 J.  
The spaceship rises to 10,000 m and compresses helium (@ 0 psi) to fill a volume V (@ 14 psi), and takes it back to earth's surface.  There, a balloon of volume V is filled with the helium (at 14 psi).  
Because of the difference in pressure (14 vs 0 psi), the helium "wants to go back" to 0 psi ( to 10,000 m).  
This scenario makes it clear, that the energy used by the helium balloon, comes from the energy spent in compressing a volume V of helium, from 0 psi to 14 psi (or an equivalent process)!    
A: gravitational potential energy is negative and goes to zero once you move away to infinity from earth. So the energy of the brick comes from potential energy gain (more negative close to earth, less negative away from earth. 
