Problem 713

[Junglemath]

https://projecteuler.net/problem=713

Are the N fuses split up between the house and the shed?

Must he choose all the working fuses in order for the heat to work? So in the second example, if he has 8 fuses and 4 of them are working, are we looking for the smallest number of combinations of fuses so that he is guaranteed to have turned on the 4 working fuses?

[mdean]

I believe the N fuses are replacements. The only circuit has 2 fuses in series. Choose 2 replacements and, if both fuses are good, there's a closed circuit and everything works. Otherwise, there's no power. He keeps trying a different pair until he finds a pair that works.

[Junglemath]

I believe the N fuses are replacements. The only circuit has 2 fuses in series. Choose 2 replacements and, if both fuses are good, there's a closed circuit and everything works. Otherwise, there's no power. He keeps trying a different pair until he finds a pair that works.

I don't follow.

[mdean]

From https://en.wikipedia.org/wiki/Series_an ... l_circuits

In a series circuit, every device must function for the circuit to be complete. If one bulb burns out in a series circuit, the entire circuit is broken.

From this problem:

The electrical system uses two fuses in series,... For the heating system to work both fuses must work.

For the easiest given example, there are 3 fuses and 2 work. Start by inserting fuses 1 and 2 into the circuit. If this fails, either fuse 1 or fuse 2 was blown and a new pair has to be tested. If T(3,2)=3 as written in the problem, he can find a pair that works in at most 3 tries.

[Junglemath]

From https://en.wikipedia.org/wiki/Series_an ... l_circuits

In a series circuit, every device must function for the circuit to be complete. If one bulb burns out in a series circuit, the entire circuit is broken.

From this problem:

The electrical system uses two fuses in series,... For the heating system to work both fuses must work.

For the easiest given example, there are 3 fuses and 2 work. Start by inserting fuses 1 and 2 into the circuit. If this fails, either fuse 1 or fuse 2 was blown and a new pair has to be tested. If T(3,2)=3 as written in the problem, he can find a pair that works in at most 3 tries.

Right. I guess I don't see the significance of the fuses being split between the house and the shed. I'm imagining a total of N light switches, of which some number <= N work, and he needs to flip all of the working switches for the heat to work.

Is this accurate?

[LilStalker]

Im going to give you an analogy to the problem so that things might be clearer for you. If moderators find this post inappropriate, feel free to remove it.

Suppose you have N batteries, m of them are working and N-m are not working. Now you have an electronic device into which you have to insert 2 batteries. If both of the inserted batteries are working, the device will work too.
You start putting 2 batteries at a time into electronic device by using some strategy. What is the minimal number of tries that will guarantee that the device is working?

[Junglemath]

Im going to give you an analogy to the problem so that things might be clearer for you. If moderators find this post inappropriate, feel free to remove it.

Suppose you have N batteries, m of them are working and N-m are not working. Now you have an electronic device into which you have to insert 2 batteries. If both of the inserted batteries are working, the device will work too.
You start putting 2 batteries at a time into electronic device by using some strategy. What is the minimal number of tries that will guarantee that the device is working?

Expand

removed by moderator

[LilStalker]

I think you are thinking under wrong assumptions here. You know nothing about the fuses/batteries initially. For example you pick fuse number 1 and you test it together in pair with every other fuse and in none of the cases the heating system works. That means, that the fuse number 1 is definitely bad. Of course you can do better but this is just an example. You have a set of fuses and you have no clue about them. You only know how many of them work. Now you need to find out which (or just which 2 work).

[hk]

@Junglemath:
If you think you have formulated a solution you can test it out on the given examples. Don't post one in the hope it will be correct.
PS i've removed your (wrong) assumption.

For the time being I think there has been enough here.
Please stop it now.

[Junglemath]

@Junglemath:
If you think you have formulated a solution you can test it out on the given examples. Don't post one in the hope it will be correct.
PS i've removed your (wrong) assumption.

For the time being I think there has been enough here.
Please stop it now.

I find it ironic that you are accusing me of posting spoilers/fishing for answers when I have been the one to report posts in the past that had any chance of containing a spoiler. I simply replied to a question posted by LilStalker, and just to be safe, I used spoiler tags.

Anyway, the whole point of this part of the site is to clarify problems whose formulation is cryptic. Based on my questions you can see that I do not understand what is being asked in this problem, so I cannot really "test" anything. My goal is to understand the question, not to look for the answer.

Thanks

[hk]

The problem was that you posted something you thought was a solution.
Several people tried to answer your questions.
In my opinion you have been served enough.

Actually Lilstalker didn't ask you a question.
Lilstalker translated the question of the problem to the translation if it he gave you.
That you are not able to understand that he didn't ask you a question is not my failure.

Anyhow I don't care to be the bitten dog here.
I've a hide like a rhino's

[Junglemath]

Actually Lilstalker didn't ask you a question.
Lilstalker translated the question of the problem to the translation if it he gave you.
That you are not able to understand that he didn't ask you a question is not my failure.

What is the minimal number of tries that will guarantee that the device is working?

Is that not a question?

[hk]

Yes, but not a question you should try to answer here.
Selecting a single sentence from a longer post is not the way to go.
Please let your grey cells do a little bit of working instead of trolling here.

[bjmgeek]

I wanted to make sure my assumption is correct: Each of the (working) fuses must have a current rating higher than the current used by the heater. Is that a valid assumption?

[DJohn]

I wanted to make sure my assumption is correct: Each of the (working) fuses must have a current rating higher than the current used by the heater. Is that a valid assumption?

The problem says nothing about current ratings, so you can assume that they play no part in it. Fuses are either working or blown. If you have two working fuses, the heater will come on. That's all you need to know.

[h_anand]

Question regarding "We denote by T(N,m) the smallest number of tries required to ensure the heating system turns on.".

Is T(N, N) identically equal to one because there is an action of putting two fuses together, or is it zero because - since the outcome is guaranteed, there is no question of trying to ensure?

For what it is worth, I have not been able to validate the base-case of L(1000) with either interpretation.

thank you,

[wrongrook]

T(N,N) = 1 as otherwise the heating system will not be on. The example T(3,2)=3 shows this as well. After two failing tries you will have enough information to conclude that your third try is guaranteed successful, but you still need to try it to ensure the heating system is on.

[h_anand]

Thank you for the clarification, @wrongrook.

[bac0n]

Can someone help me understand why T(8,4) = 7. I need 8 tries to deduce which is the working pair?

[neverforget]

IMO T(8,4)=7 is a crucial hint, but it's small enough to discover with exhaustive search.
There are 28c7=1184040 possible sets to check against each of 8c4=70 possible scenarios.