# Tag Info

## New answers tagged combinatorics

2

Partial: It's at least using I just wrote a program to enumerate them; it's still running. I would hope to find an analytical solution but I figured it would be best to generate some examples first. Obviously any rotations or reflections of this also work. Note that if you are enumerating them, you can reduce the work by quite a lot if you assume the ...

1

EDIT : I found a better solution for Omitting the older solution as that is no more valid

2

7

The 2 buttons can do the following With these settings we can reach any target in at most Proof that this is minimal

1

Computerless proof that CDJB's solution is best possible (which also finds all possible solutions in that many steps, though I haven't filled in the details of that part since you can see the explicit solutions in CDJB's answer):

3

I found the fewest number of button presses as We get I don't see a possibility to do it in fewer, but I'll try to prove it. EDIT: Following the comment below, I continued searching and found another five solutions for n = 11. These are:

-1

Seven A little different than msh210 attempted

1

I think that where you're getting confused is in the framing of the question. The question is asking for the fewest number of candies we need to take in order to guarantee that 7 candies share a colour. The scenario you gave results in 7 candies sharing a colour after picking 13 candies out. However, if I can find a scenario where after picking 13 or more ...

-1

By my understanding of the given rules, the smallest number is The calculator starts with 0, so

7

The smallest number is: Proof:

3

With a single button press we can get 2. In two steps we can reach 4 and 6. From there we can reach three new numbers: 8, 12 and 18 require a minimum of three steps. Seven additional numbers within reach of four button presses; 10, 14, 16, 20, 24, 36 and 54. Continuing this enumeration through nine steps, we find that the smallest positive even number ...

14

Seven keystrokes. The sequence of numbers is Proof that this is the only solution in seven or fewer steps:

3

At the risk of flogging a dead horse, I wanted to solve it using Dijkstra's algorithm, since an answer implied that it required a computer to do so. First, we change it to a minimize problem. We know that all solutions use 19 steps, so we simply change the values to $10-x$ and then minimize the result: Initialize the top left to a value of 1. Everywhere ...

6

@Mohit Jain's solution is nice and provably correct. It also shows you the best way to reach any square from the top left corner. I happened to solve the puzzle in a way that's pretty much identical, but in reverse. Both methods are equally valid, but somehow I felt that finding the optimum path from any square to the bottom right might be a more ...

15

It is a 10x10 map and you need to go east 9 times and south 9 times. There are total ${18\choose9}$ = 48620 paths which are impractical to be done with pen and paper in a reasonable amount of time. But if you observe This can be done pretty quickly with just 10x10=100 calculations. The answer is Proof of work Method

1

Local maximum solution:

5

This results in Note that A proof of optimality:

-1

If we take this pattern as a part of a bigger and complete pattern with a well defined rule, then this makes sense: It is a complete palindrome-like pattern with "mirrored" operations (add-change-add- change-change-remove-change-remove). It eliminates the obscurity how to add white spheres after item 5. It involves operations that have already been used, so ...

0

The pattern appears to build up, adding dots and colors, leaving the sequence "full" at the fifth square, with no room to add anything after that, so you could make an arbitrary choice as to what happens next, such as:

2

It seems that the pattern goes: Therefore a suitable pattern for the last image would be:

1

I have an algorithm to achieve the task with no more than There are some interesting solutions here, most of them do not appear to be complete, however, so I have decided to add mine as well. First, divide the 30 coins into 5 groups of 6 coins each. Label them A, B, C, D, and E. The gist of the algorithm is to find out which of these groups have a fake and ...

2

First, observe the facts that: Proceeding further, the final answer is then:

1

If we allow moving a peg into a neighboring cell (without jumping) then the optimal solution requires The solution is

4

There are ${30 \choose 2} = 435$ ways of selecting 2 coins out of 30. Since the fakes can be heavy or light, that yields $435 \times 2 = 870$ possible combinations. Since each test yeilds one of 3 outcomes, and $3^6 = 729 < 870 < 2187 = 3^7$, at least 7 tests are needed. Below is proof that Update with more details

1

Here is my simple methodology; Let's call then Step 12v34 and the possible outcomes become; \begin{array}{c|c|c|c|} & \text{12} & \text{34}& \text{Result} \\ \hline \text{I} & GG & GF& NE\\ \hline \text{II} & GG & FF& NE\\ \hline \text{III} & GG & GG& E\\ \hline \text{IV} & GF & GF &E\\ \...

0

At first sight I would say it is: reasoning: EDIT Not because I think the above written is entirely bullshit, but I have an intuition, that it is very arbitrary and it is far from the optimality (both in theoretical and practical terms). I have a different idea. With this type of scale after k measurements we have 3^k outcomes. If there would be one ...

4

These steps detail a full algorithm to figuring out which two coins are fake. Worst case, this takes $10$ comparisons. Edit: The algorithm was fixed to account for the error noted in the comments. This didn't affect the worst case scenario. Step 1: Split the $30$ coins into $3$ piles of $10$, which we will call $A$, $B$, and $C$. Compare $A$ and $B$. If ...

3

Code link The algorithm is basically generating the table as seen in answers to the previous question, with each row stored as an extended bit field. The rows are the taken in groups, bitwise ANDed together to get their intersection, with a population count on the result to find the size of the intersection. If the size of the intersection is equal to or ...

8

Computer search solution. A quick and dirty Python script then identifies... Here is the script: from sympy import isprime solutions = [] def find_odd(odds, evens): if len(odds) >= 6: solutions.append((odds, evens)) for o in range(odds[-1]+2 if odds else 1, 101, 2): if not odds: print(f"\n{o: 2d} ", end="") if all(isprime(o + ...

15

It is possible to solve this without a computer search. The proof of $\min|O|$ is below.

1

List O List P List Q

3

Computer search solution Solutions. Code. Not a shining light for correct coding but it runs quickly until you hand it 32 instead of 20. Not much interesting happens with higher numbers. Algorithm is basically loop from 1 to 2^N where N is number of evens, then loop over 2^N again for odds, and for each, check which even and odd numbers are 'present' in ...

5

As it is currently worded: Therefore which can be obtained by This feels like a non-answer, but it seems valid as far as I can tell.

8

Incorrect answer Oops! The "solution" below is wrong in the following way: Unfortunately it's 3:25am local time and I don't have time to attempt a proper fix. My apologies; hopefully someone else will do a less-hilariously-broken job. My incorrect solution follows, because I don't believe in hiding my screwups :-). First of all, Obviously the same holds ...

4

An answer for the first part of the question:

1

This just answers one part: "Can you place all the tiles onto a 7x8 rectangle"

3

Here's my first attempt. Edit: I have now used a computer to find a better solution. The search was not exhaustive, but I suspect this is optimal. Edit 2: I have now done an exhaustive computer search, and if my program is correct then this is an optimal solution.

20

The answer is PROBABLY I don't have a proof yet, but experimenting with it will yield something like My strategy is Now my reasoning is that One idea to rigorously prove it is to use some result similar to and reason that EDIT: There was an error in my picture above: I put $18$ to the right of $15$. But this is very easy to correct. In the beginning ...

7

Note that So there are Now just The final answer:

5

The question seems to ask that you need to ensure that in the N candies, you always find some 7 candies have same shared colors, and find the minimum N. The answer should be $16$ due to you can take 3 candies in each type(total 5 types) by considering the worst case. This cause you have all colors with 6 candies shared for each. And plus any candy you ...

0

This seems like a relationship problem to me. I think we can try to use Assumptions: There are no conflicting relationships Represent all the bulbs with 2 states. a11 means a1 bulb which is ON. Similarly a10 means a1 bulb which is OFF Converse also hold true. For the given example, if 𝑎1 is OFF , then 𝑎2 and 𝑎3 are ON, 𝑎7 is OFF Input example for ...

1

Another approach (probably somewhat different of @jarnbjo's one):

3

Since we are looking for a generic approach without knowing the exact 'rules', I would suggest the following:

1

Proof with brute-force procedure. Here I used fact that we for sure can cover with 16 pentominoes, so I tried to cover half with 8 or less and then see if two such half-covers cover the whole board. It takes about 15 seconds on my PC to get the answer. #include <iostream> #include <vector> const int kHalfUpperBound = 8; const int kSide = 8; ...

5

The only solutions are After finding these, I have brute forced this with the following ugly Mathematica script to prove no other solutions exist:

5

I have found one answer

12

6

I have found that solution (thanks Python !) : Here is my code if you're curious !

9

I used a computer, and found the following solution: You can move $16$ or $17$ to the first group, but not both. Those are the only three solutions according to my program, other than permuting the groups. Note that $24$ cannot be added to any group.

9