Puzzle: trouver le nombre minimum de poids

Question

Je suis tombé sur cette question: dire donné deux poids 1 et 3, vous pouvez peser 1,2 (par 3-1), 3,4 (par 3 + 1) (en utilisant les deux côtés de l'équilibre). Maintenant, trouver le nombre minimum de poids afin que vous puissiez mesurer 1 à 1000.

La réponse a été 1,3,9,27 ...

Je veux savoir comment vous arrivez à une telle solution signifie pouvoirs de 3. Quel est le processus de pensée?

Source: http://classic-puzzles.blogspot.com/search/label/Google%20Interview%20Puzzles

Solution: http://classic-puzzles.blogspot.com/2006/12/solution-to-shopkeeper-problem.html

Answer 1

Théorème: Vous aurez besoin des poids 3^0 à 3^N pour couvrir les valeurs 1 à S (N) = somme (3^i) pour i = 0 à N.

preuve:

1. Vous avez donné le cas de base où N = 1.
2. supposons maintenant cela est pour N < M. Pour le cas N = M nous aurons des poids 3^0 = 1 à 3^M dont nous connaissons déjà les valeurs jusqu'à S (M-1). Considérons qu'en échangeant des côtés pour chaque poids sur l'échelle, nous pouvons exprimer toutes les valeurs négatives jusqu'à -S (M-1) avec ces mêmes poids. Cela suffira pour prouver que l'on peut exprimer les valeurs S (M-1) + 1 à S (M) comme 3^M + X où -S (M-1) < = X < = S (M-1) . Mais S (M) = S (M-1) + 3^M donc c'est clair à condition que S (M-1) + 1> = 3^M - S (M-1). Autrement dit, si 3^M < = 1 + 2 * S (M-1) = 1 + somme (2 * 3^i) pour i = 0 à M-1. Cela me semble clair pour l'instant, mais j'ai eu quelques cocktails et une preuve n'était pas vraiment ce que vous demandiez de toute façon, alors je vais laisser cette dernière étape comme un exercice au lecteur.
3. Par induction, QED.

Answer 2

Supposons que vous ayez un ensemble de poids à l'aide duquel vous pouvez peser n'importe quel nombre jusqu'à n. Maintenant, vous voulez élargir votre ensemble de poids pour peser plus de chiffres, ce qui signifie que vous voulez peser n + 1, n + 2 et ainsi de suite. Ajouter des poids n + 1, n + 2, ...., 2n serait redondant. Le prochain poids de la série devrait être le ((somme de tous les poids précédents) * 2) + 1)

Je pense que vous commencez juste au cas de base 1, et progressez. Pour atteindre le numéro 2, vous avez le choix entre {2, 3, 4 ...}. 4 - 1 ne peut pas atteindre, 2 est redondant. Après un nombre de plus, le motif émerge.

Answer 3

Voici comment j'ai résolu le problème. Supposons que vous ayez des poids a_1, a_2, ..., a_r.

Maintenant, vous pouvez le poids d'un x poids est que vous avez

a_i1 + a_i2 + ... + x + = a_ik a_j1 + a_j2 + ... + a_jl

ie x = Somme E_I * a_i

où E_I est soit -1, 0 ou 1.

-à-dire que nous devons écrire chaque numéro comme une combinaison linéaire des coefficients a_i avec -1 ou 1,0. Maintenant nous savons que nous pouvons écrire n'importe quel nombre dans la base 3 comme une combinaison de puissances de 3 avec les coefficients (chiffres) 0,1,2.Un fait similaire est que nous pouvons également utiliser les chiffres 1, 0 et -1 lorsque nous écrivons un nombre dans la base 3!

Le fait que nous avons besoin d'obtenir tous les numéros possibles conduit au fait que vous pourriez peut-être en mesure d'utiliser les pouvoirs de 3.

Le puzzle est construit que cela fonctionne réellement bien et vous pouvez le prouver facilement.

La même idée peut être appliquée au problème similaire où vous avez une balance à ressort (c'est-à-dire une seule casserole). Ici, les coefficients sont 0 et 1, et les puissances de 2 viennent immédiatement à l'esprit.

Et un autre problème:

Supposons que je dit que vous aviez deux copies de chaque poids et un équilibre commun et a dû peser tous les poids de 1 à 61. Quel poids choisiriez-vous?

Answer 4

Tenir compte du problème à un niveau de base:

Si vous voulez trouver les poids minimum pour 20 kg,

Dans un premier temps: 20 = 1 + 1 + 1 + 1 + 1 + 1 .... (20 fois). En utilisant binaire, vous pouvez le réduire à moitié en utilisant seulement les poids impairs.

=> 1, 2, 4, 6, 8, 10...20 (for all odd weights even no.s can be "added" by 1) 
     ... 2+1, 4+1, 6+1...18+1. 

Maintenant, si « soustraction » est également considéré, à savoir les deux casseroles sont utilisés, nous pouvons prendre des multiples de 3.

1  3  6  9  12  15  18  21  24  27 

    2  4 5  7 8 10 11 13 14  16 17  19 20  22 23  25 26 

     _________________ _________________ __________________ ___________________

Nous voyons tous les poids peuvent être produits en ajoutant ainsi et en soustrayant 1 au multiple de 3 de

IMP: 1 est l'unité de base ci-dessus

Ensuite, nous pouvons faire 3 l'unité de base de l'addition et la soustraction, car il peut déduire tous les autres Nombres. Par conséquent, considérons les ensembles, 3-6-9, 9-12-15, 16-17-18 etc peuvent être prises et les termes intermédiaires peuvent être éliminés comme.

Nous avons donc,

1  3    9     15     21     27 

    2  4 5 6 7 8 10 11 12 13 14  16 17 18 19 20  22 23 24 25 26 

          _________________ __________________ __________________

maintenant 9 est notre unité de base, nous pouvons accéder à un nombre de 1 à 9, directement. Si l'on ajoute ou retranche, nous obtenons un écart de 18. Ainsi, nous avons les moyens termes éliminés:

1  3    9               27 

    2  4 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 

          _________________________________________________________

Maintenant, tous les numéros de 1 à 27 peut être déduit. Ainsi, 27 devient notre unité de base et le prochain écart qui peut être accessible impliquera l'addition et la soustraction de 27, donnant 54.

Ainsi nous pouvons conclure que les puissances de 3 sont répétées comme la différence entre les puissances de 3 est toujours 3 (n).

D'où la preuve.